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

《运筹学课件第四节最大流问题精.ppt》由会员分享，可在线阅读，更多相关《运筹学课件第四节最大流问题精.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学课件第四节最大流问题第1页，本讲稿共28页 引言引言 在在许许多多实实际际的的网网络络系系统统中中都都存存在在着着流流量量和和最最大大流流问问题题。例例如如铁铁路路运运输输系系统统中中的的车车辆辆流流，城城市市给给排排水水系系统统的的水水流流问问题题等等等等。而而网网络络系系统统流流最最大大流流问问题题是是图图与与网网络络流流理理论论中中十十分分重重要要的的最最优优化化问问题题，它它对对于于解解决决生生产产实实际际问问题题起起着着十十分重要的作用。分重要的作用。第2页，本讲稿共28页 图图图图是是是是联联联联结结结结某某某某个个个个起起起起始始始始地地地地v vs s和和和和目目目目的的

2、的的地地地地v vt的的的的交交交交通通通通运运运运输输输输网网网网，每每每每一一一一条条条条弧弧弧弧v vi i 旁旁旁旁边边边边的的的的权权权权c cij ij表表表表示示示示这这这这段段段段运运运运输输输输线线线线的的的的最最最最大大大大通通通通过过过过能能能能力力力力，货货货货物物物物从从从从v vs s运运运运送送送送到到到到v vt t.要要要要求求求求指指指指定定定定一一一一个个个个运运运运输输输输方方方方案案案案，使使使使得得得得从从从从vs s到到到到vt的的的的货货货货运运运运量量量量最最最最大大大大，这个问题就是寻求网络系统的最大流问题这个问题就是寻求网络系统的最大流问题

3、这个问题就是寻求网络系统的最大流问题这个问题就是寻求网络系统的最大流问题。一、最大流有关概念一、最大流有关概念连通网络连通网络G G(V,EV,E)有有有有 m 个节点个节点个节点个节点,n n条弧条弧条弧条弧,弧弧e eij ij 上的流量上的流量上的流量上的流量上界为上界为上界为上界为 c cij ij,求从起始节点求从起始节点v vs到终点到终点到终点到终点 v vt t 的最大流量。的最大流量。vtv3v2v1v4vs1735108611453Cij第3页，本讲稿共28页 定定义义20202020 设设设设一一一一个个个个赋赋赋赋权权权权有有有有向向向向图图图图G=（V,EV,E）,对

4、对于于G G中中中中的的的的每每每每一一一一个个个个边边边边（弧弧弧弧）（vi i,v,vj j）E E,都都有有一一个个非非非非负负负负数数数数c cijij叫叫叫叫做做做做边边边边的的的的容容容容量量量量。在在VV中中一一个个入入次次为为零零的的点点称称为为发发点点vs s，一一一一个个个个出出出出次次次次为为为为零零零零的的的的点点点点称称称称为为为为收收收收点点点点v vt,其其它它的的点点叫叫做做中中间间点点。我我们们把把这这样样的的图图G叫叫做一个做一个容量容量容量容量网络，网络，网络，网络，记做记做G G=（V V，E E，C C）。）。）。）。网网络络GG上上上上的的的的流流流

5、流，是是指指定定义义在在边边(v(vi ,v,v,v,vj j)上上上上有有有有流流流流量量量量f f f fij ij，称称称称集合集合集合集合f=ff=fij 为网络为网络G G上的一个流，上的一个流，f f f f为可行流。为可行流。为可行流。为可行流。第4页，本讲稿共28页网络上的一个流网络上的一个流f f 叫做可行流，如果叫做可行流，如果叫做可行流，如果叫做可行流，如果f f 满足以下条件：满足以下条件：（1 1）容容量量条条件件：对对于于每每一一个个弧弧（vi i,vj j）E E,有有有有 0 0 fij ij c cij ij.（2 2）平衡条件：）平衡条件：）平衡条件：）平衡

6、条件：对于发点对于发点vs,收点收点vt有有对于中间点，有对于中间点，有第5页，本讲稿共28页 任意一个网络上的可行流总是存在的。例如零流任意一个网络上的可行流总是存在的。例如零流w w(f)=0)=0,就是满足以上条件的可行流。就是满足以上条件的可行流。网络系统中最大流问题就是在给定的网络上寻求一个网络系统中最大流问题就是在给定的网络上寻求一个网络系统中最大流问题就是在给定的网络上寻求一个网络系统中最大流问题就是在给定的网络上寻求一个可行流可行流可行流可行流f f f f,其流量其流量其流量其流量w w(f f f f)达到最大值。达到最大值。设流设流f=fij ij 是网络是网络G上的一个

