《网络最大流问题.ppt》由会员分享，可在线阅读，更多相关《网络最大流问题.ppt（52页珍藏版）》请在三一办公上搜索。
1、,课程讲授：黄玉诚,运筹学,中国矿业大学(北京),第六章 图与网络分析,第一节 图的基本知识第二节 树第三节 最短路问题第四节 网络最大流问题第五节 最小费用最大流问题,第四节 网络最大流问题,图10-23是联结某产品产地v1和销地v6的交通网，每一弧(vi，vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数字表示这条运输线的最大通过能力。现在要求制定一个运输方案使从v1运到v6的产品数量最多。,图10-23,图10-24给出了一个运输方案，每条弧旁的数字表示每条运输线上的运输数量。这个方案使8个单位的产品从v1运到v6。在这个运输网络中，从v1到v6的最大输送量是多少呢?
2、,图10-23,图10-24,一、基本概念与基本定理,1、网络与流 定义1 给一个有向图D=(V,A)，在V中指定了一点，称为发点(记为vs)，和另一点，称为收点(记为vt)，其余的点叫中间点。对于每一个弧(vi，vj)A,对应有一个c(vi，vj)0(或简写为cij)，称为弧的容量。通常把这样的D叫作一个网络。记作D=(V，A，C)。,对D中的任一弧(vi，vj)有流量f(vi，vj)(有时也简记作fij)，称集合f=fij为网络D上的一个流。,2、可行流与最大流,定义2 满足下述条件的流 f 称为可行流：1）容量限制条件：对每一弧(vi，vj)A0fijcij,可行流,2）平衡条件：对于中
3、间点：流出量流入量，即对每个i(is,t)有,对于发点vs，,式中v(f)称为这个可行流的流量，即发点的净输出量(或收点的净输入量)。,所谓最大流问题就是在网络中，寻找流量最大的可行流，即：求一个流fij使其流量v(f)达到最大，并且满足0fijcij(vi，vj)A,最大流,可行流总是存在的，例如(fij)=0就是一个流量为0的可行流。,3、增广链,若给一个可行流f=fij，我们把网络中使 fij=cij 的弧称为饱和弧，使fij0的弧称为非零流弧。,若是网络中联结发点vs和收点vt的一条链，我们定义链的方向是从vs到vt，则链上的弧被分为两类：一类是弧的方向与链的方向一致，叫作前向弧。前向
4、弧的全体记为+。另一类弧与链的方向相反，称为后向弧。后向弧的全体记为-。,定义3 设f是一个可行流，是从vs到vt的一条链，若满足下列条件,称之为(关于可行流 f 的)一条增广链。在弧(vi，vj)+上，0fijcij，即+中每一弧是非饱和弧。在弧(vi，vj)-上，0fijcij，即-中每一弧是非零流弧。,图10-24中，链=(v1,v2,v3,v4,v5,v6)是一条增广链。因为+和-中的弧满足增广链的条件。如：(v1,v2)+,f12=50。,4、截集与截量,设S,TV，ST=，我们把始点在S，终点在T中的所有弧构成的集合，记为(S，T)。,定义4 给网络D=(V，A，C)，若点集V被剖
5、分为两个非空集合V1和，使vsV1，vt，则把弧集(V1,)称为是(分离vs和vt的)截集。,可以看出，从网络中去掉任一截集，则从vs到vt便不存在路。所以，截集是从vs到的vt必经之路。,定义5 给一截集(V1,)，把截集(V1,)中所有弧的容量之和称为这个截集的容量(简称为截量)，记为c(V1,)，即,任何一个可行流的流量v(f)都不会超过任一截集的容量。即,显然，若对于一个可行流f*，网络中有一个截集(V1*,)，使v(f*)=c(V1*,),则f*必是最大流，而(V1*,)必定是D的所有截集中容量最小的一个，即最小截集。,定理1 可行流f*是最大流的充分必要条件是不存在从vs到vt的(
6、关于f*)增广链。,由增广链的定义，可知0,令网络上的另一个流：,仍为可行流(即满足容量限制条件与平衡条件)，但 的总流量等于 的流量加，即,这与 是最大流的前提矛盾。,(二)充分性：若不存在关于f*增广链，那么f*是最大流。,显然有,那么，可行流f*上的流量,则f*必然是最大流。,最大流量最小截量定理：任一个网络D中，从vs到vt的最大流的流量等于分离vs，vt的最小截集的容量。,增广链的实际意义是：沿着这条链从vs到vt输送的流，还有潜力可挖，只需按照定理1证明中的调整方法，就可以把流量提高，调整后的流，在各点仍满足平衡条件及容量限制条件，即仍为可行流。,这样就得到了一个寻求最大流的方法：
7、从一个可行流开始，寻求关于这个可行流的增广链，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的增广链时就得到了最大流。,寻求最大流的思路：利用定理1中对V1*定义，根据vt是否属于V1*来判断D中有无关于f的增广链。,实际计算时，可以用给顶点标号的方法来确定属于V1*的点。在标号过程中，有标号的顶点表示是V1*中的点，没有标号的点表示不是V1*中的点。一旦vt有了标号，就表明找到一条增广链；,如果标号过程进行不下去，而vt尚未标号，则说明不存在增广链，于是得到最大流。而且同时也得到一个最小截集。,二、寻求最大流的标号法,在标号过程中，网络
8、中的点分为两类：(1)标号点(又分为已检查和未检查两种)。每个标号点的标号内容包含两部分：标号的第一部分表明它的标号是从哪一点得到的，以便找出增广链；标号的第二部分是为确定增广链的调整量用的。(2)未标号点。,标号过程:,(1)给发点vs标上(0，+)；这时vs是标号而未检查的点，其余都是未标号点。,(2)取一个标号而未检查的点vi，对于vi的所有未给标号的相邻点vj按下列规则处理：,(a)若在弧(vi,vj)上，fijcij，则给vj标号(vi，l(vj)。这里l(vj)=minl(vi),cij-fij。这时点vj成为标号而未检查的点。,(b)若在弧(vj,vi)上，fji0，则给vj标号
9、(-vi，l(vj)，这里l(vj)=min(l(vi),fij。这时点vj成为标号而未检查的点。,这样，vj成为标号而已检查过的点。,若vt未获得标号，而标号过程无法进行时，则算法结束，这时的可行流 f 就是最大流。,(3)重复步骤(2)，直到vt被标上号，表明得到一条从vs到vt的增广链，转入调整过程。,例如：设vt的第一个标号为vk，则弧(vk,vt)是上的弧。接下来检查vk的第一个标号，若为vi，则找出(vi,vk)。再检查vi的第一个标号，依此下去，直到vs为止。这时被找出的弧就构成了增广链。,(1)找出增广链。按vt及其它点的第一个标号，利用“反向追踪”的办法，找出增广链。,(2)
10、在增广链上调整流量。,令调整量为 l(vt)，即vt的第二个标号。,(3)去掉所有的标号，对新的可行流，重新进入标号过程。,例 用标号法求图10-25所示网络的最大流。弧旁的数是(cij,fij)。,解(一)标号过程(1)首先给vs标上(0，+),(0,+),图10-25,(2)检查vs。,(vs,4),弧(vs，v1)上，fs11，cs1=5，fs1 cs1,则v1的标号为(vs,l(v1)，其中，l(v1)=minl(vs),(cs1-fs1)=min+,5-1=4,在弧(vs，v2)上，fs2=cs23，不满足标号条件。,(3)检查v1。,(-v1,1),在弧(v2，v1)上，f21=1
11、0，则给v2记下标号为(-v1,l(v2)，这里 l(v2)=minl(v2),f21=min4，1=1,在弧(v1，v3)上，f13=2，c13=2，不满足标号条件。,(4)检查v2。,(v2,1),(-v2,1),在弧(v2，v4)上，f21=3，c24=4，f24 c24，则给v4标号(v2,l(v4)。l(v4)=minl(v2),(c24-f24)=min1,1=1,在弧(v3，v2)上，f32=10，给v3标号：(-v2,l(v3)，l(v3)=minl(v2),f32=min1,1=1,(5)在v3,v4中任选一个进行检查。,(v4,1),例如，在弧(v4，vt)上，f4t=3，
12、c4t=5，f4t c4t,给vt标号为(v4,l(vt)，这里l(vt)minl(v4),(c4t-f4t)=min1,2=1,因vt有了标号，故转入调整过程。,(二)调整过程,(1)按点的第一个标号找到一条增广链。,(2)在增广链上调整流量。,在增广链上+=(vs，v1),(v2，v4),(v4，vt)-=(v2，v1),-上：,调整后的网络图如下:,(0,+),(一)标号过程(1)首先给vs标上(0，+),(0,+),(2)检查vs。,(vs,3),弧(vs，v1)上，fs12，cs1=5，fs1 cs1,则v1的标号为(vs,l(v1)，其中，l(v1)=minl(vs),(cs1-f
13、s1)=min+,5-3=3,在弧(vs，v2)上，fs2=cs23，不满足标号条件。,(0,+),(vs,3),(3)检查v1。,标号过程无法继续下去，算法结束。,在弧(v2，v1)上，f21=0，不满足标号条件。在弧(v1，v3)上，f13=2，c13=2，不满足标号条件。,这时的可行流即为所求最大流。最大流量为：v(f)=fs1+fs2=f4t+f3t5。,同时，可以得到已标号点集合V1=vs,v1，和未标号点集合=v2,v3,v4,vt。,相应地，弧集合=(vs,v2),(v1,v3)即为最小截集，它的容量也是5，等于最大流量。,由此，也可以体会到最小截集的意义。网络从发点到收点的各通
14、路中，向容量决定其通过能力，最小截集则是这些路中的咽喉部分，或者叫瓶颈，其容量最小，它决定了整个网络的最大通过能力。要提高整个网络的运输能力，必须首先改进这个咽喉部分的通过能力。,图10-23,例如，图10-23就是一个网络，指定v1是发点，v6是收点，其它的点是中间点。弧旁的数字为cij。,图10-24所示的运输方案，就可看作是这个网络上的一个流，每个弧上的运输量就是该弧上的流量，如：f12=5，f24=2，f13=3，f34=1。,图10-24,图10-24给出了一个运输方案，每条弧旁的数字表示每条运输线上的运输数量。这个方案使8个单位的产品从v1运到v6。在这个运输网络中，从v1到v6的
15、最大输送量是多少呢?,图10-23,图10-24,图10-24中，(v5,v4)是饱和弧，其它的弧为非饱和弧。所有弧都是非零流弧。,图10-23,图10-24,图10-23,图10-23中，在链=(v1,v2,v3,v4,v5,v6)中+=(v1,v2),(v2,v3),(v3,v4),(v5,v6)-=(v5,v4),图10-24中，链=(v1,v2,v3,v4,v5,v6)是一条增广链。因为+和-中的弧满足增广链的条件。比如：(v1,v2)+,f12=50。,图10-24,图10-23,+1,+1,+1,-1,+1,图10-23,例如，弧集(v1,v2)，(v2,v3)，(v2,v5)，(
16、v2,v4)、弧集(v2,v4)，(v2,v5)，(v3,v4)，(v3,v5)都是网络D的截集。,弧集(v4,v6)，(v2,v5)，(v3,v5)也是网络D的截集。,图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的截集。,由增广链的定义，可知0,令网络上的另一个流：,仍为可行流(即满足容量限制条件与平衡条件)，但 的总流量等于 的流量加，即,这与 是最大流的前提矛盾。,图10-23,例如，弧集(v1,v2)，(v2,v3)，(v2,v5)，(v2,v4)和弧集(v2,v4)，(v2,v5)，(v3,v4)，(v3,v5)都是网络D的截集。,
