最適な組合せ・順序を求める計算

結論：5つの型は解き方で見分ける

「最適な組合せ・順序」の問題は、型が分かれば解き方は1つに決まります。科目Aに出るのは次の5つの型です。どれも電卓なしで解ける数値になっています。

出題回数は公開過去問での観測値で、CBT での出題確率ではありません。回数では①が圧倒的に多いので、まず①を確実に解けるようにしましょう。

flowchart TD
  Q["何を決める問題？"] --> P1["何個ずつ作るか"]
  Q --> P2["誰に何を割り当てるか"]
  Q --> P3["どの順に処理するか"]
  Q --> P4["どの買い方を組み合わせるか"]
  P1 --> L1["① 制約が2つ：交点と端点を比べる"]
  P1 --> L2["① 制約が時間だけ：1分当たり利益の高い順"]
  P2 --> L4["④ 割当：重複なしで全通り"]
  P3 --> L3["② 機械2台を順に通す：ジョンソン法"]
  P3 --> L5["③ 切替・移動の表：段取り／巡回を総当たり"]
  P4 --> L6["⑤ 必須条件を先に満たし、残りは最安単価"]

① 線形計画法（制約2つ）：答えは「角」のどこかにある

線形計画法は、限られた資源の中で利益が最大になる生産量を求める方法です。最大になるのは、作れる範囲（グラフ上の多角形）の角のどれかです。2製品・2制約なら、調べる角は「交点（両方の資源をちょうど使い切る点）」と「端点（片方の製品だけを作る点）2つ」の3つで足ります。

手順

1. 製品の個数を x、y とおき、表の各行を「必要量×個数 ≦ 上限」の式にする（これが制約条件）
2. 2つの式を「＝」にして連立方程式を解く → 交点
3. x だけ作る場合と y だけ作る場合の最大個数を出す → 端点（上限は厳しいほうの制約で決まる）
4. 3つの点それぞれで利益（目的関数）を計算し、一番大きいものを選ぶ

交点が最大になることが多いですが、いつもそうとは限りません。3つとも計算して比べるのが確実です。端点を出すときは、緩いほうの制約で個数を出してしまう間違いに気をつけてください（2019年の問題で X だけを作る場合、原料Bなら80個作れそうに見えますが、原料Aの制約で50個が上限です）。

① の別パターン：制約が時間だけなら「時給」の高い順

2016年の問題のように、全製品に共通する制約が「工場の稼働時間」の1つだけで、あとは製品ごとの需要上限しかない場合は、連立方程式を使いません。限られた資源1単位（ここでは1分）当たりの利益を計算し、その値が高い製品から需要上限まで作っていきます。

たとえば、使える時間が決まっていてアルバイトを掛け持ちするなら、1回の報酬が高い仕事ではなく時給が高い仕事から入れるのと同じ考え方です。

1個当たりの利益では Z が一番高いのに、1分当たりでは最下位です。出題者はこの逆転を狙っています。

② ジョンソン法：一番小さい時間から、前か後ろに並べる

ジョンソン法は、すべての製品が2台の機械を同じ順番（M1→M2）で通るとき、全部の加工が終わるまでの時間を最短にする並べ方です。ルールは1つだけです。表の中で一番小さい時間を探し、それが M1 の時間ならその製品を前から、M2 の時間なら後ろから並べます。並べた製品を表から消し、残りの製品で同じことを繰り返します。

このルールで最短になる理由は次のとおりです。M1 の時間が短い製品を先頭にすると、M2 が早く動き始められます。M2 の時間が短い製品を最後にすると、最後に M2 だけが動いている時間が短くなります。

答えの確認には、各機械の開始・終了時刻を書き出す方法が使えます。M2 の開始時刻は「その製品の M1 が終わった時刻」と「M2 が前の製品を終えた時刻」の遅いほうです。

③ 段取り・巡回と ④ 割当：まとめて比べる

3つとも「表の値を組み合わせて合計する」問題ですが、条件が違います。取り違えないよう比較表で押さえましょう。

巡回は、宅配ドライバーが営業所を出て全部の配達先を回り、営業所に戻るルートを考えるのと同じです。段取りの問題は24通りすべてを書くと時間がかかるので、値が小さい矢印をつないでいくと早く答えが見つかります（例題を参照）。割当は、各担当者の最大値を拾うと顧客が重複しがちなので、必ず「1人1件」になっているかを確かめます。

⑤ ライセンス購入：必須の条件を先に満たす

出題は1回だけです。「各部署にマニュアル1冊」のような必須の条件を満たせる買い方を先に決め、残りの台数を1台当たりの単価が最も安い買い方で買います。まとめ買いで少し余っても、ばらで買い足すより安くなることがある点が狙われます。

試験での問われ方

• 線形計画法：選択肢に端点の利益が必ず入っています。2019年の問題では ア 5,000円＝X だけを作る場合、イ 6,000円＝Y だけを作る場合です。2013年の問題でも イ 20万円＝A だけ、ア 16万円＝B だけ、が並んでいます。交点を計算しないと、このどちらかを選んでしまいます。
• 制約が時間だけのパターン：1個当たり利益が大きい順（Z→Y）に作ると 2,625,000円（ア）、Y を先に作ると 3,150,000円（ウ）になり、どちらも選択肢に入っています。
• ジョンソン法：M1 の時間が短い順に並べた C→B→A（エ）は19時間で、正解の18時間と1時間しか違いません。B→C→A（ウ）も19時間です。ルールどおりに並べてから、時刻を書き出して確かめましょう。
• 段取り・巡回：段取りの表を FROM と TO の向きを逆に読むと、別の値（5や6）が出ます。巡回では、最後に出発点へ戻る1区間を足し忘れる間違いが典型です。
• 割当：各担当者の最大値を足すと 5+6+8=19 となり、選択肢エに入っている。ただし A も B も顧客 z を選んでいて重複しているので、条件を満たさない。
• ライセンス：残り24台を「5ライセンス4本＋1ライセンス4本」で買うと 318,000円（エ）になります。マニュアルの条件を無視して5ライセンスを6本買うと 270,000円（ア）になります。