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