chapter 7.4 最大流问题

《chapter 7.4 最大流问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章   图与网络规划图的基本概念最小树问题最短路问题最大流问题最小费用最大流问题7.4最大流问题如同我们可以把一个实际的道路地图抽象成一个有向图来计算两点之间的最短路径，我们也可以将一个有向图看作一个网络流来解决另一类型的问题。网络流比较适合用来模拟液体流经管道、电流在电路网络中的运动、信息网络中信息的传递等等类似的过程。问题的提出在一个输油管网中，有生产石油的油井、储存石油的油库、转运石油的中间泵站，同时，还有各种口径不同的输油管。当一个输油管网给定后，单位时间内最多可把多少石油从油井输送到油库？具体方案如何？分析：就输油管网络问题，可

2、用顶点表示油井、油库和中间泵站，用有向边表示输油管，用有向边上的权表示单位时间沿相应的输油管可以输送石油的最大数量（容量）。如果我们把图看做输油管道网，为起点，为终点，为中转站，边上的数表示该管道的最大输油能力，问应该如何安排各管道输油量，才能使从到的总输油量最大？问题的提出管道网络中每边的最大通过能力即容量是有限的，实际流量也不一定等于容量，上述问题就是要讨论如何充分利用装置的能力，以取得最好效果（流量最大），这类问题通常称为最大流问题。vsv1v3vtv2v48799562510容量发点（源）收点（汇）中间点容量网络网络有向图D=（V，A

3、，C）网络上流的基本概念vsv1v3vtv2v48799562510流vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)运输问题中，每个运输方案就是一个流可行流网络最大流问题且满足此为一个特殊的线性规划问题，将会看到利用图的特点，解决这个问题的方法要比单纯形法较为直观方便。设是网络D=（V，A，C）的一个可行流（v1，v2）是饱和的2、如果0≤fij

4、=5cij=5v1v2fij=3cij=5v1v2设是网络D=（V，A，C）的一个可行流（v1，v2）是0流弧4、如果fij>0，该弧是非0弧；（v1，v2）是非0弧3、如果fij=0，该弧是0流弧；弧关于流的分类fij=0cij=5v1v2fij>0cij=5v1v2链及增广链链在最大流问题中，研究的是有向网络图。但是在求最大流的方法中，则要使用无向网络中的链。vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)非0流弧增广链vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1

5、)2(0)5(4)10(8)非饱和弧截集和截集的容量设有网络D={V，A，C}，点vs与点vt是集合V中的任意两点，若点集V被剖分成两个非空集合，使，记以中的点为始点，的A中弧的集合记为则称这个弧的集合是分离点vs与点vt的截集。中的点为终点截集的容量是截集中各弧的容量之和，用表示。截集的容量为9+9=18截集KK截集的意义：若把某一截集的弧从网络中丢去，则从vs到vt便不存路，即截集是从vs到vt的必经之道！这里(v3,v2)不属于此截集vsv1v3vtv2v48(8)7(5)9(4)5(5)6(1)2(0)5(4)10(8)9(9)考虑K

6、K的不同画法vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)截集截集容量由于有限网络的截集只有有限多个，则截集容量的集合是有限的实数集合，令称截集容量为C0的截集为D的最小截集。（瓶颈）{v3,t}基本定理(可行流与截集的关系)最大流-最小截定理：构造法证明截截这样就得到了一个寻求最大流的方法(算法思想)：从一个可行流开始，寻求关于这个可行流的增广链，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的增广链时就得到了最大流。沿着这条链从vs

7、到vt输送流，还有潜力可挖，只需按照调整方法，就可以把流量提高，调整后的流，在各点仍满足平衡条件及容量限制条件，即仍为可行流。增广链的实际意义求解最大流的标号算法：求解最大流的标号算法：0l(vj)=min[l(vi),cij-fij],标号(vi,l(vj));l(vj)=min[l(vi),fji],标号(-vi,l(vj));否则不标号θθ例7.5用标号法求图所示网络的最大流。弧旁的数是(cij,fij)b)接着检查与相邻接的点已饱和，流量不可再增。再检查，可调整量为5-1=4，可提供量+∞，取调整量先给标号（0，+∞）1）寻找增广链：

8、给标号，其中表示的所调整量4来自，且为正向流（向前流）。下对已标号点（可望调整点）接着向下检查。已饱和。再检查与相邻接且未标号的点可令调整量为给标号为表示可控量，反