この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

最適化・線形計画法の問題

難易度 3期末試験の応用レベル大学数学最適化・線形計画法

$2$ つの倉庫 $A, B$ から $3$ つの店舗 $P, Q, R$ へ、ある品物を輸送する。倉庫 $A, B$ の在庫はそれぞれ $30$ , $40$ （単位：トン）で、在庫はすべて出荷する。店舗 $P, Q, R$ の需要はそれぞれ $20$ , $25$ , $25$ （トン）で、ちょうど需要量だけ受け取る。 $1$ トンあたりの輸送費（単位：万円）は次の表のとおりである。

	$P$	$Q$	$R$
$A$	$4$	$6$	$9$
$B$	$5$	$3$	$7$

ただし、 $B$ から $Q$ への輸送量は $15$ トン以下でなければならない。各経路の輸送量は $0$ 以上の実数で、総輸送費は各経路の（輸送量） $\times$ （ $1$ トンあたりの輸送費）の和とする。総輸送費の最小値（万円）を求めよ。

この問題で使うもの

線形計画問題の定式化と標準形（説明と入口の問題）
端点（基底解）の列挙による最適解（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$A$ からの輸送量 $a_{1}, a_{2}, a_{3}$ を変数にすると、 $B$ からの輸送量は需要の条件から $a_{1}, a_{2}, a_{3}$ で表せる。すべての輸送量が $0$ 以上という条件と $B \to Q$ の上限を不等式にする。

ヒント 2

総輸送費は $z = 350 - a_{1} + 3 a_{2} + 2 a_{3}$ となり、 $a_{1} = 30 - a_{2} - a_{3}$ を使って $2$ 変数の式にできる。上限の条件は $a_{2} \geq 10$ と同値。

ヒント 3

$z = 320 + 4 a_{2} + 3 a_{3}$ で、制約は $a_{2} \geq 10$ , $a_{3} \geq 0$ , $10 \leq a_{2} + a_{3} \leq 30$ など。 $a_{2}, a_{3}$ の係数がともに正であることに注目する。

答えと解説

答えを見る

360

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

解説を読む

$A$ から $P, Q, R$ への輸送量を $a_{1}, a_{2}, a_{3}$ とする。在庫はすべて出荷するので $a_{1} + a_{2} + a_{3} = 30$ 。需要の条件から、 $B$ から $P, Q, R$ への輸送量は $20 - a_{1}$ , $25 - a_{2}$ , $25 - a_{3}$ と決まる（このとき $B$ からの合計は $70 - 30 = 40$ となり、 $B$ の在庫の条件も自動的にみたされる）。

制約　すべての輸送量が $0$ 以上で、 $B \to Q$ が $15$ 以下なので
$a_{1}, a_{2}, a_{3} \geq 0, a_{1} \leq 20, a_{2} \leq 25, a_{3} \leq 25, 25 - a_{2} \leq 15 (i.e. a_{2} \geq 10) .$

総輸送費
$z = 4 a_{1} + 6 a_{2} + 9 a_{3} + 5 (20 - a_{1}) + 3 (25 - a_{2}) + 7 (25 - a_{3}) = 350 - a_{1} + 3 a_{2} + 2 a_{3} .$
$a_{1} = 30 - a_{2} - a_{3}$ を代入すると
$z = 320 + 4 a_{2} + 3 a_{3} .$
このとき $a_{1} = 30 - a_{2} - a_{3}$ についての条件 $0 \leq a_{1} \leq 20$ は $10 \leq a_{2} + a_{3} \leq 30$ となる。

最小化　 $a_{2} \geq 10$ , $a_{3} \geq 0$ より
$z = 320 + 4 a_{2} + 3 a_{3} \geq 320 + 4 \cdot 10 + 0 = 360$
で、等号は $a_{2} = 10$ , $a_{3} = 0$ のときに限る。このとき $a_{2} + a_{3} = 10$ で条件 $10 \leq a_{2} + a_{3} \leq 30$ や $a_{2} \leq 25$ , $a_{3} \leq 25$ もみたされ、 $a_{1} = 20$ である。

よって最適な輸送計画は
$A \to P : 20, A \to Q : 10, A \to R : 0, B \to P : 0, B \to Q : 15, B \to R : 25$
で、総輸送費は $4 \cdot 20 + 6 \cdot 10 + 3 \cdot 15 + 7 \cdot 25 = 80 + 60 + 45 + 175 = 360$ （万円）。

（参考： $B \to Q$ の上限がなければ $a_{2} = 0$ , $a_{3} = 10$ が最適で最小値は $350$ になる。上限のため $10$ 万円増える。）

別解

A から P, Q, R へ $a_{P}, a_{Q}, a_{R}$ 、B から P, Q, R へ $b_{P}, b_{Q}, b_{R}$ トン輸送するとする。

制約: $a_{P} + a_{Q} + a_{R} = 30$ , $b_{P} + b_{Q} + b_{R} = 40$ , $a_{P} + b_{P} = 20$ , $a_{Q} + b_{Q} = 25$ , $a_{R} + b_{R} = 25$ , $b_{Q} \leq 15$ , すべて $0$ 以上。

需要の式から $a_{P} = 20 - b_{P}$ , $a_{Q} = 25 - b_{Q}$ , $a_{R} = 25 - b_{R}$ と書ける。総輸送費は
$4 (20 - b_{P}) + 6 (25 - b_{Q}) + 9 (25 - b_{R}) + 5 b_{P} + 3 b_{Q} + 7 b_{R} = 455 + b_{P} - 3 b_{Q} - 2 b_{R}$ 。
B の在庫の式 $b_{P} = 40 - b_{Q} - b_{R}$ を代入すると、総輸送費 $= 495 - 4 b_{Q} - 3 b_{R}$ 。

これを最小にするには $4 b_{Q} + 3 b_{R}$ を最大にすればよい。
条件: $0 \leq b_{Q} \leq 15$ , $0 \leq b_{R} \leq 25$ (需要 R より), $b_{P} = 40 - b_{Q} - b_{R} \geq 0$ , $a_{P} = 20 - b_{P} = b_{Q} + b_{R} - 20 \geq 0$ , $a_{Q} = 25 - b_{Q} \geq 0$ , $a_{R} = 25 - b_{R} \geq 0$ 。
$b_{Q} \leq 15$ , $b_{R} \leq 25$ なので $4 b_{Q} + 3 b_{R} \leq 60 + 75 = 135$ 。 $b_{Q} = 15$ , $b_{R} = 25$ のとき $b_{P} = 0$ , $a_{P} = 20$ , $a_{Q} = 10$ , $a_{R} = 0$ となり、すべての条件を満たす。よって最大値は $135$ で、最小の総輸送費は $495 - 135 = 360$ 。

検算: A→P 20, A→Q 10, B→Q 15, B→R 25。A の出荷 $30$ , B の出荷 $40$ , P 受取 $20$ , Q 受取 $25$ , R 受取 $25$ で適合。費用は $4 \cdot 20 + 6 \cdot 10 + 3 \cdot 15 + 7 \cdot 25 = 80 + 60 + 45 + 175 = 360$ 。

答え: $360$ 万円。

最適化・線形計画法の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題