运筹学课件四最大流问题.ppt

第四节 最大流问题 求最大流的标号算法可以解决多发点多收点网络的最大流问题 小结 1、最大流问题的概念、最大流-最小割定理。 2、求最大流问题的标号算法。 作业 8.10,8.14 * 运筹学教程 理解最大流问题的概念、最大流-最小割定理。 掌握求最大流问题的标号算法。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. ? 引言 在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 图是联结某个起始地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 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 定义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为可行流。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 网络上的一个流f 叫做可行流，如果f 满足以下条件： （1）容量条件：对于每一个弧（vi ,vj）∈E,有 0 ? fij ? cij . （2）平衡条件： 对于发点vs,收点vt有 对于中间点，有 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 任意一个网络上的可行流总是存在的。例如零流w(f)=0,就是满足以上条件的可行流。 网络系统中最大流问题就是在给定的网络上寻求一个可行流f,其流量w(f)达到最大值。 设流f ={fij}是网络G上的一个可行流。我们把G中fij=cij的弧叫做饱和弧，fijcij的弧叫做不饱和弧，fij0的弧为非零流弧，fij=0的弧叫做零流弧 . 最大流问题实际是个线性规划问题。 其中发点的总流量（或收点的总流量） w 叫做这个可行流的总流量。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. v3 v2 v1 v4 vs （2） （3） （2） （5） （3） （3） （6） （1） （1） （2） fij vt 网络上的一个流（运输方案），每一个弧上的流量fij就是运输量。例如fs1=5 , fs2=3 , f13=2 等等。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 定义21 设一个网络G=（V，E，C），vs、v