网络最大流问题

1、精品文档给定一个有向图D=(V,A) ，在 V 中指定一点称为发点（记为），该点只有出发去的弧，指定另一点称为收点（记为），该点只有指向它的弧，其余的点叫做中间点。对于A 中的每一条弧，对应一个数（简记），称之为弧的容量。通常我们把这样的 D 叫做网络，记为D=(V,A,C) 。（ 2）网络流：在弧集A 上定义一个非负函数。是通过弧的实际流量，简记，称是网络上的 流函数 ，简称 网络流 或流，称为网络流的流量。§ 4网络最大流问题网络最大流问题是网络的另一个基本问题。许多系统包含了流量问题。 例如交通系统有车流量， 金融系统有现金流， 控制系统有信息流等。许多流问题主要是确定这类系统

2、网络所能承受的最大流量以及如何达到这个最大流量。4.1基本概念与定理1 1 网络与流定义 14 （1）网络：例 1如图 7-20 是连结某产品产地和销地的交通图。弧表示从到的运输线，弧旁的数字表示这条运输线的最大通过能力，括号内的数字表示该弧上的实际流。现要求制定一个运输方案，使从运到的产品数量最多。可行流与最大流。1 欢迎下载精品文档在运输网络的实际问题中，我们可以看出，对于流有两个基本要求：一是 每条弧上的流量必须是非负的且不能超过该弧的最大通过能力（即该弧的容量）；二是 起点发出的流的总和（称为流量），必须等于终点接收的流的总和，且各中间点流入的流量之和必须等于从该点流出的流量之和，即流

3、入的流量之和与流出的流量之和的差为零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。因此有下面所谓的可行流的定义。定义 14对于给定的网络D=（ V,A,C ）和给定的流，若满足下列条件：（ 1）容量限制条件：对每一条弧，有(7.9)（ 2）平衡条件：对于中间点：流出量 =流入量，即对于每一个i (i s,t)，有(7.10)对于出发带点，有(7.11)对于收点，有(7.12)则称为一个 可行流 ，称为这个可行流的流量 。注意，我们这里所说的出发点是指只有从发出去的弧， 而没有指向的弧；收点是指只有弧指向，而没有从它的发出去的弧。2 欢迎下载精品文档可行流总是存在的。

4、例如令所有弧上的流，就得到一个可行流， （称为 零流 ），其流量。如图 7-20 中，每条弧上括号内的数字给出的就是一个可行流，它显然满足定义中的条件（1）和（ 2）。其流量。所谓网络最大流问题就是求一个流，使得总流量达到最大， 并且满足定义 15 中的条件（ 1）和（ 2），即max(7.13)网络最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点，解决这个问题的方法较直线性规划的一般方法要简便和直观的多。例 2 写出图 7-20 所表示的网络最大流问题的线性规划模型。解 设，则其线性规划模型为max3. 增广链。3 欢迎下载精品文档在网络 D=(V,A,C) 中，若给定一个可行流

5、，我们把网络中使的弧称为饱和弧，使的弧称为 非饱和弧 。把的弧称为 零流弧 ，把的称为 非零流弧 。如图 7-20 中的弧都是非饱和弧，而弧为零流弧。若是网络中联结发点和收点的一条链，我定义链的方向是从到S ，则链上的弧被分为两：一类是： 弧的方向与链的方向一致，我们称此类和为前向弧 ，所有前向弧的集合记为。另一类是： 弧的方向与链的方向一致，我们称此类弧为后向弧 ，所有后向弧的集合记为。如图 7-20 中，设是一条从到的链，则,定义15设是网络 D=(V,A,C) 上的一个可行流，是从到的一条链，若满足下列条件：(1)在弧(v i ,v j ) +上，即中的每一条弧都是非饱和弧；(2)在弧上

6、，即中的每一条弧都是非零流弧。则称是关于的一条 增广链 。如前面所说的链就是一条增广链。因为其中+上的弧均非饱和，如(v s ,v 2) +,fs2s2-上的弧为非零流弧，如 (v32)-,f32=5<c=13；而,v=1>0，。显然这样的增广链不止一条。4. 截集与截量定义16给定网络D=(V,A,C) ，若点集V 被分割成两个非空集合V1 和 V2，使得V=V1+V2,V 1 V2= ( 空集 ) ，且 vs V1,v t V2，则把始点在V1, 终点在V2 的弧的集合称为分离vs 和 vt 的一个 截集 ，记为 (V1,V 2) 。如图 9.26 中，设 V1= vs,v 2

