5-5最小费用最大流问题

5-5最小费用最大流问题一、基本概念1、什么是最小费用最大流问题？对每一条弧都给出单位流量费用的容量网络D=（V，A，B）（称为费用容量网络）中，求取最大流X，使输送流量的总费用C（X）=∑cijxij为最小的一类优化问题。其中，bij表示弧（vi，vj）上的容量，xij表示弧（vi，vj）上的流量，cij表示弧（vi，vj）上通过单位流量所花费的费用。2、最小费用流对一费用容量网络，具有相同流量f的可行流中，总费用最小的可行流称为该费用容量网络关于流量f的最小费用流，简称流量为f的最小费用流。3、增广链的费用当沿着一条关于可行流X的增广链（流量修正路线）μ，以修正量ε=1进行调整，得到新的可行流，则称C（）-C（X）为增广链μ的费用。x~x~②增广链μ的费用就是以单位调整量调整可行流时所付出的费用；③当修正量ε=1时，此时，①的流量f()=f(X)+1；x~x~ijijijijijijijijccxxcxxc)~()~(x~C()-C(X)=二、求解最小费用最大流问题的对偶法1、求解途径：（1）始终保持网络中的可行流是最小费用流，然后不断调整，使流量逐步增大，最终成为最小费用的最大流；（2）始终保持可行流是最大流，通过不断调整使费用逐步减小，最终成为最大流量的最小费用流。2、算法原理（1）定理若X是流量为f(X)的最小费用流，μ是关于X的所有增广链中费用最小的增广链，那么沿着μ去调整X得到的新的可行流就是流量为f()的最小费用流。x~x~（2）实现思路基于第一种求解途径，根据上述定理，只要找到最小费用增广链，在该链上调整流量，得到增加流量后的最小费用流。循环往复直至求出最小费用最大流。对偶法原理和步骤求最大流Ford算法找从vs到vt的最短增广链调整流量得费用最小的可行流maxf将0流作为初始可行流Yes绘制扩展费用网络No流量等于最大流?得最小费用最大流确保流量最大确保费用最小实施中的关键构造增广费用网络图（即扩展费用网络图），借助最短路算法寻找最小费用增广链。为什么?理由:正向饱和弧不标记,反向零流弧不标记。—不构造增广费用网络,就无法调整流量(1)饱和弧,流量无法减小;(2)非饱和弧,流量只能增加,不能减小;增广链流量调整：正向弧增加流量，反向弧减少流量。jj零流弧上Wij=cij原有弧（流量可以增加）∞后加弧（流量不能再减少）饱和弧上wij=∞原有弧（流量不能再增加）-cij后加弧（流量可以减少）非饱和且非零流(0xijbij)弧上cij原有弧（流量可以增加）-cij后加弧（流量可以减少）Wij=增广费用网络图的构造方法将网络中的每一条弧（vi,vj）都变成一对方向相反的弧，以形成四通八达的“路”，权数定义如下：将上述思想加以简化，出现∞处相应的弧不画，按下面的方法具体构造增广费用网络图：零流弧上，保持原弧不变，将单位费用作为权数，即wij=cij:ViVj(,,0)ijijbc原网络ViVj(,)ijijbc增广费用网络非饱和弧上，原有弧以单位费用作权数，后加弧（虚线弧）以单位费用的负数作权数（p167更正）：(0)ijijxb(,,)ijijijbcx原网络(,)ijijijbxc(,)ijijxc增广费用网络饱和弧上,去掉原有弧,添上后加弧(虚线弧),权数为单位费用的负数：()ijijxbViVj(,,)ijijijbcb原网络ViVj(bij,-cij)增广费用网络于是，在容量网络中寻找最小费用增广链就相当于在增广费用网络图（扩展费用网络图）中寻找从发点到收点的最短路。注意将找到的最短路还原到原网络图中（虚线弧改成原图中的反向弧）。3、步骤：第一步---用Ford-Fukerson算法求出该容量网络的最大流量fmax；（本步骤的作用是什么？）第二步---取初始可行流为零流，其必为流量为0的最小费用流（为什么？）第三步---一般为第k-1次迭代，得一最小费用流X(k-1)，对当前可行流构造增广费用网络图W(X(k-1))，用最短路算法求出从发点到收点的最短路。若不存在最短路，则X(k-1)即最小费用最大流，停止迭代；否则，转下一步。第四步---将最短路还原成原网络图中的最小费用增广链μ，在μ上对可行流X(k-1)进行调整，得到新的可行流图，若其流量等于fmax,迭代结束。否则转入第一步，进入下一次迭代过程。4、举例增广费用网络图(容量费用图(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氏标号法求出最短路：恰也是最小费用增广链。tsvvvv12①流量调整量ε1=min{8-0,5-0,7-0}=5总流量f1=5②最小费用增广链的费用∑cij=1+2+1=4③总费用C1=4×5=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)①零流弧保持原边,非饱和非零流弧(vs,v2)和(v1,vt)增添后加弧,饱和弧(v2,v1)去掉原弧增添后加弧；②用列表法求出最短路:恰也是最小费用增广链。①流量调整量ε2=min{10-0,2-0}=2，总流量=原流量+新增流量=5+2=7；②最小费用增广链的费用∑cij=4+1=5③总费用C2=原费用+新增费用=20+5×2=30tsvvv1vsvtv2v3v1(8,4)（2,-4）(5,-1)(7,-1)(10,3)(4,2)(2,6)(5,-2)(3,1)①零流弧保持原边，此外的非饱和弧增添后加弧，饱和弧去掉原边增添反向虚线弧②用列表法求得最短路恰也是最小费用增广链。①流量调整量ε3=min{3，10,4}=3，总流量=原流量+新增流量=7+3=10；②最小费用增广链的费用∑cij=1+3+2=6③总费用C2=原费用+新增费用=30+6×3=48tsvvvv32第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）①零流弧保持原边，此外的非饱和弧增添后加弧，饱和弧去掉原边增添反向虚线弧；②用列表法求得最短路③对应的最小费用增广链是tsvvvvv321tsvvvvv321①流量调整量ε4=min{8,5,7,1}=1，总流量=原流量+新增流量=10+1=11；②最小费用增广链的费用∑cij=4-2+3+2=7③总费用C2=原费用+新增费用=48+7×1=55。由于总流量11已达到最大流量，故停止迭代，当前的可行流图即最大流图。第4次迭代(7,1,7)vsvtv2v3v1(10,4,3)(8,1,8)(10,3,4)(4,2,4)(2,6,0)(5,2,4)第十三次作业P179：13）；举例—求最小费用-最大流问题求下图中网络从到的最小费用最大流，图中弧上的数字为。svtv(,)ijijbcvsv2v3v4v5vt(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算法求最短增广链，路线是vs—v3—v5—vtvsv2v3v4v5vt(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{,,}min{90,60,100}6ssttbxbxbx在初始可行流的基础上调整流量④得到新的可行流，刷新网络图max620ff(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算法求最短增广链，路线是vs—v2—v5—vtvsv2v3v4v5vt(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{,,}min{150,40,106}4ssttbxbxbx在原可行流基础上调整流量④得到新的可行流，刷新网络图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算法求最短增广链，路线是vs—v2—v4—vt③调整流量：在增广链上有：22242444min{,,}min{154,70,110}7ssttbxbxbx在初始可行流的基础上调整流量④得到新的可行流，刷新网络图max1720ffvsv2v3v4v5vt(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算法求最短增广链，路线是vs—v3—v4—vtvsv2v3v4v5vt(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{,,}min{96,50,117}3ssttbxbxbx在初始可行流的基础上调整流量④得到新的可行流，刷新网络图max2020ff