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

第四节 最大流问题 求最大流的标号算法可以解决多发点多收点网络的最大流问题 小结 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