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

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

2 つの農場 $P_{1}, P_{2}$ から 3 つの市場 $Q_{1}, Q_{2}, Q_{3}$ へ野菜を輸送する。出荷量は $P_{1}$ が $50$ トン、 $P_{2}$ が $40$ トンで、すべて出荷する。需要量は $Q_{1}$ が $30$ トン、 $Q_{2}$ が $35$ トン、 $Q_{3}$ が $25$ トンで、ちょうど満たす。 $1$ トンあたりの輸送費（単位：千円）は次の表のとおりである。
$P_{1} P_{2} 需要量 Q_{1} 4630 Q_{2} 6535 Q_{3} 3425 出荷量 5040$
各輸送量は $0$ 以上の実数とし、輸送費は輸送量に比例するものとする。北西隅法で初期の実行可能解を作り、ポテンシャル法で最適性の判定と改善を行って、総輸送費の最小値（千円）を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

北西隅法で初期解を作り、ポテンシャル法（基底セルで $u_{i} + v_{j} = c_{ij}$ を解き、非基底セルで $c_{ij} - u_{i} - v_{j}$ の符号を調べる方法）を使いましょう。

ヒント 2

$u_{1} = 0$ とおいて、基底セル $(1, 1), (1, 2), (2, 2), (2, 3)$ から $v_{1}, v_{2}, u_{2}, v_{3}$ を順に決めます。負の値になる非基底セルがあれば、そのセルから始まる閉路に沿って輸送量を移します。

ヒント 3

初期解は $x_{11} = 30, x_{12} = 20, x_{22} = 15, x_{23} = 25$ （総輸送費 $415$ ）で、ポテンシャルは $u_{1} = 0, u_{2} = - 1, v_{1} = 4, v_{2} = 6, v_{3} = 5$ です。 $(1, 3)$ の値が $- 2$ なので、閉路 $(1, 3) \to (2, 3) \to (2, 2) \to (1, 2)$ に沿って $θ$ を移します。

答えと解説

答えを見る

375

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

解説を読む

$P_{i}$ から $Q_{j}$ への輸送量を $x_{ij}$ 、輸送費を $c_{ij}$ とする。出荷量の合計は $50 + 40 = 90$ 、需要量の合計は $30 + 35 + 25 = 90$ で等しいので、ダミーを加えずにそのまま扱える。

1. 北西隅法による初期解

左上のセルから順に割り当てる。
- $x_{11} = min (50, 30) = 30$ （ $Q_{1}$ の需要が満たされ、 $P_{1}$ の残りは $20$ ）
- $x_{12} = min (20, 35) = 20$ （ $P_{1}$ の出荷が尽き、 $Q_{2}$ の残りは $15$ ）
- $x_{22} = min (40, 15) = 15$ （ $Q_{2}$ の需要が満たされ、 $P_{2}$ の残りは $25$ ）
- $x_{23} = 25$

基底セルは $(1, 1), (1, 2), (2, 2), (2, 3)$ の $4$ 個で、 $m + n - 1 = 2 + 3 - 1 = 4$ に一致する。総輸送費は
$30 \cdot 4 + 20 \cdot 6 + 15 \cdot 5 + 25 \cdot 4 = 120 + 120 + 75 + 100 = 415.$

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} = 5$ より $u_{2} = - 1$
- $(2, 3)$ : $u_{2} + v_{3} = 4$ より $v_{3} = 5$

3. 非基底セルの判定

$c_{ij} - u_{i} - v_{j}$ を計算する。
- $(1, 3)$ : $3 - 0 - 5 = - 2$
- $(2, 1)$ : $6 - (- 1) - 4 = 3$

$(1, 3)$ が負なので、この解は最適ではない。 $(1, 3)$ に輸送量を入れると $1$ トンあたり $2$ 千円下がる。

4. 閉路に沿った改善

$(1, 3)$ から出発して基底セルをたどる閉路は $(1, 3) \to (2, 3) \to (2, 2) \to (1, 2) \to (1, 3)$ である。符号を $+, -, +, -$ と交互につけると
$x_{13} : + θ, x_{23} : - θ, x_{22} : + θ, x_{12} : - θ .$
$-$ のセルの値は $x_{23} = 25$ 、 $x_{12} = 20$ なので、 $θ = min (25, 20) = 20$ 。新しい解は
$x_{11} = 30, x_{12} = 0, x_{13} = 20, x_{22} = 35, x_{23} = 5$
で、 $(1, 2)$ が基底から外れる。総輸送費は
$30 \cdot 4 + 20 \cdot 3 + 35 \cdot 5 + 5 \cdot 4 = 120 + 60 + 175 + 20 = 375$
であり、 $415 - 2 \cdot 20 = 375$ とも一致する。

5. 再び最適性を判定

基底セル $(1, 1), (1, 3), (2, 2), (2, 3)$ で $u_{1} = 0$ とおくと、 $v_{1} = 4$ 、 $v_{3} = 3$ 、 $u_{2} = 4 - 3 = 1$ 、 $v_{2} = 5 - 1 = 4$ 。非基底セルでは
- $(1, 2)$ : $6 - 0 - 4 = 2 > 0$
- $(2, 1)$ : $6 - 1 - 4 = 1 > 0$

すべて正なので、この解が最適である。よって総輸送費の最小値は $375$ 千円である。

別解

北西隅法: $x_{11} = 30, x_{12} = 20, x_{22} = 15, x_{23} = 25$ とすると、費用は $120 + 120 + 75 + 100 = 415$ 千円。

ポテンシャル法: 基底変数 $(1, 1), (1, 2), (2, 2), (2, 3)$ に対して $c_{ij} = u_{i} + v_{j}$ とおく。 $u_{1} = 0$ とすると、 $v_{1} = 4, v_{2} = 6, u_{2} = - 1, v_{3} = 5$ 。
非基底変数の被約費用は $c_{13} - (u_{1} + v_{3}) = 3 - 5 = - 2 < 0$ 、 $c_{21} - (u_{2} + v_{1}) = 6 - 3 = 3$ 。 $x_{13}$ が負なので改善できる。

改善: $x_{13}$ を入れると閉路は $x_{13} (+), x_{12} (-), x_{22} (+), x_{23} (-)$ となる。 $θ = min (20, 25) = 20$ 。
新しい解は $x_{11} = 30, x_{13} = 20, x_{22} = 35, x_{23} = 5$ 、 $x_{12} = 0$ 。費用は $120 + 60 + 175 + 20 = 375$ 千円。

最適性の確認: 基底変数 $(1, 1), (1, 3), (2, 2), (2, 3)$ に対して $u_{1} = 0$ とすると、 $v_{1} = 4, v_{3} = 3, u_{2} = 1, v_{2} = 4$ 。
非基底変数の被約費用は $c_{12} - (u_{1} + v_{2}) = 6 - 4 = 2 \geq 0$ 、 $c_{21} - (u_{2} + v_{1}) = 6 - 5 = 1 \geq 0$ 。すべて 0 以上なので最適。

検算: 供給は $30 + 20 = 50, 35 + 5 = 40$ 、需要は $30, 35, 20 + 5 = 25$ でいずれも一致する。

最小費用は $375$ 千円。

この問題の確認

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

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

確認の方法について

間違いを報告する

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