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

難易度 4大学院入試の標準レベル大学数学オペレーションズ・リサーチ

3 つの倉庫 $A_{1}, A_{2}, A_{3}$ から 4 つの店舗 $B_{1}, B_{2}, B_{3}, B_{4}$ へ、ある商品を輸送する。倉庫の在庫量は $A_{1}$ が $30$ 、 $A_{2}$ が $40$ 、 $A_{3}$ が $30$ であり、在庫はすべて出荷する。店舗の需要量は $B_{1}$ が $20$ 、 $B_{2}$ が $30$ 、 $B_{3}$ が $25$ 、 $B_{4}$ が $25$ であり、需要はちょうど満たす（総在庫量と総需要量はともに $100$ で等しい）。倉庫 $A_{i}$ から店舗 $B_{j}$ へ $1$ 単位輸送する費用 $c_{ij}$ は次の表のとおりである。

	$B_{1}$	$B_{2}$	$B_{3}$	$B_{4}$
$A_{1}$	$5$	$10$	$8$	$7$
$A_{2}$	$9$	$9$	$12$	$6$
$A_{3}$	$8$	$6$	$7$	$1$

ただし、経路 $A_{3} \to B_{4}$ は輸送能力に制限があり、この経路で輸送できる量は $10$ 以下である。ほかの経路には輸送量の上限はない。 $A_{i}$ から $B_{j}$ への輸送量 $x_{ij}$ は $0$ 以上の実数とし、総輸送費用 $i = 1 \sum 3 j = 1 \sum 4 c_{ij} x_{ij}$ を最小にする。総輸送費用の最小値を求めよ。

この問題で使うもの

ポテンシャル法による輸送問題の最適化（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

上限のある経路 $A_{3} \to B_{4}$ は費用が極端に安いので、まず上限いっぱいまで使うことを考え、残りを通常の輸送問題として扱ってみよう。

ヒント 2

ポテンシャル $u_{i}, v_{j}$ を、使っている経路で $c_{ij} = u_{i} + v_{j}$ となるように定め、被約費用 $c_{ij} - u_{i} - v_{j}$ の符号を調べる。上限いっぱいの経路では被約費用が負でも最適性は崩れない。

ヒント 3

$x_{34} = 10$ とし、 $x_{11} = 20$ , $x_{13} = 10$ , $x_{22} = 25$ , $x_{24} = 15$ , $x_{32} = 5$ , $x_{33} = 15$ とすると実行可能になる。 $u = (0, 2, - 1)$ , $v = (5, 7, 8, 4)$ を使って、任意の実行可能解の費用が $\sum u_{i} s_{i} + \sum v_{j} d_{j} - 2 \cdot 10$ 以上であることを示そう。

答えと解説

答えを見る

640

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

解説を読む

方針. 実行可能な輸送計画を 1 つ作り、その費用が下界と一致することを双対変数（ポテンシャル）を使って示す。

実行可能解. 経路 $A_{3} \to B_{4}$ は費用 $1$ と非常に安いので上限いっぱいの $x_{34} = 10$ とし、残りを次のように割り当てる（上限付き輸送問題の単体法で得られる解）。
$x_{11} = 20, x_{13} = 10, x_{22} = 25, x_{24} = 15, x_{32} = 5, x_{33} = 15, x_{34} = 10$
（ほかの $x_{ij}$ は $0$ ）。在庫について $A_{1} : 20 + 10 = 30$ 、 $A_{2} : 25 + 15 = 40$ 、 $A_{3} : 5 + 15 + 10 = 30$ 、需要について $B_{1} : 20$ 、 $B_{2} : 25 + 5 = 30$ 、 $B_{3} : 10 + 15 = 25$ 、 $B_{4} : 15 + 10 = 25$ で、すべての条件を満たす。費用は
$20 \cdot 5 + 10 \cdot 8 + 25 \cdot 9 + 15 \cdot 6 + 5 \cdot 6 + 15 \cdot 7 + 10 \cdot 1 = 100 + 80 + 225 + 90 + 30 + 105 + 10 = 640.$

下界. ポテンシャルを $u_{1} = 0, u_{2} = 2, u_{3} = - 1$ 、 $v_{1} = 5, v_{2} = 7, v_{3} = 8, v_{4} = 4$ とおく。これは上の解で正の輸送量をもつ経路のうち $A_{3} \to B_{4}$ 以外の 6 本で $c_{ij} = u_{i} + v_{j}$ となるように定めたものである（ $c_{11} = 0 + 5$ 、 $c_{13} = 0 + 8$ 、 $c_{22} = 2 + 7$ 、 $c_{24} = 2 + 4$ 、 $c_{32} = - 1 + 7$ 、 $c_{33} = - 1 + 8$ ）。被約費用 $c ˉ_{ij} = c_{ij} - u_{i} - v_{j}$ を計算すると
$c ˉ_{12} = 3, c ˉ_{14} = 3, c ˉ_{21} = 2, c ˉ_{23} = 2, c ˉ_{31} = 4, c ˉ_{34} = 1 - 3 = - 2$
で、残りは $0$ である。

