运筹学 最大流问题.pptx

《运筹学 最大流问题.pptx》由会员分享，可在线阅读，更多相关《运筹学 最大流问题.pptx（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、 引言 在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。第1页/共28页 图图是是联联结结某某个个起起始始地地v vs s和和目目的的地地v vt t的的交交通通运运输输网网，每每一一条条弧弧v vi i 旁旁边边的的权权c cij ij表表示示这这段段运运输输线线的的最最大大通通过过能能力力，货货物物从从v vs s运运送送到到v vt t.要要求求指指定定一一个个运运输输方方案案，使使得得从从v vs s到到v vt t的的货货运

2、运量量最最大大，这这个个问问题题就就是是寻寻求求网网络络系系统统的的最最大大流流问题问题。一、最大流有关概念连通网络连通网络 GG(V,V,E E)有有 m m 个节点个节点,n n条弧条弧,弧弧 e eij ij 上上的流量上界为的流量上界为 c cij ij,求从起始节点求从起始节点 v vs s 到终点到终点 v vt t 的最大的最大流量。流量。vtv3v2v1v4vs1735108611453Cij第2页/共28页 定定义义20202020 设设一一个个赋赋权权有有向向图图GG=（V,EV,E）,对对于于GG中中的的每每一一个个边边（弧弧）（v vi i,v,vj j）E E,都都有

