最小费用最大流问题

1、2021/3/2712021/3/272 对每一条弧都给出对每一条弧都给出的的容量网络容量网络D=（V,A,B）（称为费用容量网络）中，求取）（称为费用容量网络）中，求取最大流最大流X，使输送流量的，使输送流量的总费用总费用 C（X）=cijxij为最小为最小的一类优化问题。的一类优化问题。 其中，其中，bij表示弧（表示弧（vi，vj）上的容量，）上的容量，xij表表示弧（示弧（vi，vj）上的流量，）上的流量，cij表示弧（表示弧（vi，vj）上通过单位流量所花费的费用。上通过单位流量所花费的费用。2021/3/2732021/3/274从上节可知,寻求最大流的方法是从某个可行流出发,找到

2、关于这个流的一条增广链 。沿着调整f，对新的可行流试图寻求关于它的增广链，如此反复直至最大流。现在，要寻求最小费用的最大流，我们首先考察一下，当沿着一条关于可行流f的增广链 ，以=1调整f，得到新的可行流f（显然v（f）=v（f）+1）时，C（f）比C（f）增加多少(输送流量的总费用 )?2021/3/275 当沿着一条关于可行流当沿着一条关于可行流 X 的增广的增广链（流量修正路线）链（流量修正路线），以修正量，以修正量=1进行调整进行调整，得到新的可行流，得到新的可行流 ，则，则称称C（ ）- C（X）为）为 。xx2021/3/276增广链增广链的费用就是以单位调整量调整的费用就是以单位

