运输网络最大流问题ppt课件.ppt

,运输网络最大流问题,本节内容的安排,一、引言,1.应用背景在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题,控制系统中的信息流问题，常见的人流，物流，水流，气流，电流，现金流等。在一定条件下,求解给定系统的最大流量,就是网络最大流问题.,2.问题描述连通网络 G(V, A) 中有 m 个节点, n条弧, 弧 eij 上的流量上界为 cij , 求从起始节点 vs 到终点 vt 的最大流量的问题就是 最大流问题。,引例：如下输水网络，南水北调工程，从v1到v6送水，弧旁数字为管道容量，问应当如何输水使得流量最大？,1、网络与流设一个赋权有向图D=（V, A）,在V-图中的节点，中指定一个发点vs和一个收点vt ,其它的点叫做中间点。对于A-图中的弧，D中的每一个弧（vi , vj）A ,都有一个非负数cij ,叫做弧的容量- cij 。我们把这样的图D叫做一个容量网络，简称网络，记做D=（V，A，C）。弧的容量：是对网络上的每条弧(vi,vj)都给出一个最大的通过能力，记为c (vi,vj)或简写为cij 。,二、基本概念,对有多个发点和多个收点的网络,可以另外虚设一个总发点和一个总收点,并将其分别与各发点、收点连起来（见图），就可以转换为只含一个发点和一个收点的网络。,所以一般只研究具有一个发点和一个收点的网络,流：加在网络各条弧上的一组负载量,即弧线上的流量f(vi,vj)：加在弧(vi,vj)上的负载量简记为fij， fij=0.网络上的流：是指定义在弧集合上的一个函数f=f(vi,vj),注意：弧的流量f(vi,vj)：表示弧(vi,vj)上每单位时间内的实际通过能力弧的容量c(vi,vj)：表示弧（vi,vj)上每单位时间内的最大通过能力零流：网络上所有的fij = 0,例如下图表示的就是这个网络上的一个流（运输方案），每一个弧上的流量fij就是运输量。例如：f12=1 , f13=2 , f24=3 等等。,对于实际的网络系统上的流，有几个显著的特点：(1)发点的净流出量和收点的净流入量必相等。(2)每一个中间点的流入量与流出量的代数和等于零。(3)每一个弧上的流量不能超过它的最大通过能力 （即容量）,称满足下列条件的流为可行流：（1）容量限制条件：对于每一个弧（vi ,vj）A 有 0f(vi,vj) c(vi,vj) （简记为0 fij cij）,2、可行流与最大流,（2）平衡条件：,总流量v(f)=发点的净输出量v(f) =收点的净输入量-v(f)容量网络的可行流总是存在的，如当所有弧的流均取零，即对所有的i,j,有f(vi,vj)=0就是一个可行流,可行流中 f ijc ij 的弧叫做饱和弧，f ijc ij的弧叫做非饱和弧。f ij0 的弧为非零流弧，f ij0 的弧叫做零流弧。,图中 谁是零流弧，谁是饱和弧？,就是要求一个流fij ,使其流量v(f)达到最大,并且满足 0 fij cij,网络的最大流:,求网络的最大流，即是指满足容量限制条件和平衡条件的条件下，使v(f)值达到最大.,容量网络D，若给定向为从vs到vt，图上的弧分为两类：凡与方向相同的称为前向弧，凡与方向相反的称为后向弧，其集合分别用+和-表示。,链的方向：若是联结vs和vt的一条链， 定义链的方向是从vs到vt。,3、增广链,增广链：一条链中的可行流，如果满足：,中的每一条弧都是非饱和弧,中的每一条弧都是非零流弧,则称为从vs到vt 的关于f 的一条增广链。,=(v1,v2,v3,v4,v5,v6),+=(v1,v2) ,(v2,v3), (v3 , v4),(v5,v6),- =(v5,v4),是一个增广链,显然图中增广链不止一条,4、截集与截量,我们在图中画一条线，使 所有始点属于Vs，而终点属于Vt ，,1=(v4,v5,v6),1=(v4,v5,v6),截集为所有被割断的弧线，黄色弧集：,截集为所有被割断的弧线，弧线上的容量之和，称作截量。,截量为24,设 ，,则截集为,截量为20,对应的截量也不相同，其中截量最小的截集称为最小截集。,截集与可行流无关，而只与网络本身有关最小截 量是个定值,结论2：可行流f *fij*是最大流，当且仅当D中不存在关于f *的增广链。,结论1：,即任何一个可行流的流量都不会超过任一截集的容量,总结：对最大流问题有下列结论和定理：,三、最大流问题的标号法,步骤：判断是否存在增广链,并设法把增广链找出来,并予以调整,最终使图中无增广链.此算法从网络中的一个可行流f 出发（如果D中 没有 f，可以令f 是零流），运用标号法，经过标号过程和调整过程，最终可以得到网络中的一个最大流。,在标号过程中，网络中的点分为两种：已标号的点（分为已检查和未检查）和未标号的点。每个标号点的标号包含两部分：第一个标号表示这个标号是从那一点得到的，以便找出增广链。第二个标号是从上一个标号点到这个标号点的流量的最大允许调整值，是为了用来确定增广链上的调整量。,1 标号过程,标号过程开始，先给vs 标号（0，+）。这时，vs 是标号未检查的点，其它都是未标号点。如果vt有了标号，表示存在一条关于f 的增广链。如果标号过程无法进行下去，并且vt未被标号，则表示不存在关于f 的增广链。此时，就得到了网络中的一个最大流。,例 求图10-25的网络最大流，弧旁的权数 表示（cij , fij）。,解： 1. 标号过程。1）首先给vs标号（0，+） 2）看vs : 在弧(vs ,v2)上,fs2=cs3=3 , 不具备标号条件。 在弧(vs ,v1)上 , fs1=1 cs1= 5 , 故给v1标号（vs , l(v1), 其中l(v1)表示最大可调整量=min+, 5 1=4. v1标号为：（vs , 4），此时vs为已检查的标号点。,。（3）看v1:在弧（v1 ,v3）上,f13=c13=2,不具备标号条件. 在弧(v2 ,v1)上,f21 =1 0 , 故给v2标号（-v1 , l(v2)）, 其中l (v2 )=minl(v1) , f21 = min 4 , 1 = 1. v2标号（-v1 , 1），此时v1为已检查的标号点,（4）看v2:在弧（v2 ,v4）上，f24 =3 0 ,故给v3标号（-v2，l(v3) , 其中 l (l(v3 )= minl(v2) , f32 = min1 , 1 =1。,（5）在v3 ,v4中任意选一个，如v3 ,在弧（v3 , vt）上，f3t =1 c3t =2, 故给vt标号(v3 ,l(vt), 其中l(vt)=minl(v3),(c3t-f3t)=min1,1=1. 因为vt被标上号，根据标号法，转入调整过程。,(v3 , 1),（1）如果在前向弧（vi ,vj）上，有fij 0,那么给vj标号（-vi , l(vj)）.其中l (vj)=min l(vi), fji .这时，vj 成为标号未检查点。 于是vi 成为标号已检查的点。,总结标号过程,重复以上步骤，如果所有的标号都已经检查过，而标号过程无法进行下去，则标号法结束。这时的可行流就是最大流。但是，如果vt 被标上号，表示得到一条增广链，转入下一步调整过程。,2.调整过程 利用反向追踪找增广链，调整增广链的流量， 去掉旧的标号，对新的可行流重新进行标号。具体做法如下：（1） 按照vt 和其它已检查的标号点的第一个标号，反向追踪，找出增广链 ，确定调整量。（2),得新的可行流。 (3)再去掉所有的标号，对新的可行流f =f ij,重新进行标号过程，直到找到网络D的最大流为止。,非增广链上的弧,(5 , 2),(1 , 0),(1 , 0),(2 , 2),(cij , fij),增广链的调整量为1，则有：,调整后的可行流f *如图,再对这个 可行流从新进行标号过程，寻找增广链。一直到标号过程无法进行下去，不存在从vS到vt的增广链，算法结束。,(0 , +),(vs , 3),最大流的流量v(f * )= fs1+fs2=5.最小截集它的容量也为5.,得到的截集为最小截集（V1， ），其中V1是标号的集合， 是未标号的集合。,此时，网络中的可行流f * 即是最大流，,(0,),(s,2),(-v2,2),(v1,2),(-v3,1),(v4,1),例:用标号法求下图中st的最大流量,并找出该网络的最小割.,(v2)=min(s),(cs2-fs2)=2(v1)=min(v2),f12= min2,4=2(v3)=min(v1), (c13-f13)=min2,5=2(v4)=min(v3),f43= min2,1=1(t)=min(v4), (c4t-f4t)= min1,2=1,V*(f)= =,s,v2,v4,v3,v1,t,7(6),8(8),9(5),5(3),2(0),9(9),6(0),10(9),5(5),(-v2,1),(0, ),(v1,1),(s,1),(0+,),(s+,6),(2,6),(3+,1),(4+,1),(0+,),(s+,5),(2+,2),(5,2),(4+,2),例：,(0+,),(s+,3),(2,3),最小截集,最大流的流量为：14+12+5+4=35,例： 求下图所示网络的最大流,解：给定初始可行流为全零流，即 f （0） = 0,给vs 标号（0，+），检查 vs ： 给 v1 标号(vs ,4) , 给 v2 标号(vs , 3) , 给 v3 标号(vs , 10) ,(0 , +),(vs , 4),(vs , 3),(vs , 10),检查 v1 ：给 v4 标号(v1 , 1) ，检查完毕；,(v1 , 1),检查 v2 ：给 v5 标号(v2 , 3) ，检查完毕；,(v2 , 3),检查 v5 ：给 vt 标号(v5 , 3) ，检查完毕；,(v5 , 3),因为终点 vt 已标号，故找出一条从vs到vt的增广链： vs v2 v5 vt . 取 = 3,(vs , 4),(v1 , 3),(vs , 10),(v1 , 1),(v2 , 2),(0 , +),(v5 , 2),(vs , 2),(v3 , 3),(vs , 10),(v2 , 3),(v3, 4),(0 , +),(v4 , 3),(0 , +),(vs , 2),(vs , 7),(v3, 4),(v5, 2),(v5, 3),(0 , +),(vs , 2),(vs , 4),(v1 , 1),(v1 , 1),(v4 , 1),(0 , +),(vs , 4),(vs , 1),(v3 , 1),(v5 , 1),(v4 , 1),(0 , +),(vs , 1),(vs , 3),(v1 , 1),(v2 , 1),(v4 , 1),(0 , +),(vs , 3),首先给vs标号（0，+），看vs ,给v3标号（vs ,3）。看v3,在弧（v3 ,v2）上，f32=c32,弧（v3 ,v5）上，f35= c35,均不符合条件。因此标号过程无法进行下去，不存在从vS到vt的增广链，算法结束。最大流量 f * =4+3+3+4= 14 。,考试1：求下图所示网络中的最大流，弧旁数为,考试2：求下图所示网络中的最大流，弧旁数为,