3、有一一个个非非负负数数c c c cijijijij叫叫做做边边的的容容量量。在在V V 中中一一个个入入次次为为零零的的点点称称为为发发点点v vs s，一一个个出出次次为为零零的的点点称称为为收收点点v vt t,其其它它的的点点叫叫做做中中间间点点。我我们们把把这这样样的的图图GG叫叫做做一一个个容容量量网网络络，记记做做GG=（V V，E E，C C）。）。网网络络GG上上的的流流，是是指指定定义义在在边边(v(v(v(vi i ,v,v,v,vj j)上上有有流流量量f f f fij ij，称集合，称集合f=ff=ff=ff=fij ij 为网络为网络G G G G上的一个流，上的

4、一个流，f f f f为可行流。为可行流。第3页/共28页网络上的一个流网络上的一个流f f 叫做可行流，如果叫做可行流，如果f f 满足以下条件：满足以下条件：（1 1 1 1）容容量量条条件件：对对于于每每一一个个弧弧（v vi i ,v,vj j）E E,有有 0 0 f fij ij c cij ij .（2 2 2 2）平衡条件：）平衡条件：对于发点vs,收点vt有对于中间点，有第4页/共28页 任意一个网络上的可行流总是存在的。例如零任意一个网络上的可行流总是存在的。例如零流流ww(f f)=0)=0,就是满足以上条件的可行流。就是满足以上条件的可行流。网络系统中最大流问题就是在给

5、定的网络上寻网络系统中最大流问题就是在给定的网络上寻求一个可行流求一个可行流f f f f,其流量其流量w w w w(f f f f)达到最大值。达到最大值。设流设流f f=f fij ij 是网络是网络GG上的一个可行流。我们把上的一个可行流。我们把GG中中f fij ij=c cij ij的弧叫做饱和弧，的弧叫做饱和弧，f fij ij 00的弧为非零流弧，的弧为非零流弧，f fij ij=0=0的弧叫做零流弧的弧叫做零流弧 .最大流问题实际是个线性规划问题。最大流问题实际是个线性规划问题。其中发点的总流量（或收点的总流量）其中发点的总流量（或收点的总流量）ww 叫做这个可行流的总流量。

6、叫做这个可行流的总流量。第5页/共28页v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fijvt网络上的一个流（运输方案），每一个弧上的流量网络上的一个流（运输方案），每一个弧上的流量fijfij就是运输量。例如就是运输量。例如f fs1s1=5,=5,f fs2s2=3,=3,f f1313=2=2 等等。等等。第6页/共28页定义定义21212121 设一个网络设一个网络GG=（V V，E E，C C），v vs s、v vt t为发为发和和收点，边集收点，边集 为为E E的的子子集集，将将GG分分成成2 2个个子子图图GG1 1,G,G2 2;其其顶顶点

7、点集集合合分分别别为为:,发点发点v vs sS,S,收点收点v vt t /S/S ,满足满足1.1.1.1.GG=（V V，E-E-）不连通；）不连通；2.2.为为 的真子集，而的真子集，而GG=（V V，E-E-）连通；）连通；那么那么 为为G G G G的割集，记为的割集，记为 =(S,)=(S,)=(S,)=(S,)。割割集集 (S,(S,(S,(S,)所所有有始始点点在在S S S S，终终点点在在 的的容容量量之之和和，称称为为(S,(S,(S,(S,)的的割割集集容容量量，记记为为C(S,C(S,C(S,C(S,)。第7页/共28页vtvsv1v2v3v442443322231

8、边集(vs,v1),(vs,v3),(vs,v4)边集(vs,v1),(v1,v3),(v2,v3),(v3,vt)为图的割集，割集容量分别为11，9第8页/共28页二、最大流二、最大流-最小割定理最小割定理定理定理1010：设设f f为网络为网络GG=（V V，E E，C C）的任一个可行流，流量为）的任一个可行流，流量为W,W,(S,)(S,)(S,)(S,)是分离是分离v vs s v vt t的任一个割集，则有的任一个割集，则有W W C(S,).C(S,).C(S,).C(S,).定理定理1111：最大流最大流-最小割定理最小割定理:任一个任一个网络网络GG=（V V，E E，C C

9、）,从从v vs s到到v vt t的的最大流的最大流的流量等于流量等于分离分离v vs s v vt t的最小割的容量。的最小割的容量。定定义义22222222：设设 是是网网络络GG中中连连接接发发点点 s s和和收收点点v vt t的的一一条条链链。定定义义链链的的方方向向是是从从 s s到到 v vt t ，于于是是链链 上上的的边边被被分分为为两两类类：一一类类是是边边的的方方向向与与链链的的方方向向相相同同，叫叫做做前前向向边边，前前向向边边的的集集合合记记做做+。二二类类是是边边的的方方向向与与链链的的方方向向相相反反，叫叫做做后后向向边边，后向边边的集合记做。第9页/共28页

10、如果链如果链 满足以下条件：满足以下条件：1 1 1 1在边在边（v vi i,v,vj j）+上，有上，有0 0 f fij ij c cij ij。2 2 2 2在边在边（v vi i,v,vj j）上，有上，有00f fij ij c cij ij,。则称则称 为为从从 s s到到 v vt t可增广链。可增广链。在链在链（v vs s,v,v1 1,v,v2 2,v,v3 3,v,v4 4,v,vt t)中，中，+=(=(v vs s,v,v1 1),(v v1 1,v,v2 2),(),(v v2 2,v,v3 3),(),(v v4 4,v,vt t),),=(=(v v4 4 ,

11、v,v3 3).).vtvsv1v2v3v442443322231第10页/共28页定理定理11111111提供了一个寻求网络系统最大流的方法。如果网络提供了一个寻求网络系统最大流的方法。如果网络GG中有一个可行流中有一个可行流 f f，只要判断网络是否存在关于可行流，只要判断网络是否存在关于可行流 f f 的增广链的增广链 。如果没有增广链，那么。如果没有增广链，那么f f一一定是最大流。如有增广链，那么可以按照定理中必要性，不断改进和增大可行定是最大流。如有增广链，那么可以按照定理中必要性，不断改进和增大可行流流f f 的流量，最终可以得到网络的流量，最终可以得到网络G G G G中的一个

12、最大流。中的一个最大流。推论：推论：网络中的一个可行流网络中的一个可行流f*f*是最大流的充分必要条件是，不存在关于是最大流的充分必要条件是，不存在关于f f*的的增广链。增广链。在一个网络在一个网络GG中，最大流的流量等于分离中，最大流的流量等于分离v vs s 和和v vt t 的最小割集的割量。的最小割集的割量。第11页/共28页 三、标号法三、标号法 从从从从网网网网络络络络中中中中的的的的一一一一个个个个可可可可行行行行流流流流f f f f 出出出出发发发发（如如如如果果果果G G G G中中中中没没没没有有有有 f f f f，可可可可以以以以令令令令f f f f 是是是是零零

13、零零流流流流），运运运运用用用用标标标标号号号号法法法法，经经经经过过过过标标标标号号号号过过过过程程程程和调整过程，可以得到网络中的一个最大流。和调整过程，可以得到网络中的一个最大流。和调整过程，可以得到网络中的一个最大流。和调整过程，可以得到网络中的一个最大流。如如如如果果果果v v v vt t t t有有有有了了了了标标标标号号号号，表表表表示示示示存存存存在在在在一一一一条条条条关关关关于于于于f f f f 的的的的增增增增广广广广链链链链。如如如如果果果果标标标标号号号号过过过过程程程程无无无无法法法法进进进进行行行行下下下下去去去去，并并并并且且且且v v v vt t t t

14、未未未未被被被被标标标标号号号号，则则则则表表表表示示示示不不不不存存存存在在在在关关关关于于于于f f f f 的的的的增增增增广广广广链链链链。这这这这样样样样，就就就就得得得得到到到到了了了了网网网网络络络络中的一个最大流和最小割集。中的一个最大流和最小割集。中的一个最大流和最小割集。中的一个最大流和最小割集。第12页/共28页1 1 1 1 标号过程标号过程 在在标标号号过过程程中中，网网络络中中的的每每个个标标号号点点的的标标号号包包含含两两部部分分：第第一一个个标标号号表表示示这这个个标标号号是是从从那那一一点点得得到到的的，以以便便找找出出增增广广链链；第第二二个个标标号号是是为

15、为了了用用来来确确定增广链上的调整量定增广链上的调整量 。标标号号过过程程开开始始，先先给给v vs s 标标号号（，+），一一般般地地，取取一一个个标标号号顶顶点点v vi i，对对v vi i所所有有未未标标号号的的邻邻接接点点v vj j按照下面条件进行处理：按照下面条件进行处理：第13页/共28页 （1 1 1 1）如如果果在在弧弧（v vi i,v,vj j）上上，f fij ij 0 0,那那么么给给v vj j标标号号（-v vi i,(vjvj)）.其中其中 (vj)(vj)=min=minf fji ji,(vivi)。重重复复以以上上步步骤骤，如如果果收收点点VtVtVtV

16、t被被标标号号或或不不再再有有顶顶点点可可标标号号为为止止，则则标标号号法法结结束束。这这时时的的可可行行流流就就是是最最大流。大流。第14页/共28页 2.2.调整过程令 但是，如果但是，如果但是，如果但是，如果v v v vt t t t 被标上号，表示得到一条增广被标上号，表示得到一条增广被标上号，表示得到一条增广被标上号，表示得到一条增广链链链链，转入下一步调整过程。，转入下一步调整过程。，转入下一步调整过程。，转入下一步调整过程。3.3.再去掉所有的标号，对新的可行流f=f ij,重新进行标号过程，直到找到网络G G的最大流为止。第15页/共28页vsv2v5vtv4v1v6v3(5

17、,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)例 求图的网络最大流，弧旁的权 数表示（cij,fij）。第16页/共28页vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)解：解：用标号法。用标号法。1.1.标号过程。标号过程。（1 1）首先给首先给v vs s标号（标号（，+）（2 2）检查检查v vs s邻接点邻接点v v1 1,v,v2 2,v,v3 3:v v2 2点点满足（满足（v vs s,v,v2 2)E,E,且且f fs2s2=2=2c cs2s2

18、=4,=4,v2v2=min2,+=2,=min2,+=2,给给v v2 2以标号以标号(+(+v vs s,2);,2);v v3 3点点满足（满足（v vs s,v,v3 3)E,E,且且f fs3s3=2=2c cs3s3=3,=3,v3v3=min1,+=1,=min1,+=1,给给v v3 3以标号以标号(+(+v vs s,1);,1);(，+)(+(+v vs s,2),2)(+(+v vs s,1),1)第17页/共28页（3 3）检查检查v v2 2邻接点邻接点v v5 5,v,v6 6:v v5 5点点满足（满足（v v2 2,v,v5 5)E,E,且且f f2525=0=

19、0=3c c1515=0,=0,v1v1=min3,2=2,=min3,2=2,给给v v1 1以标号以标号(-(-v v5 5,2);,2);vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)(，+)(+(+v vs s,2),2)(+(+v vs s,1),1)(+(+v v2 2,2),2)(-(-v v5 5,2),2)第19页/共28页（5 5）检查检查v v1 1邻接点邻接点v v4 4:v4v4点点满足（满足（v v1 1,v4),v4)E,E,且且f f1414=2=2c c1414=5,=5,v

20、4v4=min3,2=2,=min3,2=2,给给v v4 4以标号以标号(+(+v v1 1,2);,2);vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)(，+)(+(+v vs s,2),2)(+(+v vs s,1),1)(+(+v v2 2,2),2)(-(-v v5 5,2),2)(+(+v v1 1,2),2)第20页/共28页（6 6）检查检查v v4 4邻接点邻接点v vt t:vtvt点点满足（满足（v v4 4,vt),vt)E,E,且且f f4t4t=2=2c c4t4t=4,=4,vt