任意の実行可能解 $x$ について、在庫・需要の等式 $\sum_{j} x_{ij} = s_{i}$ 、 $\sum_{i} x_{ij} = d_{j}$ を使うと
$i, j \sum c_{ij} x_{ij} = i, j \sum c ˉ_{ij} x_{ij} + i \sum u_{i} s_{i} + j \sum v_{j} d_{j}$
が成り立つ。ここで
$i \sum u_{i} s_{i} + j \sum v_{j} d_{j} = (0 \cdot 30 + 2 \cdot 40 - 1 \cdot 30) + (5 \cdot 20 + 7 \cdot 30 + 8 \cdot 25 + 4 \cdot 25) = 50 + 610 = 660.$
また $c ˉ_{ij} \geq 0$ （ $(i, j) \neq = (3, 4)$ ）かつ $x_{ij} \geq 0$ より、それらの項は $0$ 以上であり、 $c ˉ_{34} x_{34} = - 2 x_{34} \geq - 2 \cdot 10 = - 20$ （ $x_{34} \leq 10$ より）。したがって
$i, j \sum c_{ij} x_{ij} \geq 660 - 20 = 640.$

これは双対問題の実行可能解 $(u, v, w) = (u, v, 2)$ （ $w$ は上限制約 $x_{34} \leq 10$ に対応する双対変数で、 $u_{3} + v_{4} - w = 1 \leq c_{34}$ ）の目的関数値 $660 - 10 \cdot 2 = 640$ による弱双対性の評価にあたる。

上の実行可能解は費用 $640$ を達成するので、総輸送費用の最小値は $640$ である。

別解

制約付き輸送問題。経路 $A_{3} \to B_{4}$ （費用 1、最安）は上限 10 に達すると考えられる。\n\n候補解: $x_{34} = 10, x_{24} = 15, x_{11} = 20, x_{13} = 10, x_{22} = 25, x_{33} = 15, x_{32} = 5$ （ほかは 0）。\n- 供給: $A_{1} : 20 + 10 = 30$ 、 $A_{2} : 15 + 25 = 40$ 、 $A_{3} : 10 + 15 + 5 = 30$ ✓\n- 需要: $B_{1} : 20$ 、 $B_{2} : 25 + 5 = 30$ 、 $B_{3} : 10 + 15 = 25$ 、 $B_{4} : 10 + 15 = 25$ ✓\n\n費用: $A_{1} : 5 \cdot 20 + 8 \cdot 10 = 180$ 、 $A_{2} : 6 \cdot 15 + 9 \cdot 25 = 315$ 、 $A_{3} : 1 \cdot 10 + 7 \cdot 15 + 6 \cdot 5 = 145$ 。合計 $640$ 。\n\n最適性（双対）: 上限に達していない基底変数 $x_{11}, x_{13}, x_{22}, x_{24}, x_{32}, x_{33}$ （6 = 3+4−1 個）で $u_{i} + v_{j} = c_{ij}$ を解く。 $u_{1} = 0$ とすると $v_{1} = 5, v_{3} = 8, u_{3} = 7 - 8 = - 1, v_{2} = 6 + 1 = 7, u_{2} = 9 - 7 = 2, v_{4} = 6 - 2 = 4$ 。\n非基底の相対費用 $c_{ij} - u_{i} - v_{j}$ : $A_{1} B_{2} : 3, A_{1} B_{4} : 3, A_{2} B_{1} : 2, A_{2} B_{3} : 2, A_{3} B_{1} : 4$ はすべて $\geq 0$ 。上限に達している $A_{3} B_{4}$ は $1 - (- 1) - 4 = - 2 \leq 0$ で、上限まで使うのが最適であることと整合する。したがって最適。\n\n最小値は $640$ 。

この問題の確認

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

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

確認の方法について

間違いを報告する

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

	$Q_{1}$	$Q_{2}$	$Q_{3}$
$P_{1}$	$4$	$6$	$3$
$P_{2}$	$5$	$2$	$7$

作業	通常の所要日数	先行作業	最大短縮日数	$1$ 日あたりの短縮費用
$A$	$4$	なし	$1$	$30$
$B$	$6$	なし	$2$	$20$
$C$	$5$	$A$	$2$	$25$
$D$	$3$	$A$	$1$	$10$
$E$	$4$	$B, D$	$2$	$15$
$F$	$3$	$C, E$	$1$	$40$