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

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

タクシー会社が、4 台のタクシー $T_{1}, T_{2}, T_{3}, T_{4}$ を 4 人の客 $C_{1}, C_{2}, C_{3}, C_{4}$ のもとへ配車する。各タクシーはちょうど 1 人の客を担当し、各客にはちょうど 1 台のタクシーが向かう。タクシー $T_{i}$ が客 $C_{j}$ のもとに着くまでの時間（分）は次の表のとおりである。

$T_{1} T_{2} T_{3} T_{4} C_{1} 9685 C_{2} 4376 C_{3} 7548 C_{4} 8967$

4 台の到着時間の合計を最小にするとき、その最小値（分）を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

割当問題なので、ハンガリー法（各行・各列の最小値を引き、0 を最少の線で覆う操作）を使う。

ヒント 2

行の最小値、列の最小値を順に引いたあと、0 を覆う線の最少本数が 4 本未満なら、覆われていない数の最小値を引き、線の交点に足して表を調整する。

ヒント 3

行・列の削減後、0 は列 $C_{2}$ 、行 $T_{3}$ 、行 $T_{4}$ の 3 本で覆え、覆われていない数の最小値は $2$ になる。調整後の表で $T_{4} \to C_{1}$ が決まる。

答えと解説

答えを見る

20

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

解説を読む

ハンガリー法で解く。

手順 1（行の最小値を引く） 各行の最小値は $T_{1} : 4, T_{2} : 3, T_{3} : 4, T_{4} : 5$ である。各行からそれぞれ引くと
$T_{1} T_{2} T_{3} T_{4} C_{1} 5340 C_{2} 0031 C_{3} 3203 C_{4} 4622$

手順 2（列の最小値を引く） 各列の最小値は $0, 0, 0, 2$ なので、 $C_{4}$ の列から $2$ を引くと
$T_{1} T_{2} T_{3} T_{4} C_{1} 5340 C_{2} 0031 C_{3} 3203 C_{4} 2400$

手順 3（0 を最少の線で覆う） 0 は $(T_{1}, C_{2}), (T_{2}, C_{2}), (T_{3}, C_{3}), (T_{3}, C_{4}), (T_{4}, C_{1}), (T_{4}, C_{4})$ にある。列 $C_{2}$ 、行 $T_{3}$ 、行 $T_{4}$ の 3 本ですべて覆える（ $T_{1}, T_{2}$ の 0 はどちらも $C_{2}$ 列にあるので、0 だけで 4 組を割り当てることはできず、最少本数は 3 本）。 $3 < 4$ なので、まだ最適な割当は読み取れない。

手順 4（表の調整） 線で覆われていない数（ $T_{1}, T_{2}$ 行の $C_{1}, C_{3}, C_{4}$ 列）は $5, 3, 2, 3, 2, 4$ で、最小値は $2$ 。覆われていない数から $2$ を引き、2 本の線が交わる位置 $(T_{3}, C_{2}), (T_{4}, C_{2})$ に $2$ を足すと
$T_{1} T_{2} T_{3} T_{4} C_{1} 3140 C_{2} 0053 C_{3} 1003 C_{4} 0200$

手順 5（0 の位置で割当） $C_{1}$ 列の 0 は $T_{4}$ だけなので $T_{4} \to C_{1}$ 。残りは例えば $T_{1} \to C_{2}, T_{2} \to C_{3}, T_{3} \to C_{4}$ とすれば、異なる行・異なる列の 0 が 4 つ選べる（4 本の線が必要になった）。

手順 6（元の表で合計） 元の表で
$4 + 5 + 6 + 5 = 20.$
（ $T_{1} \to C_{4}, T_{2} \to C_{2}, T_{3} \to C_{3}, T_{4} \to C_{1}$ でも $8 + 3 + 4 + 5 = 20$ となり、最小値は同じ。）

よって最小値は $20$ 分である。

別解

これは割当問題なので、4! = 24 通りの割当をすべて調べる。 $T_{1}$ がどの客に向かうかで場合分けし、残り 3 台の最小合計を求める。

$T_{1} \to C_{1}$ （9）：残りの最小は $T_{2} \to C_{2}$ （3）、 $T_{3} \to C_{3}$ （4）、 $T_{4} \to C_{4}$ （7）の 14。合計 23。
$T_{1} \to C_{2}$ （4）：残りの最小は $T_{2} \to C_{3}$ （5）、 $T_{3} \to C_{4}$ （6）、 $T_{4} \to C_{1}$ （5）の 16。合計 20。
$T_{1} \to C_{3}$ （7）：残りの最小は $T_{2} \to C_{2}$ （3）、 $T_{3} \to C_{4}$ （6）、 $T_{4} \to C_{1}$ （5）の 14。合計 21。
$T_{1} \to C_{4}$ （8）：残りの最小は $T_{2} \to C_{2}$ （3）、 $T_{3} \to C_{3}$ （4）、 $T_{4} \to C_{1}$ （5）の 12。合計 20。

各場合の残り 3 台の割当は 6 通りずつすべて計算して最小を確認した。よって全体の最小値は 20 分である。

検算： $T_{1} \to C_{2}$ 、 $T_{2} \to C_{3}$ 、 $T_{3} \to C_{4}$ 、 $T_{4} \to C_{1}$ では $4 + 5 + 6 + 5 = 20$ 。 $T_{1} \to C_{4}$ 、 $T_{2} \to C_{2}$ 、 $T_{3} \to C_{3}$ 、 $T_{4} \to C_{1}$ では $8 + 3 + 4 + 5 = 20$ 。どちらも 20 になる。

この問題の確認

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

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

確認の方法について

間違いを報告する

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