【正文】 0, 0i j i j i j i j i ji j j ii j i j i jd f c d fww f c f? ? ?????????? ? ? ? ? ???第一種情形： 當(dāng)?。?i， j）上的流量滿足 0fijcij時(shí)，在點(diǎn) vi與 vj之間添加一條方向相反的?。?j， i），權(quán)為（－ dij）。 第二種情形： 當(dāng)?。?i， j）上的流量滿足 fij＝ cij時(shí)將弧（ i， j）反向變?yōu)椋?j， i） , 權(quán)為（－ bij）。不在最小費(fèi)用增廣鏈上的弧不作任何變動(dòng)，得到一個(gè)賦權(quán)網(wǎng)絡(luò)圖 D。 （ 2）求賦權(quán)圖 D從發(fā)點(diǎn)的收點(diǎn)的最短路，如果最短路存在，則這條最短路就是 f(k－ 1)的最小費(fèi)用增廣鏈，轉(zhuǎn)第 2步。 賦權(quán)圖 D的所有權(quán)非負(fù)時(shí)，可用 Dijkstra算法求最短路，存在負(fù)權(quán)時(shí)用 Floyd算法。 （ 3）如果賦權(quán)圖 D不存在從發(fā)點(diǎn)到收點(diǎn)的最短路，說明 v(k－ 1)已是最大流量，不存在流量等于 v的流，計(jì)算結(jié)束。 最大流問題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 59 2022年 2月 16日星期三 【 例 611】 對(duì)圖 6－ 28，制定一個(gè)運(yùn)量 v＝ 15及運(yùn)量最大總運(yùn)費(fèi)最小的運(yùn)輸方案。 【 解 】 令所有弧的流量等于零，得到初始可行流 f(0)＝ {0}，流量 v(0)＝ 0，總運(yùn)費(fèi) d(f(0))=0。 3 5 4 2 4 6 3 12 圖 6－ 29 ① ② ③ ④ ⑤ ⑥ s 0 0 0 (a) f (0)，賦權(quán)圖 D0 最小費(fèi)用增廣鏈 μ1： s→ ① → ④ → ⑥ ,見圖 6－ 29(a) 最大流問題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 60 2022年 2月 16日星期三 調(diào)整量 θ＝ 4，對(duì) f(0)＝ {0}進(jìn)行調(diào)整得到 f(1)，括號(hào)（ ）內(nèi)的數(shù)字為弧的流量，網(wǎng)絡(luò)流量 v(1)＝ 4，總運(yùn)費(fèi) d(f(1))＝ 0 4＋ 2 4＋ 3 4＝ 20 如圖 6－ 29(b)。 圖 6－ 29 (12,3) (3,5) (3,4) (1,6) (2,3) (9,12) ① ② ③ ④ ⑤ ⑥ s (10,0) (6,0) (3,0) (b) f (1) (4) (4) (4) (6,4) (4,2) 圖中：（ cij， dij) ( fij ) 最大流問題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 61 2022年 2月 16日星期三 3 5 4 － 2 4 6 3 12 圖 6－ 29 ① ② ③ ④ ⑤ ⑥ s 0 0 0 (c) f (1)，賦權(quán)圖 D1 － 3 (3) v(1)＝ 415，沒有得到最小費(fèi)用流。在圖 6－ 29(b)中，弧 (s,1)和 (4,6)滿足條件 0fijcij，添加兩條邊 (1,s)和 (6,4)，權(quán)分別為“ 0”和“－ 3”，邊 (1,s)可以去掉，弧 (1,4)上有 fij＝ cij說明已飽和，將弧 (1,4)反向變?yōu)?(4,1)，權(quán)為“－ 2”，如圖 6－ 29(c)。 最大流問題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 62 2022年 2月 16日星期三 (12,3) (3,5) (3,4) (1,6) (2,3) (9,12) 圖 6－ 29 ① ② ③ ④ ⑤ ⑥ s (10,0) (6,0) (3,0) (d) f (2) (4) (4) (7) (6,4) (4,2) (3) (3) 圖中：（ cij， dij) ( fij ) 用 Floyd算法得到最小費(fèi)用增廣鏈 μ2： s→ ② → ④ → ⑥ ，調(diào)整量 θ＝ 3，調(diào)整后得到最小費(fèi)用流 f(2)，流量 v(2)＝ 7，總運(yùn)費(fèi) d(f(2))＝ 2 4＋ 3 7＋ 5 3＝ 44 如圖 6－ 29(d)。 最大流問題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 63 2022年 2月 16日星期三 (4) v(2)＝ 715，對(duì)最小費(fèi)用增廣鏈 μ2上的弧進(jìn)行調(diào)整，在圖 6－29(c)中，弧 (s,2)和 (4,6)滿足條件 0fijcij，添加兩條邊 (2,s)和(6,4)，權(quán)分別為“ 0”和“－ 3”，邊 (2,s)可以去掉，弧 (6,4)已經(jīng)存在，弧 (2,4)上有 fij＝ cij說明已飽和，將弧 (2,4)反向變?yōu)?(4,2)，權(quán)為“－ 5”，如圖 6－ 29(e)。 3 － 5 4 － 2 4 6 3 12 圖 6－ 29 ① ② ③ ④ ⑤ ⑥ s 0 0 0 (e) f (2)，賦權(quán)圖 D2 － 3 最大流問題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 64 2022年 2月 16日星期三 用 Floyd算法得到最小費(fèi)用增廣鏈 μ3： s→ ③ → ④ → ⑥ ，調(diào)整量 θ＝ 1，調(diào)整后得到最小費(fèi)用流 f(3)，流量 v(3)＝ 8，總運(yùn)費(fèi) 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) 最大流問題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 65 2022年 2月 16日星期三 (5)類似地，得到圖 6－ 29(g) 3 － 5 4 － 2 4 － 6 3 12 圖 6－ 29 ① ② ③ ④ ⑤ ⑥ s 0 0 0 (g) f (3)，賦權(quán)圖 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) 最小費(fèi)用增廣鏈 μ4： s→ ③ →⑤ → ⑥ ，調(diào)整量 θ＝ 2，流量v(4)＝ 10。見圖 6－ 29(h) 最大流問題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 66 2022年 2月 16日星期三 最小費(fèi)用增廣鏈 μ5： s→① → ⑤ → ⑥ ,調(diào)整量 θ＝ 6，取 θ＝ 5，流量 v(5)＝ v＝ 15得到滿足，最小費(fèi)用流見圖 6－ 29(j)，問題 1計(jì)算結(jié)束。 3 － 5 4 － 2 4 － 6 － 3 12 圖 6－ 29 ① ② ③ ④ ⑤ ⑥ s 0 0 0 (i) f (4)，賦權(quán)圖 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), 最大流問題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 67 2022年 2月 16日星期三 (7)求最小費(fèi)用最大流。對(duì)圖 6－ 29(i)的最小費(fèi)用增廣鏈 μ5，取調(diào)整量 θ＝ 6對(duì)流量調(diào)整，得到圖 6－ 30(a)及賦權(quán)圖 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) 最大流問題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 68 2022年 2月 16日星期三 3 － 5 － 4 － 2 4 － 6 － 3 12 圖 6－ 30 ① ② ③ ④ ⑤ ⑥ s 0 0 0 (b) f (5)，賦權(quán)圖 D5 － 3 － 12 (8)圖 6－ 30(b)的最小費(fèi)用增廣鏈 μ6： s→ ② → ⑤ → ⑥ ， 最大流問題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 69 2022年 2月 16日星期三 (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) 調(diào)整量 θ＝ 1，流量 v(6)＝ 17，最小費(fèi)用流為 f(6)，見圖 6－ 30(c)。 最大流問題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 70 2022年 2月 16日星期三 賦權(quán)圖見圖 6－ 30（ d）。圖 6－ 30(d)不存在從 vs發(fā)點(diǎn)到 v6的最短路，則圖 6－ 30(c)的流就是最小費(fèi)用最大流，最大流量 v=17，最小的總運(yùn)費(fèi)為 d(f)=2 4＋ 4 6＋ 5 3＋ 4 1＋ 6 1＋ 3 2＋ 3 8＋ 12 9＝ 195 3 － 5 － 4 － 2 4 － 6 － 3 － 12 圖 6－ 30 ① ② ③ ④ ⑤ ⑥ s 0 0 0 (d) f (6)，賦權(quán)圖 D6 － 3 － 4 3個(gè)工廠分別運(yùn)送