《运筹学第四节最大流问题幻灯片.ppt》由会员分享，可在线阅读，更多相关《运筹学第四节最大流问题幻灯片.ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、运筹学课件第四节最大流问题第1页，共28页，编辑于2022年，星期三 引言引言 在在许许多多实实际际的的网网络络系系统统中中都都存存在在着着流流量量和和最最大大流流问问题题。例例如如铁铁路路运运输输系系统统中中的的车车辆辆流流，城城市市给给排排水水系系统统的的水水流流问问题题等等等等。而而网网络络系系统统流流最最大大流流问问题题是是图图与与网网络络流流理理论论中中十十分分重重要要的的最最优优化化问问题题，它它对对于解决生产实际问题起着十分重要的作用。于解决生产实际问题起着十分重要的作用。第2页，共28页，编辑于2022年，星期三 图图图图是是是是联联联联结结结结某某某某个个个个起起起起始始始始
2、地地地地v vs s和和目目的的地地v vt t的的的的交交交交通通通通运运运运输输输输网网网网，每每每每一一一一条条条条弧弧弧弧v vi i 旁旁旁旁边边边边的的的的权权权权c cij ij表表表表示示示示这这这这段段段段运运运运输输输输线线线线的的的的最最最最大大大大通通通通过过过过能能能能力力力力，货货货货物物物物从从从从vs运运运运送送送送到到到到v vt t.要要要要求求求求指指指指定定定定一一一一个个个个运运运运输输输输方方方方案案案案，使使使使得得得得从从从从v vs到到到到vt t的的的的货货货货运运运运量量量量最最最最大大大大，这这这这个个个个问问问问题就是寻求网络系统的最大
3、流问题题就是寻求网络系统的最大流问题题就是寻求网络系统的最大流问题题就是寻求网络系统的最大流问题。一、最大流有关概念一、最大流有关概念连通网络连通网络连通网络连通网络 G(V,E)有有m 个节点个节点,n条弧条弧,弧弧eij 上的流上的流上的流上的流量上界为量上界为量上界为量上界为 cij ij,求从起始节点求从起始节点求从起始节点求从起始节点 vs到终点到终点vt 的最大流量。的最大流量。vtv3v2v1v4vs1735108611453Cij第3页，共28页，编辑于2022年，星期三 定定定定义义义义20202020 设设设设一一一一个个个个赋赋赋赋权权权权有有有有向向向向图图图图G G=
4、（V,EV,E）,对对于于G中中中中的的的的每每每每一一一一个个个个边边边边（弧弧弧弧）（vi i,v,vj）E E,都都有有一一个个非非负负数数c cijijijij叫叫叫叫做做做做边边边边的的的的容容容容量量量量。在在VV中中一一个个入入次次为为零零的的点点称称为为发发点点vs，一一一一个个个个出出出出次次次次为为为为零零零零的的的的点点点点称称称称为为为为收收收收点点点点v vt t,其其它它的的点点叫叫做做中中间间点点。我我们们把把这这样样的的图图G叫叫做一个做一个容量容量网络，网络，网络，网络，记做记做G G=（V V，E E，C C）。）。网网网网络络络络GG上上的的流流，是是指指
5、定定义义在在边边(v(v(v(vi ,v,vj j)上上有有流流量量f f f fij，称称集合集合f=ff=ff=ff=fij 为网络为网络为网络为网络G G上的一个流，上的一个流，f f f f为可行流。为可行流。为可行流。为可行流。第4页，共28页，编辑于2022年，星期三网络上的一个流网络上的一个流f 叫做可行流，如果叫做可行流，如果f 满足以下条件：满足以下条件：（1 1）容容量量条条件件：对对对对于于于于每每每每一一一一个个个个弧弧弧弧（vi ,v,vj j）E E,有有 0 f fij ij cij .（2 2）平衡条件：）平衡条件：对于发点对于发点vs,收点收点vt有有对于中间
6、点，有对于中间点，有第5页，共28页，编辑于2022年，星期三 任意一个网络上的可行流总是存在的。例如零流任意一个网络上的可行流总是存在的。例如零流任意一个网络上的可行流总是存在的。例如零流任意一个网络上的可行流总是存在的。例如零流w(f)=0)=0,就是满足以上条件的可行流。就是满足以上条件的可行流。网络系统中最大流问题就是在给定的网络上寻求一个网络系统中最大流问题就是在给定的网络上寻求一个网络系统中最大流问题就是在给定的网络上寻求一个网络系统中最大流问题就是在给定的网络上寻求一个可行流可行流可行流可行流f f,其流量其流量w w(f f)达到最大值。达到最大值。设流设流设流设流f=fij
7、ij是网络是网络是网络是网络G G上的一个可行流。我们把上的一个可行流。我们把GG中中fij ij=cij的弧叫做饱和弧，的弧叫做饱和弧，的弧叫做饱和弧，的弧叫做饱和弧，f fij ij 00的的弧为非零流弧，弧为非零流弧，fij ij=0的弧叫做零流弧的弧叫做零流弧 .最大流问题实际是个线性规划问题。最大流问题实际是个线性规划问题。其中发点的总流量（或收点的总流量）其中发点的总流量（或收点的总流量）其中发点的总流量（或收点的总流量）其中发点的总流量（或收点的总流量）w叫做这个可行流的总流量。叫做这个可行流的总流量。叫做这个可行流的总流量。叫做这个可行流的总流量。第6页，共28页，编辑于202
8、2年，星期三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页，编辑于2022年，星期三定义定义定义定义21212121 设一个网络设一个网络设一个网络设一个网络G G=（V V，E E，C C
9、），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页，编辑于2022年，星期三vtvsv1v2v3v442443322231边集边集(vs,v1),(vs,v3),(vs,v4)边集边集(vs,v1),(v
11、1,v3),(v2,v3),(v3,vt)为图的割集，割集容量分别为为图的割集，割集容量分别为11，9第9页，共28页，编辑于2022年，星期三二、最大流二、最大流二、最大流二、最大流-最小割定理最小割定理最小割定理最小割定理定理定理定理定理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,).
12、C(S,).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页，编辑于2022年，星期三 如果链如果链如果链如果链 满足以下条件：满足以下条件：满足以下条件：满足以下条件：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,
15、vt t)中中中中，+=(v vs 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页，编辑于2022年，星期三定理定理定理定理11111111提供了一个寻求网络系统最大流的方法。如果网络提供了一个寻求网络系统最大流的方法。如果网络提供了一个寻求网络系统最大流的方法。如果网络提供了一个寻求网络系统最大流的方法。如果网络G G中有一中有一中有一中有一个可行流个可行流个可行流个可行流 f f，只要判断网络是否存在关于
16、可行流，只要判断网络是否存在关于可行流，只要判断网络是否存在关于可行流，只要判断网络是否存在关于可行流 f f 的增广链的增广链的增广链的增广链 。如。如。如。如果没有增广链，那么果没有增广链，那么果没有增广链，那么果没有增广链，那么f f一定是最大流。如有增广链，那么可以按照定一定是最大流。如有增广链，那么可以按照定一定是最大流。如有增广链，那么可以按照定一定是最大流。如有增广链，那么可以按照定理中必要性，不断改进和增大可行流理中必要性，不断改进和增大可行流理中必要性，不断改进和增大可行流理中必要性，不断改进和增大可行流f f 的流量，最终可以得到网络的流量，最终可以得到网络的流量，最终可以
17、得到网络的流量，最终可以得到网络G G G G中的一个最大流。中的一个最大流。中的一个最大流。中的一个最大流。推论：推论：推论：推论：网络中的一个可行流网络中的一个可行流网络中的一个可行流网络中的一个可行流f*f*是最大流的充分必要条件是，不存是最大流的充分必要条件是，不存是最大流的充分必要条件是，不存是最大流的充分必要条件是，不存在关于在关于在关于在关于f f*的增广链。的增广链。的增广链。的增广链。在一个网络在一个网络在一个网络在一个网络G G中，最大流的流量等于分离中，最大流的流量等于分离中，最大流的流量等于分离中，最大流的流量等于分离v vs s和和和和v vt t 的最小割集的割量。
18、的最小割集的割量。的最小割集的割量。的最小割集的割量。第12页，共28页，编辑于2022年，星期三 三、标号法三、标号法 从从从从网网网网络络络络中中中中的的的的一一一一个个个个可可可可行行行行流流流流f f f f 出出出出发发发发（如如如如果果果果G G G G中中中中没没没没有有有有 f f f f，可可可可以以以以令令令令f f 是是是是零零零零流流流流），运运运运用用用用标标标标号号号号法法法法，经经经经过过过过标标标标号号号号过过过过程程程程和和和和调调调调整整整整过过过过程程程程，可以得到网络中的一个最大流。可以得到网络中的一个最大流。可以得到网络中的一个最大流。可以得到网络中的
19、一个最大流。如如如如果果果果v v v vt t t t有有了了标标号号，表表示示存存在在一一条条关关于于f f 的的的的增增增增广广广广链链链链。如如如如果果果果标标标标号号号号过过过过程程程程无无无无法法法法进进进进行行行行下下下下去去去去，并并并并且且且且v vt t t t未未被被标标号号，则则表表示示不不存存在在关关于于f f f f 的的增增广广链链。这这样样，就就得得到到了了网网络络中中的的一一个最大流和最小割集。个最大流和最小割集。第13页，共28页，编辑于2022年，星期三1 1 标号过程标号过程 在在标标号号过过程程中中，网网络络中中的的每每个个标标号号点点的的标标号号包包
20、含含两两部部分分：第第一一个个标标号号表表示示这这个个标标号号是是从从那那一一点点得得到到的的，以以便便找找出出增增广广链链；第第二二个个标标号号是是为为了了用用来来确确定增广链上的调整量定增广链上的调整量 。标标标标号号号号过过过过程程程程开开开开始始始始，先先先先给给给给v vs标标号号（，+），一一般般地地，取取一一个个标标号号顶顶点点vi i，对对vi i所所有有未未未未标标标标号号号号的的的的邻邻邻邻接接接接点点点点vj j按按照照下下面面条件进行处理：条件进行处理：第14页，共28页，编辑于2022年，星期三 （1 1 1 1）如如如如果果果果在在在在弧弧弧弧（v vi,v,vj
21、j）上上上上，fij ij0 0,那那那那么么么么给给给给vj标标号号（-vi i,(vj vj)）.其中其中其中其中 (vj)(vj)=min=minf fji,(vi)。重重复复以以上上步步骤骤，如如果果收收点点VtVtVtVt被被标标号号或或不不再再有有顶顶点点可可标标号为止，则标号法结束。这时的可行流就是最大流。号为止，则标号法结束。这时的可行流就是最大流。第15页，共28页，编辑于2022年，星期三 2.2.调整过程调整过程令令 但是，如果但是，如果但是，如果但是，如果v vt t t t 被标上号，表示得到一条增广链被标上号，表示得到一条增广链被标上号，表示得到一条增广链被标上号，
22、表示得到一条增广链，转入下一步调整过程。转入下一步调整过程。3.3.再去掉所有的标号，对新的可行流再去掉所有的标号，对新的可行流f=f ij,重新进重新进行标号过程，直到找到网络行标号过程，直到找到网络G G的最大流为止。的最大流为止。第16页，共28页，编辑于2022年，星期三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页，编辑于2022年，星期三vsv2v5vtv4v1v6v3(5,5)(3,2
23、)(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=4,=4,v2v2=min2,+=2,=min2,+=2,给给给给v v2 2以标号以标号以标号以标号(+(
24、+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)第18页，共28页，编辑于2022年，星期三（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
25、=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)第20页，共28页，编辑于2022年，星期三（5 5）检查检查检查检查v v1 1邻接点邻接点邻接点邻接点v v4 4:v4v4点点点点满足（满足（满足（满足（v v1
26、1,v4),v4)E,E,且且且且f f1414=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页，编辑于2022年，星期三（6 6）检查检查检查检查v v4 4邻接点邻
27、接点邻接点邻接点v vt t:vtvt点点点点满足（满足（满足（满足（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,
28、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页，编辑于2022年，星期三开始调整开始调整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)(+(
29、+v v4 4,2),2)第23页，共28页，编辑于2022年，星期三2.2.调整过程调整过程 从从vt开开始始，按按照照标标号号点点的的第第一一个个标标号号，用用反反向向追追踪踪的的方方法法，找找出出一一条条从从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 v
30、tvt=32=1 在在-上上其它的不变其它的不变第24页，共28页，编辑于2022年，星期三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不满足标号条件，标号无法进行，不满足标号条件，标号无法进行，不满足标
31、号条件，标号无法进行，不满足标号条件，标号无法进行，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,/
32、s）=(v=(vs s,v,v1 1),(v),(vs s,v,v2 2),(v),(v3 3,v,v6 6),),割集容量割集容量割集容量割集容量C(s,/s)=CC(s,/s)=Cs1s1+C+Cs2s2+C+C3636=5+4+2=11=5+4+2=11第25页，共28页，编辑于2022年，星期三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页，编辑于2022年，星期三求最大流的标号算法可以解决多发点多收点网络的最大流问题X1X2X3xmY1Y2Y3ynvsvt+第27页，共28页，编辑于2022年，星期三小结1、最大流问题的概念、最大流-最小割定理。2、求最大流问题的标号算法。作业作业8.10,8.14 第28页，共28页，编辑于2022年，星期三