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

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

4 人の作業員 $W_{1}, W_{2}, W_{3}, W_{4}$ に 4 つの仕事 $J_{1}, J_{2}, J_{3}, J_{4}$ を 1 つずつ割り当てる。各作業員はちょうど 1 つの仕事を担当し、各仕事はちょうど 1 人が担当する。作業員 $W_{i}$ が仕事 $J_{j}$ を行うのにかかる時間（単位：時間） $c_{ij}$ は次の表のとおりである。

	$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$

4 人の作業時間の合計が最小になるように割り当てるとき、作業時間の合計の最小値を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

割当問題はハンガリー法で解ける。各行・各列から同じ数を引いても最適な割当は変わらないことを利用する。

ヒント 2

各行からその行の最小値を引き、続いて各列からその列の最小値を引く。そのあと、 $0$ の成分だけを使って各行・各列から 1 つずつ選べるかを調べる。

ヒント 3

行の最小値は $4, 3, 6, 5$ 、その後の列の最小値は $1, 0, 0, 0$ である。縮約後の $0$ は第 1 行が $J_{2}$ 、第 2 行が $J_{4}$ だけにあることに注目する。

答えと解説

答えを見る

19

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

解説を読む

ハンガリー法で解く。費用行列のある行（または列）の全成分から同じ数を引いても、どの割当も合計がその数だけ減るだけなので、最適な割当は変わらない。

行の縮約　各行の最小値 $4, 3, 6, 5$ をそれぞれの行から引く。
$4211060233402024$

列の縮約　各列の最小値は $1, 0, 0, 0$ なので、第 1 列から $1$ を引く。
$3100060233402024$
ここまでに引いた数の合計は $4 + 3 + 6 + 5 + 1 = 19$ である。

0 による割当　縮約後の行列の成分はすべて $0$ 以上である。 $0$ の位置は
- 第 1 行： $J_{2}$
- 第 2 行： $J_{4}$
- 第 3 行： $J_{1}, J_{2}$
- 第 4 行： $J_{1}, J_{3}$

である。 $W_{1} \to J_{2}$ , $W_{2} \to J_{4}$ と決めると、 $W_{3}$ は $J_{2}$ が使えないので $J_{1}$ 、 $W_{4}$ は $J_{3}$ となり、すべて $0$ の位置で互いに異なる列を選ぶ割当
$W_{1} \to J_{2}, W_{2} \to J_{4}, W_{3} \to J_{1}, W_{4} \to J_{3}$
が得られる。縮約後の行列で合計 $0$ （最小）なので、この割当は元の問題でも最適である。

元の表で合計を確かめると
$c_{12} + c_{24} + c_{31} + c_{43} = 4 + 3 + 7 + 5 = 19$
であり、引いた数の合計 $19$ と一致する。

よって作業時間の合計の最小値は $19$ 時間である。

別解

ハンガリー法で解く。各行から行の最小値（4, 3, 6, 5、合計 18）を引くと
$W_{1} : (4, 0, 3, 2)$ , $W_{2} : (2, 6, 3, 0)$ , $W_{3} : (1, 0, 4, 2)$ , $W_{4} : (1, 2, 0, 4)$ 。
各列の最小値は $(1, 0, 0, 0)$ なので第 1 列から 1 を引くと
$W_{1} : (3, 0, 3, 2)$ , $W_{2} : (1, 6, 3, 0)$ , $W_{3} : (0, 0, 4, 2)$ , $W_{4} : (0, 2, 0, 4)$ 。
0 の位置は $W_{1} : J_{2}$ , $W_{2} : J_{4}$ , $W_{3} : J_{1}, J_{2}$ , $W_{4} : J_{1}, J_{3}$ で、 $W_{1} \to J_{2}$ , $W_{2} \to J_{4}$ , $W_{3} \to J_{1}$ , $W_{4} \to J_{3}$ という 0 だけの完全割り当てが存在する。したがって最適で、最小値は引いた量の合計 $18 + 1 = 19$ 。

検算: $c_{12} + c_{24} + c_{31} + c_{43} = 4 + 3 + 7 + 5 = 19$ 。下界も $18 + 1 = 19$ なので一致し、これより小さい割り当てはない。

この問題の確認

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

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

確認の方法について

間違いを報告する

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