(9.3.1)--最大流问题（NO26）.pdf

《(9.3.1)--最大流问题（NO26）.pdf》由会员分享，可在线阅读，更多相关《(9.3.1)--最大流问题（NO26）.pdf（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 运运 筹筹 学学 第二十六讲第二十六讲 最大流问题最大流问题 2 最大流问题最大流问题 最大流问题是一类极为广泛的网络问题。不仅最大流问题是一类极为广泛的网络问题。不仅在交通运输网络中有人流、车流、货物流、供水在交通运输网络中有人流、车流、货物流、供水网络中有水流、金融系统中有现金流、通讯网络网络中有水流、金融系统中有现金流、通讯网络中信息流中信息流等。五十年代，等。五十年代，Ford(福特福特)、Fulkerson(富克逊富克逊)建立的“网络流理论”，是网建立的“网络流理论”，是网络应用的重要组成部分。络应用的重要组成部分。3 一、网络与流的基本概念一、网络与流的基本概念 1 1、网络流

2、、网络流 对于有向图对于有向图N=(V,A)，如果如果V中有一发点中有一发点vs（亦亦称源），还有一收点（亦称为汇）记为称源），还有一收点（亦称为汇）记为vt，其余均其余均为中间点，且对为中间点，且对A中的每条弧均有权中的每条弧均有权r(vi,vj)=rij 0（称为弧容量），则称这样的赋权有向图称为弧容量），则称这样的赋权有向图N为容量为容量网络，记为网络，记为N=(V,A,R)。通过通过N中弧中弧(vi,vj)的物流量的物流量xij，称为弧称为弧(vi,vj)的流量。所有弧上流量的集合的流量。所有弧上流量的集合X=xij称为该网络称为该网络N的一个流。的一个流。4 在下图中，弧旁括号中的两

3、个数字在下图中，弧旁括号中的两个数字(rij,xij)，第第1个数字表示弧容量，第二个数字表示通过该弧的流个数字表示弧容量，第二个数字表示通过该弧的流量。弧量。弧(vs,v1)上的上的(9,7)，前者是弧容量，表示可通，前者是弧容量，表示可通过该弧最大流量的能力为过该弧最大流量的能力为9，后者是目前通过该弧，后者是目前通过该弧的实际流量为的实际流量为7。s 1 2 3 4 t(9,7)(4,4)(6,3)(3,1)(2,1)(7,7)(5,5)(3,2)(5,3)5 一般地一般地，在容量网络在容量网络D=(V,A,R)中中，满足以下条件的流满足以下条件的流f，称为可行流：称为可行流：（1）弧流

4、量限制条件弧流量限制条件 0 xij rij (vi,vj)A （2）平衡条件平衡条件 ijjiijtiftsiOsifxx当当当,式中式中f为该可行流的流量，即发点的净输出量，或收为该可行流的流量，即发点的净输出量，或收点的净输入量。对于网络的流，可行流总是在存在的。点的净输入量。对于网络的流，可行流总是在存在的。如如X=0，称为零流。称为零流。2、可行流、可行流 6 3 3、最大流、最大流 最大流问题就是在容量网络最大流问题就是在容量网络N中，求一个可行流中，求一个可行流X=xij，使其流量使其流量f达到最大。其数学模型为达到最大。其数学模型为 显然，最大流问题是个特殊的显然，最大流问题是

