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

難易度 3期末試験の応用レベル大学数学オペレーションズ・リサーチ

3 つの工場 $A_{1}, A_{2}, A_{3}$ から 3 つの販売店 $B_{1}, B_{2}, B_{3}$ へ、ある製品を輸送する。各工場の生産量は $A_{1}$ が $25$ 、 $A_{2}$ が $35$ 、 $A_{3}$ が $40$ で、すべて輸送しなければならない。各販売店の需要量は $B_{1}$ が $30$ 、 $B_{2}$ が $45$ 、 $B_{3}$ が $25$ で、ちょうど需要量を受け取らなければならない。製品 $1$ 単位あたりの輸送費用は次の表のとおりである。ただし、 $A_{3}$ から $B_{1}$ への輸送費用 $t$ だけは未定であり、 $t$ は $t \geq 0$ を満たす実数とする。

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

輸送量は $0$ 以上の実数とし、総輸送費用の最小値を $f (t)$ とする。「すべての $t^{'} \geq t$ について $f (t^{'}) = f (t)$ が成り立つ」ような $t (\geq 0)$ の最小値 $t_{0}$ を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$t$ が十分大きいとき経路 $A_{3} \to B_{1}$ は使われない。まず $x_{31} = 0$ として最適解を求め、その最適性が $t$ のどの範囲で保たれるかを調べよう。

ヒント 2

最適解の基底セルで $u_{i} + v_{j} = c_{ij}$ となるポテンシャルを求め、セル $(3, 1)$ の相対費用 $t - u_{3} - v_{1}$ の符号を調べる。

ヒント 3

$x_{31} = 0$ のときの最適解は $x_{11} = 25, x_{21} = 5, x_{22} = 30, x_{32} = 15, x_{33} = 25$ で総費用 $435$ 。 $u_{1} = 0$ とするとポテンシャルは $v_{1} = 4, u_{2} = 1, v_{2} = 2, u_{3} = 6, v_{3} = - 2$ となる。

答えと解説

答えを見る

10

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

解説を読む

$A_{i}$ から $B_{j}$ への輸送量を $x_{ij}$ 、費用を $c_{ij}$ とする。総供給量 $25 + 35 + 40 = 100$ と総需要量 $30 + 45 + 25 = 100$ は等しいので、つり合った輸送問題である。

1. 経路 $A_{3} \to B_{1}$ を使わない解

$x_{31} = 0$ とすると、 $A_{3}$ の $40$ は $B_{2}, B_{3}$ に送るしかない。費用の安い $A_{3} \to B_{3}$ （費用 $4$ ）で $B_{3}$ の需要 $25$ をすべてまかない、残り $15$ を $A_{3} \to B_{2}$ に送る。 $B_{2}$ の残り $30$ は $A_{2} \to B_{2}$ （費用 $3$ ）でまかない、 $A_{2}$ の残り $5$ を $B_{1}$ に、 $B_{1}$ の残り $25$ を $A_{1}$ から送る。
$x_{11} = 25, x_{21} = 5, x_{22} = 30, x_{32} = 15, x_{33} = 25$
その他は $0$ 。総費用は
$25 \cdot 4 + 5 \cdot 5 + 30 \cdot 3 + 15 \cdot 8 + 25 \cdot 4 = 100 + 25 + 90 + 120 + 100 = 435.$
この解は正の基底変数が $m + n - 1 = 5$ 個の非退化な基底解である。

2. ポテンシャル（双対変数）による最適性の判定

基底セルで $u_{i} + v_{j} = c_{ij}$ となるように $u_{1} = 0$ として定めると
$v_{1} = 4, u_{2} = 5 - 4 = 1, v_{2} = 3 - 1 = 2, u_{3} = 8 - 2 = 6, v_{3} = 4 - 6 = - 2.$
非基底セルの相対費用 $c ˉ_{ij} = c_{ij} - u_{i} - v_{j}$ は
$c ˉ_{12} = 6 - 0 - 2 = 4, c ˉ_{13} = 9 - 0 + 2 = 11, c ˉ_{23} = 7 - 1 + 2 = 8, c ˉ_{31} = t - 6 - 4 = t - 10.$

3. $t \geq 10$ のとき

