ポテンシャル法による輸送問題の最適化

基底セルで $u_{i} + v_{j} = c_{ij}$ を解いてポテンシャルを求め、非基底セルの $c_{ij} - u_{i} - v_{j}$ の符号で最適性を判定できる。負のセルがあれば閉路に沿って輸送量を移して解を改善し、総輸送費の最小値を求められる

前提

輸送問題の定式化と初期解（大学数学オペレーションズ・リサーチ）
掃き出し法と連立 1 次方程式（大学数学線形代数）

この技能までの道筋（28 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

輸送問題の定式化と初期解（大学数学オペレーションズ・リサーチ）
三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
乗法公式による展開（中学数学数と式）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）
掃き出し法と連立 1 次方程式（大学数学線形代数）

説明

輸送問題では、北西隅法などで作った初期解が最も安いとは限りません。ポテンシャル法（u-v 法、MODI 法とも呼ぶ）を使うと、今の解が最適かどうかを数値で判定できます。最適でないときは、どのルートにどれだけの量を移せば総輸送費が下がるかがわかります。判定と改善を繰り返すと、総輸送費の最小値にたどり着きます。

なぜそうしてよいのか

供給地 $i$ の供給量を $a_{i}$ 、需要地 $j$ の需要量を $b_{j}$ とし、需給が釣り合っている（ $\sum_{i} a_{i} = \sum_{j} b_{j}$ ）とします。実行可能解は $x_{ij} \geq 0$ で、 $\sum_{j} x_{ij} = a_{i}$ 、 $\sum_{i} x_{ij} = b_{j}$ を満たします。このとき、供給地ごとの数 $u_{i}$ と需要地ごとの数 $v_{j}$ をどう選んでも、次の等式が成り立ちます。 $i, j \sum c_{ij} x_{ij} = i, j \sum (c_{ij} - u_{i} - v_{j}) x_{ij} + i \sum u_{i} a_{i} + j \sum v_{j} b_{j}$ 右辺の第 2 項と第 3 項は、輸送量によらない定数です。いま輸送量を割り当てているセルを基底セルと呼びます。基底セルで $c_{ij} - u_{i} - v_{j} = 0$ となるように $u_{i}, v_{j}$ を決めます。これをポテンシャルと呼びます。さらに $d_{ij} = c_{ij} - u_{i} - v_{j}$ とおきます。今の解では非基底セルの輸送量が 0 です。したがって、今の総費用はちょうど定数部分に等しくなります。

すべての非基底セルで $d_{ij} \geq 0$ なら、どの実行可能解でも $x_{ij} \geq 0$ なので、第 1 項は 0 以上です。よって総費用は定数部分以上になり、今の解が最適だとわかります。反対に $d_{ij} < 0$ のセルがあれば、そこへ量 $θ$ を流すと費用は $d_{ij} θ$ だけ変わります。つまり費用が下がります。ただし、行の和と列の和は保たなければなりません。そこで、そのセルから出発し、基底セルだけを通って縦横に曲がりながら元に戻る閉路をたどります。たどった順に $+ θ, - θ$ を交互に加えると、各行・各列で増減が打ち消し合います。閉路上の費用を符号付きで足し合わせ、基底セルで $c_{ij} = u_{i} + v_{j}$ であることを使うと、 $u_{i}, v_{j}$ が打ち消し合います。その結果、 $d_{ij}$ だけが残ります。

基底セルは $m + n - 1$ 個あります（ $m$ は供給地の数、 $n$ は需要地の数）。一方、未知数 $u_{i}, v_{j}$ は $m + n$ 個なので、自由度が 1 つ残ります。実際、すべての $u_{i}$ に $t$ を足し、すべての $v_{j}$ から $t$ を引いても、 $d_{ij}$ は変わりません。そのため $u_{1} = 0$ と決めてかまいません。基底セルは閉路を作らずにつながっているので、この連立 1 次方程式は一つずつ代入するだけで解が 1 通りに決まります。掃き出し法で解いても同じ結果になります。

手順

基底セル（輸送量を割り当てたセル）が $m + n - 1$ 個あることを確かめる。足りないとき（退化）は、閉路を作らないセルを輸送量 $0$ の基底セルとして加える
$u_{1} = 0$ とおき、基底セルの式 $u_{i} + v_{j} = c_{ij}$ を順に解いて、すべての $u_{i}, v_{j}$ を求める
各非基底セルで $d_{ij} = c_{ij} - u_{i} - v_{j}$ を計算する。すべて $d_{ij} \geq 0$ なら今の解が最適なので、総輸送費を求めて終える
$d_{ij} < 0$ のセル（ふつうは最も負のもの）を選ぶ。そこから基底セルだけを縦横にたどって戻る閉路を作り、選んだセルから順に $+, -, +, -, \dots$ の符号を付ける
$-$ のセルの輸送量の最小値を $θ$ とする。 $+$ のセルに $θ$ を足し、 $-$ のセルから $θ$ を引く。0 になったセルを 1 つだけ非基底にして、手順 2 に戻る。このとき総費用は $∣ d_{ij} ∣ θ$ だけ減る

例題

