早稲田大学 創造理工学研究科 経営システム工学専攻 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]

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

で、他は0となる。

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

総輸送費は

[小問 2]

空きセル を始点とする閉路

の単位改善量は

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

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

となる。総輸送費は

[小問 3]

新しい基底セルは である。空きセルの改善量は

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