オペレーションズ・リサーチの問題

難易度 1教科書の例題レベル大学数学オペレーションズ・リサーチ

ある工場に 4 台の機械 $M_{1}, M_{2}, M_{3}, M_{4}$ があり、4 種類の製品 $P_{1}, P_{2}, P_{3}, P_{4}$ を 1 種類ずつ加工させる。各機械はちょうど 1 種類の製品を担当し、各製品はちょうど 1 台の機械が担当する。機械 $M_{i}$ が製品 $P_{j}$ を加工するのにかかる時間（単位：時間）は、次の表の第 $i$ 行・第 $j$ 列の値である。

$M_{1} M_{2} M_{3} M_{4} P_{1} 55410 P_{2} 7476 P_{3} 8388 P_{4} 6666$

4 台の加工時間の合計が最小になるように割り当てるとき、その合計時間の最小値を求めよ。

この問題で使うもの

割当問題（ハンガリー法）（説明と入口の問題）

この問題を解けるようになるまで（10 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

ハンガリー法を使う。まず各行・各列からその最小値を引いて、0 をつくる。

ヒント 2

0 をすべて覆う線の最少本数が 4 本未満なら、覆われていない数の最小値を覆われていない数から引き、線の交点に足す。

ヒント 3

行の最小値を引くと、 $M_{1}$ 行と $M_{3}$ 行の 0 はどちらも $P_{1}$ 列だけにあり、0 は $P_{1}$ 列・ $M_{2}$ 行・ $M_{4}$ 行の 3 本の線で覆える。覆われていない数の最小値は $1$ である。

答えと解説

答えを見る

19

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

ハンガリー法を使う。

手順 1（行の最小値を引く） 各行の最小値は $M_{1} : 5, M_{2} : 3, M_{3} : 4, M_{4} : 6$ である。各行からその最小値を引くと
$M_{1} M_{2} M_{3} M_{4} P_{1} 0204 P_{2} 2130 P_{3} 3042 P_{4} 1320$
ここまでで引いた量の合計は $5 + 3 + 4 + 6 = 18$ である。

手順 2（列の最小値を引く） どの列にもすでに $0$ があるので、列の最小値はすべて $0$ で、表は変わらない。

手順 3（0 を最少の線で覆う） $0$ の位置は $(M_{1}, P_{1}), (M_{2}, P_{3}), (M_{3}, P_{1}), (M_{4}, P_{2}), (M_{4}, P_{4})$ 。 $M_{1}$ と $M_{3}$ の $0$ はどちらも $P_{1}$ 列にしかないので、 $0$ だけで 4 組の割当は作れない。実際、 $P_{1}$ 列・ $M_{2}$ 行・ $M_{4}$ 行の 3 本の線ですべての $0$ を覆える。線の本数 $3$ が $4$ より少ないので、表を変形する。

手順 4（表の変形） 線で覆われていない数は $M_{1}$ 行と $M_{3}$ 行の $P_{2}, P_{3}, P_{4}$ 列の $2, 3, 1, 3, 4, 2$ で、その最小値は $1$ 。覆われていない数から $1$ を引き、2 本の線が交わる位置 $(M_{2}, P_{1}), (M_{4}, P_{1})$ に $1$ を足すと
$M_{1} M_{2} M_{3} M_{4} P_{1} 0305 P_{2} 1120 P_{3} 2032 P_{4} 0310$

手順 5（割当を読み取る） $M_{3}$ 行の $0$ は $P_{1}$ だけなので $M_{3} \to P_{1}$ 。 $M_{2}$ 行の $0$ は $P_{3}$ だけなので $M_{2} \to P_{3}$ 。 $M_{1}$ は $P_{1}$ が使われたので $M_{1} \to P_{4}$ 。残る $M_{4} \to P_{2}$ 。これで $0$ の位置だけを使う割当が完成した（0 を覆うには 4 本の線が必要になっている）。

手順 6（もとの表で合計を計算）
$M_{1} \to P_{4} : 6, M_{2} \to P_{3} : 3, M_{3} \to P_{1} : 4, M_{4} \to P_{2} : 6$
より合計は $6 + 3 + 4 + 6 = 19$ 。

（確認：行の最小値の和 $18$ を実現するには $M_{1}$ と $M_{3}$ がともに $P_{1}$ を担当する必要があり不可能なので、合計は $19$ 以上。よって $19$ が最小。）

答えは $19$ 時間。

別解

これは割り当て問題なので、 $4! = 24$ 通りの割り当てを、 $M_{2}$ が担当する製品で場合分けして調べる。

(1) $M_{2} \to P_{3}$ （3 時間）のとき、残り $M_{1}, M_{3}, M_{4}$ を $P_{1}, P_{2}, P_{4}$ に割り当てる。
- $M_{1} P_{1} + M_{3} P_{2} + M_{4} P_{4} = 5 + 7 + 6 = 18$
- $M_{1} P_{1} + M_{3} P_{4} + M_{4} P_{2} = 5 + 6 + 6 = 17$
- $M_{1} P_{2} + M_{3} P_{1} + M_{4} P_{4} = 7 + 4 + 6 = 17$
- $M_{1} P_{2} + M_{3} P_{4} + M_{4} P_{1} = 7 + 6 + 10 = 23$
- $M_{1} P_{4} + M_{3} P_{1} + M_{4} P_{2} = 6 + 4 + 6 = 16$
- $M_{1} P_{4} + M_{3} P_{2} + M_{4} P_{1} = 6 + 7 + 10 = 23$

最小は 16 なので、合計は $3 + 16 = 19$ 。

(2) $M_{2} \to P_{2}$ （4 時間）のとき、残り $M_{1}, M_{3}, M_{4}$ を $P_{1}, P_{3}, P_{4}$ に割り当てる。最小は 18 なので、合計は $4 + 18 = 22$ 。

(3) $M_{2} \to P_{1}$ （5 時間）のとき、残りの最小は 20 なので、合計は 25。

(4) $M_{2} \to P_{4}$ （6 時間）のとき、残りの最小は 18 なので、合計は 24。

以上より最小値は 19。最適な割り当ては $M_{1} \to P_{4}, M_{2} \to P_{3}, M_{3} \to P_{1}, M_{4} \to P_{2}$ で、 $6 + 3 + 4 + 6 = 19$ となる。

検算として、各行の最小値の和は $5 + 3 + 4 + 6 = 18$ で、これは下界である。この下界 18 を達成するには $M_{1} \to P_{1}$ かつ $M_{3} \to P_{1}$ が必要となり、同じ製品を 2 台が担当してしまうので不可能である。したがって 19 は妥当である。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる

	$J_{1}$	$J_{2}$	$J_{3}$	$J_{4}$
$W_{1}$	$8$	$4$	$7$	$6$
$W_{2}$	$5$	$9$	$6$	$3$
$W_{3}$	$7$	$6$	$10$	$8$
$W_{4}$	$6$	$7$	$5$	$9$