分享
分销 收藏 举报 申诉 / 28

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

  • 上传人:仙人****88
  • 文档编号:14749252
  • 上传时间:2026-11-13
  • 格式:PPT
  • 页数:28
  • 大小:299.50KB
  • 下载积分:10 金币
  • 配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

    关 键  词:
    运筹学 课件 第四 最大 问题
    资源描述:
    单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学教程,第四节 最大流问题,理解最大流问题的概念、最大流,-,最小割定理。,掌握求最大流问题的标号算法。,引言,在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流,城市给排水系统的水流问题等等。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题,它对于解决生产实际问题起着十分重要的作用。,图是联结某个起始地,v,s,和,目的地,v,t,的交通运输网,每一条弧,v,i,旁边的权,c,ij,表示这段运输线的最大通过能力,货物从,v,s,运送到,v,t,.,要求指定一个运输方案,使得从,v,s,到,v,t,的货运量最大,这个问题就是寻求网络系统的最大流问题,。,一、最大流有关概念,连通网络,G,(,V,E,),有,m,个节点,n,条弧,弧,e,ij,上的流量上界为,c,ij,求从起始节点,v,s,到终点,v,t,的最大流量。,v,t,v,3,v,2,v,1,v,4,v,s,17,3,5,10,8,6,11,4,5,3,C,ij,定义,20,设一个赋权有向图,G,=(,V,E,),对于,G,中的每一个边(弧)(,v,i,v,j,),E,都有一个,非负数,c,ij,叫做边的,容量,。在,V,中一个入次为零的点称为发点,v,s,,,一个出次为零的点称为收点,v,t,其它的点叫做中间点。我们把这样的图,G,叫做一个,容量,网络,,记做,G,=(,V,E,,,C,)。,网络,G,上的流,,是指定义在边,(,v,i,v,j,),上有流量,f,ij,,,称集合,f=,f,ij,为网络,G,上的一个流,,f,为可行流。,网络上的一个流,f,叫做可行流,如果,f,满足以下条件:,(,1,)容量条件:,对于每一个弧,(,v,i,v,j,),E,有,0,f,ij,c,ij,.,(2),平衡条件:,对于发点,v,s,收点,v,t,有,对于中间点,有,任意一个网络上的可行流总是存在的。例如零流,w,(,f,)=0,就是满足以上条件的可行流。,网络系统中最大流问题就是在给定的网络上寻求一个可行流,f,其流量,w,(,f,),达到最大值。,设流,f,=,f,ij,是网络,G,上的一个可行流。我们把,G,中,f,ij,=,c,ij,的弧叫做饱和弧,,f,ij,0,的弧为非零流弧,,f,ij,=0,的弧叫做零流弧,.,最大流问题实际是个线性规划问题。,其中发点的总流量(或收点的总流量),w,叫做这个可行流的总流量。,v,3,v,2,v,1,v,4,v,s,(2),(3),(2),(5),(3),(3),(6),(1),(1),(2),f,ij,v,t,网络上的一个流(运输方案),每一个弧上的流量,fij,就是运输量。例如,f,s1,=5,f,s2,=3,f,13,=2,等等。,定义,21,设一个网络,G,=(,V,E,C,),,,v,s,、,v,t,为发,和,收点,边集,为,E,的子集,将,G,分成,2,个子图,G,1,G,2,;,其顶点集合分别为,:,发点,v,s,S,收点,v,t,/S,满足,1.,G,=(,V,E-,),不连通;,2.,为 的真子集,而,G,=(,V,E-,),连通;,那么 为,G,的,割集,记为,=(,S,)。,割集,(,S,),所有始点在,S,,终点在 的容量之和,称为,(,S,),的,割集容量,记为,C(S,)。,v,t,v,s,v,1,v,2,v,3,v,4,4,2,4,4,3,3,2,2,2,3,1,边集,(,v,s,v,1,),(v,s,v,3,),(v,s,v,4,),边集,(,v,s,v,1,),(v,1,v,3,),(v,2,v,3,),(v,3,v,t,),为图的割集,割集容量分别为,11,,9,二、最大流,-,最小割定理,定理,10,:,设,f,为网络,G,=(,V,E,C,),的,任一个可行流,流量为,W,(S,),是分离,v,s,v,t,的,任一个割集,则有,W,C(S,).,定理,11,:,最大流,-,最小割定理,:,任一个,网络,G,=(,V,E,C,),从,v,s,到,v,t,的,最大流的流量等于,分离,v,s,v,t,的最小割的容量。,定义,22,:,设,是网络,G,中连接发点,s,和收点,v,t,的一条链。定义链的方向是从,s,到,v,t,,,于是链,上的边被分为两类:一类是边的方向与链的方向相同,叫做前向边,前向边的集合记做,+,。,二类是边的方向与链的方向相反,叫做后向边,,后向,边,的集合记做,。,如果链,满足以下条件:,1,在边,(,v,i,v,j,),+,上,有,0,f,ij,c,ij,。,2,在边,(,v,i,v,j,),上,有,0,f,ij,c,ij,。,则称,为,从,s,到,v,t,可增广链。,在链,(,v,s,v,1,v,2,v,3,v,4,v,t,),中,,+,=(,v,s,v,1,),(,v,1,v,2,),(,v,2,v,3,),(,v,4,v,t,),=(,v,4,v,3,).,v,t,v,s,v,1,v,2,v,3,v,4,4,2,4,4,3,3,2,2,2,3,1,定理,11,提供了一个寻求网络系统最大流的方法。如果网络,G,中有一个可行流,f,,,只要判断网络是否存在关于可行流,f,的增广链。如果没有增广链,那么,f,一定是最大流。如有增广链,那么可以按照定理中必要性,不断改进和增大可行流,f,的流量,最终可以得到网络,G,中的一个最大流。,推论:,网络中的一个可行流,f*,是最大流的充分必要条件是,不存在关于,f,*,的增广链。,在一个网络,G,中,最大流的流量等于分离,v,s,和,v,t,的最小割集的割量。,三、标号法,从网络中的一个可行流,f,出发(如果,G,中没有,f,,,可以令,f,是零流),运用标号法,经过标号过程和调整过程,可以得到网络中的一个最大流。,如果,v,t,有了标号,表示存在一条关于,f,的增广链。如果标号过程无法进行下去,并且,v,t,未被标号,则表示不存在关于,f,的增广链。这样,就得到了网络中的一个最大流和最小割集。,1,标号过程,在标号过程中,网络中的每个标号点的标号包含两部分:第一个标号表示这个标号是从那一点得到的,以便找出增广链;第二个标号是为了用来确定增广链上的调整量,。,标号过程开始,先给,v,s,标号,(,,,+,),,一般地,取一个标号顶点,v,i,,,对,v,i,所有,未标号的邻接点,v,j,按照下面条件进行处理:,(,1,)如果在弧(,v,i,v,j,),上,,f,ij,0,那么给,v,j,标号,(,-,v,i,(,vj,),),.,其中,(,vj,),=min,f,ji,(,vi,),。,重复以上步骤,如果收点,Vt,被标号或不再有顶点可标号为止,则标号法结束。这时的可行流就是最大流。,2.,调整过程,令,但是,如果,v,t,被标上号,表示得到一条增广链,,,转入下一步调整过程。,3.,再去掉所有的标号,对新的可行流,f,=,f,ij,重新进行标号过程,直到找到网络,G,的最大流为止。,v,s,v,2,v,5,v,t,v,4,v,1,v,6,v,3,(5,5),(3,2),(3,3),(4,2),(5,4),(3,3),(2,2),(5,2),(4,2),(2,2),例,求图的网络最大流,弧旁的权,数表示(,c,ij,f,ij,),。,v,s,v,2,v,5,v,t,v,4,v,1,v,6,v,3,(5,5),(3,2),(3,3),(4,2),(5,4),(3,3),(2,2),(5,2),(4,2),(2,2),解:,用标号法。,1.,标号过程。,(,1,),首先给,v,s,标号(,,+,),(,2,),检查,v,s,邻接点,v,1,v,2,v,3,:,v,2,点,满足(,v,s,v,2,)E,且,f,s2,=2,c,s2,=4,v2,=min2,+=2,给,v,2,以标号,(+,v,s,2);,v,3,点,满足(,v,s,v,3,)E,且,f,s3,=2,c,s3,=3,v3,=min1,+=1,给,v,3,以标号,(+,v,s,1);,(,,+,),(+,v,s,2),(+,v,s,1),(3),检查,v,2,邻接,点,v,5,v,6,:,v,5,点,满足(,v,2,v,5,)E,且,f,25,=0,c,15,=0,v1,=min3,2=2,给,v,1,以标号,(-,v,5,2);,v,s,v,2,v,5,v,t,v,4,v,1,v,6,v,3,(5,5),(3,2),(3,3),(4,2),(5,4),(3,3),(2,2),(5,2),(4,2),(2,2),(,,+,),(+,v,s,2),(+,v,s,1),(+,v,2,2),(-,v,5,2),(5),检查,v,1,邻接点,v,4,:,v4,点,满足(,v,1,v4)E,且,f,14,=2,c,14,=5,v4,=min3,2=2,给,v,4,以标号,(+,v,1,2);,v,s,v,2,v,5,v,t,v,4,v,1,v,6,v,3,(5,5),(3,2),(3,3),(4,2),(5,4),(3,3),(2,2),(5,2),(4,2),(2,2),(,,+,),(+,v,s,2),(+,v,s,1),(+,v,2,2),(-,v,5,2),(+,v,1,2),(6),检查,v,4,邻接点,v,t,:,vt,点,满足(,v,4,vt)E,且,f,4t,=2,c,4t,=4,vt,=min2,2=2,给,v,t,以标号,(+,v,4,2);,V,t,得到标号,说明已经得到一条可增广链,标号过程结束。,v,s,v,2,v,5,v,t,v,4,v,1,v,6,v,3,(5,5),(3,2),(3,3),(4,2),(5,4),(3,3),(2,2),(5,2),(4,2),(2,2),(,,+,),(+,v,s,2),(+,v,s,1),(+,v,2,2),(-,v,5,2),(+,v,1,2),(+,v,4,2),开始调整,v,s,v,2,v,5,v,t,v,4,v,1,v,6,v,3,(5,5),(3,2),(3,3),(4,2),(5,4),(3,3),(2,2),(5,2),(4,2),(2,2),(,,+,),(+,v,s,2),(+,v,s,1),(+,v,2,2),(-,v,5,2),(+,v,1,2),(+,v,4,2),2.,调整过程,从,v,t,开始,按照标号点的第一个标号,用反向追踪的方法,找出一条从,v,s,到,v,t,的增广链,,,如图,G,中虚线所示。不难看出,+,=(,v,s,v,2,),(,v,1,v,4,),(,v,4,v,t,),=(,v,5,v,1,),取,=,vt,=,2,,,在,上调整,f,,,得到,f,*,=,f,4t,+,vt,=2+2=4,在,+,上,f,14,+,vt,=2+2=4,在,+,上,f,25,+,vt,=0+2=2,在,+,上,f,s2,+,vt,=2+2=4,在,+,上,f,15,vt,=3,2=1,在,-,上,其它的不变,vs,v2,v5,vt,v4,v1,v6,v3,(5,5),(3,2),(3,1,),(4,4,),(5,4),(3,3),(2,2),(5,4,),(4,4,),(2,2),(,,,+),(,+,vs,,1),(3,2,),重新开始标号,寻找可增广链,当标到,V,3,,,与,V,S,V,3,相连的,V,1,V,2,V,6,不满足标号条件,标号无法进行,,v,t,得不到标号。,流量:,w=,f,s1,+,f,s2,+,f,s3,=,f,4t,+,f,5t,+,f,6t,=11,得到一个最小割,标点号集合:,S=v,s,v,3,非标点号集合:,/,S=v,1,v,2,,v,4,v,5,,v,6,v,t,此时割集(,s,/s)=(v,s,v,1,),(v,s,v,2,),(v,3,v,6,),割集容量,C(s,/s)=C,s1,+C,s2,+C,36,=5+4+2=11,v,s,v,2,v,5,v,t,v,4,v,1,v,6,v,3,(5,5),(3,2),(3,3),(4,2),(5,4),(3,3),(2,2),(5,2),(4,2),(2,2),(,,+,),(+,v,s,2),(+,v,s,1),(+,v,2,2),(-,v,5,2),(+,v,1,2),(+,v,4,2),4),4),1),(3,0),2),4),第一条可增广链:,vs,-v2,v5,v1,v4,vt,调整量为:2,流量:,f=11,无可增广链,最大流=14,割集=(,vs,v1),(,vs,v2),(v3,v6),求最大流的标号算法可以解决多发点多收点网络的最大流问题,X1,X2,X3,xm,Y1,Y2,Y3,yn,v,s,v,t,+,+,小结,1,、最大流问题的概念、最大流,-,最小割定理。,2,、求最大流问题的标号算法。,作业,8.10,8,.14,
    展开阅读全文

    开通VIP折扣优惠下载文档

    提示  咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。

    咨信网小贴示:
    1、浏览或下载可查看了解,请点击【咨信网告知】。
    2、下载文件中如有侵权或不适当内容,将立即纠正。
    3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
    4、开具发票登录电脑端申请,请点击【索取发票】。

    咨信网客服组:【微信客服】

    自信AI创作助手
    关于本文
    本文标题:运筹学课件-第四节--最大流问题.ppt
    链接地址:https://www.zixin.com.cn/doc/14749252.html

    Copyright ©2010-2026   All Rights Reserved  宁波自信网络信息技术有限公司 版权所有   |  客服电话:0574-28810668    微信客服:咨信网客服    投诉电话:18658249818   

    违法和不良信息举报邮箱:help@zixin.com.cn    文档合作和网站合作邮箱:fuwu@zixin.com.cn    意见反馈和侵权处理邮箱:1219186828@qq.com   | 证照中心

    12321jubao.png12321网络举报中心 电话:010-12321  jubao.png中国互联网举报中心 电话:12377   gongan.png浙公网安备33021202000488号  icp.png浙ICP备2021020529号-1 浙B2-20240490   


    关注我们 :微信公众号  抖音  微博  LOFTER               

    自信网络  |  ZixinNetwork