【正文】 最大流問(wèn)題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 70 2022年 2月 16日星期三 賦權(quán)圖見(jiàn)圖 6－ 30（ d）。 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), 最大流問(wèn)題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 67 2022年 2月 16日星期三 (7)求最小費(fèi)用最大流。 (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) 最大流問(wèn)題 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。 最大流問(wèn)題 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說(shuō)明已飽和，將弧 (2,4)反向變?yōu)?(4,2)，權(quán)為“－ 5”，如圖 6－ 29(e)。在圖 6－ 29(b)中，弧 (s,1)和 (4,6)滿足條件 0fijcij，添加兩條邊 (1,s)和 (6,4)，權(quán)分別為“ 0”和“－ 3”，邊 (1,s)可以去掉，弧 (1,4)上有 fij＝ cij說(shuō)明已飽和，將弧 (1,4)反向變?yōu)?(4,1)，權(quán)為“－ 2”，如圖 6－ 29(c)。 3 5 4 2 4 6 3 12 圖 6－ 29 ① ② ③ ④ ⑤ ⑥ s 0 0 0 (a) f (0)，賦權(quán)圖 D0 最小費(fèi)用增廣鏈 μ1： s→ ① → ④ → ⑥ ,見(jiàn)圖 6－ 29(a) 最大流問(wèn)題 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)。 最大流問(wèn)題 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)輸方案。 賦權(quán)圖 D的所有權(quán)非負(fù)時(shí)，可用 Dijkstra算法求最短路，存在負(fù)權(quán)時(shí)用 Floyd算法。不在最小費(fèi)用增廣鏈上的弧不作任何變動(dòng)，得到一個(gè)賦權(quán)網(wǎng)絡(luò)圖 D。 最大流問(wèn)題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 58 2022年 2月 16日星期三 (1) 對(duì)可行流 f(k－ 1)的最小費(fèi)用增廣鏈上的?。?i， j）作如下變動(dòng) 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）。調(diào)整后得到最小費(fèi)用流 f(k) ，流量為 v(k)＝ v(k－ 1)＋ θ，當(dāng) v(k)＝ v時(shí)計(jì)算結(jié)束，否則轉(zhuǎn)第 3步繼續(xù)計(jì)算。 第 2步 ：調(diào)整流量。 最小費(fèi)用流的標(biāo)號(hào)算法步驟如下。 d(μ)最小的增廣鏈稱為最小費(fèi)用增廣鏈。 設(shè)?。?i,j）的單位流量費(fèi)用為 dij≥0，弧的容量為 cij≥0 設(shè)可行流 f的一條增廣鏈為 μ，稱 ????????? ijij ddd )(為增廣鏈 μ的費(fèi)用。 另一個(gè)問(wèn)題是滿足流量到達(dá)最大使總費(fèi)用最小，稱為 最小費(fèi)用最大流問(wèn)題 。 【 定理 】 最大流量等于最小截集的截量。 第一步： 找出第一個(gè)可行流，例如所有弧的流量 fij =0 FordFulkerson標(biāo)號(hào)算法 最大流問(wèn)題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 42 2022年 2月 16日星期三 第三步：調(diào)整流量 （ 1）求增廣鏈上點(diǎn) vi 的標(biāo)號(hào)的最小值，得到調(diào)整量 ? ?m in jj???（ 2）調(diào)整流量 ????????????????????),(),(),(1jifjifjiffijijij得到新的可行流 f1，去掉所有標(biāo)號(hào)，返回到第二步從發(fā)點(diǎn)重新標(biāo)號(hào)尋找增廣鏈，直到收點(diǎn)不能標(biāo)號(hào)為止 【 定理 】 可行流 f是最大流的充分必要條件是不存在發(fā)點(diǎn)到收點(diǎn)的增廣鏈 最大流問(wèn)題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 43 2022年 2月 16日星期三 ① ② ③ ④ ⑤ ⑥ 8 14 5 6 3 3 8 10 7 6 ⑦ 3 圖 6－ 19 (10) (6) (3) (6) (3) (7) (0) (6) (1) 4 (3) (1) (7) 【 例 610】 求圖 6－ 18發(fā)點(diǎn) v1到收點(diǎn) v7的最大流及最大流量 【 解 】 給定初始可行流，見(jiàn)圖 619 最大流問(wèn)題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 44 2022年 2月 16日星期三 ① ② ③ ④ ⑤ ⑥ 8 14 5 6 3 3 8 10 7 6 ⑦ 3 圖 6－ 20(b) (10) (6) (3) (6) (3) (7) (0) (6) (1) 4 (3) (1) (7) ∞ 2 3 3 7 第一輪標(biāo)號(hào)： c12f12,v2標(biāo)號(hào) 2 cij=fij， v v5不能標(biāo)號(hào) 后向弧 f320, v3標(biāo)號(hào) θ3=f32 增廣鏈 μ＝ {(1,2)， (3,2)， (3,4)， (4,7) },μ+={(1,2)， (3,4)，(4,7)},μ－ ={(3， 2)}，調(diào)整量為增廣鏈上點(diǎn)標(biāo)號(hào)的最小值 θ＝ min{∞， 2， 3， 3， 7}＝ 2 最大流問(wèn)題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 45 2022年 2月 16日星期三 ① ② ③ ④ ⑤ ⑥ 8 14 5 6 3 3 8 10 7 6 ⑦ 3 圖 6－ 21 (10) (8) (1) (6) (3) (7) (2) (6) (1) 4 (5) (1) (7) 調(diào)整后的可行流： 最大流問(wèn)題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 46 2022年 2月 16日星期三 ① ② ③ ④ ⑤ ⑥ 8 14 5 6 3 3 8 10 7 6 ⑦ 3 圖 6－ 22 (10) (8) (1) (6) (3) (7) (2) (6) (1) 4 (5) (1) (7) ∞ 4 4 1 5 第二輪標(biāo)號(hào)： Cij=fij， v v5不能標(biāo)號(hào)，返回到 v3 增廣鏈 μ＝ μ＋ ＝ {(1,3)， (3,4)， (4,7) }，調(diào)整量為 θ＝ min{∞， 4， 1， 5}＝ 1 最大流問(wèn)題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 47 2022年 2月 16日星期三 ① ② ③ ④ ⑤ ⑥ 8 14 5 6 3 3 8 10 7 6 ⑦ 3 圖 6－ 23 (11) (8) (1) (6) (3) (7) (3) (6) (1) 4 (6) (1) (7) 調(diào)整后得到可行流： 最大流問(wèn)題 Maximal Flow Problem Ch6 網(wǎng)絡(luò)模型 Network Model 制作與教學(xué) 武漢理工大學(xué) 管理學(xué)院 熊偉 Page 48 2022年 2月 16日星期三 ① ② ③ ④ ⑤ ⑥ 8 14 5 6 3 3 8 10 7 6