5、个特殊的LP问题可用单纯形法或问题可用单纯形法或表上作业法求解，但利用它与图的紧密关系，能更为直观表上作业法求解，但利用它与图的紧密关系，能更为直观简便地求解。简便地求解。在一网络中，流量最大的可行流称为最大流，记为在一网络中，流量最大的可行流称为最大流，记为X*=xij*，其流量记为其流量记为f*=f(X*)7 4、链的前向弧与后向弧链的前向弧与后向弧 设设N=(V,A,R)中中，有一可行流有一可行流X=xij，按每条弧上流量的多少按每条弧上流量的多少，可可将弧分四种类型：将弧分四种类型：饱和弧饱和弧(即即xij=rij)非饱和弧非饱和弧(即即xij0)如图中如图中，(v2,v4),(v1,

6、v3)是饱和弧是饱和弧，又是非零流弧又是非零流弧，其它各弧均为其它各弧均为非饱和弧非饱和弧，也是非零流弧也是非零流弧。设设 是是N中从中从vs别别vt的一条链的一条链，沿此方向沿此方向，链上各弧可分为两类：链上各弧可分为两类：前向弧前向弧（与链的方向一致的弧与链的方向一致的弧），其集合记为其集合记为+后向弧后向弧（与链的方向相反的弧与链的方向相反的弧），其集合记为其集合记为-如图中如图中，在在=vs,v2,v1,v4,v3,vt中中，+=(vs,v2),(v1,v4),(v3,vt),-=(v1,v2),(v3,v4)s 1 2 3 4 t(9,7)(4,4)(6,3)(3,1)(2,1)(7

7、,7)(5,5)(3,2)(5,3)8 5、增广链、增广链 对于可行流对于可行流X,是一条从是一条从vs到到vt的链，若的链，若+中的每弧均为中的每弧均为非饱和弧，非饱和弧，-中的每弧均为非零流弧，是称链中的每弧均为非零流弧，是称链 是关于是关于X的增的增广链。广链。6、割集割集 若将若将N=(V,A,R)的的V分为两部分分为两部分S和和 ,使使vs S,vt ,且且 ，则把从则把从S指向指向 的弧的全体称为割集的弧的全体称为割集。记为记为()，即即 。7、割集的截量割集的截量割集中所有弧容量之和称为该割集的截量割集中所有弧容量之和称为该割集的截量。记为记为r(S,S)，不同割集的截量不同不同

