网络优化-第7章+最小费用流问题.ppt

1,网络优化,NetworkOptimization,清华大学数学科学系谢金星办公室：理科楼2206#（电话：62787812）Email:jxie,清华大学课号：70420133（研）,第7章最小费用流问题(MinimumCostFlowProblem)第1讲,2,许多实际问题都可以转化为最小费用流问题,S,T,最小费用流问题的例子,公路交通网络：车辆路线确定,最短路问题,最小费用流问题,1辆车,多辆车:车流,3,定义7.1在流网络N=(V,A，L,U,D)上增加如下的权函数：C：AR为弧上的权函数，弧（i，j）对应的权C（i，j）记为cij，称为弧（i，j）的单位流量的成本或费用（cost）;此时网络可称为容量-费用网络(一般仍可简称为网络),记为N=(V,A,C，L,U,D).,7.1.1最小费用流问题,di0:供应点(supplynode)或源(source)、起始点或发货点di0:需求点(demandnode)或汇(sink)、终止点或吸收点di0:转运点(transshipmentnode)或平衡点、中间点,可以把L0的网络转化为L=0的网络进行研究(思考？)除非特别说明,假设L=0,网络简记为N=(V,A,C，U,D).,4,定义7.2（容量-费用网络中的流(flow)的定义同前一章）流x的（总）费用定义为,通常又称为转运问题(transshipmentproblem)或容量受限的转运问题(capacitatedtransshipmentproblem).,最小费用流问题就是在网络中寻找总费用最小的可行流.,最小费用流问题,引理7.1最小费用流问题存在可行流的必要条件,经典的最小费用流问题：单源单汇(起点s，终点t)，寻找从s流到t的给定流量(或最大流量、最小流量等)的最小费用流.,线性费用网络,思考：经典问题与一般问题有什么关系？是否等价？,5,例7.1最短路问题,在有向网络中，令所有弧上容量下界为0，容量（上界）为1，并令图中节点s的供需量为1，节点t的供需量为-1，则：从s到t的一条有向路正好对应于网络中的一个可行流x（弧(i，j)位于s-t路上：xij=1；弧(i，j)不在s-t路上：xij=0）.如果再令所有弧上的(单位流量)的费用为“弧长”,则此时的最小费用流问题就是第五章讨论过的最短路问题.在第五章我们正是用这样的方式对最短路问题进行建模的,7.1.2最小费用流模型的特例及扩展,6,例-最大流问题,设s为起点,t为终点,增加弧(t,s),令,7.1.2最小费用流模型的特例及扩展,而令所有其他弧上的费用为0,所有顶点上的供需量(外部流量)全为0.,7,例-运输问题(transportationProblem)又称Hitchcock问题（Hitchcock,1941年）,完全二部图只有源和汇没有中间转运点,7.1.2最小费用流模型的特例及扩展,如果每条弧上还有容量(上下限)的限制,则称为容量受限的运输问题(capacitatedtransportationproblem).,有解的必要条件,可以不失一般性,指派问题(assignmentproblem),8,7.1.2最小费用流模型的特例及扩展,（1）当一定的流量流过一条弧时，该弧上导致的总费用与流量大小成线性正比关系，这样的流网络一般称为线性费用网络.如果当一定的流量流过一条弧时，该弧上导致的总费用不一定与流量大小成线性正比关系，而是流量大小的一个凹（或凸）函数，则这样的网络称为凹（或凸）费用网络，相应的最小费用流问题称为凹（凸）费用网络上的最小费用流问题.,（2）当流量流过一条弧时，流出该弧的流量（即流入该弧终点的流量）与进入该弧的流量（即流出该弧起点的流量）相等.如果当流量流过一条弧时，流出该弧的流量是进入该弧的流量的一个线性函数，即流出该弧的流量是对进入该弧的流量按一定比例进行放大或缩小的结果，则这样的流网络一般称为带增益(或盈亏)的流网络（flowwithgainnetwork）.增益除了可以发生在弧上，类似地可以考虑增益发生在节点上,9,7.1.2最小费用流模型的特例及扩展,最小费用流问题,狭义模型,广义模型,10,单源单汇网络可行流x的流量（或流值）为v=v（x）=ds=-dt如果我们并不给定ds和dt,则网络一般记为N=(s,t,V,A,C,U)容量可行且转运点流量守恒的流称为s-t可行流，有时为了方便也称为可行流.最小费用流问题就是在网络N=(s,t,V,A,C,U)中计算流值为v的最小费用流x或者当不给定流值时,计算流值最大的最小费用流x(此时流x称为最小费用最大流).,7.2消圈算法与最小费用路算法,最小费用最小流?,11,7.2消圈算法与最小费用路算法,定义7.3对网络N=(s,t,V,A,C,U)中给定的s-t可行流x，网络N关于流x的残量网络N(x)=(s,t,V,A(x),C(x),U(x),其中A(x),C(x)，U(x)定义如下：（residualnetwork，或增量网络或辅助网络）,讨论算法复杂度时，假定:弧（i，j）A时，弧（j，i）A；cij=-cjiA（x）=A(允许容量为0的弧仍然保留在网络中就可以了),其中称,uij(x)为弧(i,j)上的残留容量(residualcapacity).,12,定义W的费用为,对于N(x)中的任何一个有向圈W,它一定对应于原网络N中的一个增广圈(增广弧构成的圈)；通过沿W对当前流x进行增广，可以获得流值相等的s-t可行流y.,消圈算法的思想,则当增广的流量为时,只要N中存在费用为负数的增广圈W，即C（W）0，则可以通过沿W对当前流x进行增广，获得流值相等但费用更小的s-t可行流y.,13,设x0为不同于的可行流，但费用低于x的费用，即,7.2.1消圈算法(cycle-cancelingalgorithm),定理7.1可行流x为最小费用流的充要条件是N(x)中不存在负费用增广圈.,令x1=x0-x,则，即令x1为网络N中的循环流.,一个循环流一定可以表示为至多m个非零圈流之和，所以可以将x1表示为r个非零圈流之和（）。设对应的有向圈为Wk，,至少存在一个费用为负的增广圈.矛盾,必要性是显然的.反证法证明充分性：,14,N(x)中找负圈可用最短路算法(如Bellman-Ford算法，O(mn)则该算法的复杂度为O(nm2CU),不是多项式时间算法.,STEP2.沿找到的负圈增广流量,转STEP1.,Step0可借用最大流算法，复杂度为O(n2m),STEP0.在网络N=(s,t,V,A,C,U)中计算流值为v的可行流x.,7.2.1消圈算法:Klein(1967)等,STEP1.在残量网络N(x)中判别负圈.若无负圈,则已经找到了最小费用流，结束；否则转STEP2.,如按一些特定次序消圈,可得到一些多项式时间算法,复杂度？,任何可行流的费用不可能超过mCU设数据是整数,每次消去一个负圈至少使费用下降一个单位设数据是整数,消去负圈的STEP12最多执行O(mCU)次,15,略,7.2.1消圈算法,例：,16,能否首先在网络N=(s,t,V,A,C,U)中计算流值为v且费用最小的s-t可行流(v0,所以=-()=-0,因此(j,i)弧不属于残量网络N(x).所以=0.,当时，即0时，=0；(7.19)当0时，=；(7.23)当0时，=；(7.23)当0时，=；(7.24)当时，=0.(7.25),40,-残量网络,7.4瑕疵算法,当xijuij时,则(j,i)N(x),uji(x)=xij-uij,cji(x)=-cij.,瑕疵算法仍然是在残量网络上对弧上的流量进行操作;由于流不一定满足容量约束,需定义这时残量网络的构造方法:把原网络中可能增加流量的弧(前向弧)、减少流量的弧(反向弧)纳入残量网络.具体方法如下:,瑕疵算法的思想：在算法过程中使弧上的Kilter数不断下降,最后降为0.,当时:如果xijlij,则(j,i)N(x),uji(x)=xij-lij,cji(x)=-cij.,41,-残量网络,7.4瑕疵算法,可以直接定义弧(i,j)N(x)的Kilter数，分三种情况讨论:,可知:原网络中的任何一条瑕疵弧一定会在残量网络中得到反映(即瑕疵弧不以前向弧的形式出现,就以反向弧的形式出现).,当时:如果(i,j)是瑕疵弧(0),则其Kilter数必然等于(i,j)的残留容量:kij=uij(x),当xij0(即0),则kij=xji-lji;如果0(即0),则kij=uij(x)=xji-uji.,42,-步骤,7.4瑕疵算法,STEP0.给出初始势和初始循环流(如=0,x=0).,Yakovleva(1959),Minty(1960),Fulkerson(1961)等提出;Aashtiani和Magnanti(1976)给出一种高效率的实现方法.,STEP1.计算弧上的Kilter数.若网络中不存在瑕疵弧,则已经得到最优解,计算结束；否则在残量网络N(x)中，选择一条瑕疵弧（p,q）,继续下一步.,STEP3.若（p,q）仍为瑕疵弧,则沿P(p,q)确定的增广圈增广流量(增广的流值为该增广圈的容量),转STEP1;否则直接转STEP1.,STEP2.在N(x)(q,p)中,以max0,为（i,j）弧的弧长，计算从节点q到所有节点i的最短路路长d(i)，并记从节点q到节点p的最短路为P.令i=i-d(i),继续STEP3.,主要过程:一是对节点上势的修改;一是沿增广圈增广,43,-正确性,7.4瑕疵算法,证明,引理7.6在瑕疵算法中,对节点上势的修改不会增加任何弧上的Kilter数.,=-+=-(i-d(i)+(j-d(j)=+(d(i)-d(j)-max0,当0:-max0,=0(6.26),当0,所以,=-+=-(i-d(i)+(j-d(j)=+(d(i)-d(j)(6.28),44,-正确性,7.4瑕疵算法,从Kilter数的定义知:当弧上流量保持不变时,只有的符号改变时,弧上的Kilter数才可能改变.下面分别对几种情况讨论:,节点上势的修改不会增加任何弧上的Kilter数.沿增广圈增广呢?,当时:如果(i,j)关于是无瑕弧,则关于也是无瑕弧;如果(i,j)关于是瑕疵弧(uji时:此时在节点上势的修改前后(i,j)一定都是瑕疵弧.与xijlij类似可证,当xijlij时:此时在节点上势的修改前后（i,j）一定都是瑕疵弧.如果0,则0,kij=kij=uij(x)=lij-xij不变.如果0,则:若0,则kij=kij=uij-xij不变;若0,则kij=lij-xijuij-xij,45,-正确性,7.4瑕疵算法,引理7.7在瑕疵算法中,沿增广圈P(p,q)增广流量不会增加任何弧上的Kilter数,且弧(p,q)的Kilter数严格减少,沿增广圈P(p,q)增广流量只可能改变圈上的弧及其反向弧的Kilter数.对于增广圈上容量不可行的弧(i,j),由残量网络的构造方法可知:流量增广后该弧的Kilter数一定严格下降,且不会在残量网络中加入新的弧(j,i).对于增广圈上容量可行的弧,流量增广不改变容量可行弧的容量可行性.,=-+=-(i-d(i)+(j-d(j)=+(d(i)-d(j)0,对于最短路P上的容量可行弧(i,j),由最短路方程有d(j)=d(i)+max0,d(i)+,若弧(i,j)在原网络中对应的弧为(i,j),则流的增广不会增加其Kilter数，且当0时实际上会严格减少其Kilter数.,若弧(i,j)在原网络中对应的弧为(j,i),则由=-0可知,流的增广也不会增加其Kilter数，且当0,则令xij=0(下界);如果0时,称e(i)为节点i的盈余(Excess);e(i)r(,S):同时修改和x,使得LR()严格增加.,7.5松弛算法,由（7.29）：LR()增加e(S)-r(,S),算法首先沿(S,)中满足=0的弧增广流量使之饱和,即流量达到残留容量的上界,相应的弧不再属于残量网络;从(7.29)可知,这样的修改不会改变c(x,)的值,但使得S中的节点上的总盈余减少为e(S)-r(,S)（仍然为正数）.,由于算法保持互补松弛条件,对于N(x)中的任意弧一定有0.增广后前向弧集(S,)中的弧满足0,记其中的最小值为0.,N(x)中的任意弧仍有0：保持互补松弛条件,52,-算法思想,(case2)若e(S)r(,S):不变，修改x,使得e(S)严格减少.,7.5松弛算法,如果e(j)0时，=0；(7.38),设给定了一个基本可行解x,基矩阵所对应的可行树为T.由于只有树弧上的流量可以为正数,所以只有树弧才可能满足(7.38).支撑树上的弧共有(n-1)条,而对偶变量(节点上的势)共有n个.在相差一个常数的意义下,由T中的弧满足=0可以唯一地确定对偶变量.,可以任意选定一个节点（这一节点通常称为“根”（Root）,令它的势为0;然后利用(7.38)计算与它相邻的其它节点上的势,如此重复就可以方便地获得所有节点上的势.,如果此时使得(7.37)也成立,则x就是原问题的最优解.,62,7.6.1算法的一般思路旋转变换,W为一个负费用圈,所以沿W增广流量将会使得总费用下降.为了在W中找出一条弧出基,我们应当令增广的流量等于W-所有弧上当前流量中的最小值,而取到该最小值的弧出基如果W-=,则原问题是无界的,即最小费用可以趋于负无穷,为了找出一条弧出基,我们可以看出T(p,q)一定含有唯一的圈W,我们把弧(p,q)的方向定义为W的方向.W的费用为,若x不最优,则存在一条非树弧(p,q)使得(7.37)不成立,即0，弧(p,q)可以进入基.,63,STEP0.获得一个初始的可行树T及对应的基本可行解x,-步骤,STEP1.计算对偶变量.,7.6.1算法的一般思路,STEP2.判断是否最优解,若是,则停止;否则选定一个进基变量(即选进基弧(p,q).,STEP3.选定一个出基变量(即选出基弧),如果找不到这样的弧,则原问题是无界的,停止;否则进行下一步.,STEP4.设W为T(p,q)所含的圈.沿W的正向增广流量,即修改x及对应的可行树T,回到STEP1.,问题,获得一个初始的可行树T及对应的基本可行解x？,退化与循环？90%以上退化,容量有界情形？,复杂度？一般非为多项式算法，但可以设计多项式算法,64,略,7.6.1算法的一般思路例,65,计算测试表明，网络单纯形法中往往90%以上的旋转是退化的.能否要求每次所操作的可行树“都不相同”？,7.6.2处理退化的方法,定义7.6假定计算节点上的势时所选定的根节点是固定的.对于可行树T中的一条树弧(i,j),如果T中从根到j的路通过节点i，则(i,j)称为远离根节点的弧（DownwardPointingArc）.如果T中的所有流量为0的弧都是远离根节点的弧，则称可行树T为强可行树（StronglyFeasibleSpanningTree）.,例7.8假设弧上的数字表示当前可行流.节点1为根节点.T1=(1,3),(3,2),(3,4)为强可行树,T2=(1,3),(2,3),(3,4)不是强可行树,因为T2中(2,3)不是远离根节点的弧.,66,引理7.9如果网络单纯形算法中生成的所有可行树都是强可行树，则这些树互不相同.,7.6.2处理退化的方法,如果T为生成树，r为根节点，记,证明:如果网络单纯形算法中的旋转变换不是退化的，则相应的可行树对应的可行流费用互不相同，因此这些树也一定互不相同.所以，我们只需要考虑旋转变换退化的情况.,考虑算法过程中连续生成的两棵强可行树T，=T(p,q)(k,l),即(p,q)为进基弧,(k,l)为出基弧,且从T到的旋转是退化的.,67,7.6.2处理退化的方法,记对应的势为,根据势的确定方法,可以得到(留作练习):,旋转变换前后,(p,q)上的流量都是0,由于是强可行树,所以(p,q)弧一定是远离根节点r的弧.(p,q)弧将分解为两棵子树和,并且p,q分别属于和,则r.,因此,T和是两棵不同的强可行树.,所以=+|(n-1)C/2,7.6.3初始的基本可行解,(3)人工网络上的最小费用流问题没有有界的最优解(即最优值趋向负无穷),则原问题也没有有界的最优解(即最优值趋向负无穷).,实用中：自适应策略-先取M为某中等规模大小的正数计算;若最优解中有人工弧上的流量不为0