Ch6网络模型.pptVIP

用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 应用举例 1.二分图的最大匹配问题 【例6.12】某公司需要招聘5个专业的毕业生各一个，通过本人报名和筛选，公司最后认为有6人都达到录取条件。这6人所学专业见表6-10,表中打“√”表示该生所学专业。公司应招聘哪几位毕业生，如何分配他们的工作 √ √ 6 √ √ 5 √ √ 4 √ √ 3 √ √ 2 √ √ 1 E.企业管理 D.计算机 C.管理信息 B.工程管理 A.市场营销 毕业生 表6-10 6.3 最大流问题 Maximal F