Ch6网络模型.pptVIP

  1. 1、本文档共81页,可阅读全部内容。
  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文档。上传文档
查看更多
Ch6网络模型ppt课件

* 用Floyd算法得到最小费用增广链μ3:s→③→④→⑥,调整量θ=1,调整后得到最小费用流f(3),流量v(3)=8,总运费 d(f(3))=2×4+3×8+5×3+6×1=53 如图6-29(f)。 (12,3) (3,5) (3,4) (1,6) (2,3) (9,12) 图6-29 ① ② ③ ④ ⑤ ⑥ s (10,0) (6,0) (3,0) (f) f (3) (4) (4) (8) (6,4) (4,2) (3) (3) (1) (1) 6.3 最大流问题 Maximal Flow Problem * (5)类似地,得到图6-29(g) 3 -5 4 -2 4 -6 3 12 图6-29 ① ② ③ ④ ⑤ ⑥ s 0 0 0 (g) f (3),赋权图D3 -3 (12,3) (3,5) (3,4) (1,6) (2,3) (9,12) 图6-29 ① ② ③ ④ ⑤ ⑥ s (10,0) (6,0) (3,0) (h) f (4) (4) (4) (8) (6,4) (4,2) (3) (3) (3) (1) (2) (2) 最小费用增广链μ4:s→③→⑤→⑥,调整量θ=2,流量v(4)=10。见图6-29(h) 6.3 最大流问题 Maximal Flow Problem * 最小费用增广链μ5:s→①→⑤→⑥,调整量θ=6,取θ=5,流量v(5)=v=15得到满足,最小费用流见图6-29(j),问题1计算结束。 3 -5 4 -2 4 -6 -3 12 图6-29 ① ② ③ ④ ⑤ ⑥ s 0 0 0 (i) f (4),赋权图D4 -3 -12 (12,3) (3,5) (3,4) (1,6) (2,3) (9,12) 图6-29 ① ② ③ ④ ⑤ ⑥ s (10,0) (6,0) (3,0) (j) f (5) (9) (4) (8) (6,4) (4,2) (3) (3) (3) (1) (2) (7) (5) (6)由图6-29(g)及(h),得到图 6-29(i), 6.3 最大流问题 Maximal Flow Problem * (7)求最小费用最大流。对图6-29(i)的最小费用增广链μ5,取调整量θ=6对流量调整,得到图6-30(a)及赋权图6-30(b) (12,3) (3,5) (3,4) (1,6) (2,3) (9,12) 图6-30 ① ② ③ ④ ⑤ ⑥ s (10,0) (6,0) (3,0) (a) f (5) (10) (4) (8) (6,4) (4,2) (3) (3) (3) (1) (2) (8) (6) 6.3 最大流问题 Maximal Flow Problem * 3 -5 -4 -2 4 -6 -3 12 图6-30 ① ② ③ ④ ⑤ ⑥ s 0 0 0 (b) f (5),赋权图D5 -3 -12 (8)图6-30(b)的最小费用增广链μ6:s→②→⑤→⑥, 6.3 最大流问题 Maximal Flow Problem * (12,3) (3,5) (3,4) (1,6) (2,3) (9,12) 图6-30 ① ② ③ ④ ⑤ ⑥ s (10,0) (6,0) (3,0) (c) f (6) (10) (4) (8) (6,4) (4,2) (4) (3) (3) (1) (2) (9) (6) (1) 调整量θ=1,流量v(6)=17,最小费用流为f(6),见图6-30(c)。 6.3 最大流问题 Maximal Flow Problem * 赋权图见图6-30(d)。图6-30(d)不存在从vs发点到v6的最短路,则图6-30(c)的流就是最小费用最大流,最大流量v=17,最小的总运费为 d(f)=4×4+4×6+5×3+4×1+6×1+3×2+3×8+9×9=176 3 -5 -4 -2 4 -6 -3 -12 图6-30 ① ② ③ ④ ⑤ ⑥ s 0 0 0 (d) f (6),赋权图D6 -3 -4 3个工厂分别运送10、4及3个单位物质到v6,总运量为17,运费为176 6.3 最大流问题 Maximal Flow Problem * 6.3.5最大流应用举例 1.二分图的最大匹配问题 【例6.12】某公司需要招聘5个专业的毕业生各一个,通过本人报名和筛选,公司最后认为有6人都达到录取条件。这6人所学专业见表6-10,表中打“√”表示该生所学专业。公司应招聘哪几位毕业生,如何分配他们的工作 毕业生 A.市场营销 B.工程管理 C.管理信息 D.计算机 E.企业管理 1 √ √ 2 √ √ 3 √ √ 4 √ √ 5 √ √ 6 √ √ 表

文档评论(0)

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

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

1亿VIP精品文档

相关文档