课程名称：《运筹学》第_18_讲次最大流问题授课题目本讲目的要求及重点难点：【目的要求】通过本讲课程的学习，掌握最大流问题中的相关概念，学会用标号法求最大流。[重点及难点】用标号法求最大流。内容[本讲课程的引入]在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。因而网络系统最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。[本讲课程的内容]一、基本概念定义19设一个赋权有向图D=（V,E），在V中指定一个发点vs和一个收点Vt，其它的点叫做中间点。对于D中的每一个弧（vi，y）EE，都有一个非负数cj，叫做弧的容量。我们把这样的图D叫做一个容量网络，简称网络，记做D=（V，E，C)。网络D上的流，是指定义在弧集合E上的一个函数f=(f(v,y)=(，其中(vi,)=f叫做弧(vi)上的流量。称满足下列条件的流为可行流：（1）容量条件：对于每一个弧（vi.y）EE，有0≤fj≤cij。(2)平衡条件：对于发点vs，有，Z_J,-ZJj,=W(p)EE(E对于收点v，有J,-Zj=-W(vv,)E(j.v,)EE对于中间点，有Jij-Zfji=0(M)EE(.)EE即对于中间点，满足：流出量=流入量，对发点和收点满足：从发点1s发出的物资总量减去其它点运往Vs的货物总量等于各点运往收点Vt的货物总量减去从Vt运往其它点的货物总量）
课程名称：《运筹学》 第 18 讲次 授课题目 最大流问题 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，掌握最大流问题中的相关概念，学会用标号法求最大 流。 [重点及难点] 用标号法求最大流。 内 容 [本讲课程的引入] 在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的 车辆流，城市给排水系统的水流问题等等。因而网络系统最大流问题是图与网络流 理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。 [本讲课程的内容] 一、 基本概念 定义 19 设一个赋权有向图 D=（V, E）,在 V 中指定一个发点 vs 和一个收点 vt ,其它的点叫做 中间点。对于 D 中的每一个弧（vi , vj）∈E ,都有一个非负数 i j c ,叫做弧的容量。我们把这样的图 D 叫做一个容量网络，简称网络，记做 D=（V，E，C）。 网络 D 上的流，是指定义在弧集合 E 上的一个函数 ( , ) { } i j i j f f v v f ，其中 f(vi ,vj ) =fi j 叫做弧(vi，vj)上的流量。 称满足下列条件的流 f 为可行流： （1）容量条件：对于每一个弧（vi ,vj）∈E，有 0 ≤ f ij ≤ cij 。 （2）平衡条件：对于发点 vs，有 v v E v v E s j js s j j s f f W ( , ) ( , ) 对于收点 vt ，有 v v E v v E t j jt t j j t f f W ( , ) ( , ) 对于中间点，有 v v E v v E i j ji i j j i f f ( , ) ( , ) 0 即对于中间点，满足：流出量＝流入量，对发点和收点满足：从发点 vs 发出的物资总量减去其它点 运往 vs 的货物总量等于各点运往收点 vt 的货物总量减去从 vt 运往其它点的货物总量）
内容任意一个网络上的可行流总是存在的。例如零流f=0，就是满足以上条件的可行流。网络系统中最大流问题，就是在给定的网络上寻求一个可行流了，其流量达到最大值。设流f=(fj)是网络D上的一个可行流。我们把D中fj=cj的弧叫做饱和弧，fj0的弧为非零流弧，fj=0的弧叫做零流弧。定义20容量网络G=（V，E，C），vs为始点，vt为终点。如果把V分成两个非空集合S,S，使v,ES，VeS，则所有始点属于S，而终点属于S的弧的集合，称为由S决定的截集，记作(S，S)。截集(S，S)中所有弧的容量之和，称为这个截集的容量，记为C(S，S)。例如在图8—17中，取S=(vs,V2), 则S=(v1,V3,V4,V,),于是,截集(S, 5) = (v,,1)),(v2,v4), (v2, v3))图8—17而截集容量C(S,S)=l+124+123=7+6+5=18。由于V的分解方法不同，所以截集就不相同，对应的截集的容量也不相同，其中容量最小的称为最小截集。二、（Fold一Fulkerson）定理由截集的定义可以看出：一个网络G中，任何一个可行流f的流量W，都小于或等于这个网络中任何一个截集(S，S)的容量。定义21容量网络G，若μ为网络中从vs到v的一条链，给μ定向为从vs到v1，μ上的边凡与μ方向相同的称为前向边，凡与μ方向相反的称为后向边，其集合分别用μu和μ表示，f是一个可行流，如果满足：[o≤Ji<cu(vi,v,)eμt[o<fu, ≤Cu(vi,y,)eμ则称μ为从vs到vt的（关于的）一条可增广链。关于网络的最大流与最小截集满足下面定理
内 容 任意一个网络上的可行流总是存在的。例如零流 f =0，就是满足以上条件的可行流。网络 系统中最大流问题，就是在给定的网络上寻求一个可行流 f ，其流量达到最大值。设流 f ={f ij} 是网络 D 上的一个可行流。我们把 D 中 f ij＝cij 的弧叫做饱和弧， f ij＜cij 的弧叫做非饱和弧。f ij＞0 的弧为非零流弧，f ij＝0 的弧叫做零流弧。 定义 20 容量网络 G =（V，E，C），vs 为始点，vt 为终点。如果把 V 分成两个非空集 合 S , S ，使 vs S , vt S ，则所有始点属于 S，而终点属于 S 的弧的集 合，称为由 S 决定的截集，记作 (S , S) 。截集 (S , S) 中所有弧的容量之和，称为这 个截集的容量，记为 C(S , S)。 S 例如在图 8—17 中，取 ( , ) 2 S v v s ，则 ( , , , ) 1 3 4 t S v v v v ，于是， 截集 (S , S ) (vs ,v1 ),(v2 ,v4 ), (v2 , v3 ) 而截集容量 C(S , S ) l s1 l 24 l 23 7 6 5 18。 由于 V 的分解方法不同，所以截集就不相同，对应的截集的容量也不相同，其中容量最小的 称为最小截集。 二、( Fold— Fulkerson )定理 由截集的定义可以看出：一个网络 G 中，任何一个可行流 f 的流量 W，都小于或等于这 个网络中任何一个截集 (S , S) 的容量。 定义 21 容量网络 G，若 为网络中从 vs 到 vt 的一条链，给 定向为从 vs 到 vt ， 上的边凡与 方向相同的称为前向边，凡与 方向相反的称为后向边，其集合 分别用 和 表示，f 是一个可行流，如果满足： 0 ( , ) 0 ( , ) i j i j i j i j i j i j f c v v f c v v 则称 为从 vs 到 vt 的（关于 f 的）一条可增广链。 关于网络的最大流与最小截集满足下面定理。 vs v1 v2 v4 v3 vt 3 7 4 5 5 6 3 7 8 图 8—17 S
内容定理6设f为网络G=（V，E，C）的任一可行流，流量为W，（S,S)为任一截集则有W0，则令y,ESt。在这种定义下，V,一定不属于s，否则，若,ES，则得到一条从,到v,的链μ，根据s的定义，μ中前向弧(v，V)上必有f,0，令Jcu-f当(vi,)为前向弧8,=(i)当(y，)为后向弧取8=min(8,],显然 8>0。我们把修改为：[i +8当(v)为前向弧8, =3-8当(v,)为后向弧[其余可以验证，仍为可行流，但的总流量等于于的流量加，与f*为最大流矛盾，所以y不属于s。令S"=V\S"，则v,eS。则得到一个截集(S"，S)，对截集中的弧(v,v)有
内 容 定理 6 设 f 为网络 G =（V，E，C）的任一可行流，流量为 W，(S , S) 为任一截集， 则有 W C(S , S ) 。（证明略） 由上面定理可知，如果网络上的一个可行流 * f 和网络中的一个截集 (S * , S*) ，满足条 件 W C(S * , S*) ，那么 f * 一定是 D 上的最大流，而 (S * , S*) 一定是 G 的最小截集。下 面给出的 Fold— Fulkerson 定理，实际上就说明了这个结论。 定理 7（Fold— Fulkerson 定理） 在任何网络中，从 s v 到 t v 的最大流的流量等于最小 截集的容量。 证明 设 * f 是一个最大流，流量为 W，用下面的方法定义点集 S * ， 令 * vs S ， 若点 * vi S ，且 i j i j f c * ，则令 * v j S ， 若点 * vi S ，且 0 * f j i ，则令 * v j S 。 在这种定义下， t v 一定不属于 S *，否则，若 * vt S ，则得到一条从 s v 到 t v 的链 ，根 据 S *的定义， 中前向弧 ( , ) i j v v 上必有 i j i j f c * ，后向弧上必有 0 * f j i ，令 当 为后向弧 当 为前向弧 ( , ) ( , ) * * i j i j i j i j i j i j f v v c f v v 取 min{ } i j ，显然 0 。 我们把 * f 修改为 * 1 f ： 其余 当 为后向弧 当 为前向弧 * * * ( , ) ( , ) i j i j i j i j i j i j f f v v f v v 可以验证， * 1 f 仍为可行流，但 * 1 f 的总流量等于 * f 的流量加 ，与 * f 为最大流矛盾， 所以 t v 不属于 S * 。 令 * * S V \ S ，则 * vt S 。则得到一个截集 ( , ) * * S S ，对截集中的弧 ( , ) i j v v 有
内容Ti-feu ves'yes.',es',v,es0但流量W又满足W= _f, -i]= ≥_c, =c(S",s)res'syesyesjes所以最大流的流量等于最小截集的容量。由定理7及可增广链的定义可得：推论可行流是最大流的充分必要条件是不存在从v到的（关于于的）一条可增广链。定理7的证明及推论为我们提供了一个寻求网络系统最大流的方法。亦即，如果网络G中有一个可行流于，只要判断网络是否存在关于可行流于的增广链。如果没有增广链，那么一定是最大流。如有增广链，那么可以按照定理7的证明，不断改进和增大可行流「的流量，最终可以得到网络中的一个最大流。3、求最大流的标号法标号法是从网络中的一个可行流厂出发（如果D中没有可行流f，可以令于是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。一、标号过程：1.给发点vs标号（0，+)。2．取一个已标号的点vi，对于vi一切未标号的邻接点y按下列规则处理：(1)如果边(y,v)eE，且fj,>0，那么给y标号（-V,8），其中：,=min(fjn0）(2）如果边(v,)eE，且fj<Cj，那么给y标号(+V,o,)，其中：, =min(c, -fu,,0,)。3.重复步骤（2），直到v，被标号或标号过程无法进行下去，则标号法结束。若v，被标号，则存在一条可增广链，转调整过程（第二步）；若v，未被标号，而标号过程无法进行下去，这时的可行流就是最大流二、调整过程设μ是一条从,到v,的可增广链，μ的前向边和后向边分别用和μ表示
内 容 * * * * * 0 , , v S v S c v S v S f j i i j i j i j 但流量 W 又满足 S j S v i v i j S j S v i v W f i j f ji c C S S , * * * * , * * * [ ] ( , ) 所以最大流的流量等于最小截集的容量。 由定理 7 及可增广链的定义可得： 推论 可行流 f 是最大流的充分必要条件是不存在从 vs 到 vt 的（关于 f 的）一条可增 广链。 定理 7 的证明及推论为我们提供了一个寻求网络系统最大流的方法。亦即，如果网络 G 中有一个可行流 f，只要判断网络是否存在关于可行流 f 的增广链 。如果没有增广链，那么 f 一定是最大流。如有增广链，那么可以按照定理 7 的证明，不断改进和增大可行流 f 的流量， 最终可以得到网络中的一个最大流。 3、 求最大流的标号法 标号法是从网络中的一个可行流 f 出发（如果 D 中没有可行流 f，可以令 f 是零流），运 用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。 一、标号过程： 1． 给发点 vs 标号（0，+∞）。 2． 取一个已标号的点 vi，对于 vi 一切未标号的邻接点 vj 按下列规则处理： （1）如果边 (v j ,vi ) E ，且 f j i 0 ，那么给 vj 标号 ( , ) i j v ，其中： min( , ) j ji i f （2）如果边 (vi ,v j ) E ，且 j i i j f c ，那么给 vj 标号 ( , ) i j v ，其中： min( , ) j i j i j i c f 。 3．重复步骤（2），直到 t v 被标号或标号过程无法进行下去，则标号法结束。 若 t v 被标号，则存在一条可增广链，转调整过程（第二步）；若 t v 未被标号，而标号过程 无法进行下去，这时的可行流就是最大流 二、调整过程 设 是一条从 s v 到 t v 的可增广链， 的前向边和后向边分别用 和 表示
内容设g, =min(cu-Ju, [(v,v,)eut, S, =minf, [(v,v)eμ如果μ上没有后向弧，则令8,=+00，取8=min(88,）[f,+? (v,y)eu*1. 令 f=J-8(vi,)eμ[Ui(v,v,)eμ2.去掉所有标号，回到第一步，对可行流重新标号。例8.10求图8-18所示网络中的最大流，每条边上的有序数表示(cij，J.)。解用(4 ,3)V2V4(5 ,3)(1,1)(3,3)(3 ,0)(1, 1)(5, 1)(2 ,1)iV3(2 ,2)图8—18标号法，1.标号过程（1）给Vs标号（0，+°0）。（2）检查vs的邻接点在边(vsV2)上，J2=C2=3,不具备标号条件。在边(vs-)上，J,=10，=min(f21,0,}=min(1,4)=1，故给标号（—),1)。（4）检查vz点的尚未标号的邻接点，在边（v2，V）上，J24=3<C24=4，=min(c24-J240,}=min(1,1)=1故给v4标号（+V2，1)；在边（vg，12）上，J2=1
内 容 设 min{ ( , ) } 1 ci j f i j vi v j ， min{ ( , ) } 2 f i j vi v j ， 如果 上没有后向弧，则令 2 ，取 min( , ) 1 2 1．令 ( , ) ( , ) ( , ) i j i j i j i j i j i j i j f v v f v v f v v f 2．去掉所有标号，回到第一步，对可行流重新标号。 例 8.10 求图 8—18 所示网络中的最大流，每条边上的有序数表示 ( , ) i j i j c f 。 解 用 标号法， 1．标号过程 （1）给 vs 标号（0，+∞）。 （2）检查 vs 的邻接点 在边(vs ,v2 )上，f s2= c s2 =3 , 不具备标号条件。 在边(vs ,v1 )上，f s1=1 0 , min{ , } min{1, 4} 1 2 21 1 v f v ，故给 v 2标号（－ v 1 , 1）。 （4）检查 v 2点的尚未标号的邻接点，在边（v 2，v 4）上，f 24 =3 ＜ c 24 = 4 , min{ , } min{1, 1} 1 4 24 24 2 v c f v ，故给 v4 标号（+ v 2，1）；在边（v 3 , v 2）上，f 32 =1 (1 ,1) v2 v1 v4 v3 vs vt 图 8—18 (3 , 3) (5 , 1) (1 , 1) (4 ,3) (2 , 2) (3 ,0) (5 ,3) (2 ,1)
内容>0，且0,=min(f32,,）=min(1,1)=1，故给v3标号（-y2，1)。（5）在v，V4中任意选一个，比如，在边（，）上，J=<c=2，且,=min(c-Jsr,0,）=min(1,1)=1，故给t标号(+y3，1)，因为v被标上号，根据标号法，转入调整过程。2．调整过程从ut开始，按照标号点的第一个标号，用反向追踪的方法，找出一条从vs到vt的可增广链μ，见图8一19中用双箭线表示的路线。从图中可以看出：μt=((vs,),(v3,)),μ=((v2,y), (V3,V2))所以,8,=min(4,1)=1,8, =min(1, 1)=1,8=min(8,8,)=1,在可增广链μ上做对可行流调整，得到：(+ v2, 1)(4 ,3)(-9,1) v2V4(5 ,3)1,1)(3,3)(+v3 1)(3 ,0)(0, +)(1,1)e(5,1)(2 ,1)13(+ys,4) (2,2)(-v, ,1)图8——19J,+8=1+1=2，在μ+上Js,+8=1+1=2，在μ+上f=f2-8=1-1=0，在μ上f2-8=1-1=0，在μ上其它不变调整后的可行流f如图8一20所示，对这个可行流重新进行标号过程，寻求可增广链。首先给vs标号（0，+）。检查vs的邻接点，给v1标号（+vs，3)，再检查v点的尚未标号的邻接点，在边（y）上，J=C13=2，边（，）上，J1=0都不具备标号条件，所以，标号过程无法进行下去，不存在从vs到vt的可增广链，算法结束
内 容 ＞0，且 min{ , } min{1, 1} 1 3 32 2 v f v ，故给 v3 标号（－v 2，1）。 （5）在 v 3 ，v 4 中任意选一个，比如 v 3 ，在边（v 3 , vt）上，f 3t =1< c 3t =2 ，且 min{ , } min{1, 1} 1 3 3 3 v c t f t v t ，故给 vt 标号(+ v 3 ，1)，.因为 vt 被标上号，根据 标号法，转入调整过程。 2．调整过程 从 vt 开始，按照标号点的第一个标号，用反向追踪的方法，找出一条从 vs 到 vt 的可增广链 ，见图 8—19 中用双箭线表示的路线。从图中可以看出： {( , ) , ( , )} s 1 3 t v v v v ， {( , ) , ( , )} 2 1 3 2 v v v v 所以， 1 min{4 , 1} 1， 2 min{1, 1} 1， min{ 1 , 2 } 1， 在可增广链 上做对可行流调整，得到： 其它不变 ，在 上 ，在 上 ，在 上 ，在 上 1 1 0 1 1 0 1 1 2 1 1 2 3 2 2 1 3 1 f f f f f t s 调整后的可行流 f 如图 8—20 所示，对这个可行流重新进行标号过程，寻求可增广链。 首先给 vs 标号（0，+∞）。检查 vs 的邻接点，给 v1 标号（+ vs , 3），再检查 v1 点的尚未 标号的邻接点，在边（v 1 ,v3）上，f 13= c 13=2，边（v 2 ，v 1）上，f 21 = 0 都不具备标号条件，所 以，标号过程无法进行下去，不存在从 vs 到 vt 的可 增广链，算法结束。 (1 ,1) v2 v1 v4 v3 vs vt 图 8——19 (3 , 3) (5 , 1) (1 , 1) (4 ,3) (2 , 2) (3 ,0) (5 ,3) (2 ,1) （0，+∞） （－v 1 , 1） （+ vs , 4） （－v 2 ，1） （+ v2，1） (+ v3 ，1)
容内 (4 ,3)(5 ,3)(1,0)13(3 ,0)(1, 0)(2 ,2)52V3(2,2)S图8——20这时，网络中的可行流f'就是最大流f*，最大流量W=f，+f，2=5，同时得到G的最小截集（S,S"），其中s是标号点的集合S=(vs,），5=(V2,V3,V4,V）是未标号点的集合。由上面可以看到，用标号法寻找可增广链求最大流的结果，同时得到一个最小截集。最小截集的容量的大小影响总的运输量的大小，所以最小截集是这些路中的咽喉部分，或者称为瓶颈。因此，为提高总的运输量，必须首先考虑改善最小截集中各边的输送状况，提高它们的通过能力。【本讲小结】最大流问题的标号法可以推广到含有无向边的网络，以及多发点和多收点的网络中应用。网络上的流是由发点V，到收点v的，它是有方向的，因此网络流一般总在有向图上进行。实际网络有些边可能是无向的。在求含有无向边网络的最大流问题时，首先要把无向边变成等价的有向边，这时可用一对容量相等方向相反的边代替，然后用标号法计算。[本讲课程的作业]】求图所示网络的最大流V11V4V2310
内 容 这时，网络中的可行流 f 就是最大流 * f ，最大流量 W f s1 f s2 5， 同时得到 G 的 最 小 截 集 ( , ) * * S S ，其中 S * 是标号点的集合 ( , ) 1 * S v v s ， ( , , , ) 2 3 4 * t S v v v v 是未标号点的集合。 由上面可以看到，用标号法寻找可增广链求最大流的结果，同时得到一个最小截集。最 小截集的容量的大小影响总的运输量的大小，所以最小截集是这些路中的咽喉部分，或者称 为瓶颈。因此，为提高总的运输量，必须首先考虑改善最小截集中各边的输送状况，提高它 们的通过能力。 [本讲小结] 最大流问题的标号法可以推广到含有无向边的网络，以及多发点和多收点的网络中应 用。网络上的流是由发点 s v 到收点 t v 的，它是有方向的，因此网络流一般总在有向图上进行。实际 网络有些边可能是无向的。在求含有无向边网络的最大流问题时，首先要把无向边变成等价的有向 边，这时可用一对容量相等方向相反的边代替，然后用标号法计算。 [本讲课程的作业] 求图所示网络的最大流 vs v1 vt v5 v4 v3 v2 4 3 10 4 1 3 3 5 4 2 7 8 (1 ,0) v2 v1 v4 v3 vs vt 图 8——20 (3 , 3) (5 , 2) (1 , 0) (4 ,3) (2 , 2) (3 ,0) (5 ,3) (2 ,2) S