供給地 $A_{1}$ の供給量は $30$ 、 $A_{2}$ の供給量は $40$ であり、需要地 $B_{1}, B_{2}, B_{3}$ の需要量はそれぞれ $20, 30, 20$ である。単位あたりの輸送費は、 $A_{1}$ から $B_{1}, B_{2}, B_{3}$ へ順に $4, 6, 8$ 、 $A_{2}$ から $B_{1}, B_{2}, B_{3}$ へ順に $5, 3, 7$ である。北西隅法による初期解 $x_{11} = 20, x_{12} = 10, x_{22} = 20, x_{23} = 20$ （それ以外は $0$ ）から出発して、ポテンシャル法で総輸送費の最小値を求めよ。

例題の解答

初期解の総輸送費は $20 \cdot 4 + 10 \cdot 6 + 20 \cdot 3 + 20 \cdot 7 = 340$ である。

【手順 1】基底セルは $(1, 1), (1, 2), (2, 2), (2, 3)$ の 4 個である。 $m + n - 1 = 2 + 3 - 1 = 4$ と一致する。

【手順 2】 $u_{1} = 0$ とおく。 $(1, 1)$ から $v_{1} = 4$ 、 $(1, 2)$ から $v_{2} = 6$ が決まる。続いて $(2, 2)$ から $u_{2} = 3 - 6 = - 3$ 、 $(2, 3)$ から $v_{3} = 7 - (- 3) = 10$ が決まる。

【手順 3】非基底セルを調べると、 $d_{13} = 8 - 0 - 10 = - 2$ 、 $d_{21} = 5 - (- 3) - 4 = 4$ である。負のセルがあるので、まだ最適ではない。

【手順 4】 $(1, 3)$ を選ぶ。閉路は $(1, 3)^{+} \to (2, 3)^{-} \to (2, 2)^{+} \to (1, 2)^{-} \to (1, 3)$ となる。

【手順 5】 $-$ のセルの輸送量は $x_{23} = 20$ と $x_{12} = 10$ なので、 $θ = min (20, 10) = 10$ である。更新すると $x_{13} = 10, x_{23} = 10, x_{22} = 30, x_{12} = 0$ となり、 $(1, 2)$ が非基底になる。新しい基底セルとその輸送量は $(1, 1)$ が $20$ 、 $(1, 3)$ が $10$ 、 $(2, 2)$ が $30$ 、 $(2, 3)$ が $10$ である。総輸送費は $340 - 2 \cdot 10 = 320$ になる。直接計算しても $80 + 80 + 90 + 70 = 320$ で一致する。

【手順 2 に戻る】 $u_{1} = 0$ とおく。 $(1, 1)$ から $v_{1} = 4$ 、 $(1, 3)$ から $v_{3} = 8$ が決まる。続いて $(2, 3)$ から $u_{2} = 7 - 8 = - 1$ 、 $(2, 2)$ から $v_{2} = 3 - (- 1) = 4$ が決まる。

【手順 3】 $d_{12} = 6 - 0 - 4 = 2 \geq 0$ 、 $d_{21} = 5 - (- 1) - 4 = 2 \geq 0$ である。すべて 0 以上なので、この解が最適である。

よって、総輸送費の最小値は $320$ である。

答え: $320$

よくある誤り

判定に使う量を $u_{i} + v_{j} - c_{ij}$ として、符号を逆に読んでしまう誤り。正しくは $d_{ij} = c_{ij} - u_{i} - v_{j}$ で、 $d_{ij} < 0$ のセルに流すと費用が下がる。例題では $d_{13} = 8 - 0 - 10 = - 2 < 0$ なので、 $(1, 3)$ が改善の対象になる。
$θ$ を「 $-$ のセルの輸送量の最小値」以外から取ってしまう誤り。例題で $-$ のセルのうち大きい方の $x_{23} = 20$ を $θ$ に取ると、 $x_{12} = 10 - 20 = - 10 < 0$ となり、負の輸送量が出る。また $+$ のセルの最小値 $x_{13} = 0$ を取ると $θ = 0$ となり、輸送量がまったく動かず改善されない。正しくは $θ = min (x_{23}, x_{12}) = min (20, 10) = 10$ である。
閉路の曲がり角に非基底セルを使ってしまう誤り。正しくは、曲がり角に使うのは入れるセル 1 つと基底セルだけである。非基底セルでは $c_{ij} = u_{i} + v_{j}$ が成り立つとは限らないので、閉路に沿った費用の変化が $d_{ij} θ$ と一致しなくなる。さらに、そのセルに $-$ が付くと、輸送量 0 から $θ$ を引くことになり負になる。
$-$ のセルが同時に 2 つ 0 になったとき、両方を非基底にしてしまう誤り。こうすると基底セルが $m + n - 2$ 個に減ってしまう。正しくは 1 つだけを非基底にし、もう 1 つは輸送量 $0$ の基底セルとして残す。こうすれば基底セルは $m + n - 1$ 個に保たれ、 $u_{i} + v_{j} = c_{ij}$ が解ける。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

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

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

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

	$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$

ポテンシャル法による輸送問題の最適化

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題