运筹学第7章 最大流问题(精简).ppt

1、最大流问题,给定一个有向图G(V,E)，其中仅有一个点的入次为零称为发点（源），记为vs，仅有一个点的出次为零称为收点（汇），记为vt，其余点称为中间点。,基本概念,3,5,1,1,4,2,3,5,2,vs,v2,v1,v3,v4,vt,对于G中的每一条边(vi,vj)，相应地给一个数cij（cij0），称为边(vi,vj)的容量。我们把这样的网络 G称为容量网络 ，记为G(V,E,C)。,网络上的流，是指定义在边集E上的函数ff(vi,vj)，并称f(vi,vj)为边(vi,vj)上的流量，简记为fij。,3,1,5,2,1,0,1,0,4,1,2,2,3,1,5,2,2,1,vs,v2,v

2、1,v3,v4,vt,标示方式：每条边上标示两个数字，第一个是容量，第二是流量,可行流、可行流的流量、最大流。,可行流是指满足如下条件的流：,（1）容量限制条件：对G中每条边(vi,vj), 有,（2）平衡条件：,对中间点，有：,（即中间点vi的物资输入量等于输出量）,对收点vt与发点vs，有：,（即vs发出的物资总量等于vt接收的物资总量），W是网络的总流量。,可行流总是存在的，例如f=0就是一个流量为0的可行流。 所谓最大流问题就是在容量网络中寻找流量最大的可行流。 一个流f=fij，当fij=cij，则称f对边(vi, vj)是饱和的，否则称f对边(vi, vj)不饱和。对于不饱和的，其

3、间隙为ij=cij-fij 最大流问题实际上是一个线性规划问题。 但利用它与图的密切关系，可以利用图直观简便地求解。,给定容量网络G(V,E,C)，若点集V被剖分为两个非空集合V1和V2，使 vsV1 ，vtV2，则把边集(V1,V2)称为（分离vs和vt的）割集。,显然，若把某一割集的边从网络中去掉，则从vs到vt便不存在路。所以，直观上说，割集是从vs到vt的必经之路。,3,5,1,1,4,2,3,5,2,vs,v2,v1,v3,v4,vt,vs,v1,v4,v3,vt,v2,边集（vs,v1），（v1,v3），（v2,v3），（v3,vt），（v4,vt）是G的割集。其顶点分别属于两个互

4、补不相交的点集。去掉这五条边，则图不连通，去掉这五条边中的任意1-4条，图仍然连通。,割集的容量(简称割量) 最小割集,割集(V1, V2)中所有起点在V1，终点在V2的边的容量的和称为割集容量。例如下图中所示割集的容量为5,3,5,1,1,4,2,3,5,2,vs,v2,v1,v3,v4,vt,在容量网络的所有割集中，割集容量最小的割集称为最小割集（最小割）。,对于可行流ffij，我们把网络中使fijcij的边称为饱和边，使fij0的边称为非零流边。,设f是一个可行流，是从vs到vt的一条链，若满足前向边都是非饱和边,后向边都是都是非零流边,则称是（可行流f的）一条可增广链。,3,1,5,2

5、,1,0,1,0,4,1,2,2,3,1,5,2,2,1,vs,v2,v1,v3,v4,vt,若是联结发点vs和收点vt的一条链，我们规定链的方向是从vs到vt，则链上的边被分成两类：前向边、后向边。,对最大流问题有下列定理： 定理1 容量网络中任一可行流的流量不超过其任一割集的容量。 定理2（最大流-最小割定理）任一容量网络中，最大流的流量等于最小割集的割量。 推论1 可行流f*fij*是最大流，当且仅当G中不存在关于f*的增广链。,求最大流的标号法,标号法思想是：先找一个可行流。对于一个可行流，经过标号过程得到从发点vs到收点vt的增广链；经过调整过程沿增广链增加可行流的流量，得新的可行流

6、。重复这一过程，直到可行流无增广链，得到最大流。,标号过程: (1)给vs标号(,+)，vs成为已标号未检查的点，其余都是未标号点。 (2)取一个已标号未检查的点vi，对一切未标号点vj：若有非饱和边(vi,vj)，则vj标号(vi,l(vj)，其中l(vj)minl(vi),cij fij，vj成为已标号未检查的点；若有非零边(vj,vi)，则vj标号(-vi,l(vj)，其中l(vj)minl(vi), fji，vj成为已标号未检查的点。vi成为已标号已检查的点。 (3)重复步骤(2)，直到vt成为标号点或所有标号点都检查过。若vt成为标号点，表明得到一条vs到vt的增广链，转入调整过程；

7、若所有标号点都检查过，表明这时的可行流就是最大流，算法结束。 调整过程：在增广链上，前向边流量增加l(vt)，后向边流量减少l(vt)。,下面用实例说明具体的操作方法：例,(3,3),(5,1),(1,1),(1,1),(4,3),(2,2),(3,0),(5,3),(2,1),vs,v2,v1,v3,v4,vt,(3,3),(5,1),(1,1),(1,1),(4,3),(2,2),(3,0),(5,3),(2,1),vs,v2,v1,v3,v4,vt,在图中给出的可行流的基础上，求vs到vt的最大流。,(,+),(vs,4),(-v1,1),(-v2,1),(v2,1),(v3,1),(3

8、,3),(5,2),(1,0),(1,0),(4,3),(2,2),(3,0),(5,3),(2,2),vs,v2,v1,v3,v4,vt,(vs,3),(,+),得增广链，标号结束，进入调整过程,无增广链，标号结束，得最大流。同时得最小割。,下图中已经标示出了一个可行流，求最大流, ,vs, 3,vs, 4,v2, 4,-v4, 2,v4, 3,如图已经得到增广链，然后进行调整。,调整后的可行流如下图：, ,vs, 3,vs, 1,v2, 1,-v4, 1,v3, 1,v5, 1,如图已经得到增广链，然后进行调整。,调整后的可行流如下图：,-, ,vs, 3,如图所示最小割集的容量（即当前可

9、行流的流量），就是最大流的流量。注：用该方法可以同时得到最小割集，即图中连结已标号的点与未标号的点的边集。,具有实际背景的例子,国庆大假期间旅游非常火爆，机票早已订购一空。成都一家旅行社由于信誉好、服务好，所策划的国庆首都游的行情看好，要求参加的游客众多，游客甚至不惜多花机票钱辗转取道它地也愿参加此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此问题。很快，各办事处将其已订购机票的情况传到了总社。根据此资料，总社要作出计划，最多能将多少游客从成都送往北京以及如何取道转机。下面是各办事处已订购机票的详细情况表：,用图来描述就是,发点vs =成都，收点vt =北京。前面已订购机票情况表中的数字即是各边上的容量（允许通过的最大旅客量），当各边上的实际客流量为零时略去不写，以零流作为初始可行流。,利用标号法（经5次迭代）可以得到从成都发送旅客到北京的最大流量如图所示,重,武,昆,上,广,西,郑,沈,京