7、可行流。我们把上的一个可行流。我们把上的一个可行流。我们把上的一个可行流。我们把GG中中中中fij=cij ij的弧叫做饱和弧，的弧叫做饱和弧，的弧叫做饱和弧，的弧叫做饱和弧，f fij00的弧的弧的弧的弧为非零流弧，为非零流弧，为非零流弧，为非零流弧，f fij=0=0的弧叫做零流弧的弧叫做零流弧的弧叫做零流弧的弧叫做零流弧 .最大流问题实际是个线性规划问题。最大流问题实际是个线性规划问题。其中发点的总流量（或收点的总流量）其中发点的总流量（或收点的总流量）其中发点的总流量（或收点的总流量）其中发点的总流量（或收点的总流量）w 叫做这个可行流的总流量。叫做这个可行流的总流量。叫做这个可行流的

8、总流量。叫做这个可行流的总流量。第6页，本讲稿共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等等。等等。等等。等等。第7页，本讲稿共28页定义定义定义定义21212121 设一个网络设一个网络设一个网络设一个网络G G=（

9、V V，E E，C C），v vs s、v vt t为发为发为发为发和和和和收点，边集收点，边集收点，边集收点，边集 为为为为E E的的的的子子子子集集集集，将将将将GG分分分分成成成成2 2个个个个子子子子图图图图GG1 1,G,G2 2;其其其其顶顶顶顶点点点点集集集集合合合合分分分分别别别别为为为为:,发点发点发点发点v vs sS,S,收点收点收点收点v vt t/S/S,满足满足满足满足1.1.1.1.G G=（V V，E-E-）不连通；）不连通；）不连通；）不连通；2.2.为为为为的真子集，而的真子集，而的真子集，而的真子集，而G G=（V V，E-E-）连通；）连通；）连通；）连

10、通；那么那么那么那么 为为为为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,)。第8页，本讲稿共28页vtvsv1v2v3v442443322231边集边集(vs,v1),(vs,v3),(vs,v4)边集边集(vs,v1),(

11、v1,v3),(v2,v3),(v3,vt)为图的割集，割集容量分别为为图的割集，割集容量分别为11，9第9页，本讲稿共28页二、最大流二、最大流二、最大流二、最大流-最小割定理最小割定理最小割定理最小割定理定理定理定理定理1010：设设设设f f为网络为网络为网络为网络G G=（V V，E E，C C）的任一个可行流，流量为）的任一个可行流，流量为）的任一个可行流，流量为）的任一个可行流，流量为W,W,(S,)(S,)(S,)(S,)是分离是分离是分离是分离v vssv vt t的任一个割集，则有的任一个割集，则有的任一个割集，则有的任一个割集，则有WW C(S,).C(S,).C(S,).

12、C(S,).定理定理定理定理1111：最大流最大流最大流最大流-最小割定理最小割定理最小割定理最小割定理:任一个网络任一个网络任一个网络任一个网络G G=（V V，E E，C C）,从从从从v vs s到到到到v vt t的最大流的流量等于的最大流的流量等于的最大流的流量等于的最大流的流量等于分离分离分离分离v vssv vt t的最小割的容量。的最小割的容量。的最小割的容量。的最小割的容量。定定定定义义义义22222222：设设设设 是是是是网网网网络络络络G G中中中中连连连连接接接接发发发发点点点点 s s和和和和收收收收点点点点v vt t的的的的一一一一条条条条链链链链。定定定定义义

13、义义链链链链的的的的方方方方向向向向是是是是从从从从 s s到到到到 v vt t ，于于于于是是是是链链链链 上上上上的的的的边边边边被被被被分分分分为为为为两两两两类类类类：一一一一类类类类是是是是边边边边的的的的方方方方向向向向与与与与链链链链的的的的方方方方向向向向相相相相同同同同，叫叫叫叫做做做做前前前前向向向向边边边边，前前前前向向向向边边边边的的的的集集集集合合合合记记记记做做做做+。二二二二类类类类是是是是边边边边的的的的方方方方向向向向与与与与链链链链的方向相反，叫做后向边，的方向相反，叫做后向边，的方向相反，叫做后向边，的方向相反，叫做后向边，后向后向边边边边的集合记做的集

