最小費用流 宿題
久保 幹雄
最小費用フロー問題
(4,20)
(3,2)
5
１
２
(1,2)
(4,1)
(2,3)
４
5
(3,10)
(u,c)
３
各点iに整数b(i)
（需要・供給量）
ｂ＝(5,0,0,-5)
b(i)>0: iは供給点
b(i)<0: iは需要点
各枝(i,j)に
容量 u(i,j)
費用 c(i,j)
割り当て問題(Assignment Problem)
4
１
４
3
4
２
３
５
6
8
4
６
• 応用
– 作業者の仕事への割り振り
– 仕事の機械への割り振り
輸送問題(Transportation Problem)
供給地点
供給量
10
１
4
3
需要地点
需要量
４
15
５
25
６
20
4
２
20
30
３
6
8
4
• 応用
– 工場から中間倉庫への輸送
– 倉庫から顧客への輸送

dangerous

ネットワーク理論（授業概要）

離散システム特論 powerpoint資料5