运筹学第四节最大流问题.ppt
《运筹学第四节最大流问题.ppt》由会员分享,可在线阅读,更多相关《运筹学第四节最大流问题.ppt(28页珍藏版)》请在三一文库上搜索。
1、第四节 最大流问题,理解最大流问题的概念、最大流-最小割定理。 掌握求最大流问题的标号算法。,引言 在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流,城市给排水系统的水流问题等等。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题,它对于解决生产实际问题起着十分重要的作用。,图是联结某个起始地vs和目的地vt的交通运输网,每一条弧vi 旁边的权cij表示这段运输线的最大通过能力,货物从vs运送到vt.要求指定一个运输方案,使得从vs到vt的货运量最大,这个问题就是寻求网络系统的最大流问题。,一、最大流有关概念 连通网络 G(V, E) 有 m 个节点, n条
2、弧, 弧 eij 上的流量上界为 cij, 求从起始节点 vs 到终点 vt 的最大流量。,定义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
3、. (2)平衡条件:,对于发点vs,收点vt有,对于中间点,有,任意一个网络上的可行流总是存在的。例如零流w(f)=0,就是满足以上条件的可行流。 网络系统中最大流问题就是在给定的网络上寻求一个可行流f,其流量w(f)达到最大值。 设流f =fij是网络G上的一个可行流。我们把G中fij=cij的弧叫做饱和弧,fij0的弧为非零流弧,fij=0的弧叫做零流弧 . 最大流问题实际是个线性规划问题。,其中发点的总流量(或收点的总流量) w 叫做这个可行流的总流量。,网络上的一个流(运输方案),每一个弧上的流量fij就是运输量。例如fs1=5 , fs2=3 , f13=2 等等。,定义21 设一个
4、网络G=(V,E,C),vs、vt为发和收点,边集 为E的子集,将G分成2个子图G1,G2;其顶点集合分别为: ,发点vsS,收点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,
5、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)+上,有0fijcij。 2在边(vi,vj
6、)上,有0fijcij,。 则称为从s到 vt可增广链。 在链(vs,v1,v2,v3,v4,vt)中,+ = (vs,v1 ),(v1,v2),(v2,v3),(v4,vt), = (v4 ,v3).,vt,vs,v1,v2,v3,v4,4,2,4,4,3,3,2,2,2,3,1,定理11提供了一个寻求网络系统最大流的方法。如果网络G中有一个可行流 f,只要判断网络是否存在关于可行流 f 的增广链 。如果没有增广链,那么f一定是最大流。如有增广链,那么可以按照定理中必要性,不断改进和增大可行流f 的流量,最终可以得到网络G中的一个最大流。,推论: 网络中的一个可行流f*是最大流的充分必要条件
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 第四 最大 问题
链接地址:https://www.31doc.com/p-2709594.html