14、合记做。第10页，本讲稿共28页 如果链如果链如果链如果链 满足以下条件：满足以下条件：满足以下条件：满足以下条件：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 v

15、s s,v,v11),(v v1 1,v,v2 2),(),(v v2 2,v,v3 3),(),(v v4 4,v,vt t),),=(v v4 4 ,v,v3 3).).vtvsv1v2v3v442443322231第11页，本讲稿共28页定理定理定理定理11111111提供了一个寻求网络系统最大流的方法。如果网络提供了一个寻求网络系统最大流的方法。如果网络提供了一个寻求网络系统最大流的方法。如果网络提供了一个寻求网络系统最大流的方法。如果网络G G中有一中有一中有一中有一个可行流个可行流个可行流个可行流 f f，只要判断网络是否存在关于可行流，只要判断网络是否存在关于可行流，只要判断网络

16、是否存在关于可行流，只要判断网络是否存在关于可行流 f f 的增广链的增广链的增广链的增广链 。如果没有增广链，那么如果没有增广链，那么如果没有增广链，那么如果没有增广链，那么f f一定是最大流。如有增广链，那么可以一定是最大流。如有增广链，那么可以一定是最大流。如有增广链，那么可以一定是最大流。如有增广链，那么可以按照定理中必要性，不断改进和增大可行流按照定理中必要性，不断改进和增大可行流按照定理中必要性，不断改进和增大可行流按照定理中必要性，不断改进和增大可行流f f 的流量，最终可的流量，最终可的流量，最终可的流量，最终可以得到网络以得到网络以得到网络以得到网络G G G G中的一个最大

17、流。中的一个最大流。中的一个最大流。中的一个最大流。推论：推论：推论：推论：网络中的一个可行流网络中的一个可行流网络中的一个可行流网络中的一个可行流f*f*是最大流的充分必要条件是，不是最大流的充分必要条件是，不是最大流的充分必要条件是，不是最大流的充分必要条件是，不存在关于存在关于存在关于存在关于f f*的增广链。的增广链。的增广链。的增广链。在一个网络在一个网络在一个网络在一个网络G G中，最大流的流量等于分离中，最大流的流量等于分离中，最大流的流量等于分离中，最大流的流量等于分离v vs s和和和和v vt t 的最小割集的割量。的最小割集的割量。的最小割集的割量。的最小割集的割量。第1

18、2页，本讲稿共28页 三、标号法三、标号法三、标号法三、标号法 从从从从网网网网络络络络中中中中的的的的一一一一个个个个可可可可行行行行流流流流f f 出出出出发发发发（如如如如果果果果G G中中中中没没没没有有有有 f f f f，可可以以令令f f f f 是是是是零零零零流流流流），运运运运用用用用标标标标号号号号法法法法，经经经经过过过过标标标标号号号号过过过过程程程程和和和和调调调调整整整整过过过过程程程程，可以得到网络中的一个最大流。可以得到网络中的一个最大流。可以得到网络中的一个最大流。可以得到网络中的一个最大流。如如果果v vt t有有有有了了了了标标标标号号号号，表表表表示示

19、示示存存存存在在在在一一一一条条条条关关关关于于于于f f f f 的的增增广广链链。如如果果标标号号过过程程无无法法进进行行下下去去，并并且且v vt t未未被被标标号号，则则表表示示不不存存在在关关于于f f 的的的的增增增增广广广广链链链链。这这这这样样样样，就就就就得得得得到到到到了了了了网网网网络络络络中中中中的的的的一一一一个个个个最大流和最小割集。最大流和最小割集。最大流和最小割集。最大流和最小割集。第13页，本讲稿共28页1 1 标号过程标号过程标号过程标号过程 在在标标号号过过程程中中，网网络络中中的的每每个个标标号号点点的的标标号号包包含含两两部部分分：第第一一个个标标号号

