6 (pp.42--47)

7
最小費用流問題
ある１点（ s ）から他の１点（ t ）へ指定された流量を最小費用で輸送する計画を求める問題．
（一般性を失うことなく）s から t へ q だけ流すと考える．（枝 ts は考える必要がない）
枝 ij においては，単位流量あたり
c の費用がかかる．
l = 0，u = a ．（ 8 (ij ) 2 E ）
b(s) = q ，b(t) = ;q，b(i) = 0（ i 2 V i 6= s t ）
ij
7.1
ij
E）
ij
定式化
min
X
z=
2E
c x
ij
ij
(i j )
(*)
（ 8 (ij ) 2
ij
X
s.t.
j
0
2SUCC(i)
x
ij
x
ij
X
;
j
aij
2PRED(i)
( 8 (ij )
2
x
ji
E)
8 q
>
<
= > 0
: ;q
(i = s)
(i 2 V i =
6 s t)
(i=t)
(*) の制約条件をすべて満たす x = (x ) を流れと呼ぶ．
i = s t における等式制約を流量 q0（ q0 < q ）で満たす x = (x ) を疑似流れと呼ぶ．
x = 0 は疑似流れである．
ij
ij
7.2
例題ネットワーク，残余グラフ
残余枝
負の費用の閉路
7.3
最適性の基準
定理 D
流れ x = (xij ) が最小費用流であるための必要十分条件は，残余グラフ G(x) に負の費用の閉路が存
在しないことである．
42
7.4 クライン法（プライマル法）
step0：（初期化）
（費用を無視して最大流問題を解けばよい）
流れ x を用意する．
step1：（負の経路の検出）
（べき乗法，ウォーシャル・フロイド法による）
残余グラフ G(x) において負の閉路を検出する．
8
>
>
<
d = >
>
:
残余グラフの距離（費用）行列
cij
(ij ) 2 E で
ij
;cj i
0
1
x < a のとき，
E で x > 0 のとき，
（ (ij )：残余枝）
ij
(ji) 2
i = j のとき，
ij
ji
上記以外．
D( ) の対角成分に負の値が現れなければ（負の閉路が存在しないので）終了．
負の閉路を検出したら step2 へ進む．
k
step2：（流れの更新）
step1 で検出した閉路に沿って流せる最大流量
q を求め，現在の流れ x を次のように更新する．
8 x + q
本来枝
(
ij
)
（
(
ij
)
2
E ）が閉路に含まれる，
>
<
x = > x ; q
残余枝 (ji)（ (ij ) 2 E ）が閉路に含まれる，
: x （不変）
上記以外．
step1 へ戻る．
ij
ij
ij
ij
7.5
例題
43
例題で，
1|
2|
4|
5 に 30 単位，
1|
3|
5 に 30 単位流した場合の距離行列（ D(0) ）と最短路長行
列（ D ）および経路情報行列（ P ），
dij
(k )
= min( d(
k
;1)
ij
d( ;1) + d( ;1) )
k
k
ik
kj
D (k) の ij 成分が更新されるとき，Pij の値を k とする．
(k )
0
1
0
1 9 1 1
B
C
B
;3 0
5 7 1C
B
CC
D =B
B
CC
;9 1 0
8
6
B
B
@ 1 ;7 1 0 7 CA
0
BB 12
B
P
=B
BB 3
B@ 4
0
1
0
1 9 1 1
B
C
B
;3 0
5 7 1C
B
CC
D =B
B
CC
;9 1 0
8
6
B
B
@ 1 ;7 1 0 7 CA
0
BB 12
B
P
=B
BB 3
B@ 4
(0)
1
1
;6 ;7
(0)
0
(1)
1
1
;6 ;7
(1)
0
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5 5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
0
1
0
1 9 1 1
B
C
B
;3
0 5 7 1C
B
CC
D =B
B
CC
;9 1 0
8
6
B
B
@ ;10 ;7 ;2 0 7 CA
0
BB 12
B
P
=B
BB 3
B@ 2
0
0 1 9
B
B
;4
0 5
B
B
D =B
;9 1 0
B
B
@ ;11 ;7 ;2
0
BB 13
B
P
=B
BB 3
B@ 3
(2)
1
1
(3)
;15
1
; 6 ;7
0
17
7
8
0
; 6 ;7
15
11
6
4
0
0
0 10 9
B
B
;4
0 5
B
B
D =B
;9
1 0
B
B
@ ;11 ;7 ;2
(4)
対角成分
17
7
8
0
;18 ;14 ;9 ;7
1
CC
CC
CC
CA
15
11
6
4
;3
1
CC
CC
CC
CA
(2)
(3)
(4)
D55
が負になった．
44
1
CC
CC
CC
CA
1
2
3
4
5 5
1
2
3
2
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
3 5
1
2
3
2
5
3
2
3
4
5
3
3
3
3
5
0
BB 13
B
P
=B
BB 3
B@ 3
(4)
1
CC
CC
CC
CA
1
2
3
4
5 5
1
2
4
4
4 4
1
2
3
2
4
3
2
3
4
5
1
CC
CC
CC
CA
1
CC
CC
CC
CA
3
3
3
3
4
1
CC
CC
CC
CA
7.6
逐次最短路法（プライマル・デュアル法）
なにも流れていない状態 xij
= 0，
（ q 0 = 0 に対する擬流 x ）から出発し，残余グラフにおいて，単位
量を最小費用で流せる道（ path ）を探しては，そこにできるだけ多くを流すことを繰り返して，q 0 の
値を大きくしていき，q に達する．
最短路（最小費用路）を探すとき，残余グラフには負の費用の枝があるので，Dijkstra 法は使えない．
残余グラフの枝の費用を次のように（非負の値に）修正して，Dijkstra 法による最短路探索を可能に
したものを，一般に，プライマル・デュアル法と呼んでいる．
8
>
>
>
<
e = >
>
>
:
(***)
c + ;
;c ; + 0
0
ij
ij
i
j
ji
j
i
,
（ LP の simplex 基準）
i
2 Eで
2 Eで
2 Eで
2 Eで
上記以外．
1
「 eij が非負である」
(ij )
(ji)
(ij )
(ji)
x = 0 のとき，
x = a のとき，
0 < x < a のとき，
0 < x < a のとき，
ij
ji
ji
ij
ij
ji
ji
「流量 q 0 に対する疑似流 x が最適解である」
は疑似流 x（流量 q 0 に対する最適解）が流れた状態での sipmlex 乗数（最短距離）であり，
その値は x とともに変化する．
の更新は，距離行列 e （現在のに基づく悪化量）における s から i までの最短距離をするとき， + で行なう．
ij
i
i
i
と
i
逐次最短路法
step0：（初期化）
k := 0； x(0) := 0， (0) := 0， q(0) := 0．
step1：（ e の計算）
( )
( )
現在のを使い，式 (***) に従って e を計算する．
step2：（最短路探索）
( )
(
距離行列 (e ) の上で，Dijksta 法により，s から他の点 i（含 t ）への最短路と最短距離 ij
i
ij
k
k
i
ij
k)
k
ij
i
を
求める．
（各枝ごとの悪化量をもとに，総悪化量の小さい経路を探し出す．
）
step3：（の更新）
( +1) := ( ) + ( ) (i = 1 2 : : : m)
step4：（流れの更新）
step2 で求めた s から t への最短路に沿って流せる最大流量 q(
i
k
i
k
k
i
i
8 x + q
>
<
:= > x ; q
: x （不変）
ように更新する．
(k )
x
(k )
ij
(k +1)
ij
(k )
(k )
ij
(k )
ij
本来枝 (ij )（ (ij ) 2
残余枝 (ji)（ (ij ) 2
上記以外．
k)
を求め，現在の流れ x を次の
E ）が最短路に含まれる，
E ）が最短路に含まれる，
q
:= q + q
q( +1) が q に達したら終了，そうでなければ，k := k + 1 として step1 へ戻る．
(k +1)
(k )
(k )
k
45
step1
( ) ： RG(q( ) ) における，s から i への最短経路長（本来の枝費用 c にもとづく費用）．
step0 から来たとき（ k = 0 のとき）は，何も流していないので，各点へ至る費用は 0 と考える．
step4 から来たとき（ k 1 のとき）は，s から t への，費用 ( ) を実現する path（最短路／最
小費用路）は RG(q ( ) ) において存在しない．
k
k
ij
i
k
t
k
e( ) ： RG(q( ) ) において，枝 ij に 1 単位流した場合の 1 単位あたりの費用増加額（現在の
k
k
ij
最短路長＝最小費用と比べて）．
「 eij 0 」が成立する．（証明）
(k )
step2
( ) ： RG(q( ) e( )) において s から i まで，費用の増加が一番小さくなるように流したと
きの，増加費用（ path 構成枝の費用増加額の和）．すなわち，RG(q ( ) e( ) ) における s から i
k
k
k
i
k
k
までの最短路長（最小増加費用路の増加費用）
e( ) + ( ) ; ( ) 0
k
ij
step3
k
i
k
j
( +1) ： RG(q( ) e( ) ) の上で，s から t への最小増加費用路に，q だけ流すときの，s か
ら各点 i への最短経路長（本来の枝費用 c にもとづく費用）．
k
k
k
i
ij
step4
最短経路（最小費用増加路＝現状況での最小費用路）に
q だけ流すことにより，RG(q(
k
＋ 1)
)
では，その経路は消滅する．
k := k + 1 では，つぎに短い（増加費用の和が小さい）path を見つけてそこに流そうとする．
（ goto step1 ）
46

Download Report