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

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

5 人の作業者 $W_{1}, W_{2}, W_{3}, W_{4}, W_{5}$ を 5 つの仕事 $J_{1}, J_{2}, J_{3}, J_{4}, J_{5}$ に 1 人 1 つずつ割り当てる（各仕事にはちょうど 1 人を割り当てる）。作業者 $W_{i}$ が仕事 $J_{j}$ を行うときの費用 $c_{ij}$ は次の表のとおりである。ただし $t$ は実数の定数である。

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

費用の総和を最小にする割当て（最適割当て）のうちに、 $W_{1}$ を $J_{1}$ に割り当てるものが存在するような $t$ の最大値を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$W_{1}$ を $J_{1}$ に割り当てる割当てと，割り当てない割当てに分け，それぞれの最小費用を比べましょう。

ヒント 2

$W_{1} \to J_{1}$ の場合の費用は $t + (残り 4 \times 4 の最小費用)$ です。割り当てない場合は $c_{11} = \infty$ として最小費用を求めます。どちらもハンガリー法で計算できます。

ヒント 3

残りの $4 \times 4$ 割当問題の最小費用は $22$ です（ $W_{2} \to J_{3}, W_{3} \to J_{2}, W_{4} \to J_{5}, W_{5} \to J_{4}$ ）。あとは $c_{11}$ を禁止したときの最小費用を求め， $t + 22$ と比べます。

答えと解説

答えを見る

4

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

解説を読む

割当ては $5!$ 通りの置換であり， $W_{1}$ を $J_{1}$ に割り当てるものとそうでないものに分けて考える。

(1) $W_{1} \to J_{1}$ とする場合

費用は $t + C_{1}$ である。ここで $C_{1}$ は， $W_{2}, \dots, W_{5}$ を $J_{2}, \dots, J_{5}$ に割り当てる $4 \times 4$ 割当問題の最小費用で，費用行列は
$1058948769611771065$
である。ハンガリー法を用いる。各行から行の最小値 $4, 5, 6, 5$ を引くと
$6024031151523500$
となる。第 3 列（ $J_{4}$ の列）の最小値 $1$ を引くと（引いた量の合計 $4 + 5 + 6 + 5 + 1 = 21$ ）
$6024031140413500$
となる。 $W_{4}, W_{5}$ の 0 はともに $J_{5}$ の列にしかないので，0 だけで完全な割当ては作れない。0 は $W_{3}$ の行， $J_{3}$ の列， $J_{5}$ の列の 3 本の線で覆える。覆われていない成分の最小値は $1$ である。覆われていない成分から $1$ を引き，2 本の線の交点に $1$ を足すと（引いた量の合計は $22$ ）
$5013041130303600$
となる。0 の位置で $W_{2} \to J_{3}, W_{3} \to J_{2}, W_{4} \to J_{5}, W_{5} \to J_{4}$ と割り当てられる。費用は $4 + 5 + 6 + 7 = 22$ である。ハンガリー法で行列から引いた量の合計 $22$ は最小費用の下界なので， $C_{1} = 22$ である。

(2) $W_{1} \to J_{1}$ としない場合

$c_{11} = \infty$ （禁止）とした $5 \times 5$ 割当問題の最小費用を $C_{2}$ とする。各行から行の最小値 $7, 4, 5, 4, 5$ を引くと
$\infty 2403 06044203311517243520$
となる。 $J_{4}$ の列の最小値 $1$ を引くと（引いた量の合計 $25 + 1 = 26$ ）
$\infty 2403 06044203310406143520$
となる。0 の位置で $W_{1} \to J_{2}, W_{2} \to J_{3}, W_{3} \to J_{4}, W_{4} \to J_{1}, W_{5} \to J_{5}$ と割り当てられる。費用は $7 + 4 + 6 + 4 + 5 = 26$ で，下界 $26$ に一致する。したがって $C_{2} = 26$ である。

(3) 結論

全体の最小費用は $min (t + 22, 26)$ である。 $W_{1} \to J_{1}$ を含む最適割当てが存在する条件は
$t + 22 \leq 26 ⟺ t \leq 4$
である。 $t = 4$ のときは両方の割当てが最適になるので，条件を満たす。よって求める最大値は $4$ である。

別解

$W_{1}$ を $J_{1}$ に割り当てる最良の費用は $t + M_{s u b}$ である。ここで $M_{s u b}$ は残りの $W_{2} \sim W_{5}$ を $J_{2} \sim J_{5}$ に割り当てる 4×4 問題の最小費用。

(1) $M_{s u b}$ を求める。 $W_{2}$ の割当て先で場合分けして 24 通りを調べると次のようになる。
- $W_{2} \to J_{3}$ のとき最小 22(例: $W_{2} J_{3} = 4, W_{3} J_{2} = 5, W_{4} J_{5} = 6, W_{5} J_{4} = 7$ )
- $W_{2} \to J_{5}$ のとき最小 26
- $W_{2} \to J_{4}$ のとき最小 26
- $W_{2} \to J_{2}$ のとき最小 28

よって $M_{s u b} = 22$ 。

(2) $W_{1}$ を $J_{1}$ に割り当てない割当ての最小費用 $M_{w i t h o u t}$ ( $t$ に依存しない)を求める。
- $W_{1} \to J_{2}$ ( $c = 7$ ): 残りは $W_{2} J_{3} = 4, W_{4} J_{1} = 4, W_{3} J_{4} = 6, W_{5} J_{5} = 5$ で合計 19。各行の最小値の和も $4 + 6 + 4 + 5 = 19$ なのでこれが最小。総費用 26。
- $W_{1} \to J_{3}$ ( $c = 9$ ): 残りの最小は 23(例: $W_{4} J_{1} = 4, W_{5} J_{5} = 5, W_{3} J_{2} = 5, W_{2} J_{4} = 9$ )。総費用 32。
- $W_{1} \to J_{4}$ ( $c = 8$ ): 残りは $W_{2} J_{3} = 4, W_{3} J_{2} = 5, W_{4} J_{1} = 4, W_{5} J_{5} = 5$ で合計 18。各行の最小値の和も 18 なので最小。総費用 26。
- $W_{1} \to J_{5}$ ( $c = 11$ ): 残りの最小は 20。総費用 31。

よって $M_{w i t h o u t} = 26$ 。

(3) $W_{1} \to J_{1}$ を含む最適割当てが存在する条件は $t + 22 \leq 26$ 、すなわち $t \leq 4$ 。 $t = 4$ のとき $W_{1} \to J_{1}$ を含む割当ての費用は 26 で、 $J_{1}$ を使わない割当ての最小費用と等しい。よってこれが最適であり、 $t$ の最大値は 4。

この問題の確認

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

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

確認の方法について

間違いを報告する

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

作業	所要日数	先行作業
$1$	$3$	なし
$2$	$5$	なし
$3$	$4$	$1$
$4$	$2$	$1$
$5$	$6$	$2, 4$
$6$	$3$	$3$
$7$	$4$	$5, 6$
$8$	$2$	$3$