最小费用最大流问题

对每一条弧都给出对每一条弧都给出的的容量网络容量网络D=（V，A，B）（称为费用容量网络）中，）（称为费用容量网络）中，求取求取最大流最大流X，使输送流量的，使输送流量的总费用总费用 C（X）=cijxij为最小为最小的一类优化问题。的一类优化问题。 其中，其中，bij表示弧（表示弧（vi，vj）上的容量，）上的容量，xij表表示弧（示弧（vi，vj）上的流量，）上的流量，cij表示弧（表示弧（vi，vj）上通过单位流量所花费的费用。上通过单位流量所花费的费用。从上节可知，寻求最大流的方法是从某个可行流出发，找到关于这个流的一条增广链 。沿着调整f，对新的可行流试图寻求关于它的增广链，如此反复直至最大流。现在，要寻求最小费用的最大流，我们首先考察一下，当沿着一条关于可行流f的增广链 ，以=1调整f，得到新的可行流f（显然v（f）=v（f）+1）时，C（f）比C（f）增加多少(输送流量的总费用 )？ 当沿着一条关于可行流当沿着一条关于可行流 X 的增广的增广链（流量修正路线）链（流量修正路线），以修正量，以修正量=1进行调整进行调整，得到新的可行流，得到新的可行流 ，则，则称称C（ ）- C（X）为）为 。xx增广链增广链的费用就是以单位调整量调整的费用就是以单位调整量调整可行流时所付出的费用；可行流时所付出的费用；当修正量当修正量=1时，时，此时，此时， 的流量的流量 f( ) = f(X)+1；xxijijijijijijijijccxxcxxc)()(xC( )-C( X )=始终保持始终保持网络中的可行流是网络中的可行流是最小费用流最小费用流，然后不断调整，使然后不断调整，使，最终成为最，最终成为最小费用的最大流；小费用的最大流；始终保持始终保持可行流是可行流是最大流最大流，通过不断调整，通过不断调整使使，最终成为最大流量的最小费，最终成为最大流量的最小费用流。用流。若若X 是流量为是流量为f(X)的最的最小费用流，小费用流，是关于是关于X 的所有增广的所有增广链中费用最小的增广链，那么沿着链中费用最小的增广链，那么沿着去调整去调整X得到的新的可行流得到的新的可行流 就是流量为就是流量为 f ( )的最小费用流。的最小费用流。xx 基于第一种求解途径，根据上述基于第一种求解途径，根据上述定理，只要定理，只要。循环往复直至求出最小。循环往复直至求出最小费用最大流。费用最大流。对偶法原理和步骤求最大流Ford算法找从vs到vt的最短增广链调整流量得费用最小的可行流maxf将0流作为初始可行流Yes绘制扩展费用网络No流量等于最大流?得最小费用最大流确保流量最大确保费用最小 构造构造（即扩展费用网络图），（即扩展费用网络图），借助借助寻找寻找。 为什么?理由理由: 正向饱和弧不标记,反向零流弧不标记。 不构造增广费用网络,就无法调整流量(1)饱和弧,流量无法减小;(2)非饱和弧,流量只能增加,不能减小;jjcij 原有弧（流量可以增加）原有弧（流量可以增加） 后加弧（流量不能再减少）后加弧（流量不能再减少） 原有弧（流量不能再增加）原有弧（流量不能再增加） -cij 后加弧（流量可以减少）后加弧（流量可以减少） cij 原有弧（流量可以增加）原有弧（流量可以增加） -cij 后加弧（流量可以减少）后加弧（流量可以减少） 的的将网络中的每一条弧（将网络中的每一条弧（vi, vj）都变成一对方向相反的）都变成一对方向相反的弧，以形成弧，以形成，权数定义如下：，权数定义如下： ： ，保持原弧不变，将单位费用，保持原弧不变，将单位费用作为权数，即作为权数，即wij= cij: Vi Vj(,0)ijijb c原网络原网络 Vi Vj(,)ijijb c增广费用网络增广费用网络，原有弧以单位，原有弧以单位费用作权数，后加弧（虚线弧）以单位费用作权数，后加弧（虚线弧）以单位费用的负数作权数：费用的负数作权数：(0)ijijxbViVj(,)ijijijb cx原网络原网络ViVj(,)ijijijbx c(,)ijijxc增广费用网络增广费用网络,去掉原有弧去掉原有弧,添上添上后加弧后加弧(虚线弧虚线弧),权数为单位费用的负权数为单位费用的负数：数： ()ijijxb Vi Vj(,)ijijijb c b原网络原网络 Vi Vj(bij, -cij)增广费用网络增广费用网络 于是，在容量网络中寻找最小费用于是，在容量网络中寻找最小费用增广链就增广链就相当于相当于。-用用Ford-Fukerson算法求出算法求出该容量网络的最大流量该容量网络的最大流量fmax；增广费用网络图增广费用网络图(容量费用图容量费用图(bij,cij) 可可 行行 流流 图图 (流量网络流量网络(bij,cij,xij)vsvtv2v3v1(10,7)(7,7)(8,4)(10,4)(4,4)(5,0)(2,0)最大流图最大流图fmax=11 (未标费用未标费用) 第第 0 次次 迭迭 代代vsvtv2v3v1(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 次次 迭迭 代代原图全部是零流弧原图全部是零流弧, ,保持原保持原边不变边不变, ,单位费用为权；单位费用为权；所有的权均大于零，可用所有的权均大于零，可用D D氏标号法求出最短路：氏标号法求出最短路：恰也是恰也是。 tsvvvv12流量调整量流量调整量1 1=min8-0,5-0,7-0=5=min8-0,5-0,7-0=5 总流量总流量f f1 1=5=5最小费用增广链的费用最小费用增广链的费用ccijij=1+2+1=4=1+2+1=4总费用总费用C C1 1=4=45=205=20 第第 2 次次 迭迭 代代(3,1)v1vt(5,-2)(2,6)v2v3(10,4)(5,-1)(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(7-5)=2，总流量总流量= =原流量原流量+ +新增流量新增流量 =5+2=7=5+2=7；最小费用增广链的费用最小费用增广链的费用 ccijij=4+1=5=4+1=5总费用总费用C C2 2= =原费用原费用+ +新增费用新增费用=20+5=20+52=30 2=30 tsvvv1vsvtv2v3v1(8,4)（2,-4）(5,-1)(7,-1)(10,3)(4,2)(2,6)(5,-2)(3,1)零流弧保持原边，此外的非零流弧保持原边，此外的非饱和弧增添后加弧，饱和弧去饱和弧增添后加弧，饱和弧去掉原边增添反向虚线弧掉原边增添反向虚线弧用列表法求得最短路用列表法求得最短路恰也是最小费用增广链。恰也是最小费用增广链。流量调整量流量调整量3 3=min3=min3，10,4=310,4=3，总流量总流量= =原流量原流量+ +新增流量新增流量 =7+3=10=7+3=10；最小费用增广链的费用最小费用增广链的费用 ccijij=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)(2,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；最小费用增广链的费用最小费用增广链的费用 ccijij=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)举例举例 求最小费用求最小费用-最大流问题最大流问题求下图中网络从 到 的最小费用最大流，图中弧上的数字为 。svtv(,)ijijb cvsv2v3v4v5vt(15,2)(9,6)(7,8)(3,3)(6,3)(5,5)(10,1)(4,9)(11,3)vsv2v3v4v5vt(15,2)(9,6)(7,8)(3,3)(6,3)(5,5)(10,1)(4,9)(11,3)(0)求网络的最大流量maxfmax20f由前面计算知， 。 将0流作为初始可行流。扩展费用网络与原网络相同(1)第一次迭代：用Ford算法求最短增广链，路线是vsv3v5vtvsv2v3v4v5vt(15,2,0)(9,6,6)(7,8,0)(3,3,0)(6,3,6)(5,5,0)(10,1,6)(4,9,0)(11,3,0)调整流量：在增广链上有：33353555min,min90,60,1006ssttbxbxbx在初始可行流的基础上调整流量得到新的可行流，刷新网络图max620ff（bij, cij, xij）(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，单位费用1；（2）流量也可减小，当前流量为6，每减单位流量，费用节省1。用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在原可行流基础上调整流量得到新的可行流，刷新网络图max1020ff(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算法求最短增广链，路线是vsv2v4vt调整流量：在增广链上有：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)(3)第四次迭代扩展费用网络用Ford算法求最短增广链，路线是vsv3v4vtvsv2v3v4v5vt(11, 2)(3,6)(7, 8)(3,3,0)(6, 3)(5,5,0)(10, 1)(4, 9)(4,3)(4,2)(6, 6)(7, 3)vsv2v3v4v5vt(15,2,11)(9,6,9)(7,8,7)(3,3,0)(6,3,6)(5,5,3)(10,1,10)(4,9,4)(11,3,10)调整流量：在增广链上有：33343444min,min96,50,11 73ssttbxbxbx在初始可行流的基础上调整流量得到新的可行流，刷新网络图max2020ffOVER!