1、 课程讲授：黄玉诚运筹学中国矿业大学中国矿业大学(北京北京)2023-1-14第六章 图与网络分析n第一节第一节 图的基本知识图的基本知识n第二节第二节 树树n第三节第三节 最短路问题最短路问题n第四节第四节 网络最大流问题网络最大流问题n第五节第五节 最小费用最大流问题最小费用最大流问题 2023-1-14第四节 网络最大流问题8431763511v1v2v3v5v4v6105图图10-23是联结某产品产地是联结某产品产地v1和销地和销地v6的交通网，每一弧的交通网，每一弧(vi，vj)代表从代表从vi到到vj的运输线，产品经这条弧由的运输线，产品经这条弧由vi输送到输送到vj，弧旁的数字表
2、示这条运输线的最大通过能力。现在，弧旁的数字表示这条运输线的最大通过能力。现在要求制定一个运输方案使从要求制定一个运输方案使从v1运到运到v6的产品数量最多。的产品数量最多。图图10-232023-1-14v1v2v3v5v4v6图图10-2410-24给出了一个运输方案，每条弧旁的数字表给出了一个运输方案，每条弧旁的数字表示每条运输线上的运输数量。这个方案使示每条运输线上的运输数量。这个方案使8 8个单位个单位的产品从的产品从v v1 1运到运到v v6 6。在这个运输网络中，从。在这个运输网络中，从v v1 1到到v v6 6的最大输送量是多少呢的最大输送量是多少呢?8431763511v
3、1v2v3v5v4v6105图图10-23图图10-242023-1-14一、一、基本概念与基本定理基本概念与基本定理1、网络与流、网络与流 定义定义1 给一个有向图给一个有向图D=(V,A)，在，在V中指定了一点，中指定了一点，称为称为发点发点(记为记为vs)，和另一点，称为，和另一点，称为收点收点(记为记为vt)，其余，其余的点叫的点叫中间点中间点。对于每一个弧。对于每一个弧(vi，vj)A,对应有一个对应有一个c(vi，vj)0(或简写为或简写为cij)，称为弧的，称为弧的容量容量。通常把这样的。通常把这样的D叫作一个叫作一个网络网络。记作。记作D=(V，A，C)。对对D中的任一弧中的任
4、一弧(vi，vj)有流量有流量f(vi，vj)(有时也简记有时也简记作作fij)，称集合，称集合f=fij为网络为网络D上的一个上的一个流流。2023-1-142 2、可行流与最大流、可行流与最大流定义定义2 满足下述条件的流满足下述条件的流 f 称为称为可行流可行流：1）容量限制条件：对每一弧）容量限制条件：对每一弧(vi，vj)A0fijcij可行流可行流0),(),(AvvjiAvvijijjiff2 2）平衡条件：平衡条件：对于中间点：流出量流入量，即对每个对于中间点：流出量流入量，即对每个i(is,t)i(is,t)有有2023-1-14对于发点对于发点v vs s，fvffAvvj
5、sAvvsjsjjs),(),(式中式中v v(f)(f)称为这个可行流的流量，即称为这个可行流的流量，即发点的净发点的净输出量输出量(或收点的净输入量或收点的净输入量)。于是对于收点于是对于收点v vt t，fvffAvvtjAvvjtjttj),(),(fvffAvvjtAvvtjtjjt),(),(或或2023-1-14 所谓所谓最大流问题最大流问题就是在网络中，寻找流量最大的可就是在网络中，寻找流量最大的可行流，即：求一个流行流，即：求一个流ffijij 使其流量使其流量v(f)v(f)达到最大，并达到最大，并且满足且满足0 0f fijijc cijij (v (vi i，v vj
6、j)A)A tifvtsisifvffjiij,0最大流最大流 可行流总是存在的，例如可行流总是存在的，例如(f fijij)=0就是一个流量为就是一个流量为0的可行流。的可行流。2023-1-143 3、增广链、增广链 若给一个可行流若给一个可行流f=fij，我们把网络中使，我们把网络中使 fij=cij 的的弧称为弧称为饱和弧饱和弧，使，使fij0的弧称为的弧称为非零流弧非零流弧。若若是网络中联结发点是网络中联结发点v vs s和收点和收点v vt t的一条链，我们的一条链，我们定义链的方向是从定义链的方向是从v vs s到到v vt t，则链上的弧被分为两类：一，则链上的弧被分为两类：一
7、类是弧的方向与链的方向一致，叫作类是弧的方向与链的方向一致，叫作前向弧前向弧。前向弧的。前向弧的全体记为全体记为+。另一类弧与链的方向相反，称为。另一类弧与链的方向相反，称为后向弧后向弧。后向弧的全体记为后向弧的全体记为-。2023-1-14 定义定义3 设设f是一个可行流，是一个可行流，是从是从vs到到vt的一条链，若的一条链，若满足下列条件满足下列条件,称之为称之为(关于可行流关于可行流 f 的的)一条一条增广链增广链。在弧在弧(vi，vj)+上，上，0fijcij，即，即+中每一弧是非饱中每一弧是非饱和弧。和弧。在弧在弧(vi，vj)-上，上，0fijcij，即，即-中每一弧是非零中每一
8、弧是非零流弧。流弧。图图10-24中，链中，链=(v1,v2,v3,v4,v5,v6)是一条增广链。因是一条增广链。因为为+和和-中的弧满足增广链的条件。如：中的弧满足增广链的条件。如：(v1,v2)+,f12=50。2023-1-144 4、截集与截量、截集与截量 设设S,TVS,TV，ST=ST=，我们把始点在，我们把始点在S S，终点在，终点在T T中的所有弧构成的集合，记为中的所有弧构成的集合，记为(S(S，T)T)。_1V_1V_1V 定义定义4 4 给网络给网络D=(VD=(V，A A，C)C)，若点集，若点集V V被剖分被剖分为两个非空集合为两个非空集合V V1 1和和 ，使，使
9、v vs sVV1 1，v vt t ，则把，则把弧集弧集(V(V1 1,),)称为是称为是(分离分离v vs s和和v vt t的的)截集截集。可以看出，从网络中去掉任一截集，则从可以看出，从网络中去掉任一截集，则从v vs s到到v vt t便不存在路。所以，截集是从便不存在路。所以，截集是从v vs s到的到的v vt t必经之路。必经之路。2023-1-14定义定义5 5 给一截集给一截集(V(V1 1,),)，把截集，把截集(V(V1 1,),)中所有中所有弧的容量之和称为这个截集的容量弧的容量之和称为这个截集的容量(简称为截量简称为截量)，记为记为c(Vc(V1 1,),)，即，即
10、 )V,(V),(1111,jivvijcVVc_1V_1V_1V 任何一个可行流的流量任何一个可行流的流量v v(f)(f)都不会超过任一截都不会超过任一截集的容量。即集的容量。即 11,VVcfv2023-1-14 显然，若对于一个可行流显然，若对于一个可行流f*，网络中有一个截集，网络中有一个截集(V1*,)，使，使v(f*)=c(V1*,),则则f*必是最大流，而必是最大流，而(V1*,)必定是必定是D的所有截集中容量最小的一个，即的所有截集中容量最小的一个，即最小截集。最小截集。*_1V*_1V*_1V2023-1-14定理定理1 可行流可行流f*是最大流的充分必要条件是不存在从是最
11、大流的充分必要条件是不存在从v vs s到到v vt t的的(关于关于f*)增广链。增广链。证明：证明：(一一)必要性必要性 用反证法。用反证法。可行流可行流f*是最大流，假设存在从是最大流，假设存在从v vs s到的到的v vt t的的(关于关于f*)增广链。增广链。令：令：*min,minminijijijffc2023-1-14由增广链的定义，可知由增广链的定义，可知0,令网络上的另一个流：令网络上的另一个流：jiijjiijjiijijvvfvvfvvff,*仍为可行流仍为可行流(即满足容量限制条件与平衡条件即满足容量限制条件与平衡条件)，但，但 的总流量等于的总流量等于 的流量加的流
12、量加，即，即*ijf*ijf*ijf*ijijfvfv这与这与 是最大流的前提矛盾。是最大流的前提矛盾。*ijf2023-1-14 (二二)充分性：若不存在关于充分性：若不存在关于f*增广链，那么增广链，那么f*是最是最大流。大流。因为不存在关于因为不存在关于f*增广链，那么在这种定义下，增广链，那么在这种定义下，。*1Vvt 令：令：,*1*1VVV 则则 。*1Vvt因此，可以得到一个截集因此，可以得到一个截集 。*1*1,VV*1V 令：令：;*1Vvs 若若,*1Vvi且且,*ijijcf则令则令,*1Vvj 若若,*1Vvi且且,0*jif则令则令,*1Vvj 用下面方法定义点集用下
13、面方法定义点集 2023-1-14显然有显然有*1*1*1*1*,0,VVvvVVvvcfjijiijij那么，可行流那么，可行流f*上的流量上的流量*1*1,),(*,*1*1VVccfvVVvvijji则则f*必然是最大流。必然是最大流。2023-1-14 最大流量最小截量定理：最大流量最小截量定理：任一个网络任一个网络D D中，从中，从v vs s到到v vt t的最大流的流量等于分离的最大流的流量等于分离v vs s，v vt t的最小截集的容量。的最小截集的容量。增广链的实际意义增广链的实际意义是：沿着这条链从是：沿着这条链从v vs s到到v vt t输送的输送的流，还有潜力可挖，
14、只需按照流，还有潜力可挖，只需按照定理定理1 1证明中的调整方法，证明中的调整方法，就可以把流量提高，调整后的流，在各点仍满足平衡条就可以把流量提高，调整后的流，在各点仍满足平衡条件及容量限制条件，即仍为可行流。件及容量限制条件，即仍为可行流。这样就这样就得到了一个寻求最大流的方法得到了一个寻求最大流的方法：从一个可行：从一个可行流开始，寻求关于这个可行流的增广链，若存在，则可流开始，寻求关于这个可行流的增广链，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的增广行流要大，重复这个过程，直到
15、不存在关于该流的增广链时就得到了最大流。链时就得到了最大流。2023-1-14寻求最大流的思路寻求最大流的思路：利用定理：利用定理1中对中对V1*定义，根据定义，根据vt是是否属于否属于V1*来判断来判断D中有无关于中有无关于f的增广链。的增广链。实际计算时，可以用给顶点标号的方法来确定属实际计算时，可以用给顶点标号的方法来确定属于于V1*的点。的点。在标号过程中，有标号的顶点表示是在标号过程中，有标号的顶点表示是V1*中的点，中的点，没有标号的点表示不是没有标号的点表示不是V1*中的点。一旦中的点。一旦vt有了标号，就有了标号，就表明找到一条增广链；表明找到一条增广链；如果标号过程进行不下去
16、，而如果标号过程进行不下去，而vt尚未标号，则说明尚未标号，则说明不存在增广链，于是得到最大流。而且同时也得到一个不存在增广链，于是得到最大流。而且同时也得到一个最小截集。最小截集。2023-1-14二、二、寻求最大流的标号法寻求最大流的标号法 设已有一个可行流设已有一个可行流(若网络中没有给定若网络中没有给定f，则可以设，则可以设f是零流是零流)，从这个可行流开始，标号法的过程分为两步：，从这个可行流开始，标号法的过程分为两步：第一步：标号过程，通过标号来寻找增广链；第一步：标号过程，通过标号来寻找增广链；第二步：调整过程，沿增广链调整第二步：调整过程，沿增广链调整 f 以增加流量。以增加流
17、量。2023-1-14 在标号过程中，网络中的点分为两类：在标号过程中，网络中的点分为两类：(1)标号点标号点(又分为已检查和未检查两种又分为已检查和未检查两种)。每个标号。每个标号点的标号内容包含两部分：点的标号内容包含两部分：标号的第一部分标号的第一部分表明它的标表明它的标号是从哪一点得到的，以便找出增广链；号是从哪一点得到的，以便找出增广链；标号的第二部标号的第二部分分是为确定增广链的调整量是为确定增广链的调整量用的。用的。(2)未标号点未标号点。1 1、标号过程、标号过程 2023-1-14标号过程标号过程:(1)给发点给发点vs标上标上(0，+)；这时；这时vs是标号而未检查是标号而
18、未检查的点，其余都是未标号点。的点，其余都是未标号点。(2)取一个标号而未检查的点取一个标号而未检查的点vi，对于，对于vi的所有未给的所有未给标号的相邻点标号的相邻点vj按下列规则处理：按下列规则处理：(a)若在弧若在弧(vi,vj)上，上，fij0，则给，则给vj标号标号(-vi，l(vj)，这，这里里l(vj)=min(l(vi),fij。这时点。这时点vj成为标号而未检查的点。成为标号而未检查的点。这样，这样，v vj j成为标号而已检查过的点。成为标号而已检查过的点。2023-1-14 若若vt未获得标号，而标号过程无法进行时，则算法未获得标号，而标号过程无法进行时，则算法结束，这时
19、的可行流结束，这时的可行流 f 就是最大流。就是最大流。(3)重复步骤重复步骤(2)，直到，直到vt被标上号，表明得到一条从被标上号，表明得到一条从vs到到vt的增广链的增广链，转入调整过程。，转入调整过程。2023-1-14 例如：设例如：设vt的第一个标号为的第一个标号为vk，则弧，则弧(vk,vt)是是上的上的弧。接下来检查弧。接下来检查vk的第一个标号，若为的第一个标号，若为vi，则找出，则找出(vi,vk)。再检查再检查vi的第一个标号，依此下去，直到的第一个标号，依此下去，直到vs为止。这时被为止。这时被找出的弧就构成了增广链找出的弧就构成了增广链。1 1、调整过程、调整过程 (1
20、)找出增广链找出增广链。按。按vt及其它点的第一个标号，利用及其它点的第一个标号，利用“反向追踪反向追踪”的办法，找出增广链的办法，找出增广链。2023-1-14 (2)在增广链上调整流量在增广链上调整流量。令调整量令调整量为为 l(vt)，即，即vt的第二个标号。的第二个标号。jiijjiijjiijijvvfvvfvvff,(3)去掉所有的标号，对新的可行流去掉所有的标号，对新的可行流 ，重，重新进入标号过程。新进入标号过程。ijff 2023-1-14例例 用标号法求图用标号法求图10-25所示网络的最大流。弧旁的所示网络的最大流。弧旁的数是数是(cij,fij)。解解 (一一)标号过程
21、标号过程 (1)首先给首先给vs标上标上(0，+)vsv2v1v3vt(3,3)(5,1)(4,3)v4(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)(0,+)图图10-252023-1-14(2)检查检查vs。vsv2v1v3vt(3,3)(5,1)(4,3)v4(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)(0,+)(vs,4)弧弧(vs，v1)上，上，fs11，cs1=5，fs10，则给，则给v2记下标号为记下标号为(-v1,l(v2)，这里，这里 l(v2)=minl(v2),f21=min4，1=1 在弧在弧(v1，v3)上，上，f13=2，c13=2，不
22、满足标号条件。，不满足标号条件。2023-1-14(4)检查检查v2。vsv2v1v3vt(3,3)(5,1)(4,3)v4(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)(0,+)(vs,4)(-v1,1)(v2,1)(-v2,1)在弧在弧(v2，v4)上，上，f21=3，c24=4，f240，给，给v3标号：标号：(-v2,l(v3)，l(v3)=minl(v2),f32=min1,1=12023-1-14(5)在在v3,v4中任选一个进行检查中任选一个进行检查。(v4,1)vsv2v1v3vt(3,3)(5,1)(4,3)v4(2,2)(1,1)(1,1)(3,0)(5,3)
23、(2,1)(0,+)(vs,4)(-v1,1)(v2,1)(-v2,1)例如，在弧例如，在弧(v4，vt)上，上，f4t=3，c4t=5，f4t c4t,给给vt标标号为号为(v4,l(vt)，这里，这里l(vt)minl(v4),(c4t-f4t)=min1,2=1因因vt有了标号，故转入调整过程。有了标号，故转入调整过程。2023-1-14(二二)调整过程调整过程 (v4,1)vsv2v1v3vt(3,3)(5,1)(4,3)v4(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)(0,+)(vs,4)(-v1,1)(v2,1)(-v2,1)(1)按点的第一个标号找到一条增广链。按
24、点的第一个标号找到一条增广链。2023-1-14(v4,1)vsv2v1v3vt(3,3)(5,1)(4,3)v4(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)(0,+)(vs,4)(-v1,1)(v2,1)(-v2,1)(2)在增广链上调整流量。在增广链上调整流量。在增广链上在增广链上 +=(vs，v1),(v2，v4),(v4，vt)-=(v2，v1)2023-1-14(v4,1)vsv2v1v3vt(3,3)(5,1)(4,3)v4(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)(0,+)(vs,4)(-v1,1)(v2,1)(-v2,1)按按=1在在上调整上调
25、整f。413413;21144242411ttssffffff +上：上：-上：上：0112121ff2023-1-14vsv2v1v3vt(3,3)(5,1)(4,3)v4(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)vsv2v1v3vt(3,3)(5,2)(4,4)v4(2,2)(1,0)(1,1)(3,0)(5,4)(2,1)调整后的网络图如下调整后的网络图如下:2023-1-14vsv2v1v3vt(3,3)(5,2)(4,4)v4(2,2)(1,0)(1,1)(3,0)(5,4)(2,1)(0,+)对新的可行流再进入标号过程，寻找增广链对新的可行流再进入标号过程，寻找增
26、广链(一一)标号过程标号过程 (1)首先给首先给vs标上标上(0，+)2023-1-14vsv2v1v3vt(3,3)(5,2)(4,4)v4(2,2)(1,0)(1,1)(3,0)(5,4)(2,1)(0,+)(2)检查检查vs。(vs,3)弧弧(vs，v1)上，上，fs12，cs1=5，fs1 cs1,则则v1的标号为的标号为(vs,l(v1)，其中，其中，l(v1)=minl(vs),(cs1-fs1)=min+,5-3=3 在弧在弧(vs，v2)上，上，fs2=cs23，不满足标号条件。，不满足标号条件。2023-1-14vsv2v1v3vt(3,3)(5,2)(4,4)v4(2,2)
27、(1,0)(1,1)(3,0)(5,4)(2,1)(0,+)(vs,3)(3)检查检查v1。标号过程无法继续下去，算法结束。标号过程无法继续下去，算法结束。在弧在弧(v2，v1)上，上，f21=0，不满足标号条件。，不满足标号条件。在弧在弧(v1，v3)上，上，f13=2，c13=2，不满足标号条件。，不满足标号条件。2023-1-14这时的可行流即为所求最大流。最大流量为：这时的可行流即为所求最大流。最大流量为：v(f)=fs1+fs2=f4t+f3t5。vsv2v1v3vt(3,3)(5,2)(4,4)v4(2,2)(1,0)(1,1)(3,0)(5,4)(2,1)(0,+)2023-1-
28、14vsv2v1v3vt(3,3)(5,2)(4,4)v4(2,2)(1,0)(1,1)(3,0)(5,4)(2,1)(0,+)V1 同时，可以得到同时，可以得到已标号点集合已标号点集合V1=vs,v1，和，和未标未标号点集合号点集合 =v2,v3,v4,vt。1V11,VV 相应地，弧集合相应地，弧集合 =(vs,v2),(v1,v3)即为最小即为最小截集，它的容量也是截集，它的容量也是5，等于最大流量。，等于最大流量。2023-1-14 由此，也可以体会到最小截集的意义。网络从发点由此，也可以体会到最小截集的意义。网络从发点到收点的各通路中，向容量决定其通过能力，到收点的各通路中，向容量决
29、定其通过能力，最小截集最小截集则是这些路中的咽喉部分，或者叫瓶颈则是这些路中的咽喉部分，或者叫瓶颈，其容量最小，其容量最小，它决定了整个网络的最大通过能力。要提高整个网络的它决定了整个网络的最大通过能力。要提高整个网络的运输能力，必须首先改进这个咽喉部分的通过能力。运输能力，必须首先改进这个咽喉部分的通过能力。2023-1-142023-1-148431763511v1v2v3v5v4v6105图图10-23 例如，图例如，图10-23就是一个网络，指定就是一个网络，指定v1是发点，是发点，v6是是收点，其它的点是中间点。弧旁的数字为收点，其它的点是中间点。弧旁的数字为cij。2023-1-1
30、4v1v2v3v5v4v6 图图10-24所示的运输方案，就可看作是这个网所示的运输方案，就可看作是这个网络上的一个流，每个弧上的运输量就是该弧上的流络上的一个流，每个弧上的运输量就是该弧上的流量，如：量，如：f12=5，f24=2，f13=3，f34=1。图图10-242023-1-14v1v2v3v5v4v6图图10-2410-24给出了一个运输方案，每条弧旁的数字表给出了一个运输方案，每条弧旁的数字表示每条运输线上的运输数量。这个方案使示每条运输线上的运输数量。这个方案使8 8个单位个单位的产品从的产品从v v1 1运到运到v v6 6。在这个运输网络中，从。在这个运输网络中，从v v1
31、 1到到v v6 6的最大输送量是多少呢的最大输送量是多少呢?8431763511v1v2v3v5v4v6105图图10-23图图10-242023-1-14v1v2v3v5v4v6 图图10-24中，中，(v5,v4)是饱和弧，其它的弧为非是饱和弧，其它的弧为非饱和弧。所有弧都是非零流弧。饱和弧。所有弧都是非零流弧。图图10-23图图10-248431763511v1v2v3v5v4v61052023-1-148431763511v1v2v3v5v4v6105图图10-23 图图10-23中，在链中，在链=(v1,v2,v3,v4,v5,v6)中中 +=(v1,v2),(v2,v3),(v3
32、,v4),(v5,v6)-=(v5,v4)2023-1-14v1v2v3v5v4v6 图图10-24中，链中，链=(v1,v2,v3,v4,v5,v6)是一条增广链。因是一条增广链。因为为+和和-中的弧满足增广链的条件。比如：中的弧满足增广链的条件。比如：(v1,v2)+,f12=50。图图10-248431763511v1v2v3v5v4v6105图图10-23+1+1+1-1+12023-1-148431763511v1v2v3v5v4v6105图图10-23 例如，弧集例如，弧集(v1,v2)，(v2,v3)，(v2,v5)，(v2,v4)、弧集、弧集(v2,v4)，(v2,v5)，(v
33、3,v4)，(v3,v5)都是网络都是网络D的截集的截集。弧集弧集(v4,v6)，(v2,v5)，(v3,v5)也是网络也是网络D的截集的截集。8431763511v1v2v3v5v4v61052023-1-148431763511v1v2v3v5v4v6105图图10-23 例如，弧集例如，弧集(v1,v2)，(v2,v3)，(v2,v5)，(v2,v4)、弧集、弧集(v2,v4)，(v2,v5)，(v3,v4)，(v3,v5)都是网络都是网络D的截集的截集。弧集弧集(v4,v6)，(v2,v5)，(v3,v5)也是网络也是网络D的截集的截集。8431763511v1v2v3v5v4v610
34、52023-1-14由增广链的定义，可知由增广链的定义，可知0,令网络上的另一个流：令网络上的另一个流：jiijjiijjiijijvvfvvfvvff,*仍为可行流仍为可行流(即满足容量限制条件与平衡条件即满足容量限制条件与平衡条件)，但，但 的总流量等于的总流量等于 的流量加的流量加，即，即*ijf*ijf*ijf*ijijfvfv这与这与 是最大流的前提矛盾。是最大流的前提矛盾。*ijf2023-1-148431763511v1v3v2v4v5v6105图图10-23 例如，弧集例如，弧集(v1,v2)，(v2,v3)，(v2,v5)，(v2,v4)和弧集和弧集(v2,v4)，(v2,v5)，(v3,v4)，(v3,v5)都是网络都是网络D的截集的截集。2023-1-14
