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

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

ある配送センターで、4 台の配送車 $T_{1}, T_{2}, T_{3}, T_{4}$ を 4 つの配送地区 $A_{1}, A_{2}, A_{3}, A_{4}$ に 1 台ずつ割り当てる。各配送車はちょうど 1 つの地区を担当し、各地区はちょうど 1 台が担当する。配送車 $T_{i}$ が地区 $A_{j}$ を担当したときにかかる時間（分）は、次の表の $i$ 行 $j$ 列の値である。

$T_{1} T_{2} T_{3} T_{4} A_{1} 5378 A_{2} 8746 A_{3} 7367 A_{4} 781011$

4 台の所要時間の合計の最小値（分）を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

割当問題なので、ハンガリー法（行の最小値を引く → 列の最小値を引く → 0 を最少の線で覆う → 必要なら調整）を使う。

ヒント 2

行の最小値 $5, 3, 4, 6$ を引いたあと、列 $A_{4}$ から $2$ を引く。0 を覆う線が 4 本未満なら、覆われていない成分の最小値を覆われていない成分から引き、線の交点に足す。

ヒント 3

縮約後の表では、行 $T_{1}$ ・行 $T_{2}$ ・列 $A_{2}$ の 3 本ですべての 0 が覆え、覆われていない成分の最小値は $1$ である。調整すると $(T_{4}, A_{3})$ が新たに 0 になる。

答えと解説

答えを見る

21

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

解説を読む

ハンガリー法を使う。ある行（または列）のすべての成分から同じ数を引いても、どの割当でもその行（列）からはちょうど 1 つの成分を使うので、すべての割当の合計が同じ数だけ減るだけで、最適な割当は変わらない。

手順 1（行の最小値を引く） 各行の最小値は $T_{1} : 5, T_{2} : 3, T_{3} : 4, T_{4} : 6$ である。これらを引くと
$T_{1} T_{2} T_{3} T_{4} A_{1} 0032 A_{2} 3400 A_{3} 2021 A_{4} 2565$

手順 2（列の最小値を引く） 各列の最小値は $A_{1} : 0, A_{2} : 0, A_{3} : 0, A_{4} : 2$ である。 $A_{4}$ 列から $2$ を引くと
$T_{1} T_{2} T_{3} T_{4} A_{1} 0032 A_{2} 3400 A_{3} 2021 A_{4} 0343$
ここまでに引いた数の合計は $5 + 3 + 4 + 6 + 2 = 20$ である。

手順 3（0 を最少の線で覆う） 0 の位置は $(T_{1}, A_{1}), (T_{1}, A_{4}), (T_{2}, A_{1}), (T_{2}, A_{3}), (T_{3}, A_{2}), (T_{4}, A_{2})$ である。 $T_{3}$ と $T_{4}$ はどちらも $A_{2}$ にしか 0 がないので、0 だけで同時に選べる位置は最大 3 個であり、0 だけを使った割当はまだ作れない。実際、行 $T_{1}$ 、行 $T_{2}$ 、列 $A_{2}$ の 3 本の線ですべての 0 を覆える（3 個の 0 $(T_{1}, A_{4}), (T_{2}, A_{1}), (T_{3}, A_{2})$ は同じ線に乗らないので 3 本より少なくはできない）。線の本数 $3 < 4$ なので調整する。

手順 4（調整） 線で覆われていない成分は、行 $T_{3}, T_{4}$ の列 $A_{1}, A_{3}, A_{4}$ にある $3, 2, 4, 2, 1, 3$ で、その最小値は $1$ である。覆われていない成分から $1$ を引き、2 本の線が交わる成分 $(T_{1}, A_{2}), (T_{2}, A_{2})$ に $1$ を足すと
$T_{1} T_{2} T_{3} T_{4} A_{1} 0021 A_{2} 4500 A_{3} 2010 A_{4} 0332$

手順 5（割当を読む） 新しく $(T_{4}, A_{3})$ が 0 になった。 $T_{3}$ は $A_{2}$ にしか 0 がないので $T_{3} \to A_{2}$ 。すると $T_{4} \to A_{3}$ 、 $T_{2}$ は残りの 0 の $A_{1}$ で $T_{2} \to A_{1}$ 、最後に $T_{1} \to A_{4}$ となり、各行・各列から 0 を 1 つずつ選べた。すべての成分は 0 以上なので、この割当が最適である。

元の表で合計を計算すると
$7 + 3 + 4 + 7 = 21$
（ $T_{1} \to A_{4} : 7, T_{2} \to A_{1} : 3, T_{3} \to A_{2} : 4, T_{4} \to A_{3} : 7$ ）。

よって、所要時間の合計の最小値は $21$ 分である。

別解

4×4 の割当問題なので、全 24 通りを T1 の担当地区ごとに場合分けして調べる。

T1→A1(5): T2→A2 のとき 29、T2→A3 のとき 23、T2→A4 のとき 24。
T1→A2(8): T2→A1 のとき 28、T2→A3 のとき 29、T2→A4 のとき 30。
T1→A3(7): T2→A1 のとき 25、T2→A2 のとき 32、T2→A4 のとき 27。
T1→A4(7): T2→A1 のとき 21、T2→A2 のとき 28、T2→A3 のとき 22。

(各場合の T3, T4 は、残り 2 地区への 2 通りのうち小さい方を採用した。)

最小は T1→A4 (7)、T2→A1 (3)、T3→A2 (4)、T4→A3 (7) で、合計 7+3+4+7=21。

検算（ハンガリー法の下界）: 行ごとに最小値 5,3,4,6（計 18）を引くと、
T1: 0 3 2 2
T2: 0 4 0 5
T3: 3 0 2 6
T4: 2 0 1 5
となる。列の最小値は 0,0,0,2 で、A4 列から 2 を引くと
T1: 0 3 2 0
T2: 0 4 0 3
T3: 3 0 2 4
T4: 2 0 1 3
0 の位置だけで完全割当 T1→A4, T2→A1, T3→A2, T4→A3 は作れない。T4→A3 は 1 で 0 ではないため、実際には補正が必要である。そこで下界は 18+2=20 以上となる。さらに 0 だけでは完全割当ができないので、最小値は 21 以上であることが分かる。全列挙の結果 21 が達成されるので、最小値は 21。

この問題の確認

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

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

確認の方法について

間違いを報告する

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