《最大流问题[稻谷书苑].ppt》由会员分享，可在线阅读，更多相关《最大流问题[稻谷书苑].ppt（43页珍藏版）》请在三一文库上搜索。
1、第八章图与网络分析,图的基本概念与模型 树图和图的最小部分树 最短路问题 网络最大流问题 最小费用最大流问题,第八章图与网络分析,图的基本概念与模型 树图和图的最小部分树 最短路问题 网络最大流问题 最小费用最大流问题,网络最大流问题,50年代福特（Ford）、富克逊（Fulkerson）建立的“网络流理论”，是网络应用的重要组成部分。,如同我们可以把一个实际的道路地图抽象成一个有向图来计算两点之间的最短路径，我们也可以将一个有向图看作一个流网络来解决另一类型的问题。,流网络比较适合用来模拟液体流经管道、电流在电路网络中的运动、信息网络中信息的传递等等类似的过程。,问题的提出,在一个输油管网中
2、，有生产石油的油井、储存石油的油库、转运石油的中间泵站，同时，还有各种口径不同的输油管。当一个输油管网给定后，单位时间内最多可把多少石油从油井输送到油库？具体方案如何？,分析：就输油管网络问题，可用顶点表示油井、油库和中间泵站，用有向边表示输油管，用有向边上的权表示单位时间沿相应的输油管可以输送石油的最大数量（容量）。,如果我们把图看做输油管道网， 为起点， 为终点， 为中转站，边上的数表示该管道的最 大输油能力，问应该如何安排各管道输油量，才能 使从 到 的总输油量最大？,问题的提出,管道网络中每边的最大通过能力即容量是有限的，实际流量也不一定等于容量，上述问题就是要讨论如何充分利用装置的能
3、力，以取得最好效果（流量最大），这类问题通常称为最大流问题。,容量 发点（源） 收点（汇） 中间点 容量网络,网络有向图D=（V，A，C）,网络上流的基本概念,流,运输问题中，每个运输方案就是一个流,可行流,网络最大流问题,且满足,此为一个特殊的线性规划问题，将会看到利用图的特点，解决这个问题的方法要比单纯形法较为直观方便。,设 是网络D=（V，A，C）的一个可行流,（v1，v2）是饱和的,2、如果0fijcij，该弧是非饱和弧；,（v1，v2）是不饱和的 间隙为12=c12-f12=5-3=2,1、如果fij=cij，该弧是饱和弧；,弧关于流的分类,设 是网络D=（V，A，C）的一个可行流,
4、（v1，v2）是0流弧,4、如果fij0，该弧是非0弧；,（v1，v2）是非0弧,3、如果fij=0，该弧是0流弧；,弧关于流的分类,链及可增广链,链 在最大流问题中，研究的是有向网络图。但是在求最大流的方法中，则要使用无向网络中的链。,非0流弧,可增广链,非饱和弧,割集和割集的容量,割集的容量是割集中各弧的容量之和，用 表示。,割集的容量为9+9=18,割集,割集的意义：若把某一割集的弧从网络中丢去，则 从vs到vt便不存路，即割集是从vs到vt的必经之道！这里(v3,v2) 不属于此割集,vs,v1,v3,vt,v2,v4,8(8),7(5),9(4),5(5),6(1),2(0),5(4
5、),10(8),9(9),考虑KK的不同画法,基本定理(可行流与割集的关系),最大流-最小割定理：,构造法证明,这样就得到了一个寻求最大流的方法(算法思想)： 从一个可行流开始，寻求关于这个可行流的可增广链，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的可增广链时 就得到了最大流。,沿着这条链从 vs 到 vt 输送流，还有潜力可挖，只需按照调整方法，就可以把流量提高，调整后的流，在各点仍满足平衡条件及容量限制条件，即仍为可行流。,可增广链的实际意义,求解最大流的标号算法：,已饱和，流量不可再增。再检查 ，可调整量为 4-2=2，可提供
6、量+，取调整量,先给标号 （，+）,1） 寻找可增广链：,同理，给 标号,下对已标号点（可望调整点）接着向下检查。 已饱 和。再检查与 相邻接且未标号的点,给 标号 ，其中 表示 的所调整量2来自 ，且为正向流（向前流） 。,调整量为,给 标号为,可令调整量为,d) 检查与 相邻接且未标号的点 ， 。而 对 来讲是流 入，现欲增加流出量，应该压缩 的流入量，只要的流入量,f) 下面检查与 相邻接且未标号的点 ，同理，调整量：,给 标号为,g) 最后，给 标号,2）调整流量：从 到 所画出的红线即为可增广链。沿 该可增广链，从 倒推，标“”号的在实际流量上加上 该调整量，标“”符号的在实际流量上
7、减去该调整量。完 成调整过程。,反 向 追 踪,当标到 时，与 ， 相邻接的点 ， ， 都不满足标号条件，标号无法继续，且没有完成标号。此时最大流量即为所求。,重新开始标号，寻找可增广链。,网络从发点到收点的各通路中，由容量决定其通过能力，最小割则是这此路中的咽喉部分，或者叫瓶颈，其容量最小，它决定了整个网络的最大通过能力。要提高整个网络的运输能力，必须首先改造这个咽喉部份的通过能力。,最小割的意义,如果我们把图看做输油管道网， 为起点， 为终点， 为中转站，边上的数表示该管道的最 大输油能力，问应该如何安排各管道输油量，才能 使从 到 的总输油量最大？,解决问题,(vs,2),(-v2,2)
8、,(v1,1),(-v3,1),(v4,1),(vs,1),(-v2,1),(v1,2),W=f *s1+f *s2=8+6 =14,最大流问题应用举例,在图中任给可行流，用标号法寻找网络最大流！,弧容量：两点间的桥梁数。,转化为求网络最小割,设容量网络G有若干发点，若干个点，可以添加两个新点vs，vt ，用容量为 的有向边分别连结vs 与发点，收点与vt，得到新的网络G，G 为只有一个发点，一个收点的网络，求解G 的最大流问题即可得到G的解。,多发点多收点网络的最大流问题,最大流问题应用举例,设有5位待业者，5项工作，他们各自能胜任工作的情况如图所示，要求设计一个就业方案，使尽量多的人能就业。,其中,表示工人。,表示工作。,最大匹配问题,图中最大匹配问题，可以转化为最大流问题求解。在 图中增加两个新点 分别作为发点，收点。并用 有向边把它们与原图中顶点相连，令全部边上的容量 均为1。当网络流达到最大时，如果 上的流量为1， 就让 作 工作，此即为最大匹配方案。,第一次标号。,调整,第二次标号。,再调整。,第三次标号。,调整。,第四次标号。,调整,第五次标号。,标号过程已无法再继续。流量为1的画红线。,工人,分别作,故最多安排四个人工作。,vs,v1,v3,vt,v2,v4,8(8),7(5),9(4),9(9),5(5),6(1),2(0),5(4),10(8),