7、,v 5， V2= v3,v 4,v 6,v t 则截集为,。4 欢迎下载精品文档而弧 (v 3,v 2) 和 (v 4,v 5) 不是该集中的弧。因为这两条弧的起点在V2 中，与定义17 不符。显然，一个网络的截集是很多的（但只有有限个），例如在图7-20中，还可以取,，则截集为另外，若把网络 D=(V,A,C) 中某截集的弧从网络 D 中去掉， 则从 vs 到 vt 便不存在路， 所以直观上说，截集是从 vs 到 vt 的必经之路。定义 17在网络 D=(V,A,C) 中，给定一个截集(V 1,V 2) ，则把该截集中所有弧的容量之和，称为这个截集的容量 ，简称为 截量 ，记为 c(V1,

8、V 2) ，即C(V1,V 2)=(7.16)例如在上面我们所举的两个截集中，有而显然，截集不同，其截量也不同。由于截集的个数是有限的，故其中必有一个截集的容量是最小的，称为最小截集 ，也就是通常所说的“ 瓶颈 ”。不难证明，网络D=(V,A,C) 中，任何一个可行流f= f ij 的流量V(f) ，都不会超过任一截集的容量，即v(f ) c(V 1,V 2)(7.17)如果存在一个可行流f*= f* ij ，网络 D=(V,A,C) 中有一个截集，使得(7.18)则必是最大流，而必是 D 中的最小截集。为了求网络最大流f * ，我们也说明下面的重要定理。定理 4在网络 D=(V,A,C) 中

9、，可行流是最大流的充要条件是D 中不存在关于 f * 的增广链。证先证必要性。用反证法。若f * 是最大流，假设D 中存在着关于f * 的增广链，令(7.19)由增广链的定义可知>0，令。5 欢迎下载精品文档(7.20)不难验证是一个可行流，且有这与 f * 是最大流的假定矛盾。再证充分性：即证明设D 中不存在关于f * 的增广链， f * 是最大流。用下面的方法定义：令若，且有，则令；若，且有，则令。因为不存在着关于的增广链，故记，于是得到一个截集(V * ,) 。显然有所以 V(f * )=c，于是 f * 必是最大流。定理得证。由上述证明中可见， 若是最大流，则网络必定存在一个截集

10、，使得 (7.18)式成立。定理 5（最大流最小截集定理）对于任意给定的网络D=(V,A,C) ，从出发点vs到收点 vt 的最大流的流量必等于分割和的最小截集的容量，即由定理4 可知，若给定一个可行流，只要判断网络D 有无关于的增广链。 如果有增广链， 则可以按定理 4 前半部分证明中的办法， 由公式 (7.19) 求出调整量Q，再按式（ 7.20 ）的方法求出新的可行流。如果流有增广链，则得到最大流。而根据定理4 后半部分证明中定义的办法，可以根据vt 是否属于来判断 D 中有无关于f 的增广链。在实际计算时，我们是用给顶点标号的方法来定义的，在标号过程中，有标号的。6 欢迎下载精品文档顶

11、点表示是中的点，没有标号的点表示不是中的点。一旦有了标号，就表明找到一条从 vs 到 vt 的增广链；如果标号过程无法进行下去，而vt 尚未标号，则说明不存在从vs到 vt 的增广链， 于是得到最大流。这时将已标号的点（至少有一个点vs ）放在集合中，将未标号点（至少有一个点vt ）放在集合中，就得到一个最小截集。4.2寻求最大流的标号法（Ford , Fulkerson）从一个可行流出发（若网络中没有给定，则可以设是零流），经过标号过程与调整过程。1） 1） 标号过程在这个过程中，网络中的点或者是标号点（又分为已检查和未检查两种），或者是未标号点， 每个标号点的标号包含两部分：第一个标号表明

12、它的标号是从哪一点得到的，以便找出增广链；第二个标号是为确定增广链的调整量用的。标号过程开始，总先给vs 标上 (0,+ ) ，这时 vs 是标号而未检查的点，其余都是未标号点，一般地，取一个标号而未检查的点vi ，对一切未标号点vj ：(1)在弧上，则给 vj 标号。这里。这时点 vj 成为标号而未检查的点。(2)若在弧上，给 vj 标号。这里。这时点 vj 成为标号而未检查的点。于是成为标号而已检查过的点，重复上述步骤，一旦被标上号，表明得到一条从到的增广链，转入调整过程。若所有标号都是已检查过， 而标号过程进行不下去时， 则算法结束， 这时的可行流就是最大流。2） 2 调整过程首先按及其