3、调整量调整可行流时所付出的费用可行流时所付出的费用;当修正量当修正量=1时时,此时，此时， 的流量的流量 f( ) = f(X)+1；xxijijijijijijijijccxxcxxc)()(xC( )-C( X )=2021/3/277始终保持始终保持网络中的可行流是网络中的可行流是最小费用流最小费用流,然后不断调整然后不断调整,使使，最终成为最小，最终成为最小费用的最大流费用的最大流;始终保持始终保持可行流是可行流是最大流最大流，通过不断调整，通过不断调整使使，最终成为最大流量的最小费，最终成为最大流量的最小费用流。用流。2021/3/278若若X 是流量为是流量为f(X)的最的最小费用

4、流，小费用流，是关于是关于X 的所有增广的所有增广链中费用最小的增广链，那么沿着链中费用最小的增广链，那么沿着去调整去调整X得到的新的可行流得到的新的可行流 就是流量为就是流量为 f ( )的最小费用流。的最小费用流。xx2021/3/279 基于第一种求解途径基于第一种求解途径,根据上述根据上述定理定理,只要只要。循环往复直至求出最小。循环往复直至求出最小费用最大流。费用最大流。2021/3/2710对偶法原理和步骤求最大流Ford算法找从vs到vt的最短增广链调整流量得费用最小的可行流maxf将0流作为初始可行流Yes绘制扩展费用网络No流量等于最大流?得最小费用最大流确保流量最大确保费用

5、最小2021/3/2711 构造构造（即扩展费用网络图）（即扩展费用网络图）,借助借助寻找寻找。 为什么?理由理由: 正向饱和弧不标记,反向零流弧不标记。 不构造增广费用网络,就无法调整流量(1)饱和弧,流量无法减小;(2)非饱和弧,流量只能增加,不能减小;jj2021/3/2712cij 原有弧（流量可以增加）原有弧（流量可以增加） 后加弧（流量不能再减少）后加弧（流量不能再减少） 原有弧（流量不能再增加）原有弧（流量不能再增加） -cij 后加弧（流量可以减少）后加弧（流量可以减少） cij 原有弧（流量可以增加）原有弧（流量可以增加） -cij 后加弧（流量可以减少）后加弧（流量可以减少

6、） 的的将网络中的每一条弧（将网络中的每一条弧（vi, vj）都变成一对方向相反的）都变成一对方向相反的弧弧,以形成以形成,权数定义如下权数定义如下: 2021/3/2713: ,保持原弧不变保持原弧不变,将单位费用作将单位费用作为权数，即为权数，即wij= cij: Vi Vj(,0)ijijb c原网络原网络 Vi Vj(,)ijijb c增广费用网络增广费用网络2021/3/2714,原有弧以单位原有弧以单位费用作权数费用作权数,后加弧（虚线弧）以单位后加弧（虚线弧）以单位费用的负数作权数费用的负数作权数:(0)ijijxbViVj(,)ijijijb cx原网络原网络ViVj(,)ij

7、ijijbx c(,)ijijxc增广费用网络增广费用网络2021/3/2715,去掉原有弧去掉原有弧,添上添上后加弧后加弧(虚线弧虚线弧),权数为单位费用的负权数为单位费用的负数数: ()ijijxb Vi Vj(,)ijijijb c b原网络原网络 Vi Vj( bi j, -cij)增广费用网络增广费用网络2021/3/2716 于是于是,在容量网络中寻找最小费用在容量网络中寻找最小费用增广链就增广链就相当于相当于。2021/3/2717-用用Ford-Fukerson算法求出算法求出该容量网络的最大流量该容量网络的最大流量fmax;2021/3/27182021/3/27192021

8、/3/2720增广费用网络图增广费用网络图(容量费用图容量费用图(bij,cij) 可可 行行 流流 图图 (流量网络流量网络(bij,cij,xij)vsvtv2v3v1(10,7)(7,7)(8,4)(10,4)(4,4)(5,0)(2,0)最大流图最大流图fmax=11 (未标费用未标费用) 第第 0 次次 迭迭 代代2021/3/2721vsvtv2v3v1(10,4)(7,1)(8,1)(10,3)(4,2)(5,2)(2,6)(5,2,5)(7,1,5)vsvtv2v3v1(10,4,0)(8,1,5)(10,3,0)(4,2,0)(2,6,0)第第 1 次次 迭迭 代代原图全部是

9、零流弧原图全部是零流弧, ,保持原保持原边不变边不变, ,单位费用为权单位费用为权; ;所有的权均大于零所有的权均大于零, ,可用可用D D氏标号法求出最短路氏标号法求出最短路: :恰也是恰也是。 tsvvvv12流量调整量流量调整量1 1=min8-0,5-0,7-0=5=min8-0,5-0,7-0=5 总流量总流量f f1 1=5=5最小费用增广链的费用最小费用增广链的费用c cijij=1+2+1=4=1+2+1=4总费用总费用C C1 1=4=45=205=20 2021/3/2722第第 2 次次 迭迭 代代(3,1)v1vt(5,-2)(2,6)v2v3(10,4)(5,-1)(

10、10,3)(4,2)（2,1）vs（ 5 ， - 1）(7,1,7)vsvtv2v3v1(10,4,2)(8,1,5)(10,3,0)(4,2,0)(2,6,0)(5,2,5)零流弧保持原边零流弧保持原边, ,非饱和非非饱和非零流弧零流弧(v(vs s,v,v2 2) )和和(v(v1 1,v,vt t) )增添后增添后加弧加弧, ,饱和弧饱和弧(v(v2 2,v,v1 1) )去掉原弧去掉原弧增添后加弧增添后加弧; ;用列表法求出最短路用列表法求出最短路: :恰也是最小费用增广链恰也是最小费用增广链。 流量调整量流量调整量2 2=min10-0,2-0(7-5)=2,=min10-0,2-0

11、(7-5)=2,总流量总流量= =原流量原流量+ +新增流量新增流量 =5+2=7;=5+2=7;最小费用增广链的费用最小费用增广链的费用 c cijij=4+1=5=4+1=5总费用总费用C C2 2= =原费用原费用+ +新增费用新增费用=20+5=20+52=30 2=30 tsvvv12021/3/2723vsvtv2v3v1(8,4)（2,-4）(5,-1)(7,-1)(10,3)(4,2)(2,6)(5,-2)(3,1)零流弧保持原边零流弧保持原边,此外的非饱此外的非饱和弧增添后加弧和弧增添后加弧,饱和弧去掉原饱和弧去掉原边增添反向虚线弧边增添反向虚线弧用列表法求得最短路用列表法求

12、得最短路恰也是最小费用增广链。恰也是最小费用增广链。流量调整量流量调整量3 3=min3,10,4=3,=min3,10,4=3,总流量总流量= =原流量原流量+ +新增流量新增流量 =7+3=10;=7+3=10;最小费用增广链的费用最小费用增广链的费用 c cijij=1+3+2=6=1+3+2=6总费用总费用C C2 2= =原费用原费用+ +新增费新增费用用=30+6=30+63=48 3=48 tsvvvv32第第 3 次次 迭迭 代代(7,1,7)vsvtv2v3v1(10,4,2)(8,1,8)(10,3,3)(4,2,3)(2,6,0)(5,2,5)2021/3/2724(2,

13、6)(7,3)(8,4)vsvtv2v3v1(3,-3)(7,-1,)(8,-1)(3,-2)（1,2）(2,-4)（5,-2）零流弧保持原边零流弧保持原边, ,此外的非饱和此外的非饱和弧增添后加弧弧增添后加弧, ,饱和弧去掉原边增饱和弧去掉原边增添反向虚线弧添反向虚线弧; ;用列表法求得最短路用列表法求得最短路 对应的最小费用增广链是对应的最小费用增广链是tsvvvvv321tsvvvvv 321流量调整量流量调整量4 4=min8,5,7,1=1,=min8,5,7,1=1,总流量总流量= =原流量原流量+ +新增流量新增流量=10+1=11;=10+1=11;最小费用增广链的费用最小费用

14、增广链的费用 c cijij=4-2+3+2=7=4-2+3+2=7总费用总费用C C2 2= =原费用原费用+ +新增费用新增费用 =48+7=48+71=551=55。由于总流量由于总流量1111已达到最大流量已达到最大流量, ,故停故停止迭代，止迭代，当前的可行流图即最大流图。当前的可行流图即最大流图。第第 4 次次 迭迭 代代(7,1,7)vsvtv2v3v1(10,4,3)(8,1,8)(10,3,4)(4,2,4)(2,6,0)(5,2,4)2021/3/2725举例举例 求最小费用求最小费用-最大流问题最大流问题求下图中网络从 到 的最小费用最大流，图中弧上的数字为 。svtv(

15、,)ijijb cvsv2v3v4v5vt(15,2)(9,6)(7,8)(3,3)(6,3)(5,5)(10,1)(4,9)(11,3)2021/3/2726vsv2v3v4v5vt(15,2)(9,6)(7,8)(3,3)(6,3)(5,5)(10,1)(4,9)(11,3)(0)求网络的最大流量maxfmax20f由前面计算知， 。 将0流作为初始可行流。扩展费用网络与原网络相同(1)第一次迭代:用Ford算法求最短增广链,路线是vsv3v5vt2021/3/2727vsv2v3v4v5vt(15,2,0)(9,6,6)(7,8,0)(3,3,0)(6,3,6)(5,5,0)(10,1,

16、6)(4,9,0)(11,3,0)调整流量:在增广链上有:33353555min,min90,60,1006ssttbxbxbx在初始可行流的基础上调整流量得到新的可行流,刷新网络图max620ff（bij, cij, xij）2021/3/2728(2)第二次迭代扩展费用网络vsv2v3v4v5vt(15,2,0)(3,6)(7,8,0)(3,3,0)(6, 3)(5,5,0)(4,1)(4,9,0)(11,3,0)(6, 6)(6, 1)饱和弧只能减小流量,单位费用减少3（1）流量还可增加3,单位费用6;（2）流量也可减小,当前流量为6，每减单位流量，费用节省6。（1）流量还可增加4,单位

17、费用1;（2）流量也可减小,当前流量为6，每减单位流量，费用节省1。2021/3/2729用Ford算法求最短增广链,路线是vsv2v5vtvsv2v3v4v5vt(15,2,4)(9,6,6)(7,8,0)(3,3,0)(6,3,6)(5,5,0)(10,1,10)(4,9,4)(11,3,0)22252555min,min150,40,1064ssttbxbxbx在原可行流基础上调整流量得到新的可行流,刷新网络图max1020ff2021/3/2730(3)第三次迭代扩展费用网络vsv2v3v4v5vt(11,2)(3,6)(7,8,0)(3,3,0)(6, 3)(5,5,0)(10, 1)(4, 9)(11,3,0)(6, 6)(4, 2)用Ford算法求最短增广链,路线是vsv2v4vt2021/3/2731调整流量:在增广链上有:22242444min,min154,70,11 07ssttbxbxbx在初始可行流的基础上调整流量得到新的可行流,刷新网络图max1720ffvsv2v3v4v5vt(15,2,11)(9,6,6)(7,8,7)(3,3,0)(6,3,6)(5,5,0)(10,1,10)(4,9,4)(11,3,7)2021/3/2732(3)第四次迭代扩展费用网络用Ford算法求最短增广链,路线是vsv