20、表表示示这这个个标标号号是是从从那那一一点点得得到到的的，以以便便找找出出增增广广链链；第第二二个个标标号号是是为为了了用用来来确确定定增增广广链链上的调整量上的调整量 。标标标标号号号号过过过过程程程程开开开开始始始始，先先先先给给给给vs s标标标标号号号号（，+），一一般般地地，取取一一个个标标号号顶顶点点vi i，对对v vi i所所所所有有有有未未未未标标标标号号号号的的的的邻邻邻邻接接接接点点点点v vj j按按按按照照照照下下下下面面面面条件进行处理：条件进行处理：条件进行处理：条件进行处理：第14页，本讲稿共28页 （1 1）如如果果在在弧弧（vi,vj j）上上，f fij

21、0 0,那那那那么么么么给给给给vj标标号号（-vi,(vj vj)）.其中其中其中其中 (vj)=minf fji,(vi vi)。重重重重复复复复以以以以上上上上步步步步骤骤骤骤，如如如如果果果果收收收收点点点点VtVt被被被被标标标标号号号号或或或或不不不不再再再再有有有有顶顶顶顶点点点点可可可可标标标标号号号号为止，则标号法结束。这时的可行流就是最大流。为止，则标号法结束。这时的可行流就是最大流。为止，则标号法结束。这时的可行流就是最大流。为止，则标号法结束。这时的可行流就是最大流。第15页，本讲稿共28页 2.2.调整过程调整过程令令 但是，如果但是，如果v vt t 被标上号，表示

22、得到一条增广链被标上号，表示得到一条增广链，转入下一步调整过程。，转入下一步调整过程。3.3.再去掉所有的标号，对新的可行流再去掉所有的标号，对新的可行流f=f ij,重新进行标重新进行标号过程，直到找到网络号过程，直到找到网络G G的最大流为止。的最大流为止。第16页，本讲稿共28页vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)例例 求图的网络最大流，弧旁的权求图的网络最大流，弧旁的权 数表示（数表示（cij,fij）。第17页，本讲稿共28页vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(

23、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=4,=4,v2v2=min2,+=2,=min2,+=2,给给给给v v2 2以标号以标号以标号以标号(+(+v vs s

24、,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)第18页，本讲稿共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=0=3c c1515=0,

25、=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)第20页，本讲稿共28页（5 5）检查检查检查检查v v1 1邻接点邻接点邻接点邻接点v v4 4:v4v4点点点点满足（满足（满足（满足（v v1 1,v4),v4)E,E,且且且且f f1414

26、=2=2c c1414=5,=5,v4v4=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)第21页，本讲稿共28页（6 6）检查检查检查检查v v4 4邻接点邻接点邻接点邻接点v vt t:vtvt点点点点满足（满足（满足（满足

27、（v v4 4,vt),vt)E,E,且且且且f f4t4t=2=2c c4t4t=4,=4,vtvt=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)

28、,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页开始调整开始调整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)第23页，本讲稿共28页2.2.调整过程调整过程 从从vt开开

29、始始，按按照照标标号号点点的的第第一一个个标标号号，用用反反向向追追踪踪的的方方法法，找找出出一一条条从从vs到到vt的的增增广广链链，如如图图G G中中虚虚线线所所示。不难看出示。不难看出,+=(vs,v2),(v1,v4),(v4,vt),=(v5,v1),取取 =vtvt=2 2，在在上调整上调整f，得到，得到f*=f4t+vtvt=2+2=4 在在+上上f14+vtvt=2+2=4 在在+上上f25+vtvt=0+2=2 在在+上上fs2+vtvt=2+2=4 在在+上上f15 vtvt=32=1 在在-上上其它的不变其它的不变第24页，本讲稿共28页vsv2v5vtv4v1v6v3(

30、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不满足标号条件，标号无法进行，不满足标号条件，标号无法进行，不满足标号条件，标号无法进行，不满足标号条件，标号无法进行，v vt t得不到标号。得不到标号。得不到标号。得不到标号。流量：流量：流

31、量：流量：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),),割集容量割

32、集容量割集容量割集容量C(s,/s)=CC(s,/s)=Cs1s1+C+Cs2s2+C+C3636=5+4+2=11=5+4+2=11第25页，本讲稿共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)第26页，本讲稿共28页求最大流的标号算法可以解决多发点多收点网络的最大流问题X1X2X3xmY1Y2Y3ynvsvt+第27页，本讲稿共28页小结1、最大流问题的概念、最大流-最小割定理。2、求最大流问题的标号算法。作业作业8.10,8.14 第28页，本讲稿共28页