运筹学：教案_图论4

1、 第四节第四节 网络最大流问题网络最大流问题例例 连接某产品产地连接某产品产地v1和销地和销地v6的交通网如下：的交通网如下：v2v5348v3v1v4v65106111735弧（弧（vi，vj）：从）：从vi到到vj的运输线，的运输线，弧旁数字：这条运输线的最大通过能力弧旁数字：这条运输线的最大通过能力,制定一个运输方案，使从制定一个运输方案，使从v1到到v6的产品数量最多。的产品数量最多。弧旁数字：弧旁数字：运输能力运输能力。问题：这个运输网络中，从问题：这个运输网络中，从v1到到v6的最大输送量是多少？的最大输送量是多少？v2v5313v3v1v4v61536222一、基本概念与定理一、

2、基本概念与定理1. 网络与流网络与流定义定义1 给定一个有向图给定一个有向图D=（V，A），在），在V中指定中指定 一点一点vs 称为发点，指定另一点称为发点，指定另一点vt 称为收点，称为收点， 其余点称中间点。任意弧其余点称中间点。任意弧(vi ，vj )A，有，有 cij 0，称为弧的容量。称，称为弧的容量。称D为一个容量网为一个容量网 络。记为络。记为D=（V，A，C）。）。流流: 定义在弧集定义在弧集A上的一个函数上的一个函数f=f(vi ,vj )，并称，并称 f(vi ,vj )为弧为弧(vi ,vj )上的流量。简记上的流量。简记 f = fi ,j 弧旁数字：弧旁数字： 容量

3、容量(a)图是一个网络图是一个网络v2v5348v3v1v4v65106111735v2v5313v3v1v4v61536222弧旁数字：弧旁数字： 流量流量 cij fijvivjv2v53.14.08.3v3v1v4v65.010.56.311.617.43.25.32. 可行流与最大流可行流与最大流定义定义2 满足下述条件的流满足下述条件的流 f 称为可行流称为可行流:1)容量限制条件容量限制条件: 对每一弧对每一弧(vi , vj )A 0fij cij2)平衡条件平衡条件: 对中间点对中间点vi (is,t ),有有 0 A),(A),( ijjivvjivvijff)V( : A)

