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

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

2 つの農場 $A_{1}, A_{2}$ から 3 つの市場 $B_{1}, B_{2}, B_{3}$ へ野菜を輸送する。農場の出荷量は $A_{1}$ が $30$ トン、 $A_{2}$ が $20$ トンで、すべて出荷する。市場の需要量は $B_{1}$ が $15$ トン、 $B_{2}$ が $25$ トン、 $B_{3}$ が $10$ トンで、ちょうど満たす。 $1$ トンあたりの輸送費（単位: 千円）は次の表のとおりである。

$A_{1} A_{2} B_{1} 45 B_{2} 63 B_{3} 87$

輸送量は $0$ 以上の実数とし、総輸送費は各経路の「輸送量 $\times$ 単価」の和とする。北西隅法で初期の実行可能解を作り、ポテンシャル法で最適性を判定・改善して、総輸送費の最小値（単位: 千円）を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

ポテンシャル法を使う。まず北西隅法で初期解を作り、基底セルで $u_{i} + v_{j} = c_{ij}$ を解いてポテンシャルを求める。

ヒント 2

$u_{1} = 0$ とおいてポテンシャルを決め、非基底セル $(1, 3), (2, 1)$ について $c_{ij} - u_{i} - v_{j}$ を計算する。負のセルがあれば、そこから閉路を作って輸送量を移す。

ヒント 3

初期解は $x_{11} = 15, x_{12} = 15, x_{22} = 10, x_{23} = 10$ （総輸送費 $250$ ）、ポテンシャルは $u_{1} = 0, u_{2} = - 3, v_{1} = 4, v_{2} = 6, v_{3} = 10$ で、 $(1, 3)$ の値が $- 2$ になる。閉路 $(1, 3), (2, 3), (2, 2), (1, 2)$ に沿って移せる量を求めよう。

答えと解説

答えを見る

230

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

解説を読む

1. 初期解（北西隅法）

供給の合計は $30 + 20 = 50$ 、需要の合計は $15 + 25 + 10 = 50$ で釣り合っている。輸送量を $x_{ij}$ （ $A_{i}$ から $B_{j}$ へ）とする。北西隅から順に割り当てると
$x_{11} = 15, x_{12} = 15, x_{22} = 10, x_{23} = 10$
で、基底セルは $(1, 1), (1, 2), (2, 2), (2, 3)$ の $4 = 2 + 3 - 1$ 個。総輸送費は $4 \cdot 15 + 6 \cdot 15 + 3 \cdot 10 + 7 \cdot 10 = 60 + 90 + 30 + 70 = 250$ 。

2. ポテンシャルの計算

基底セルで $u_{i} + v_{j} = c_{ij}$ とし、 $u_{1} = 0$ とおく。
- $(1, 1)$ : $u_{1} + v_{1} = 4$ より $v_{1} = 4$
- $(1, 2)$ : $u_{1} + v_{2} = 6$ より $v_{2} = 6$
- $(2, 2)$ : $u_{2} + v_{2} = 3$ より $u_{2} = - 3$
- $(2, 3)$ : $u_{2} + v_{3} = 7$ より $v_{3} = 10$

3. 最適性の判定

非基底セルで $c_{ij} - u_{i} - v_{j}$ を計算する。
- $(1, 3)$ : $8 - 0 - 10 = - 2$
- $(2, 1)$ : $5 - (- 3) - 4 = 4$

負のセル $(1, 3)$ があるので、まだ最適ではない。

4. 閉路に沿った改善

$(1, 3)$ を始点とする閉路 $(1, 3) \to (2, 3) \to (2, 2) \to (1, 2) \to (1, 3)$ をとり、符号を $+, -, +, -$ とする。移せる量は $-$ のセルの最小値 $θ = min (x_{23}, x_{12}) = min (10, 15) = 10$ 。
$x_{13} = 10, x_{23} = 0, x_{22} = 20, x_{12} = 5, x_{11} = 15$
$(2, 3)$ が基底から外れる。総輸送費は $250 + (- 2) \cdot 10 = 230$ 。確かめると $4 \cdot 15 + 6 \cdot 5 + 8 \cdot 10 + 3 \cdot 20 = 60 + 30 + 80 + 60 = 230$ 。

5. 再判定

新しい基底セル $(1, 1), (1, 2), (1, 3), (2, 2)$ で $u_{1} = 0$ とすると $v_{1} = 4, v_{2} = 6, v_{3} = 8, u_{2} = 3 - 6 = - 3$ 。非基底セルは
- $(2, 1)$ : $5 + 3 - 4 = 4 \geq 0$
- $(2, 3)$ : $7 + 3 - 8 = 2 \geq 0$

すべて $0$ 以上なので、この解は最適である。よって総輸送費の最小値は $230$ 千円。

別解

総供給量は $30 + 20 = 50$ 、総需要量は $15 + 25 + 10 = 50$ で等しいので、均衡した輸送問題である。

【北西隅法】
左上の経路から順に割り当てる。 $x_{11} = 15$ 、 $x_{12} = 15$ 、 $x_{22} = 10$ 、 $x_{23} = 10$ となる。
総輸送費は $15 \cdot 4 + 15 \cdot 6 + 10 \cdot 3 + 10 \cdot 7 = 60 + 90 + 30 + 70 = 250$ 。

【ポテンシャル法 1 回目】
基底変数は $x_{11}, x_{12}, x_{22}, x_{23}$ である。 $u_{1} = 0$ として $u_{i} + v_{j} = c_{ij}$ を解くと、 $v_{1} = 4$ 、 $v_{2} = 6$ 、 $u_{2} = - 3$ 、 $v_{3} = 10$ となる。
非基底変数の被約費用 $c_{ij} - u_{i} - v_{j}$ は次のとおり。
- $(1, 3)$ : $8 - 0 - 10 = - 2 < 0$
- $(2, 1)$ : $5 + 3 - 4 = 4$

$(1, 3)$ が負なので最適ではなく、 $x_{13}$ を基底に入れる。
閉路は $x_{13} (+) \to x_{12} (-) \to x_{22} (+) \to x_{23} (-)$ で、 $θ = min (15, 10) = 10$ 。
更新後は $x_{11} = 15$ 、 $x_{12} = 5$ 、 $x_{13} = 10$ 、 $x_{22} = 20$ 、 $x_{23} = 0$ となる。
総輸送費は $60 + 30 + 80 + 60 = 230$ （ $250 - 2 \cdot 10 = 230$ と一致）。

【ポテンシャル法 2 回目】
基底変数は $x_{11}, x_{12}, x_{13}, x_{22}$ である。 $u_{1} = 0$ として、 $v_{1} = 4$ 、 $v_{2} = 6$ 、 $v_{3} = 8$ 、 $u_{2} = - 3$ となる。
非基底変数の被約費用は次のとおり。
- $(2, 1)$ : $5 + 3 - 4 = 4 > 0$
- $(2, 3)$ : $7 + 3 - 8 = 2 > 0$

すべて $0$ 以上なので最適である。

【検算】
$A_{1}$ は $B_{1}, B_{2}, B_{3}$ にそれぞれ $15, 5, 10$ 、 $A_{2}$ は $B_{2}$ に $20$ を送る。これは供給・需要の条件を満たし、費用は $230$ 。

最小値は $230$ 千円。

この問題の確認

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

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

確認の方法について

間違いを報告する

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