实用运筹学64

1、 6.4最大流问题在实际应用中，对一个网络，人们往往关心网络的流通能力，也就是网络的流量比如，河流系统的泄洪能力、电网的输变电能力、公路网的运输能力、制造系统的生产能力等等，这些都属于最大流问题最大流问题有两个层次：一是如何合理调配流量，使网络的流通能力达到最大；二是找到制约流量的瓶颈因素，以便对网络加以改造，提高网络的流通能力引例：下图是连接某产品产地vs和销地vt的交通网络弧（vi,v j）表示从vi到v j的运输线路，弧旁数字表示这条运输线路的最大通过能力请思考：还有其他分配流量的方法吗？这个网络的最大输送能力是多少？如果要提升网络的流通能力，应该如何入手？)1 ,2()1 ,2()1

2、,1()0 ,1()0 ,1(6.4.1基本概念基本概念1、网络与流、网络与流容量网络：对一个有向网络N=(V,A)作如下规定：网络有一个发点vs和一个收点vt；对每一弧 都赋予一个容量 表示容许通过该弧的最大流量满足以上规定的网络称为容量网络A,)v,v(ji0,)v,v(jiijrr网络流：是指流过一个网络的某种流在各边上流量的集合在一个网络N=(V,A)中，设以 表示通过弧 的流量，则集合 就称为该网络的一个流)v,x(vxjiijA)v,v(jiA)v,(vxXjiij满足下列条件的流X=xij称为一个可行流： （1）弧流量限制条件 弧的流量不超过容量，即对每一弧 有 （2）中间点平衡

3、条件 对于中间点，有总流入量=总流出量，即对每个i( )有 Avvji),( rx0ijijtsi,jjjiij 0 x-x对于发点vs和收点vt，有 （即vs的净流出量与vt的净流入量相等）f称为可行流的流量, fxxjjjtsj对于发点vs和收点vt，有 （即vs的净流出量与vt的净流入量相等）f称为可行流的流量在一个网络中，流量最大的可行流称为最大流，记为 ， ，其流量记为 , fxxjjjtsjxX*ij*)f(Xf*对于发点vs和收点vt，有 （即vs的净流出量与vt的净流入量相等）f称为可行流的流量在一个网络中，流量最大的可行流称为最大流，记为 ， ，其流量记为 , fxxjjjt

4、sjxX*ij*)f(Xf*弧的种类弧的种类在网络N=（V，A）中，若给定一个可行流X，我们把网络中 的弧称为饱和弧， 的弧称为非饱和弧， 的弧称为零流弧 rxijijijijrx0 xij设 是网络中一条连接发点和收点的链，我们定义链的方向是从vs到 vt则链 的弧分为两类：与链的方向一致的弧称为前向弧，其集合记为 ；与链的方向相反的弧称为后向弧，其集合记为 tsvvvvv321在链 上的各弧被分成以下两类：tsvvvvv321),(),(),(),(231231vvvvvvvvts增广链增广链设 是一可行流， 是从vs到vt的一条链若链 上各弧的流量满足下述条件：（1）前向弧均为非饱和弧；

5、（2）后向弧均为非零流弧则称 为一条关于可行流X的增广链，记为 。 Xijx)(Xv定理定理1 在网络N=(V,A)中，可行流X是最大流的充要条件是：N中不存在关于X的增广链5、截集、截集 在一个网络N=(V,A)中，若把点集V剖分成不相交的两个非空集合S和 ，且 , S中各点不需经由 中的点而均连通， 中各点也不需经由 S中的点而均连通，则把始点在 S中而终点在 中的一切弧所构成的集合，称为一个分离vs和vt的截集，记为 .如果从网络N中去掉截集 中的边，从vs就没有路可以到达vtSSSvS,vtsSS)S(S,)S(S,S=vs, =v1, v2 ,v3 ,v4 ,vt, =(vs, v1

6、 ),(vs ,v2 ), S)S(S,注意：截集是有方向的，只包含从S 指向 的弧截集是从vs一岸通往vt一岸的“桥梁”的总和，或者说，截集是从vs到vt的必经之路SS=vs ,v1 , =v2 ,v3 ,v4 ,vt, = (vs ,v2), (v1, v3 ) S)S(S,在一个截集 中所有弧的容量之和称为该截集的容量，简称截量截集可以有很多，不同的截集具有不同的截量找一下图6-18中的截集)S(S,S=vi =（vj） =（vi，vj） 截量vsv1,v2 ,v3,v4, vt(vs, v1),( vs, v2)11vs, v1v2 ,v3,v4, ,vt( vs, v2), (v1,

7、 v3)8vs, v2v1 ,v3,v4, ,vt( vs, v1), (v2, v1), ( v2, v4)12vs, v1, v2v3,v4, ,vt( v2, v4), (v1, v3)8vs, v1, v3v2,v4, ,vt( vs, v2), (v3, v2), ( v3, v4) , ( v3, vt)12vs, v2, v4v1 ,v3 ,vt( vs, v1), (v2, v1), ( v4, vt)13vs,v1,v2 ,v3,v4, vt( v2, v4), ( v3, v4) , ( v3, vt)11vs,v1,v2 ,v4,v3, vt( vs, v1), (v2,

8、 v1), ( v4, vt)13vs,v1,v2 ,v3,v4,vt( v3, vt), ( v4, vt)9S)S(S,截量最小的截集称为最小截集最小截集的概念很重要，它决定了网络的流通能力定理定理2 对于任意给定的网络D=(V,A,C)，从发点vs到收点vt的最大流的流量必等于分割vs和vt的最小截集的截量6.4.2 寻求最大流的标号法寻求最大流的标号法 Ford-Fulkerson标号法标号法Ford和Fulkerson提出了求解最大流问题的标号法，思路是从某一可行流出发，用标号的办法寻找增广链，然后沿着增广链调整网络流量，直到标号过程无法继续，意味着没有了增广链，表明已得到最大流同时

9、，标号点和未标号点构成了两个集合，连接两个点集的弧集就是最小截集图6.22已标号点vs,v1，未标号点集合v2,v3,v4,vt用两道横线将标号点与未标号点分开，横线截断的从 到 的弧就是最小截集：（vs,v2），（v1,v3），如图6.22所示，最小截集的截量为8，恰好就是最大流的流量最小截集容量的大小影响总输送量的提高因此，为提高总的输送量，必须首先考虑改善最小截集中各弧的输送状况，提高它们的通过能力另一方面，一旦最小截集中弧的通过能力降低，就会使网络总的输送能力下降这里需要说明的是：在求网络最大流时，若未给定初始可行流，可以自己找出初始可行流，这个可行流可以是零流，也可以是任一可行流，但

10、一般情况下为加快计算速度，可以根据网络中弧上各容量的大小，给出流量尽可能大的可行流，但该流是否为最大流须通过求增广链来确定6.4.2用Lingo软件求解最大流问题vMODEL:v sets:v nodes/s,1,2,3,4,t/;v arcs(nodes, nodes): p, c, f;v endsetsv data: vp= 0 1 1 0 0 0v 0 0 0 1 0 0v 0 1 0 0 1 0v 0 0 1 0 1 1v 0 0 0 0 0 1v 0 0 0 0 0 0;v c =0 5 6 0 0 0v 0 0 0 2 0 0v 0 1 0 0 6 0v 0 0 1 0 3 2v

11、 0 0 0 0 0 7v 0 0 0 0 0 0;v enddatavVariable Value Reduced Cost vFLOW 8.000000 0.000000 vF( S, S) 0.000000 0.000000 F( S, 1) 2.000000 0.000000 F( S, 2) 6.000000 -1.000000 F( S, 3) 0.000000 0.000000 F( S, 4) 0.000000 0.000000 v结果解读：FLOW 为8，表示最大流量为8；F(S,1)=2, F(s,2)=6, F(1,3)=2, F(2,4)=6, F(3,T)=2, F(

12、4,T)=6,其余为0，表示弧（vs,v1）,（vs,v2）,（v1,v3）, （v2,v4）, （v3,vt）, （v4,vt）上的流量分别为2，6，2，6，2，6，其余弧上的流量为0几点注意；1、网络中的点分为两部分，标了号的点和未标号的点，标了号的点又分为已检查点和未检查点即：2、每个标号点的标号包括两部分，即 :第一个标号表明 的标号是从哪一个点得到的，以便于找出增广链；第二个标号是为确定增广链的调整量 用的3、如何标号？分清弧 和弧4、标号目的：寻找增广链。若终点vt得到标号，则存在增广链；否则，不存在增广链。未标号点标号未检查点标号已检查点标号点顶点)(,(jivbvjv),(ji

13、vv),(ijvv5、寻找最大流的过程一定是在vt得不到标号停止。6、最大流跟当前可行流的大小没有关系，只跟容量网络有关。7、若没给出可行流，就要先寻找一个可行流。v6.4.4 最大流问题拓展最大流问题拓展求最大流的标号法适用于只有一个收点和一个发点的网络，但有些问题给出的网络具有多个发点和多个收点，如图6.23 中，网络G有两个发点v1,v2,两个收点v7,v8可以添加两个新顶点vs,vt,连接有向边 ， ，新添加的边容量为M（充分大的正数），得到新网络G G为只有一个发点、收点的网络图6.236.4.5最大流问题应用举例最大流问题应用举例最大流问题应用广泛，除了可以求运输网络的最大流量之外

14、，许多实际问题也可以用最大流的方法解决例6.4.3 某铁路施工企业需在13月份完成A、B、C三项工程，工程工期和所需劳动力见表6-6该企业每月可用劳动力为70人，任一项工程在一个月内投入的劳动力不能超过60人问该单位能否按期完成上述三项工程任务，应如何安排劳动力？解：本问题可以用网络图6.24表示图中的节点M1、M2、M3分别表示13月份，Ai、Bi、Ci表示工程在第i个月内完成的部分弧旁边的数字表示弧的容量，从S开始的弧，其容量为该公司每月可用劳动力90人；从节点M1、M2、M3开始的弧，以及到节点A、B、C的弧，其容量为任一工程在一个月内的劳动力投入不能超过60人，到收点T的弧，其容量为每项工程所需的劳动力合理安排每个月工程的劳动力，在不超过现有人力的条件下，尽可能保证工程按期完成，就是求图6.24中从发点到收点的最大流例6.4.4 某企业计划招聘懂法、英、德、俄语的翻译各一名，有A、B、C、D四人应聘每