文档介绍：第五节最小费用最大流问题
网络D=(V,A,C),每一弧(vi,vj)∈A,给出(vi,vj)上单位流的费用b(vi,vj)≥0,(简记bij)。
最小费用最大流问题:
求一个最大流 f,使流的总费用
取最小值。
一、求解原理
设对可行流 f 存在增广链µ,当沿µ 以=1调整f,得新的可行流 f ' 时,(显然 V(f ')=V(f )+1),两流的费用之差
b( f )-b( f′)
称为增广链µ 的费用。
最小费用最大流的原理的主要依据:
若f 是流值为V(f )的所有可行流中费用最小者,
而µ 是关于f 的所有增广链中费用最小的增广链,则沿
µ 以去调整 f ,得可行流 f ,f 就是流量为V(f )+
的所有可行流中费用最小的可行流。这样,当 f 是
最大流时, f 就是所求的最小费用最大流。
b( f ′) -b( f )
+1
-1
构造赋权有向图W( f ),它的顶点是D的顶点,W(f )中弧及其权wij 按弧(vi,vj)在D中的情形分为:
则(vi,vj)∈W(f ),且wij= bij
则( vj , vi )∈W(f ),且wji= - bij
vj
vi
4
vj
4
vi
vj
vi
3
vi
vj
-3
如果已知 f 是流量为V(f )的最小费用流, 求出关于f 的最小费用增广链。
若(vi,vj)∈A,且fij=0(零弧),
若(vi,vj )∈A,且fij=cij(饱和弧),
费用
若(vi,vj)∈A,且0<fij<cij
vj
4
vi
则(vi,vj)∈W(f ),且wij= bij
及( vj , vi )∈W(f ),且wji= - bij
vj
vi
4
vi
vj
-4
新网络W(f )成为流f 的(费用)增量网络。
由增广链费用的概念及网络W(f )的定义,知
在网络D中寻求关于可行流f 的最小费用增广链,等价于在网络W(f )中寻求从vs到vt的最短路。
二、最小费用最大流算法
算法步骤:
第一步:确定初始可行流f 0 =0,令k=0;
第二步:记经 k 次调整得到的最小费用流为f k,构造
增量网络W(f k);
在W(f k)中,寻找vs到vt的最短路。若不存
在最短路(即最短路路长是∞),则f k 就是
最小费用最大流,若存在最短路,则此最短
路即为原网络D中相应的可增广链µ,转入第
3步。
第三步:在增广链µ上对f k 按下式进行调整,调整量为
k = min
令
得新的可行流f k+1 , 返回第2步。
第四步:停止运算,并输出当前最小费用可行流fk+1 ,作为G的最小费用最大流。
vs
v2
v3
4
v1
vt
6
2
1
1
3
2
(a) w(f0)
例1 求下图所示网络的最小费用最大流。弧旁数字为
(bij,cij)。
v2
v3
(4,10)
v1
vs
vt
(6,2)
(2,5)
(1,8)
(1,7)
(3,10)
(2,4)
解:(1)取初始
可行流f 0 = 0;
(2)按算法要求构造
长度网络W(f 0 ),
求出从vs到vt的最短路。
(3)在原网络D中,与这条最短路对应的增广链为
µ =(vs,v2,v1,vt)。
(3)在原网络D中,
与这条最短路对应
的增广链为:
(4)在µ上进行调整,
= 5,得f 1 ,
如图(b)所示。
v2
v3
(10,0)
v1
vs
vt
(2,0)
(5,0)
(8,0)
(7,0)
(10,0)
(4,0)
µ =(vs,v2,v1,vt)
v2
v3
(10,0)
v1
vs
vt
(2,0)
(5,5)
(8,5)
(7,5)
(10,0)
(4,0)
(b) f 1
按照上述算法依次得f 1 ,f 2 ,f 3 ,f 4 ,流量依次为V(f 1)=5,V(f 2)=7,V(f 3)=10,V( f 4)=11, 构造相应的增量网络为W(f 1),W(f 2),W(f 3),W( f 4), 如图(a), (e), (g), (i)所示。
vs
v2
v3
4
v1
vt
6
2
1
1
3
2
(a) w(f0)
v2
v3
(10,0)
v1
vs
vt
(2,0)
(5,5)
(8,5)
(7,5)
(10,0)
(4,0)
(b) f 1
V(f 1 ) =
5
v2
v3
(10,0)
v1
vs
vt
(2,0)