55最小费用最大流问题.pptVIP

  1. 1、本文档共33页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
55最小费用最大流问题

(3)第四次迭代 ①扩展费用网络 ②用Ford算法求最短增广链,路线是vs—v3—v4—vt vs v2 v3 v4 v5 vt * 5-5 最小费用最大流问题 一、基本概念 1、什么是最小费用最大流问题? 对每一条弧都给出单位流量费用的容量网络D=(V,A,B)(称为费用容量网络)中,求取最大流X,使输送流量的总费用 C(X)=∑cijxij为最小的一类优化问题。 其中,bij表示弧(vi,vj)上的容量,xij表示弧(vi,vj)上的流量,cij表示弧(vi,vj)上通过单位流量所花费的费用。 2、最小费用流 对一费用容量网络,具有相同流量 f 的可行流中,总费用最小的可行流称为该费用容量网络关于流量 f 的最小费用流,简称流量为 f 的最小费用流。 3、增广链的费用 当沿着一条关于可行流 X 的增广链(流量修正路线)μ,以修正量ε=1进行调整,得到新的可行流 ,则称C( )- C(X)为 增广链μ的费用。 ②增广链μ的费用就是以单位调整量调整可行流时所付出的费用; ③当修正量ε=1时, 此时, ① 的流量 f( ) = f(X)+1; C( )-C( X )= 二、求解最小费用最大流问题的对偶法 1、求解途径: (1)始终保持网络中的可行流是最小费用流,然后不断调整,使流量逐步增大,最终成为最小费用的最大流; (2)始终保持可行流是最大流,通过不断调整使费用逐步减小,最终成为最大流量的最小费用流。 2、算法原理 (1)定理 若X 是流量为f(X)的最小费用流,μ是关于X 的所有增广链中费用最小的增广链,那么沿着μ去调整X得到的新的可行流 就是流量为 f ( )的最小费用流。 (2)实现思路 基于第一种求解途径,根据上述定理,只要找到最小费用增广链,在该链上调整流量,得到增加流量后的最小费用流。循环往复直至求出最小费用最大流。 对偶法原理和步骤 求最大流 Ford算法找从vs到vt的最短增广链 调整流量 得费用最小的可行流 将0流作为初始可行流 Yes 绘制扩展费用网络 No 流量等于最大流? 得最小费用最大流 确保流量最大 确保费用最小 实施中的关键 构造增广费用网络图(即扩展费用网络图),借助最短路算法寻找最小费用增广链。 为什么? 理由: 正向饱和弧不标记,反向零流弧不标记。 —不构造增广费用网络,就无法调整流量 (1)饱和弧,流量无法减小; (2)非饱和弧,流量只能增加,不能减小; 增广链流量调整:正向弧增加流量 ,反向弧减少流量 。 零流弧上 Wij = cij 原有弧(流量可以增加) ∞ 后加弧(流量不能再减少) 饱和弧上wij = ∞ 原有弧(流量不能再增加) -cij 后加弧(流量可以减少) 非饱和且非零流 (0xijbij)弧上 cij 原有弧(流量可以增加) -cij 后加弧(流量可以减少) Wij= 增广费用网络图的构造方法 将网络中的每一条弧(vi, vj)都变成一对方向相反的弧,以形成四通八达的“路”,权数定义如下: 将上述思想加以简化,出现∞处相应的弧不画,按下面的方法具体构造增广费用网络图: 零流弧上,保持原弧不变,将单位费用作为权数,即wij= cij: Vi Vj 原网络 Vi Vj 增广费用网络 非饱和弧上 ,原有弧以单位费用作权数,后加弧(虚线弧)以单位费用的负数作权数(p167更正): Vi Vj 原网络 Vi Vj 增广费用网络 饱和弧上 ,去掉原有弧,添上后加弧(虚线弧),权数为单位费用的负数: Vi Vj 原网络 Vi Vj (bij, -cij) 增广费用网络 于是,在容量网络中寻找最小费用增广链就相当于在增广费用网络图(扩展费用网络图)中寻找从发点到收点的最短路。 注意 将找到的最短路还原到原网络图中(虚线弧改成原图中的反向弧)。 3、步骤: 第一步---用Ford-Fukerson算法求出该容量网络的最大流量fmax; (本步骤的作用是什么?) 第二步--- 取初始可行流为零流,其必为流量为0的最小费用流(为什么?) 第三步 --- 一般为第k-1次迭代,得一最小费用流X(k-1) ,对当前可行流构造增广费用网络图W(X(k-1)),用最短路算法求出从发点到收点的最短路。 若不存在最短路,则X(k-1)即最小费用最大流,停止迭代; 否则,转下一步。 第四步---将最短路还原成原网络图中的最小费用增广链μ,在μ上对可行流X(k-1)进

您可能关注的文档

文档评论(0)

tmd2017 + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档