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

运筹学教程第四节第四节 最大流问题最大流问题理解最大流问题的概念、最大流理解最大流问题的概念、最大流-最小最小割定理。割定理。掌握求最大流问题的标号算法。掌握求最大流问题的标号算法。运筹学教程 引言引言 在在许许多多实实际际的的网网络络系系统统中中都都存存在在着着流流量量和和最最大大流流问问题题。例例如如铁铁路路运运输输系系统统中中的的车车辆辆流流，城城市市给给排排水水系系统统的的水水流流问问题题等等等等。而而网网络络系系统统流流最最大大流流问问题题是是图图与与网网络络流流理理论论中中十十分分重重要要的的最最优优化化问问题题，它它对对于于解解决决生生产产实实际际问题起着十分重要的作用。问题起着十分重要的作用。运筹学教程 图图图图是是是是联联联联结结结结某某某某个个个个起起起起始始始始地地地地v vs s和和和和目目目目的的的的地地地地v vt t的的的的交交交交通通通通运运运运输输输输网网网网，每每每每一一一一条条条条弧弧弧弧v vi i 旁旁旁旁边边边边的的的的权权权权c cij ij表表表表示示示示这这这这段段段段运运运运输输输输线线线线的的的的最最最最大大大大通通通通过过过过能能能能力力力力，货货货货物物物物从从从从v vs s运运运运送送送送到到到到v vt t.要要要要求求求求指指指指定定定定一一一一个个个个运运运运输输输输方方方方案案案案，使使使使得得得得从从从从v vs s到到到到v vt t的的的的货货货货运运运运量量量量最最最最大大大大，这这这这个个个个问问问问题题题题就就就就是是是是寻寻寻寻求求求求网网网网络络络络系系系系统统统统的的的的最最最最大大大大流流流流问题问题问题问题。一、最大流有关概念一、最大流有关概念连通网络连通网络连通网络连通网络 G G(V,V,E E)有有有有 m m 个节点个节点个节点个节点,n n条弧条弧条弧条弧,弧弧弧弧 e eij ij 上上上上的流量上界为的流量上界为的流量上界为的流量上界为 c cij ij,求从起始节点求从起始节点求从起始节点求从起始节点 v vs s 到终点到终点到终点到终点 v vt t 的最大流的最大流的最大流的最大流量。量。量。量。vtv3v2v1v4vs1735108611453Cij运筹学教程 定定定定义义义义20202020 设设设设一一一一个个个个赋赋赋赋权权权权有有有有向向向向图图图图G G=（V,EV,E）,对对对对于于于于G G中中中中的的的的每每每每一一一一个个个个边边边边（弧弧弧弧）（v vi i,v vj j）E E,都都都都有有有有一一一一个个个个非非非非负负负负数数数数c c c cijijijij叫叫叫叫做做做做边边边边的的的的容容容容量量量量。在在在在V V 中中中中一一一一个个个个入入入入次次次次为为为为零零零零的的的的点点点点称称称称为为为为发发发发点点点点v vs s，一一一一个个个个出出出出次次次次为为为为零零零零的的的的点点点点称称称称为为为为收收收收点点点点v vt t ,其其其其它它它它的的的的点点点点叫叫叫叫做做做做中中中中间间间间点点点点。我我我我们们们们把把把把这这这这样样样样的的的的图图图图G G叫叫叫叫做做做做一一一一个个个个容容容容量量量量网网网网络络络络，记记记记做做做做G G=（V V，E E，C C）。）。）。）。网网网网络络络络GG上上上上的的的的流流流流，是是是是指指指指定定定定义义义义在在在在边边边边(v v v vi i ,v v v vj j)上上上上有有有有流流流流量量量量f f f fij ij，称集合称集合称集合称集合f=f=f=f=f f f fij ij 为网络为网络为网络为网络G G G G上的一个流，上的一个流，上的一个流，上的一个流，f f f f为可行流。为可行流。为可行流。为可行流。运筹学教程网络上的一个流网络上的一个流网络上的一个流网络上的一个流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有有对于中间点，有对于中间点，有运筹学教程 任意一个网络上的可行流总是存在的。例如零任意一个网络上的可行流总是存在的。例如零任意一个网络上的可行流总是存在的。例如零任意一个网络上的可行流总是存在的。例如零流流流流w w(f f)=0)=0,就是满足以上条件的可行流。就是满足以上条件的可行流。就是满足以上条件的可行流。就是满足以上条件的可行流。网络系统中最大流问题就是在给定的网络上寻网络系统中最大流问题就是在给定的网络上寻网络系统中最大流问题就是在给定的网络上寻网络系统中最大流问题就是在给定的网络上寻求一个可行流求一个可行流求一个可行流求一个可行流f f f f,其流量其流量其流量其流量w w w w(f f f f)达到最大值。达到最大值。达到最大值。达到最大值。设流设流设流设流f f=f fij ij 是网络是网络是网络是网络G G上的一个可行流。我们把上的一个可行流。我们把上的一个可行流。我们把上的一个可行流。我们把GG中中中中f fij ij=c cij ij的弧叫做饱和弧，的弧叫做饱和弧，的弧叫做饱和弧，的弧叫做饱和弧，f fij ij 00的弧为非零流弧，的弧为非零流弧，的弧为非零流弧，的弧为非零流弧，f fij ij=0=0的弧叫做零流弧的弧叫做零流弧的弧叫做零流弧的弧叫做零流弧 .最大流问题实际是个线性规划问题。最大流问题实际是个线性规划问题。最大流问题实际是个线性规划问题。最大流问题实际是个线性规划问题。其中发点的总流量（或收点的总流量）其中发点的总流量（或收点的总流量）其中发点的总流量（或收点的总流量）其中发点的总流量（或收点的总流量）w w 叫做这个可行流的总流量。叫做这个可行流的总流量。叫做这个可行流的总流量。叫做这个可行流的总流量。运筹学教程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 等等。等等。等等。等等。运筹学教程定义定义定义定义21212121 设一个网络设一个网络设一个网络设一个网络G G=（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-）连通；连通；连通；连通；那么那么那么那么 为为为为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,)。运筹学教程vtvsv1v2v3v442443322231边集边集(vs,v1),(vs,v3),(vs,v4)边集边集(vs,v1),(v1,v3),(v2,v3),(v3,vt)为图的割集，割集容量分别为为图的割集，割集容量分别为11，9运筹学教程二、最大流二、最大流二、最大流二、最大流-最小割定理最小割定理最小割定理最小割定理定理定理定理定理1010：设设设设f f为网络为网络为网络为网络G G=（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：最大流最大流最大流最大流-最小割定理最小割定理最小割定理最小割定理:任一个任一个任一个任一个网络网络网络网络G G=（V V，E E，C C）,从从从从v vs s到到到到v vt t的的的的最大流的流量等于最大流的流量等于最大流的流量等于最大流的流量等于分离分离分离分离v vs s v vt t的最小割的容量。的最小割的容量。的最小割的容量。的最小割的容量。定定定定义义义义22222222：设设设设 是是是是网网网网络络络络G G中中中中连连连连接接接接发发发发点点点点 s s和和和和收收收收点点点点v vt t的的的的一一一一条条条条链链链链。定定定定义义义义链链链链的的的的方方方方向向向向是是是是从从从从 s s到到到到 v vt t ，于于于于是是是是链链链链 上上上上的的的的边边边边被被被被分分分分为为为为两两两两类类类类：一一一一类类类类是是是是边边边边的的的的方方方方向向向向与与与与链链链链的的的的方方方方向向向向相相相相同同同同，叫叫叫叫做做做做前前前前向向向向边边边边，前前前前向向向向边边边边的的的的集集集集合合合合记记记记做做做做+。二二二二类类类类是是是是边边边边的的的的方方方方向向向向与与与与链链链链的的的的方方方方向向向向相相相相反反反反，叫叫叫叫做做做做后后后后向向向向边边边边，后后向向边边边边的的集集合合记记做做。运筹学教程 如果链如果链如果链如果链 满足以下条件：满足以下条件：满足以下条件：满足以下条件：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 ,v,v3 3).).vtvsv1v2v3v442443322231运筹学教程定理定理定理定理11111111提供了一个寻求网络系统最大流的方法。如果网络提供了一个寻求网络系统最大流的方法。如果网络提供了一个寻求网络系统最大流的方法。如果网络提供了一个寻求网络系统最大流的方法。如果网络G G中有一个可行流中有一个可行流中有一个可行流中有一个可行流 f f，只要判断网络是否存在关于可行流只要判断网络是否存在关于可行流只要判断网络是否存在关于可行流只要判断网络是否存在关于可行流 f f 的增广链的增广链的增广链的增广链 。如果没有增广链，那么。如果没有增广链，那么。如果没有增广链，那么。如果没有增广链，那么f f一定是最大流。如有增一定是最大流。如有增一定是最大流。如有增一定是最大流。如有增广链，那么可以按照定理中必要性，不断改进和增大可行广链，那么可以按照定理中必要性，不断改进和增大可行广链，那么可以按照定理中必要性，不断改进和增大可行广链，那么可以按照定理中必要性，不断改进和增大可行流流流流f f 的流量，最终可以得到网络的流量，最终可以得到网络的流量，最终可以得到网络的流量，最终可以得到网络G G G G中的一个最大流。中的一个最大流。中的一个最大流。中的一个最大流。推论：推论：推论：推论：网络中的一个可行流网络中的一个可行流网络中的一个可行流网络中的一个可行流f*f*是最大流的充分必要条件是最大流的充分必要条件是最大流的充分必要条件是最大流的充分必要条件是，不存在关于是，不存在关于是，不存在关于是，不存在关于f f*的增广链。的增广链。的增广链。的增广链。在一个网络在一个网络在一个网络在一个网络G G中，最大流的流量等于分离中，最大流的流量等于分离中，最大流的流量等于分离中，最大流的流量等于分离v vs s 和和和和v vt t 的最小割的最小割的最小割的最小割集的割量。集的割量。集的割量。集的割量。运筹学教程 三、标号法三、标号法三、标号法三、标号法 从从从从网网网网络络络络中中中中的的的的一一一一个个个个可可可可行行行行流流流流f f f f 出出出出发发发发（如如如如果果果果G G G G中中中中没没没没有有有有 f f f f，可可可可以以以以令令令令f f f f 是是是是零零零零流流流流），运运运运用用用用标标标标号号号号法法法法，经经经经过过过过标标标标号号号号过过过过程程程程和调整过程，可以得到网络中的一个最大流。和调整过程，可以得到网络中的一个最大流。和调整过程，可以得到网络中的一个最大流。和调整过程，可以得到网络中的一个最大流。如如如如果果果果v v v vt t t t有有有有了了了了标标标标号号号号，表表表表示示示示存存存存在在在在一一一一条条条条关关关关于于于于f f f f 的的的的增增增增广广广广链链链链。如如如如果果果果标标标标号号号号过过过过程程程程无无无无法法法法进进进进行行行行下下下下去去去去，并并并并且且且且v v v vt t t t未未未未被被被被标标标标号号号号，则则则则表表表表示示示示不不不不存存存存在在在在关关关关于于于于f f f f 的的的的增增增增广广广广链链链链。这这这这样样样样，就就就就得得得得到到到到了了了了网网网网络络络络中的一个最大流和最小割集。中的一个最大流和最小割集。中的一个最大流和最小割集。中的一个最大流和最小割集。运筹学教程1 1 1 1 标号过程标号过程标号过程标号过程 在在在在标标标标号号号号过过过过程程程程中中中中，网网网网络络络络中中中中的的的的每每每每个个个个标标标标号号号号点点点点的的的的标标标标号号号号包包包包含含含含两两两两部部部部分分分分：第第第第一一一一个个个个标标标标号号号号表表表表示示示示这这这这个个个个标标标标号号号号是是是是从从从从那那那那一一一一点点点点得得得得到到到到的的的的，以以以以便便便便找找找找出出出出增增增增广广广广链链链链；第第第第二二二二个个个个标标标标号号号号是是是是为为为为了了了了用用用用来来来来确确确确定增广链上的调整量定增广链上的调整量定增广链上的调整量定增广链上的调整量 。标标标标号号号号过过过过程程程程开开开开始始始始，先先先先给给给给v vs s 标标标标号号号号（，+），一一一一般般般般地地地地，取取取取一一一一个个个个标标标标号号号号顶顶顶顶点点点点v vi i，对对对对v vi i所所所所有有有有未未未未标标标标号号号号的的的的邻邻邻邻接接接接点点点点v vj j按照下面条件进行处理：按照下面条件进行处理：按照下面条件进行处理：按照下面条件进行处理：运筹学教程 （1 1 1 1）如如如如果果果果在在在在弧弧弧弧（v vi i,v vj j）上上上上，f fij ij 0 0,那那那那么么么么给给给给v vj j标标标标号号号号（-v vi i,(vj vj)）.其中其中其中其中 (vjvj)=min=minf fji ji ,(vi vi)。重重重重复复复复以以以以上上上上步步步步骤骤骤骤，如如如如果果果果收收收收点点点点VtVtVtVt被被被被标标标标号号号号或或或或不不不不再再再再有有有有顶顶顶顶点点点点可可可可标标标标号号号号为为为为止止止止，则则则则标标标标号号号号法法法法结结结结束束束束。这这这这时时时时的的的的可可可可行行行行流流流流就就就就是是是是最最最最大流。大流。大流。大流。运筹学教程 2.2.调整过程调整过程令令 但是，如果但是，如果但是，如果但是，如果v v v vt t t t 被标上号，表示得到一条增广被标上号，表示得到一条增广被标上号，表示得到一条增广被标上号，表示得到一条增广链链链链，转入下一步调整过程。转入下一步调整过程。转入下一步调整过程。转入下一步调整过程。3.3.再去掉所有的标号，对新的可行流再去掉所有的标号，对新的可行流f=f ij,重重新进行标号过程，直到找到网络新进行标号过程，直到找到网络G G的最大流为止。的最大流为止。运筹学教程vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)例例 求图的网络最大流，弧旁的权求图的网络最大流，弧旁的权 数表示（数表示（cij,fij）。运筹学教程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=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)运筹学教程（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,=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)运筹学教程（5 5）检查检查检查检查v v1 1邻接点邻接点邻接点邻接点v v4 4:v4v4点点点点满足（满足（满足（满足（v v1 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)运筹学教程（6 6）检查检查检查检查v v4 4邻接点邻接点邻接点邻接点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,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)运筹学教程开始调整开始调整开始调整开始调整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)运筹学教程2.2.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 vtvt =3 2=1 在在-上上其它的不变其它的不变vsv2v5vtv4v1v6v3(5,5)(3,2)(3,1)(4,4)(5,4)(3,3)(2,2)(5,4)(4,4)(2,2)（，+）（+vsvsvsvs ，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得不到标号。得不到标号。得不到标号。得不到标号。流量：流量：流量：流量：w=w=f fs1s1+f fs2s2+f fs3s3=f f4t4t+f f5t5t+f f6t6t=11=11得到一个最小割，标点号集合：得到一个最小割，标点号集合：得到一个最小割，标点号集合：得到一个最小割，标点号集合：S=vS=vs s,v,v3 3 非标点号集合：非标点号集合：非标点号集合：非标点号集合：/S=vS=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(s,/s)=Cs1s1+C+Cs2s2+C+C3636=5+4+2=11=5+4+2=11运筹学教程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)运筹学教程求最大流的标号算法可以解决多发点多收点网络的最大流问题X1X2X3xmY1Y2Y3ynvsvt+运筹学教程小结1、最大流问题的概念、最大流-最小割定理。2、求最大流问题的标号算法。作业作业8.10,8.14