运筹学课件第四节最大流问题

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学教程,第四节 最大流问题,理解最大流问题的概念、最大流-最小割定理。,掌握求最大流问题的标号算法。,引言,在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。,图是联结某个起始地,v,s,和目的地,v,t,的交通运输网，每一条弧,v,i,旁边的权,c,ij,表示这段运输线的最大通过能力，货物从,v,s,运送到,v,t,.,要求指定一个运输方案，使得从,v,s,到,v,t,的货运量最大，这个问题就是寻求网络系统的最大流问题,。,一、最大流有关概念,连通网络,G,(,V,E,)有,m,个节点,n,条弧,弧,e,ij,上的流量上界为,c,ij,求从起始节点,v,s,到终点,v,t,的最大流量。,v,t,v,3,v,2,v,1,v,4,v,s,17,3,5,10,8,6,11,4,5,3,C,ij,定义20,设一个赋权有向图,G,=（,V,E,）,对于,G,中的每一个边（弧）（,v,i,v,j,）,E,都有一个,非负数c,ij,叫做边的,容量,。在,V,中一个入次为零的点称为发点,v,s，,一个出次为零的点称为收点,v,t,其它的点叫做中间点。我们把这样的图,G,叫做一个,容量,网络，,记做,G,=（,V，E,，,C,）。,网络,G,上的流,，是指定义在边(v,i,v,j,)上有流量f,ij,，称集合f=f,ij,为网络G上的一个流，f为可行流。,网络上的一个流,f,叫做可行流，如果,f,满足以下条件：,（1）容量条件：,对于每一个弧,（,v,i,v,j,）,E,有,0,f,ij,c,ij,.,（2）平衡条件：,对于发点,v,s,收点,v,t,有,对于中间点，有,任意一个网络上的可行流总是存在的。例如零流,w,(,f,)=0,就是满足以上条件的可行流。,网络系统中最大流问题就是在给定的网络上寻求一个可行流,f,其流量,w,(,f,)达到最大值。,设流,f,=,f,ij,是网络,G,上的一个可行流。我们把,G,中,f,ij,=,c,ij,的弧叫做饱和弧，,f,ij,0,的弧为非零流弧，,f,ij,=0,的弧叫做零流弧.,最大流问题实际是个线性规划问题。,其中发点的总流量（或收点的总流量）,w,叫做这个可行流的总流量。,v,3,v,2,v,1,v,4,v,s,（2）,（3）,（2）,（5）,（3）,（3）,（6）,（1）,（1）,（2）,f,ij,v,t,网络上的一个流（运输方案），每一个弧上的流量,fij,就是运输量。例如,f,s1,=5,f,s2,=3,f,13,=2 等等。,定义21,设一个网络,G,=（,V，E，C,）,，,v,s、,v,t,为发,和,收点，边集,为E的子集，将G分成2个子图G,1,G,2,;其顶点集合分别为:,发点,v,s,S,收点,v,t,/S,满足,1.,G,=（,V，E-,）不连通；,2.为 的真子集，而,G,=（,V，E-,）连通；,那么 为G的割集，记为 =(S,)。,割集(S,)所有始点在S，终点在 的容量之和，称为(S,)的割集容量，记为C(S,)。,v,t,v,s,v,1,v,2,v,3,v,4,4,2,4,4,3,3,2,2,2,3,1,边集(v,s,v,1,),(v,s,v,3,),(v,s,v,4,),边集(v,s,v,1,),(v,1,v,3,),(v,2,v,3,),(v,3,v,t,),为图的割集，割集容量分别为11，9,二、最大流-最小割定理,定理10：,设f为网络,G,=（,V，E，C,）的任一个可行流，流量为W,(S,)是分离,v,s,v,t,的任一个割集，则有W,C(S,).,定理11：,最大流-最小割定理:,任一个,网络,G,=（,V，E，C,）,从,v,s,到,v,t,的,最大流的流量等于,分离,v,s,v,t,的最小割的容量。,定义22：,设,是网络,G,中连接发点,s,和收点,v,t,的一条链。定义链的方向是从,s,到,v,t,，于是链,上的边被分为两类：一类是边的方向与链的方向相同，叫做前向边，前向边的集合记做,+,。,二类是边的方向与链的方向相反，叫做后向边，,后向,边,的集合记做,。,如果链,满足以下条件：,1在边,（,v,i,v,j,）,+,上，有,0,f,ij,c,ij,。,2在边,（,v,i,v,j,）,上，有,0,f,ij,c,ij,。,则称,为,从,s,到,v,t,可增广链。,在链,（,v,s,v,1,v,2,v,3,v,4,v,t,),中，,+,=(,v,s,v,1,),(,v,1,v,2,),(,v,2,v,3,),(,v,4,v,t,),=(,v,4,v,3,).,v,t,v,s,v,1,v,2,v,3,v,4,4,2,4,4,3,3,2,2,2,3,1,定理11,提供了一个寻求网络系统最大流的方法。如果网络,G,中有一个可行流,f,，只要判断网络是否存在关于可行流,f,的增广链。如果没有增广链，那么,f,一定是最大流。如有增广链，那么可以按照定理中必要性，不断改进和增大可行流,f,的流量，最终可以得到网络G中的一个最大流。,推论：,网络中的一个可行流,f*,是最大流的充分必要条件是，不存在关于,f,*,的增广链。,在一个网络,G,中，最大流的流量等于分离,v,s,和,v,t,的最小割集的割量。,三、标号法,从网络中的一个可行流,f,出发（如果,G,中没有,f,，可以令,f,是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。,如果,v,t,有了标号，表示存在一条关于,f,的增广链。如果标号过程无法进行下去，并且,v,t,未被标号，则表示不存在关于,f,的增广链。这样，就得到了网络中的一个最大流和最小割集。,1 标号过程,在标号过程中，网络中的每个标号点的标号包含两部分：第一个标号表示这个标号是从那一点得到的，以便找出增广链；第二个标号是为了用来确定增广链上的调整量,。,标号过程开始，先给,v,s,标号,（,，+），,一般地，取一个标号顶点,v,i,，对,v,i,所有,未标号的邻接点,v,j,按照下面条件进行处理：,（1）如果在弧（,v,i,v,j,）上，,f,ij,0,那么给,v,j,标号,（-,v,i,(,vj,),）,.其中,(vj),=min,f,ji,(,vi,),。,重复以上步骤，如果收点Vt被标号或不再有顶点可标号为止，则标号法结束。这时的可行流就是最大流。,2.调整过程,令,但是，如果,v,t,被标上号，表示得到一条增广链,，转入下一步调整过程。,3.再去掉所有的标号，对新的可行流,f,=,f,ij,重新进行标号过程，直到找到网络,G,的最大流为止。,v,s,v,2,v,5,v,t,v,4,v,1,v,6,v,3,(5,5),(3,2),(3,3),(4,2),(5,4),(3,3),(2,2),(5,2),(4,2),(2,2),例,求图的网络最大流，弧旁的权,数表示（,c,ij,f,ij,）,。,v,s,v,2,v,5,v,t,v,4,v,1,v,6,v,3,(5,5),(3,2),(3,3),(4,2),(5,4),(3,3),(2,2),(5,2),(4,2),(2,2),解：,用标号法。,1.标号过程。,（1）,首先给,v,s,标号（，+）,（2）,检查,v,s,邻接点v,1,v,2,v,3,:,v,2,点,满足（,v,s,v,2,)E,且,f,s2,=2,c,s2,=4,v2,=min2,+=2,给,v,2,以标号(+,v,s,2);,v,3,点,满足（,v,s,v,3,)E,且,f,s3,=2,c,s3,=3,v3,=min1,+=1,给,v,3,以标号(+,v,s,1);,(,，+,),(+,v,s,2),(+,v,s,1),（3）,检查,v,2,邻接点v,5,v,6,:,v,5,点,满足（,v,2,v,5,)E,且,f,25,=0,c,15,=0,v1,=min3,2=2,给,v,1,以标号(-,v,5,2);,v,s,v,2,v,5,v,t,v,4,v,1,v,6,v,3,(5,5),(3,2),(3,3),(4,2),(5,4),(3,3),(2,2),(5,2),(4,2),(2,2),(,，+,),(+,v,s,2),(+,v,s,1),(+,v,2,2),(-,v,5,2),（5）,检查,v,1,邻接点v,4,:,v4点,满足（,v,1,v4)E,且,f,14,=2,c,14,=5,v4,=min3,2=2,给,v,4,以标号(+,v,1,2);,v,s,v,2,v,5,v,t,v,4,v,1,v,6,v,3,(5,5),(3,2),(3,3),(4,2),(5,4),(3,3),(2,2),(5,2),(4,2),(2,2),(,，+,),(+,v,s,2),(+,v,s,1),(+,v,2,2),(-,v,5,2),(+,v,1,2),（6）,检查,v,4,邻接点v,t,:,vt点,满足（,v,4,vt)E,且,f,4t,=2,c,4t,=4,vt,=min2,2=2,给,v,t,以标号(+,v,4,2);,V,t,得到标号，说明已经得到一条可增广链，标号过程结束。,v,s,v,2,v,5,v,t,v,4,v,1,v,6,v,3,(5,5),(3,2),(3,3),(4,2),(5,4),(3,3),(2,2),(5,2),(4,2),(2,2),(,，+,),(+,v,s,2),(+,v,s,1),(+,v,2,2),(-,v,5,2),(+,v,1,2),(+,v,4,2),开始调整,v,s,v,2,v,5,v,t,v,4,v,1,v,6,v,3,(5,5),(3,2),(3,3),(4,2),(5,4),(3,3),(2,2),(5,2),(4,2),(2,2),(,，+,),(+,v,s,2),(+,v,s,1),(+,v,2,2),(-,v,5,2),(+,v,1,2),(+,v,4,2),2.调整过程,从,v,t,开始，按照标号点的第一个标号，用反向追踪的方法，找出一条从,v,s,到,v,t,的增广链,，如图G中虚线所示。不难看出,+,=(,v,s,v,2,),(,v,1,v,4,),(,v,4,v,t,),=(,v,5,v,1,),取,=,vt,=,2,，,在,上调整,f,，得到,f,*,=,f,4t,+,vt,=2+2=4,在,+,上,f,14,+,vt,=2+2=4,在,+,上,f,25,+,vt,=0+2=2,在,+,上,f,s2,+,vt,=2+2=4,在,+,上,f,15,vt,=3,2=1,在,-,上,其它的不变,vs,v2,v5,vt,v4,v1,v6,v3,(5,5),(3,2),(3,1,),(4,4,),(5,4),(3,3),(2,2),(5,4,),(4,4,),(2,2),（,，+）,（,+vs,，1）,(3,2,),重新开始标号，寻找可增广链，当标到V,3,，与,V,S,V,3,相连的V,1,V,2,V,6,不满足标号条件，标号无法进行，v,t,得不到标号。,流量：w=,f,s1,+,f,s2,+,f,s3,=,f,4t,+,f,5t,+,f,6t,=11,得到一个最小割，标点号集合：S=v,s,v,3,非标点号集合：/S=v,1,v,2,，v,4,v,5,，v,6,v,t,此时割集（s,/s）=(v,s,v,1,),(v,s,v,2,),(v,3,v,6,),割集容量C(s,/s)=C,s1,+C,s2,+C,36,=5+4+2=11,v,s,v,2,v,5,v,t,v,4,v,1,v,6,v,3,(5,5),(3,2),(3,3),(4,2),(5,4),(3,3),(2,2),(5,2),(4,2),(2,2),(,，+,),(+,v,s,2),(+,v,s,1),(