ネットワーク計画2(最小費用流問題)

ネットワークシンプレックス法

最短路問題，最大流問題，最小費用流問題
などはすべてLPに定式化できる
定式化の方法
特徴

ネットワーク計画２
1
最小費用流問題
各枝の容量と，１単位フローを流すときのコストが与えられたと
き，各ノードでの需要量と供給量を満たすような最も費用の安
いフローを求めよ．
(7,1)
10
１
(8,2)
（容量，コスト）
3
２
(2,2)
(7,1)
３
0
４
(10,3)
0
0
(6,5)
５
(7,1)
ー5
(4,5)
７
(7,2)
(5,5)
６
ー8
供給量（需要量）
ネットワーク計画２
2
供給量が正：ソース，供給節点(supply)
（１，２）
供給量が負：シンク，需要節点(demand)
（７，６）
供給量が０：通過ノード
（３，４，５）

ネットワーク計画２
3
LPへの定式化
xij : 枝(i, j )を通るフロー
cij : 枝(i, j )の単位コスト（負でも良い）
uij : 枝(i, j )の容量（下限がある場合もある）
とおくと，目的関数は
min
∑c x
ij ij
( i , j )∈E
ネットワーク計画２
4
制約条件
容量制約
0 ≤ xij ≤ uij

∀
(i, j ) ∈ E
フロー保存則
（ノードから出て行くフロー）
ー（ノードに入ってくるフロー）＝需要供給量
∑
∑
xij −
x ji = bi
{ j (i , j )∈E } { j ( j ,i )∈E }
∀
i ∈V
bi : ノード i での需要供給量
ネットワーク計画２
5
(7,1)
10
１
(8,2)
3
２
(2,2)
(7,1)
３
0
４
(10,3)
0
0
(6,5)
５
(7,1)
ー5
(4,5)
７
(7,2)
(5,5)
６
ー8
ノード１（供給点）: x12 + x13 = 10
ノード４（通過点）: x43 − ( x24 + x74 ) = 0
ノード６（需要点）: x65 − ( x36 + x76 ) = −8
ネットワーク計画２
6
min x12 + 2 x13 + 2 x24 + 5 x25 + 3 x36 + x43 + x57 + 2 x65 + 5 x74 + 5 x76
s.t. x12 + x13
− x12
= 10
+ x24 + x25
− x13
=3
+ x36 − x43
− x24
=0
+ x43
−
− x74
=0
+ x57 − x65
x25
− x36
=0
+ x65
− x57
− x76 = −8
+ x74 + x76 = −5
0 ≤ x12 ≤ 7, 0 ≤ x13 ≤ 8, 0 ≤ x24 ≤ 2, 0 ≤ x25 ≤ 6, 0 ≤ x36 ≤ 10,
0 ≤ x43 ≤ 7, 0 ≤ x57 ≤ 7,0 ≤ x65 ≤ 7, 0 ≤ x74 ≤ 4, 0 ≤ x76 ≤ 5
ネットワーク計画２
7
x = (x12 , x13 , x24 , x25 , x36 , x43 , x57 , x65 , x74 , x76 )T
u = (7,8,2,6,10,7,7,7,4,5)T
c = (1,2,2,5,5,1,1,2,5,5)T ,
b = (10,3,0,0,0,−8,−5)T

1 1


1 1

−1


−1
1 −1


A=
−1
−1
1



−1
1 −1


−1
− 1
1



−
1
1
1


とおくと
min c T x
Ax = b, 0 ≤ x ≤ u
s.t.
ネットワーク計画２
8
（節点枝）接続行列
x12
節点
1
2
3
4
5
6
7
x13
x24
枝
x25
x36
x43
x57
x65
x74
x76
1 1



1 1
−1



−1
1 −1


−1
−1
1




−1
1 −1


−1
− 1
1



−1
1 1

すべての行を足すと０になる
接続行列はフルランクではない
ネットワーク計画２
9
(7,1)
10
１
3
２
0
(2,2)
(7,1)
(8,2)
(U,C)
(U,C)
３
0
(6,5)
５
ー5
(4,5)
４
７
(7,2)
(10,3)
0
(7,1)
(U,C)
(5,5)
６
ー8
(U,C)
補助節点
補助節点を作り，補助枝
供給点から補助節点への枝
補助節点から需要点への枝
を追加．枝の単位コスト：十分大，容量：十分大とする
ネットワーク計画２
10
 x12 
 
 x13 
 x24 
 
 x25 
1
    10 
1 1
 
 x36



1
1
1
1
−
 3
 x

  43   0 

1 −1
−1
  x57   

1
−1
−1
  =  0 

 x65   


1 −1
0
−1
  x74   

1
−1
−1
−1
    − 8

  x76   

1 1
−1
− 1    − 5

 x1a 
 x2 a 
 
 xa 6 
 
行列Aはフルランク
 xa 7 
補助枝のフロー
ネットワーク計画２
11

補助枝は，人為変数に対応
単位コストを十分大きく取る
補助枝以外のコスト＝０（二段階法）
→シンプレックス法で最適解が求まる
→補助枝にフローがあれば実行不能
逆行列の要素が０，±１
接続行列の特徴
疎性＋完全ユニモジュラ性
により，実用上最も有効に解ける
ネットワーク計画２
12
最大流問題
各枝の容量が与えられたとき，ソース（ノード１）からシンク（ノー
ド７）への流量（フロー）の最大値を求める問題
最大流最小カット定理
ソース
8
7
4
6
１
枝の容量
ネットワーク計画２
２
2
3
1
2
３
4
3
４
1
4
3
５
2
2
0 3
６
3
3
７
3
シンク
8
4
最適フロー（最大値：8）
13
最大流問題の場合の定式化
7
１
4
２
4
1
2
３
４
５
3
2
4
７
3
６
4
補助枝：単位コスト＝－１，容量無限大（十分大）
元の枝の単位コストはすべて０として最小費用流問題を解く
需要点，供給点がない：循環流問題
ネットワーク計画２
14
組み合わせ的解法の計算量
節点数 n，枝数 m とする．
最短路問題
ダイクストラ法： O(n 2 ) + O(m ) = O(n 2 )
最大流問題
Dinic (1970)： O(n 2 m )
Goldberg, Tarjan(1986)： O(mn log(n 2

ネットワーク計画２
m
))
15
最小費用流
Tardos (1985)： O(nm 2 log 2 n + n 3m )
Goldberg, Tarjan (1987)： O(nm 2 log n log(n 2
m
))
（強）多項式時間アルゴリズム：
計算時間が，節点数と枝数の多項式
ネットワークシンプレックス法は多項式アルゴリ
ズムではないが，実用上早い
ネットワーク計画２
16

Download Report