21、vt=min2,2=2,=min2,2=2,给给v vt t以标号以标号(+(+v v4 4,2);,2);V Vt t得到标号，说明已经得到一条可增广链，标号过程结束。得到标号，说明已经得到一条可增广链，标号过程结束。vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)(，+)(+(+v vs s,2),2)(+(+v vs s,1),1)(+(+v v2 2,2),2)(-(-v v5 5,2),2)(+(+v v1 1,2),2)(+(+v v4 4,2),2)第21页/共28页开始调整开始调整vsv2v5v

22、tv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)(，+)(+(+v vs s,2),2)(+(+v vs s,1),1)(+(+v v2 2,2),2)(-(-v v5 5,2),2)(+(+v v1 1,2),2)(+(+v v4 4,2),2)第22页/共28页2.2.2.2.调整过程调整过程 从vt开始，按照标号点的第一个标号，用反向追踪的方法，找出一条从vs到vt的增广链，如图G G中虚线所示。不难看出,+=(vs,v2),(v1,v4),(v4,vt),=(v5,v1),取 =vt vt=2 2，在上调整f，得到f

23、*=f4t+vt vt=2+2=4 在+上f14+vt vt=2+2=4 在+上f25+vt vt=0+2=2 在+上fs2+vt vt=2+2=4 在+上 f15 vt vt=3 2=1 在-上其它的不变第23页/共28页vsv2v5vtv4v1v6v3(5,5)(3,2)(3,1)(4,4)(5,4)(3,3)(2,2)(5,4)(4,4)(2,2)（，+）（+vs+vs+vs+vs ，1 1）(3,2)重新开始标号，寻找可增广链，当标到重新开始标号，寻找可增广链，当标到V V3 3，与，与V VS S,V,V3 3相连的相连的V V1 1,V,V2 2,V,V6 6不满足标号条不满足标号

