- 1、本文档共33页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 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)进
您可能关注的文档
- 52生态系统的能量流动.ppt
- 53_ATP的主要来源细胞呼吸.ppt
- 53《细胞呼吸》.ppt
- 53三维曲面造型.ppt
- 53先天性心脏病.ppt
- 53西北地区和青藏地区.ppt
- 52-幸福像花儿一样(布衣公子作品).pptx
- 54嗜气管吸虫病.ppt
- 55(国)物料干燥的物理过程.ppt
- 53细胞的结构和功能.ppt
- 2025重庆市荣昌区残疾人联合会招聘公益性岗位人员2人考前自测高频考点模拟试题附答案详解.docx
- 2025重庆市铜梁区人力资源和社会保障局第二批公益性岗位招聘4人考前自测高频考点模拟试题及答案详解1.docx
- 2025重庆市荣昌区科协科技服务中心(区科技馆)招聘公益性岗位人员2人考前自测高频考点模拟试题及参考.docx
- 2025重庆市荣昌区残疾人联合会招聘公益性岗位人员2人考前自测高频考点模拟试题带答案详解.docx
- 2025重庆市荣昌区教育委员会选聘城区及高完中学校人员192人考前自测高频考点模拟试题带答案详解.docx
- 2025重庆市社会医疗机构协会招聘综合干事(含党务)2名考前自测高频考点模拟试题带答案详解.docx
- 2025重庆市綦江区人民政府文龙街道办事处招聘公益性岗位人员1人模拟试卷及参考答案详解1套.docx
- 2025重庆市涪陵区百胜镇人民政府选聘本土人才2人模拟试卷及参考答案详解.docx
- 2025重庆智网科技产业发展有限公司高校毕业生招聘模拟试卷及答案详解一套.docx
- 2025重庆机场集团有限公司校园招聘40人模拟试卷及参考答案详解.docx
最近下载
- 水文学基础知识课件.pptx VIP
- 水文学基础知识.pdf VIP
- 仓库仓储管理系统使用手册.pdf VIP
- 水利工程中的水文工程.pptx VIP
- 15.《文化线路宪章(2008年)》.pdf VIP
- 人教版高中物理必修第一册第1章运动的描述整合课件.ppt VIP
- 5G基站安装详细图解.docx VIP
- 教学能力比赛答辩题(一)(含答案).pdf VIP
- 水利工程基础知识-1.ppt VIP
- IEC 60146-1-1-2024(E) Semiconductor converters – General requirements and line commutated converters – Part 1-1:Specification of basic requirements 半导体变流器. 一般要求和线路换向变流器. 第1 -1部分: 基本 r 规范.pdf
文档评论(0)