网络系统的最小费用最大流问题（课堂PPT）

网络中的最小费用最大流问题,二、基本概念与基本定理,三、寻求最大流的标号法,四、最小费用最大流问题,一、引言,1,2020/5/19,2,网络系统的最大流问题,一、引言在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。,2020/5/19,3,网络系统的最大流问题,图8.23是一个网络,vt,v3,v2,v1,v4,vs,17,3,5,10,8,6,11,4,5,3,Cij,每一个弧旁边的权就是对应的容量（即最大通过能力）。要求指定一个运输方案，使得从vs到vt的货运量最大，这是寻求网络系统的最大流问题。,2020/5/19,4,网络系统的最大流问题,二、基本概念与基本定理定义8.5设一个赋权有向图D=（V,A）,在v中指定一个发点（或源点）vs和一个收点（或汇点）vt,其他的点叫做中间点。对于D中的每一个弧（vi,vj）A,都有一个权cij叫做弧的容量。我们把这样的图D叫做一个网络系统，简称网络，记做D=（V，A，C）。网络D上的流，是指定义在弧集合A上的一个函数f=f(vi,vj)=fijf(vi,vj)=fij叫做弧在(vi,vj)上的流量。,2020/5/19,5,网络系统的最大流问题,v3,v2,v1,v4,vs,（2）,（3）,（2）,（5）,（3）,（3）,（6）,（1）,（1）,（2）,fij,图8.24网络上的一个流（运输方案）每一个弧上的流量fij就是运输量例如fs1=5,fs2=3,f13=2等等,vt,2020/5/19,6,网络系统的最大流问题,网络系统上流的特点：(1)发点的总流出量和收点的总流入量必相等；(2)每一个中间点的流入量与流出量的代数和等于零；(3)每一个弧上的流量不能超过它的最大通过能力（即容量）。,2020/5/19,7,网络系统的最大流问题,定义8.6网络上的一个流f叫做可行流，如果f满足以下条件（1）容量限制条件：对每一弧（vi,vj）A,有0fijcij.（2）平衡条件：对于发点vs，有fsj-fjs=v(f)对于收点vt，有ftj-fjt=-v(f)对于中间点，有fij-fji=0式中v(f)叫做这个可行流的流量，即发点的净输出量（或收点的净输入量）,2020/5/19,8,网络系统的最大流问题,任意一个网络上的可行流总是存在的。例如零流v(f)=0,就是满足以上条件的可行流。网络系统中最大流问题就是在给定的网络上寻求一个可行流f,使其流量v(f)达到最大值。设流f=fij是网络D上的一个可行流，我们把D中fij=cij的弧叫做饱和弧，fij0的弧为非零流弧，fij=0的弧叫做零流弧。,2020/5/19,9,网络系统的最大流问题,设是网络D中连接发点s和收点vt的一条链。定义链的方向是从vs到vt，于是链上的弧被分为两类：一是弧的方向与链的方向相同，叫做前向弧，前向弧的集合记做+。二是弧的方向与链的方向相反，叫做后向弧，后向弧的集合记做-。,2020/5/19,10,在下图（图8.23与8.24合并图）中，(v4,v3)是饱和弧，其他的弧是非饱和弧，并且都是非零流弧。,v3,v2,v1,v4,vs,（17,2）,（3,3）,（5,2）,（10,5）,（8,3）,（6,3）,（11,6）,（4,1）,（5,1）,（3,2）,fij,如图，在链（vs,v1,v2,v3,v4,vt)中，+=(vs,v1),(v1,v2),(v2,v3),(v4,vt),-=(v4,v3).,vt,网络系统的最大流问题,11,网络系统的最大流问题,增广链，如果链满足以下条件：1在弧（vi,vj）+上，有0fijcij,即+中的每一条弧是非饱和弧。2在弧（vi,vj）-上，有0fijcij,即-中的每一条弧是非零流弧。例如在图8.24中，链=（vs,v1,v2,v3,v4,vt）就是一条增广链。,2020/5/19,12,网络系统的最大流问题,定义8.8设一个网络D=（V，A，C）。如果点集V被剖分为两个非空集合V1和V1，发点vsV1,收点vtV1,那么将弧集（V1,V1）叫做是分离vs和vt的截集。定义8.9设一个截集（V1,V1），将截集（V1,V1）中所有的弧的容量的和叫做截集的截量，记做c(V1,V1),亦即c(V1,V1)=cij,(vi,vj)(V1,V1),设图D=(V，A，C)，点集S,TV,ST=中，将起点在S，终点在T的所有弧构成的集合，记做（S，T）。,2020/5/19,13,网络系统的最大流问题,下面的事实是显然的：一个网络D中，任何一个可行流f的流量v(f)都小于或等于这个网络中任何一个截集(V1,V1)的截量。并且，如果网络上的一个可行流f*和网络中的一个截集（V1*,V1*），满足条件v*(f*)=c(V1*,V1*),那么f*一定是D上的最大流，而（V1*,V1*）一定是D的所有的截集中截量最小的一个（即最小截集）。,2020/5/19,14,网络系统的最大流问题,定理8.8网络中的一个可行流f*是最大流的充要条件是不存在关于f*的增广链。定理8.9在一个网络D中，最大流的流量等于分离vs和vt的最小截集的截量。定理8.8实际上提供了一个寻求网络系统最大流的方法：如果网络D中有一个可行流f，只要判断网络是否存在关于可行流f的增广链。如果没有增广链，那么f一定是最大流。如有增广链，那么可以按照定理8.9，不断改进和增大可行流f的流量，最终可以得到网络中的一个最大流。,2020/5/19,15,网络系统的最大流问题,三、寻求最大流的标号法从网络中的一个可行流f出发（如果D中没有f，可以令f是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。用给顶点标号的方法来定义V1*.在标号过程中，有标号的顶点是V1*中的点，没有标号的点不是V1*中的点。如果vt有了标号，表示存在一条关于f的增广链。如果标号过程无法进行下去，并且vt未被标号，则表示不存在关于f的增广链。这样，就得到了网络中的一个最大流和最小截集。,2020/5/19,16,网络系统的最大流问题,1标号过程在标号过程中，网络中的点或者是标号点（分为已检查和未检查两种）或者是未标号点。每个标号点的标号包含两部分：第一个标号表示这个标号是从哪一点得到的，以便找出增广链。第二个标号是为了用来确定增广链上的调整量。标号过程开始，先给vs标号（0，+）。这时，vs是标号而未检查的点，其他都是未标号点。一般地，取一个标号未检查点vi，对一切未标号点vj：,2020/5/19,17,网络系统的最大流问题,1)如果在弧（vi,vj）上，fij0,那么给vj标号（-vi,l(vj)）,其中l(vj)=minl(vi),fji.这时，vj成为标号未检查点。(考虑后向弧)于是vi成为标号已检查的点。重复以上步骤，如果所有的标号都已经检查过，而标号过程无法进行下去，则标号法结束。这时的可行流就是最大流。但是，如果vt被标上号，表示得到一条增广链，转入下一步调整过程。,2020/5/19,18,2.调整过程首先按照vt和其他点的第一个标号，利用“反向追踪”的办法，找出增广链。例如，令vt的第一个标号是vk，则弧（vk,vt）在上。再看vk的第一个标号，若是vi，则弧(vi,vk)都在上。依次类推，直到vs为止。这时，所找出的弧就成为网络D的一条增广链。取调整量=l(vt),即vt的第二个标号，,网络系统的最大流问题,2020/5/19,19,fij+，当(vi,vj)+令fij=fij-，当(vi,vj)-fij,当(vi,vj)|再去掉所有的标号，对新的可行流f=fij,重新进行标号过程，直到找到网络D的最大流为止。,网络系统的最大流问题,2020/5/19,20,网络系统的最大流问题,V4,V1,V2,V3,Vs,（2,1）,（3,0）,（4,3）,（3,3）,（5,1）,（2,2）,（5,3）,（1,1）,（1,1）,(Cij,fij),Vt,图8.21,2020/5/19,21,例8.8求图8.21的网络最大流，弧旁的权数表示（cij,fij）。解：用标号法。1.标号过程。（1）首先给vs标号（0，+）（2）检查vs:在弧(vs,v2)上,fs2=cs2=3,不具备标号条件。在弧(vs,v1)上,fs1=10,故给v2标号（-v1,l(v2)）,其中l(v2)=minl(v1),f21=min4,1=1.,网络系统的最大流问题,2020/5/19,22,（4）检查v2:在弧（v2,v4）上，f24=30,故给v3标号（-v2，l(v3),其中l(v3)=minl(v2),f32=min1,1=1。（5）在v3,v4中任意选一个，比如v3,在弧（v3,vt）上，f3t=1c3t=2,故给vt标号(v3,l(vt),其中l(vt)=minl(v3),(c3t-f3t)=min1,1=1.因为vt被标上号，根据标号法，转入调整过程。,网络系统的最大流问题,2020/5/19,23,2.调整过程。从vt开始，按照标号点的第一个标号，用反向追踪的方法，找出一条从vs到vt的增广链=vs,v1,v2,v3,vt，如图8.22中双箭线所示。不难看出,+=(vs,v1),(v3,vt),-=(v2,v1),(v3,v2),取=l(vt)=1，在上调整f，得到在+上，fs1+=1+1=2在+上，f3t+=1+1=2在-上，f21-=1-1=0在-上，f32-=1-1=0其他的fij不变。,网络系统的最大流问题,2020/5/19,24,网络系统的最大流问题,V4,V1,V2,V3,Vs,（2,1）,（3,0）,（4,3）,（3,3）,（5,1）,（2,2）,（5,3）,（1,1）,（1,1）,(Cij,fij),Vt,(v2,1),(0，+),(-v1,1),(vs,4),(-V2,1),图8.22,2020/5/19,25,调整后的可行流f*，如图8.23所示，再对这个可行流重新进行标号过程，寻找增广链：首先给vs标号（0，+），检查vs,给v1标号（vs,3）。检查v1,在弧（v1,v3）上，f13=c13,弧（v2,v1）上，f21=0,均不符合标号过程(1)的条件。因此标号过程无法进行下去，不存在从VS到Vt的增广链，算法结束。这时，网络中的可行流f*即是最大流，最大流的流量V(f*)=fs1+fs2=5.同时，也找出D的最小截集（V1，V1），其中V1是标号的集合，V1是未标号的集合。,网络系统的最大流问题,2020/5/19,26,网络系统的最大流问题,V4,V1,V2,V3,Vs,（2,1）,（3,0）,（4,3）,（3,3）,（5,2）,（2,2）,（5,3）,（1,0）,Vt,(0，+),(vs,3),图8.23,(Cij,fij),（1,0）,2020/5/19,27,四、最小费用最大流问题在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考虑费用的问题。比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。最小费用最大流问题就是要解决这一类问题。,网络系统的最小费用最大流问题,2020/5/19,28,设一个网络D=（V，A，C），对于每一个弧(vi,vj)A,给定一个单位流量的费用bij0，网络系统的最小费用最大流问题，是指要寻求一个最大流f，使流的总费用b(f)=bijfij达到最小。（Vi,Vj）A,网络系统的最小费用最大流问题,2020/5/19,29,在一个网络D中，当沿可行流f的一条增广链，以调整量=1改进f，得到的新可行流f的流量，有v(f)=v(f)+1，而此时总费用b(f)比b(f)增加了b(f)-b(f)=bij(fij-fij)-bij(fij-fij)=bij-bij+-+-将bij-bij叫做这条增广链的费用。+-,网络系统的最小费用最大流问题,2020/5/19,30,网络系统的最小费用最大流问题,如果可行流在流量为v(f)的所有可行流中的费用最小，并且是关于f的所有增广链中的费用最小的增广链，那么沿增广链调整可行流f，得到的新可行流f，也是流量为v(f)的所有可行流中的最小费用流。依次类推，当f是最大流时，就是所要求的最小费用最大流。,2020/5/19,31,显然，零流f=0是流量为0的最小费用流。一般地，寻求最小费用流，总可以从零流f=0开始。下面的问题是：如果已知f是流量为v(f)的最小费用流，那么就要去寻找关于f的最小费用增广链。对此，重新构造一个赋权有向图W(f)，其顶点是原网络D的顶点，而将D中的每一条弧(vi,vj)变成两个相反方向的弧（vi,vj）和(vj,vi)，并且定义W(f)中弧的权wij为：,网络系统的最小费用最大流问题,2020/5/19,32,bij,当fij0wji=+,当fij=0(将权为+的弧从W(f)中略去)即当0fijcij时，成为2条方向相反，权绝对值相等的弧。否则不变。,网络系统的最小费用最大流问题,2020/5/19,33,这样，在网络D中寻找关于f的最小费用增广链就等于价于在W(f)中寻求从vs到vt的最短路。算法如下：算法开始，取零流f(0)=0.一般地，如果在第K-1步得到最小费用流f(K-1),则构造图W（f(K-1)）。在图W（f(K-1)）中，寻求从vs到vt的最短路。如果不存在最短路(即最短路权是+)，则f(K-1)就是最小费用最大流。如果存在最短路，则在原网络D中得到相对应（一一对应）的增广链，在增广链上对f(K-1)进行调整，取调整量=minmin(cij-f(k-1)ij),min(f(k-1)ij).+-,网络系统的最小费用最大流问题,2020/5/19,34,令f(k-1)ij+，当(vi,vj)+f(k)ij=f(k-1)ij-，当(vi,vj)-f(k-1)ij，当(vi,vj)|得到一个新的可行流f(k)，在对f(k)重复以上的步骤，直到D中找不到相对应的增广链时为止。,网络系统的最小费用最大流问题,2020/5/19,35,例8.9求图8-24所示网络中的最小费用最大流，弧旁的权是（bij,cij）.,网络系统的最小费用最大流问题,(bij,Cij),(1,8),vt,v3,v2,vs,v1,(3,10),(2,4),(6,2),(1,7),(4,10),(2,5),2020/5/19,36,解：（1）取初始可行流为零流f(0)=0,构造赋权有向图W(f(0),求出从vs到vt的最短路(vs,v2,v1,vt),如图8.25a中双箭头所示即为最短路。,网络系统的最小费用最大流问题,(1),Vt,V3,V2,Vs,V1,(3),(2),(6),(1),(4),(2),W(f(0),图8.25a,2020/5/19,37,（2）在原网络D中，与这条最短路相对应的增广链为=（vs,v2,v1,vt）。（3）在上对f(0)=0进行调整，取=5，得到新可行流f(1)。类似地，按照以上的算法，依次类推，可以得到f(1)，f(2)，f(3)，f(4)，流量分别为5，7，10，11，并且分别构造相对应的赋权有向图W(f(1),W(f(2),W(f(3),W(f(4)。由于在W(f(4)中已经不存在从vs到vt的最短路，因此，可行流f(4)，v(f(1)=11是最小费用最大流。,网络系统的最小费用最大流问题,2020/5/19,第1次迭代,原图全部是零流弧,保持原边不变,单位费用为权；所有的权均大于零，构造赋权有向图并求出最短路：恰也是最小费用增广链。,流量调整量1=min8-0,5-0,7-0=5总流量f1=5最小费用增广链的费用bij=1+2+1=4总费用C1=45=20,(容量费用图(cij,bij),第2次迭代,零流弧保持原边,非饱和弧和非零流弧(vs,v2)和(v1,vt)增添反向弧,将饱和弧(v2,v1)变成反向弧；继续构造赋权有向图并求出最短路:恰也是最小费用增广链。,流量调整量2=min10-0,7-5=2，总流量=原流量+新增流量=5+2=7；最小费用增广链的费用bij=4+1=5总费用C2=原费用+新增费用=20+52=30,零流弧保持原边，此外的非饱和弧增添反向弧，饱和弧去掉原边增添反向虚线弧，变成反向弧继续构造赋权有向图并求出最短路:恰也是最小费用增广链。,流量调整量3=min8-5,10-0,4-0=3，总流量=原流量+新增流量=7+3=10；最小费用增广链的费用bij=1+3+2=6总费用C3=原费用+新增费用=30+63=48,第3次迭代,零流弧保持原边，此外的非饱和弧增添反向弧，饱和弧去掉原边增添反向虚线弧，变成反向弧；继续构造赋权有向图并求出最短路:对应的最小费用增广链是,流量调整量4=min10-2,5,10-3,4-3=1，总流量=原流量+新增流量=10+1=11；最小费用增广链的费用bij=4-2+3+2=