すべての相対費用が $0$ 以上なので、 $(u, v)$ は双対問題の実行可能解であり、その双対目的関数値 $\sum a_{i} u_{i} + \sum b_{j} v_{j}$ は主問題の値 $435$ と一致する（基底セルで $u_{i} + v_{j} = c_{ij}$ が成り立つため）。弱双対定理より上の解は最適で、 $f (t) = 435$ （一定）である。

4. $0 \leq t < 10$ のとき

$c ˉ_{31} = t - 10 < 0$ なので $x_{31}$ を増やすと費用が下がる。閉路 $(3, 1) + \to (3, 2) - \to (2, 2) + \to (2, 1) -$ に沿って $θ$ だけ動かすと、減るセルは $x_{32} = 15, x_{21} = 5$ なので $θ = 5$ まで動かせる。このとき総費用は
$435 + 5 (t - 10) = 435 - 5 (10 - t) < 435$
となり、 $f (t) < 435$ である。

5. 結論

$f (t) = 435 (t \geq 10)$ 、 $f (t) < 435 (0 \leq t < 10)$ なので、すべての $t^{'} \geq t$ で $f (t^{'}) = f (t)$ となる $t$ の最小値は
$t_{0} = 10.$

別解

この問題は輸送問題である。 $t$ が十分大きければ $A_{3} \to B_{1}$ の輸送量 $x_{31}$ は $0$ になる。そこで $x_{31} = 0$ のときの最適解を求め、その最適性が保たれる $t$ の下限を双対変数（ポテンシャル）から求める。

1. $x_{31} = 0$ のとき、次の基底解を考える。
$x_{11} = 25, x_{21} = 5, x_{22} = 30, x_{32} = 15, x_{33} = 25$ 。
供給の確認： $A_{1}$ は $25$ 、 $A_{2}$ は $5 + 30 = 35$ 、 $A_{3}$ は $15 + 25 = 40$ で、すべて一致する。
需要の確認： $B_{1}$ は $25 + 5 = 30$ 、 $B_{2}$ は $30 + 15 = 45$ 、 $B_{3}$ は $25$ で、すべて一致する。
すべての基底変数が正なので、非退化である。

2. 基底変数について $u_{i} + v_{j} = c_{ij}$ を解く。 $u_{1} = 0$ とすると次のようになる。
$v_{1} = 4$ 、 $u_{2} = 5 - 4 = 1$ 、 $v_{2} = 3 - 1 = 2$ 、 $u_{3} = 8 - 2 = 6$ 、 $v_{3} = 4 - 6 = - 2$ 。

3. 非基底変数の被約費用 $c_{ij} - u_{i} - v_{j}$ を求める。
- $x_{12}$ ： $6 - 0 - 2 = 4 \geq 0$
- $x_{13}$ ： $9 - 0 + 2 = 11 \geq 0$
- $x_{23}$ ： $7 - 1 + 2 = 8 \geq 0$
- $x_{31}$ ： $t - 6 - 4 = t - 10$

4. $t \geq 10$ なら被約費用がすべて $0$ 以上なので、この基底解は最適である。そのとき $f (t) = 25 \cdot 4 + 5 \cdot 5 + 30 \cdot 3 + 15 \cdot 8 + 25 \cdot 4 = 100 + 25 + 90 + 120 + 100 = 435$ （定数）となる。

5. $t < 10$ のとき $x_{31}$ の被約費用は負である。解は非退化なので、 $x_{31}$ を正にする基底変換で費用は真に減り、 $f (t) < 435$ となる。

したがって $f (t^{'}) = f (t)$ がすべての $t^{'} \geq t$ で成り立つ最小の $t$ は $t_{0} = 10$ である。

検算： $t = 10$ のとき、 $x_{31}$ を増やす閉路 $(3, 1) \to (1, 1) \to (1, \cdot) \dots$ に沿った費用変化は $t - 10 = 0$ になる。これは被約費用と一致する。

この問題の確認

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

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

確認の方法について

間違いを報告する

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

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

辺	長さ	辺	長さ
$1 \to 2$	$3$	$3 \to 6$	$7$
$1 \to 3$	$2$	$2 \to 5$	$5$
$1 \to 4$	$6$	$2 \to 6$	$6$
$3 \to 2$	$1$	$4 \to 5$	$2$
$2 \to 4$	$2$	$4 \to 6$	$3$
$3 \to 4$	$3$	$5 \to 7$	$3$
		$6 \to 7$	$2$