24、条件，标号无法进行，件，标号无法进行，v vt t得不到标号。得不到标号。流量：流量：w=w=f fs1s1+f fs2s2+f fs3s3=f f4t4t+f f5t5t+f f6t6t=11=11得到一个最小割，标点号集合：得到一个最小割，标点号集合：S=vS=vs s,v,v3 3 非标点号集合：非标点号集合：/S=v/S=v1 1,v,v2 2，v v4 4,v,v5 5 ，v v6 6,v,vt t 此时割集（此时割集（s,/ss,/s）=(v=(vs s,v,v1 1),(v),(vs s,v,v2 2),(v),(v3 3,v,v6 6),),割集容量割集容量C(s,/s)=CC

25、(s,/s)=Cs1s1+C+Cs2s2+C+C3636=5+4+2=11=5+4+2=11第24页/共28页vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)(，+)(+(+v vs s,2),2)(+(+v vs s,1),1)(+(+v v2 2,2),2)(-(-v v5 5,2),2)(+(+v v1 1,2),2)(+(+v v4 4,2),2)4)4)1)(3,0)2)4)第一条可增广链：vs-v2,v5,v1,v4,vt,调整量为：2流量：f=11无可增广链最大流=14割集=(vs,v1),(vs,v2),(v3,v6)第25页/共28页求最大流的标号算法可以解决多发点多收点网络的最大流问题X1X2X3xmY1Y2Y3ynvsvt+第26页/共28页小结1、最大流问题的概念、最大流-最小割定理。2、求最大流问题的标号算法。作业8.10,8.14 第27页/共28页感谢您的观看！第28页/共28页