欢迎来到三一办公! | 帮助中心 三一办公31ppt.com(应用文档模板下载平台)
三一办公
全部分类
  • 办公文档>
  • PPT模板>
  • 建筑/施工/环境>
  • 毕业设计>
  • 工程图纸>
  • 教育教学>
  • 素材源码>
  • 生活休闲>
  • 临时分类>
  • ImageVerifierCode 换一换
    首页 三一办公 > 资源分类 > PPT文档下载  

    最小费用最大流问题xfj.ppt

    • 资源ID:5816751       资源大小:680.55KB        全文页数:23页
    • 资源格式: PPT        下载积分:10金币
    快捷下载 游客一键下载
    会员登录下载
    三方登录下载: 微信开放平台登录 QQ登录  
    下载资源需要10金币
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    最小费用最大流问题xfj.ppt

    10-5 最小费用最大流问题,一、基本概念1、什么是最小费用最大流问题?对每一条弧都给出单位流量费用的容量网络D=(V,A,C)(称为费用容量网络)中,求取最大流f,使输送流量的总费用 b(f)=bijfij 为最小的一类优化问题。其中,cij表示弧(vi,vj)上的容量,bij表示弧(vi,vj)上通过单位流量所花费的费用,fij表示弧(vi,vj)上的流量。,2、最小费用流 对于一个费用容量网络,具有相同流量 v(f)的可行流中,总费用b(f)最小的可行流称为该费用容量网络关于流量 v(f)的最小费用流,简称流量为 v(f)的最小费用流。,3、增广链的费用 当沿着一条关于可行流 f 的增广链(流量修正路线),以修正量=1进行调整,得到新的可行流,则称 为增广链的费用。,增广链的费用定义为:以单位调整量调整可行流时所付出的费用;当修正量=1时,,此时,的流量v()=v(f)+1;,二、求解最小费用最大流问题的对偶法,1、求解途径:(1)始终保持网络中的可行流是最小费用 流,然后不断调整,使流量逐步增大,最终成为最小费用的最大流;(2)始终保持可行流是最大流,通过不断 调整使费用逐步减小,最终成为最大流 量的最小费用流。,主要学习按思路(1)的求解方法始终保持网络中的可行流是最小费用流,然后不断调整,使流量逐步增大,最终成为最小费用的最大流。,v(f),b(f),应该如何实现“始终保持网络中的可行流是最小费用流”呢?,(2)实现思路 基于第一种求解途径,根据上述定理,从流量为v(f)的最小费用流f 开始,只要找到其上的最小费用增广链,在该链上调整流量,就得到增加流量后的最小费用流。循环往复就可以求出最小费用最大流。,实施中的关键寻找最小费用增广链具体方法:构造增广费用网络图,借助最短路算法寻找最小费用增广链。,增广费用网络图的构造方法 将流量网络中的每一条弧(vi,vj)都看作一对方向相反的弧,并定义弧的权数如下:,对于零流弧(fij=0),在其对应位置构造与其方向相同且权数为bij的弧;,对于非饱和且非零流弧(cijfij0),在其对应位置构造与其方向相同且边权为bij的弧,以及与其方向相反且边权为-bij的弧。处理完所有的弧,即形成增广费用网络图。,对于饱和弧(fij=cij),在其对应位置构造与其方向相反且权数为-bij的弧;,零流弧上(fij=0),保持原弧不变,将单位费用作为权数,即wij=bij:,bij,饱和弧上(fij=cij):去掉原有弧,添加以单位费用的负数作为权数后向弧(虚线弧):,非饱和且非零流弧上(cijfij0),原有弧以单位费用作权数,并添加以单位费用的负数作为权数后向弧(虚线弧):,3、整个过程的求解步骤:第一步-取初始可行流为零流,它必为流量=0的最小费用流。,第二步-对该可行流f(0)构造增广费用网络图W(f(0),用最短路算法求出从发点到收点的最短路。(寻找f(0)的最小费用增广链)若不存在最短路,则该可行流即为最小费用最大流,停止迭代;否则,转下一步。,第三步-将最短路还原成流量网络图(cij,fij)中的最小费用增广链,在上对可行流f(0)进行调整(采用最大流问题中的增广链流量调整方法),得到新的可行流图。返回第二步,将f(0)替换为新的可行流即可。,4、举例:以下图为例,求最小费用最大流,弧旁的数字为(cij,bij)。,解:(1)以零流弧为初始可行流f(0),则初始可行流的流量v(f(0)=0。,4,1,1,3,2,2,6,第 1 次 迭 代,f(0)中全部是零流弧,则保持原边不变,单位费用为权;所有的权均大于零,可用D氏标号法求出最短路:即是f(0)的最小费用增广链。,流量调整量1=min8-0,5-0,7-0=5 总流量v(f(1)=5最小费用增广链的费用bij=1+2+1=4新的可行流为f(1),总费用b1=45=20,第 2 次 迭 代,1,-2,6,4,-1,3,2,1,-1,零流弧保持原边,非饱和非零流弧(vs,v2)和(v1,vt)增添后向弧,饱和弧(v2,v1)去掉原弧增添后向弧;用列表法求出最短路:即是f(1)的最小费用增广链。,流量调整量2=min10-0,7-5=2,总流量v(f(2)=原流量+新增 流量=5+2=7;最小费用增广链的费用 bij=4+1=5新的可行流为f(2),总费用b2=原费用+新增费用=20+52=30,4,-4,-1,-1,3,2,6,-2,1,零流弧保持原边,非饱和非零流弧增添后向弧,饱和弧去掉原边增添后向弧用列表法求得最短路 即是f(2)的最小费用增广链。,流量调整量3=min8-5,10-0,4-0=3,总流量v(f(3)=原流量+新 增流量=7+3=10;最小费用增广链的费用 bij=1+3+2=6新的可行流为f(3),总费用b3=原费用+新增费用=30+63=48,第 3 次 迭 代,添加弧;用列表法求得最短路 对应最小费用增广链,调整流量 4=min10-2,5,10-3,4-3=1,总流量v(f(4)=10+1=11;最小费用增广链的费用 bij=4-2+3+2=7新的可行流为f(4),总费用b4=原费用+新增费用=48+71=55。,第 4 次 迭 代,6,3,4,-3,-1,-1,-2,-4,-2,添加弧;用列表法计算发现Vs和Vt之间不存在一条最短路,计算结束。当前的可行流f(4)即为所求的最小费用最大流。,第 5次 迭 代,2,6,3,4,-3,-1,-1,-2,-4,-2,2,总 结,最短路算法与最大流算法的结合运用 1)构造初始可行流的增广费用网络,用最短路算法求出最小费用增广链。2)将最小费用增广链还原到容量流量网络图中的增广链,调整流量得到新的可行流,继续进行,直到用最短路算法找不到最小费用增广链。,

    注意事项

    本文(最小费用最大流问题xfj.ppt)为本站会员(sccc)主动上传,三一办公仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一办公(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    备案号:宁ICP备20000045号-2

    经营许可证:宁B2-20210002

    宁公网安备 64010402000987号

    三一办公
    收起
    展开