8、割集的截量不同。8、最小割集最小割集。在一个网络中在一个网络中，截量最小的割集称为最小截量最小的割集称为最小 割集割集，记为记为 ，其容量其容量 称为最小截量称为最小截量。SSVSSSS,SSS,|),(),(SvSvvvSSjiji*)*,(SS*)*,(SSr9 例题例题1 求下列网络的最小截量求下列网络的最小截量 s 1 2 3 4 t(9,7)(4,4)(6,3)(3,1)(2,1)(7,7)(5,5)(3,2)(5,3)S=vi S=vj 割集割集(S,S)=(vi,vj)截量截量r(S,S)s 1,2,3,4,t(s,1),(s,2)14 s,1 2,3,4,t(s,2),(1,2

9、),(1,3),(1,4)15 s,2 1,3,4,t(s,1),(2,4)14 S,1,2 3,4,t(1,3),(1,4),(2,4)12 S,1,3 2,4,t(s,2),(1,2),(1,4),(3,4),(3,t)19 S,2,4 1,3,t(s,1),(4,t)16 S,1,2,3 4,t(1,4),(2,4),(3,4),(3,t)16 S,1,2,4 3,t(1,3),(4,t)11 S,1,2,3,4 t(3,t),(4,t)13 由此可知最小割集为由此可知最小割集为(3,t),(4,t)，最小截量为最小截量为11 10 3.最大流最小截量定理：最大流最小截量定理：任一网络任

10、一网络N中中，最大流的流量最大流的流量=最小割集的截量最小割集的截量。二、基本原理二、基本原理 1、流量、流量截量定理：网络中的任一可行流的流量恒不超截量定理：网络中的任一可行流的流量恒不超过任一割集的截量。过任一割集的截量。2、最大流的充分必要条件：网络中不存在增广链。、最大流的充分必要条件：网络中不存在增广链。s 1 2 3 4 t(9,7)(4,4)(6,3)(3,1)(2,1)(7,7)(5,5)(3,2)(5,3)11 三、求最大流的方法三、求最大流的方法(FordFord-FulkersonFulkerson标号法标号法)从以上概念及定理可知从以上概念及定理可知，要判断可行流要判断

11、可行流f是否最大流有是否最大流有两种途径：两种途径：1）能否找出可行流能否找出可行流f的增广链的增广链，若能若能，则则f不是最大流不是最大流，否则否则f是最大流是最大流。2）V(f)是否等于最小截量是否等于最小截量，若等若等，则则f是最大流是最大流，否则否则 f不是最大流不是最大流。标号法的基本思想：标号法的基本思想：从可行流从可行流f出发出发，由由Vs开始开始，用对用对D中的每个顶点进行标号的办法找中的每个顶点进行标号的办法找f的增广链的增广链。若无若无，则则 f为所求的最大流为所求的最大流。否则否则，在增广链上进行调整在增广链上进行调整。调整量：调整量：min),(minminijijij

12、ffw调整方法：调整方法：),(),(),(jiijjiijjiijijvvfvvfvvff12 例题例题2 用用FordFulkerson标号法求下图的最大流标号法求下图的最大流 s 1 2 3 4 t(9,7)(4,4)(6,3)(3,1)(2,1)(7,7)(5,5)(3,2)(5,3)s 1 2 3 4 t(9,7)(4,4)(6,4)(3,2)(2,0)(7,7)(5,5)(3,1)(5,4)最大流最大流F=11 13 s 1 2 3 4 t(9,0)(4,0)(6,0)(3,0)(2,0)(7,0)(5,0)(3,0)(5,0)当然上述问题，也可以不考虑现有的流量，把当然上述问题，

13、也可以不考虑现有的流量，把0流当成初始流当成初始流，开始求解。求解过程如下：流，开始求解。求解过程如下：s 1 2 3 4 t(9,4)(4,4)(6,4)(3,0)(2,0)(7,5)(5,5)(3,0)(5,5)零流零流F1=0 可行流可行流F2=9 14 s 1 2 3 4 t(9,6)(4,4)(6,4)(3,2)(2,0)(7,7)(5,5)(3,0)(5,5)s 1 2 3 4 t(9,4)(4,4)(6,4)(3,0)(2,0)(7,5)(5,5)(3,0)(5,5)可行流可行流F2=9 最大流最大流F3=11 15 例题例题3 分配问题分配问题 有甲、乙、丙三名工人要加工有甲、

14、乙、丙三名工人要加工A、B、C、D四种零件，每种四种零件，每种零件的需求量以及每个工人胜任加工的零件如下表示。应该零件的需求量以及每个工人胜任加工的零件如下表示。应该如何安排加工任务，才能满足零件需求且使每个工人承担加如何安排加工任务，才能满足零件需求且使每个工人承担加工的件数尽量均衡。工的件数尽量均衡。工人工人 零件零件 A B C D 甲甲 乙乙 丙丙 需求量需求量 10 20 15 10 解：因为零件总数为解：因为零件总数为10+20+15+10=55，所以每个工人应该加工所以每个工人应该加工 3118件件 由于乙胜任加工的零件种类最多，故分配乙加工由于乙胜任加工的零件种类最多，故分配乙

15、加工19件，甲和件，甲和丙各加工丙各加工18件。件。16 S 甲甲 乙乙 丙丙 A B C D t（18,18）（18,10）（10,10）（19,19）（18,18）（19,0）（19,9）（18,11）（18,7）（19,10）（20,20）（15,15）（10,10）工人工人 零件零件 A B C D 甲甲 10 8 乙乙 0 9 10 丙丙 11 7 需求量需求量 10 20 15 10 对应的分配方案如下：对应的分配方案如下：（18,8）17 例题例题4 18 解：转化为一个网络图，弧的容量为两点间桥解：转化为一个网络图，弧的容量为两点间桥梁数。梁数。该问题为求最该问题为求最小割集问题小割集问题 19 最小割集为最小割集为AE、CD、CF，最小截量为最小截量为3 所以最少需要切断所以最少需要切断3座座桥才能阻止对方部队桥才能阻止对方部队过河过河 20 例题例题5 解：分析，这也是一个最小割集问题。通过分析，可知最小割集解：分析，这也是一个最小割集问题。通过分析，可知最小割集为为ad,ab,Ab,cb，最小截量为，最小截量为13。即在路段。即在路段ad,ab,Ab,cb上各建上各建一个检查站，最小建设费用为一个检查站，最小建设费用为13。21 敬请指教！谢谢！