4、,(A),(fffvsjjsvvjsvvsjs )V( : A),(A),(fffvtjjtvvjtvvtjt V( f ) 称为可行流称为可行流 f 的流量的流量,即发点的净输出量。即发点的净输出量。如所有如所有fij=0， 零流。零流。可行流总是可行流总是存在的存在的3. 增广链增广链对可行流对可行流 f = fij ：非饱和弧：非饱和弧：fij 0零流弧：零流弧：fij =0 链的方向：若链的方向：若是联结是联结vs和和vt的一条链，定义链的方的一条链，定义链的方向是从向是从vs到到vt 。 前向弧：弧的方向与链的方向一致，记为前向弧：弧的方向与链的方向一致，记为+。后向弧：弧的方向与链

5、的方向相反，记为后向弧：弧的方向与链的方向相反，记为-。v2v53.34.18.3v3v1v4v65.110.56.311.617.23.25.2 = (v1,v2,v3,v4,v5,v6 )+=(v1,v2) ,(v2,v3), (v3 , v4),(v5,v6) - =(v5,v4)v2v53.34.18.3v3v1v4v65.110.56.311.617.23.25.2定义定义3 设设 f 是一个可行流是一个可行流, 是从是从vs 到到vt 的一条链的一条链,若若满满 足下列条件足下列条件,称之为称之为(关于可行流关于可行流 f 的的)一条增广一条增广 链。链。(vi , vj ) -

6、0 fij cij 后向弧后向弧 是非零流弧，是非零流弧，(vi , vj ) + 0 fij cij 前向弧是前向弧是 非饱和弧，非饱和弧，v1v2v3v4v5v68.46.06.53.35.44. 截集与截量截集与截量 设设S，T V，S T= ，始点在，始点在S，终点在，终点在T中中的所有的所有弧的集合弧的集合，记为（，记为（S，T）。）。ST定义定义4 网络网络D=(V,A,C）,若点集若点集V被剖分为两个非空集被剖分为两个非空集 合合V1和和V1,使使vsV1，vt V1，则把弧集，则把弧集(V1，V1) 称为是分离称为是分离vs和和vt的截集。的截集。v2v53.34.18.3v3

7、v1v4v65.110.56.311.617.23.25.2=(v1,v2,v3)V1V1=(v4,v5,v6)定义定义5 给一截集（给一截集（V1，V1），把截集（），把截集（V1，V1）中所）中所 有弧的容量之和称为这个截集的容量（简称为截有弧的容量之和称为这个截集的容量（简称为截 量），记为量），记为C （V1，V1），）， 即即 )V,(V),(1111)V,C(V jivvijc定理定理1 可行流可行流 f *是最大流，当且仅当不存在关于是最大流，当且仅当不存在关于 f * 的增广链。的增广链。 二、寻求最大流的标号法（二、寻求最大流的标号法（FordFulkerson） 从任一个可

8、行流从任一个可行流 f 出发（若网络中没有给定出发（若网络中没有给定 f ，则从零流开始），经过标号过程与调整过程。则从零流开始），经过标号过程与调整过程。（一）标号过程（一）标号过程 未未标标号号点点未未检检查查已已检检查查标标号号点点网网络络中中的的点点标号：（前点标记，前点到该点的弧流量可调整量）标号：（前点标记，前点到该点的弧流量可调整量） 开始，开始，vs 标上（标上（0，），），vs 是标号未检查的点，是标号未检查的点，其余点都是未标号点，一般地，取一个标号未检查其余点都是未标号点，一般地，取一个标号未检查的点的点vi ，对一切未标号的点，对一切未标号的点vj 。（1）若弧（）若弧

9、（vi，vj）上，）上，fij0，则给，则给vj 标号标号(-i， l (vj)，l (vj)=minl (vi), fji, vj 成为标号而未检查的点。成为标号而未检查的点。fij0vivj(-i , l(vj)l(vj)=minl(vi),fji 重复上述步骤，一旦重复上述步骤，一旦vt被标号，则得到一条被标号，则得到一条vs到到vt的的增广链。若所有标号都已检查过，而增广链。若所有标号都已检查过，而vt尚未标号，结束，尚未标号，结束，这时可行流，即最大流。这时可行流，即最大流。（二）调整过程（二）调整过程 从从vt 开始，反向追踪，找出增广链开始，反向追踪，找出增广链 ，并在，并在上进

10、上进行流量调整。行流量调整。（1）找增广链）找增广链 如如vt 的第一个标号为的第一个标号为k（或或-k），），则弧（则弧（vk，vt）（或弧（或弧（vt，vk) )。检查。检查vk 的第一个标号，若为的第一个标号，若为i（或（或-i），则），则(vi,vk) (或或(vk,vi) )。再检查。再检查vi 的第一的第一个标号个标号,依此下去依此下去,直到直到vs 。被找出的弧构成了增广链。被找出的弧构成了增广链 。（2）流量调整）流量调整令调整量令调整量 是是 l(vt)，构造新的可行流，构造新的可行流 f ，令令 uvv fuvvfuvvffjiijjiijjiijij ),( ),( ),

11、( - 去掉所有的标号去掉所有的标号,对新的可行流对新的可行流 f = fij,重新进重新进入标号过程。入标号过程。例例 用标号法求下图网络的最大流。弧旁的数字是用标号法求下图网络的最大流。弧旁的数字是( cij , fij)。解：（一）标号过程。解：（一）标号过程。（1）给）给vs标上（标上（0，）；）；v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，） 415minmin111 ,)fc(),v( l)v( lsss在弧（在弧（vs，v2）上，）上， fs2=cs2=3, 不满足标号条件不满足标号条件。（2）检查）检查

12、vs，在弧（，在弧（vs，v1）上，）上，fs1=1，cs1=5， fs10， 给给v2标号标号 (-1, l l(v2), ,f),v( l)v( l114minmin2112 在弧（在弧（v1，v3）上，）上，f13=2， c13=2，不满足标号条件。，不满足标号条件。v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，）（s，4）（-1，1）（4）检查）检查v2，在弧（，在弧（v3，v2）上，）上，f32=10， 给给v3标号标号 (-2, l(v3), 这里这里 , 11 , 1min),(min)(3223fvlvl

13、（-2，1）在弧（在弧（v2，v4）上，）上，f24=3，c24=4，f24c24, 给给v4标号标号(2, l(v4), 其中其中 ,min)fc(),v( l)v( l111min242424 （5）检查）检查v3，在弧（，在弧（v3，vt）上，）上，f3t=1， c3t=2， f3tc3t， 给给vt标号标号 (3, l(vt), 这里这里 ,min)fc(),v( lmin)v( lttt111333 vt得到标号，标号过程结束。得到标号，标号过程结束。v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，）（s，4）（

14、-1，1）（-2，1）(2，1)(3，1)（二）调整过程（二）调整过程 ：从：从vt 开始逆向追踪，找到增广链。开始逆向追踪，找到增广链。（vs,v1,v2,v3,vt） =1，在在上进行流量上进行流量 =1的调整，得的调整，得可行流可行流 f 如右如右图所示：图所示：v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，）（s，4）（-1，1）（-2，1）(2，1)(3，1)v2v3v1vsv4vt(3，3)(4，3)(1，0)(5，3)(5，2)(2，2)(2，2)(1，0)(3,0)去掉各点标号，从去掉各点标号，从vs开始

15、，重新标号。开始，重新标号。点点v1：标号过程：标号过程无法进行，所以无法进行，所以f 即为最大流。即为最大流。V（f ）=3+2=5v2v3v1vsv4vt(3，3)(4，3)(1，0)(5，3)(5，2)(2，2)(2，2)(1，0)(3,0)（0，）（s，3）截集：截集：V1，V1=（vs，v2），（），（v1，v3） V（f ）=CV1，V1=5V1=(vs,v1) V1=(v2,v3,v4, vt)问题：问题：(v2,v1)是不是截集是不是截集V1，V1中的弧？中的弧？例例 1 下图中，从三口油井下图中，从三口油井、经管道将油输至经管道将油输至脱水处理厂脱水处理厂和和，中间经，中间经、三个泵站。已知三个泵站。已知图中弧旁数字为各管道通过的最大能力（吨图中弧旁数字为各管道通过的最大能力（吨/小时），小时），求从油井每小时能输送到处理厂的最大流量。求从油井每小时能输送到处理厂的最大流量。 87654321201030102015302050102050 多源、多汇的最大流问题多源、多汇的最大流问题单源、单汇。单源、单汇。s208015t6050 xv1v6v2v4v5v3y141694197226125313156例例2v2v5v34931064343482v1v5v4vtvs练习练习例例3 某产品从仓库运往市场销售。已知各仓库的可供某产品从仓库运往市场销售。已知