13、它点的第一个标号，利用“反向追踪”的办法，找出增广链。例如设vt 的第一个标号为（或），则弧（或相应地）是上的弧。接下来检查的第一个标号，若为（或），则找出（或相应地）。再检查的第一个标号，依此下去，直到为止。这时被找出的弧就构成了增广链。令调整量是，即的第二个标号。7 欢迎下载精品文档令去掉所有的标号，对新的可行流，重新进入标号过程。下面，以例题说明此算法求解过程。例 3用标号法求图 7-20所示网络最大流。弧旁的数是解 : 对图 7-20 中各顶点进行标号。首先给标(0,+ )，即检查：在弧上，因为，又有, 所以给标；在弧上，因为，又有, 所以给标。检查：在弧上，因为，又有, 所以给标；在

14、弧上，因为，又有, 所以给标；在弧上，因为，又有3标。,所以给 V因为前面已给 v3 标过号，这里又给标，它们分别表示两条不同的路线，这里不存在修改标号的问题（与最短路不同）。因为我们的目标是尽快找出一条从vs 到vt 的增广链， 即尽快使终点 vt获得标号， 所以不必在中途过多停留。 也就是说在对已标号点vi 进行检查时，每次只检查一个相邻点 vj （不论前向弧或后向弧均可） ，再给标号即可，而不必检查所有与 vi 相邻的点。事实上，其余的相邻点也不会漏掉，因为以后还要通过检查。8 欢迎下载精品文档这些点来找出新的增广链。以下我们就按这种思路进行。检查：在弧上，因为，又有.所以给标.至此，终

15、点已获得标号，于是找出一条从到的增广链。再由标号的第一部分用反向追踪法找出路线，即（见图 7-21 ）。进行调查：这时的调整量. 再按公式（ 7.20 ）调整。由于上各弧均为前向弧，故得，.（见图 7-21 ） . 其余的不变 .对这个新的可行流再进入标号过程，寻找新增广链。 开始给标，检查，给标，检查：在弧上，因为（见图 7-21 ），故该弧已饱和， 标号无法进行下去。在弧上，因为，又有所以给标，检查：。9 欢迎下载精品文档在弧上，因为，又有所以给标，检查：在弧上，因为，又有，所以给标.于是又得到一条增广链( 见图 7-22)进行调整：这时。调整结果如图9.28 所示。再重新标号求新的增广链

16、.开始给标，检查，给标。检查，给标，检查，给标，检查，因已是饱和弧 （见图 7-22 ）。标号无法进行。但在弧上，.又有，所以给标.于是又得到一条增广链：.再进行调整（见图7-23 ） .。10 欢迎下载精品文档再重新进行标号求新的增广链：开始给标（ 0，+），检查，给标.检查：这时弧均已饱和。而在弧上，因，又有所以给标，表明弧为后向弧.检查，给标。检查，给标。于是又得到一条增广链：.再进行调整（见图7-24 ）。再重新进行标号求新的增广链：开始给标 (0,+ ) ，检查，给标。检查，这时和均为前向弧，都已饱和，弧为后向弧，且为零流弧。故标号无法进行。但在弧上因为。又有。11 欢迎下载精品文档

17、.所以给标.检查, 给标。检查，因为已饱和（见图7-24 ）。而在弧上，因为，又有. 所以给标，再检查，给标。于是又得到一条增广链：.再进行调整（见图7-25 ）。再重新进行标号求新的增广链。开 始 给标 (0,+) ，检查，给标。检查，因为已饱和，而为弧上标号还可以继续进行，给标。检查。给标。于是又得到一条增广链再进行调整（见图7-26 ）。再重新进行标号：。12 欢迎下载精品文档开始给标 (0,+ ) ，检查：这时弧已饱和。标号无法进行。而还可以标号。再检查，如前所述，标号也无法进行。至此已求得最大流。我们将最大流表示在图7-27 中。最大流量为与此同时，可找到最小截集，其中为最后一轮已标号点的集合，为未标号点的集合，即最小截量为所以。图 7-27。13 欢迎下载精品文档由上述可见，用标号法找增广链以求最大流的结果，同时也得到一个最小截集。最小截集的容量的大小影响总的运输量的提高。因此，为提高总的运输量，必须首先考虑增大最小截集中各弧的容量，提高它们的通过能力。 反之，一旦最小截集中弧的通过能力降低，必然会使得运输量减少。前面讨论都是对一个发点、一个收点的网络最大流问题。对于多个发点和收点的情形，我