运筹学第四节最大流问题.pptVIP

第四节 最大流问题 求最大流的标号算法可以解决多发点多收点网络的最大流问题 小结 1、最大流问题的概念、最大流-最小割定理。 2、求最大流问题的标号算法。 作业 8.10,8.14 * 运筹学教程 理解最大流问题的概念、最大流-最小割定理。 掌握求最大流问题的标号算法。 ? 引言 在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。 图是联结某个起始地vs和目的地vt的交通运输网，每一条弧vi 旁边的权cij表示这段运输线的最大通过能力，货物从vs运送到vt.要求指定一个运输方案，使得从vs到vt的货运量最大，这个问题就是寻求网络系统的最大流问题。 一、最大流有关概念 连通网络 G(V, E) 有 m 个节点, n条弧, 弧 eij 上的流量上界为 cij, 求从起始节点 vs 到终点 vt 的最大流量。 vt v3 v2 v1 v4 vs 17 3 5 10 8 6 11 4 5 3 Cij 定义20 设一个赋权有向图G=（V,E）,对于G中的每一个边（弧）（vi ,vj）∈E,都有一个非负数cij叫做边的容量。在V 中一个入次为零的点称为发点vs，一个出次为零的点称为收点vt ,其它的点叫做中间点。我们把这样的图G叫做一个容量网络，记做G=（V，E，C）。 网络G上的流，是指定义在边(vi ,vj)上有流量fij，称集合f={fij} 为网络G上的一个流， f为可行流。 网络上的一个流f 叫做可行流，如果f 满足以下条件： （1）容量条件：对于每一个弧（vi ,vj）∈E,有 0 ? fij ? cij . （2）平衡条件： 对于发点vs,收点vt有 对于中间点，有 任意一个网络上的可行流总是存在的。例如零流w(f)=0,就是满足以上条件的可行流。 网络系统中最大流问题就是在给定的网络上寻求一个可行流f,其流量w(f)达到最大值。 设流f ={fij}是网络G上的一个可行流。我们把G中fij=cij的弧叫做饱和弧，fijcij的弧叫做不饱和弧，fij0的弧为非零流弧，fij=0的弧叫做零流弧 . 最大流问题实际是个线性规划问题。 其中发点的总流量（或收点的总流量） w 叫做这个可行流的总流量。 v3 v2 v1 v4 vs （2） （3） （2） （5） （3） （3） （6） （1） （1） （2） fij vt 网络上的一个流（运输方案），每一个弧上的流量fij就是运输量。例如fs1=5 , fs2=3 , f13=2 等等。 定义21 设一个网络G=（V，E，C），vs、vt为发和收点，边集 为E的子集，将G分成2个子图G1,G2;其顶点集合分别为: ,发点vs∈S,收点vt∈ /S ,满足 1.G=（V，E- ）不连通； 2. 为 的真子集，而G=（V，E- ）连通； 那么 为G的割集，记为 =(S, )。 割集 (S, )所有始点在S，终点在 的容量之和，称为(S, )的割集容量，记为C(S, ) 。 vt vs v1 v2 v3 v4 4 2 4 4 3 3 2 2 2 3 1 边集{(vs,v1),(vs,v3),(vs,v4)} 边集{(vs,v1),(v1,v3),(v2,v3),(v3,vt)} 为图的割集，割集容量分别为11，9 二、最大流-最小割定理 定理10：设f为网络G=（V，E，C）的任一个可行流，流量为W, (S, )是分离vs vt的任一个割集，则有W ? C(S, ) . 定理11：最大流-最小割定理:任一个网络G=（V，E，C）,从vs到vt的最大流的流量等于分离vs vt的最小割的容量。 定义22：设μ是网络G中连接发点νs和收点vt的一条链。定义链的方向是从νs到 vt ，于是链μ上的边被分为两类：一类是边的方向与链的方向相同，叫做前向边，前向边的集合记做μ+。二类是边的方向与链的方向相反，叫做后向边，后向边的集合记做μ–。 如果链μ满足以下条件： 1．在边（vi ,vj）∈μ+上，有0?fijcij。 2．在边（vi,vj）∈μ–上，有0fij?cij,。 则称μ为从νs到 vt可增广链。 在链（vs,v1,v2,v3,v4,vt)中，μ+ = {(vs,v1 ),(v1,v2)