早稲田大学 創造理工学研究科 経営システム工学専攻 2016年7月実施 オペレーションズリサーチ 問題8

标签：

• Waseda-University
• Transportation-Problem
• Stepping-Stone-Method

Author

祭音Myyura

Description

2工場から3倉庫への輸送問題を考える。単位輸送費、供給量、需要量は次のとおりである。

	倉庫1	倉庫2	倉庫3	供給量
工場1	3	8	7	28
工場2	2	10	4	17
需要量	8	25	12	45

1. 北西隅法により実行可能解と総輸送費を求めよ。
2. 飛び石法により最適解を求めよ。
3. 得られた解から総輸送費をこれ以上改善できないことを示せ。

Kai

[小問 1]

北西隅から順に割り当てると

$$x_{11}=8,\quad x_{12}=20,\quad x_{22}=5,\quad x_{23}=12$$

で、他は0となる。

	倉庫1	倉庫2	倉庫3	供給量
工場1	8	20	0	28
工場2	0	5	12	17
需要量	8	25	12

総輸送費は

$$3\cdot8+8\cdot20+10\cdot5+4\cdot12 =\boxed{282}.$$

[小問 2]

空きセル $(2,1)$ を始点とする閉路

$$(2,1)^+\to(1,1)^-\to(1,2)^+\to(2,2)^- \to(2,1)$$

の単位改善量は

$$\Delta_{21}=c_{21}-c_{11}+c_{12}-c_{22} =2-3+8-10=-3.$$

負なので輸送量を増やすと費用が減る。負号セルの最小輸送量は

$$\theta=\min(x_{11},x_{22})=\min(8,5)=5.$$

したがって閉路に沿って $5$ を加減すると

$$\boxed{ x_{11}=3,\quad x_{12}=25,\quad x_{13}=0,\quad x_{21}=5,\quad x_{22}=0,\quad x_{23}=12 }$$

となる。総輸送費は

$$3\cdot3+8\cdot25+2\cdot5+4\cdot12 =\boxed{267}.$$

[小問 3]

新しい基底セルは $(1,1),(1,2),(2,1),(2,3)$ である。空きセルの改善量は

$$\begin{aligned} \Delta_{13} &=c_{13}-c_{23}+c_{21}-c_{11} =7-4+2-3=2,\\ \Delta_{22} &=c_{22}-c_{12}+c_{11}-c_{21} =10-8+3-2=3. \end{aligned}$$

すべて非負なので、どの空きセルを基底へ入れても費用は減少しない。よって上の輸送計画は最適であり、最小総輸送費は $267$ である。