運(yùn)籌學(xué)第06章圖論概述(參考版)
2025-05-18 22:15本頁面
【正文】 在擴(kuò)展費(fèi)用圖中，從原圖的允許流量中去掉當(dāng)前可行流的流量，將圖中某些弧的單位流量費(fèi)用調(diào)整為 ∞ (這些弧的允許流量已經(jīng)減小為 0，使得此弧不通 ) ?在該擴(kuò)展費(fèi)用圖中，求出新的從 vs 到 vt 的單位流量費(fèi)用之和為最小的初等路，轉(zhuǎn)向第三步 最小費(fèi)用 最大流問題 (4) ?對偶法步驟 ?用標(biāo)號法求出最大流量 ?將原圖作為初始擴(kuò)展費(fèi)用圖，以 0流作為初始可行流 ?在擴(kuò)展費(fèi)用圖上，用 Ford 算法求出從 vs 到 vt 的單位流量費(fèi)用之和為最小的初等路作為增廣鏈 ?按前面標(biāo)號法中調(diào)整流量的方法調(diào)整流量，得到一個新的可行流 ?若當(dāng)前可行流的流量等于最大流量，則當(dāng)前可行流就是最小費(fèi)用 最大流，否則進(jìn)入下一步 ?對當(dāng)前可行流生成新的擴(kuò)展費(fèi)用圖，轉(zhuǎn)向第三步 最小費(fèi)用 最大流問題 (5) ?擴(kuò)展費(fèi)用圖的生成 ?在弧 (vi , vj )上 ?若 xij =0，則原弧不變 ?若 0＜ xij ＜ bij ，則把弧 (vi , vj )改造成如下的兩條弧 ?若 xij =bij ，則把弧 (vi , vj )改造成方向相反的另一條弧 vi vj (bijxij , cij ) (xij , cij ) vi vj (bij , cij ) 在生成增廣鏈時用不到反向弧 (vj , vi ) ，這樣就去掉了當(dāng)前可行流的流量 同理，使得弧 (vi , vj )不通，將其單位流量費(fèi)用調(diào)整為 ∞ 示例 () ?求出從 vs 到 vt 的最小費(fèi)用 最大流，圖中弧上數(shù)字含義為 (bij , cij ) vs vt v2 v4 v3 v5 (15, 2) (9, 6) (3, 3) (5, 5) (4, 9) (7, 8) (6, 3) (10, 1) (11, 3) 示例 () ?由示例 ()，如下圖，已知從 vs 到 vt 的最大流量為 20 vs vt v2 v4 v3 v5 (15, 2) (9, 6) (3,3) (5, 5) (4, 9) (7, 8) (6, 3) (10, 1) (11, 3) 示例 () ?初始擴(kuò)展費(fèi)用圖如下所示 vs vt v2 v4 v3 v5 (15, 2) (9, 6) (3, 3) (5, 5) (4, 9) (7, 8) (6, 3) (10, 1) (11, 3) ?求出了增廣鏈 示例 () ?初始流量為 0，在增廣鏈上調(diào)整流量，得 vs vt v2 v4 v3 v5 (15,2,0) (9,6,6) (3,3,0) (5,5,0) (4,9,0) (7,8,0) (6,3,6) (10,1,6) (11,3,0) ?當(dāng)前可行流流量為 6＜ 20，需要繼續(xù)調(diào)整 示例 () ?對當(dāng)前可行流生成新的擴(kuò)展費(fèi)用圖為 vs vt v2 v4 v3 v5 (15, 2) (3, 6) (3, 3) (5, 5) (4, 9) (7, 8) (6,3) (4, 1) (11, 3) (6, 6) (6, 1) ?求出了增廣鏈 示例 () ?當(dāng)前流量為 6，在增廣鏈上調(diào)整流量，得 ?當(dāng)前可行流流量為 10＜ 20，需要繼續(xù)調(diào)整 vs vt v2 v4 v3 v5 (15,2,4) (9,6,6) (3,3,0) (5,5,0) (4,9,4) (7,8,0) (6,3,6) (10,1,10) (11,3,0) 示例 () ?對當(dāng)前可行流生成新的擴(kuò)展費(fèi)用圖為 ?求出了增廣鏈 vs vt v2 v4 v3 v5 (11, 2) (3, 6) (3, 3) (5, 5) (4, 9) (7, 8) (6,3) (10, 1) (11, 3) (6, 6) (4, 2) 示例 () ?當(dāng)前流量為 10，在增廣鏈上調(diào)整流量，得 ?當(dāng)前可行流流量為 17＜ 20，需要繼續(xù)調(diào)整 vs vt v2 v4 v3 v5 (15,2,11) (9,6,6) (3,3,0) (5,5,0) (4,9,4) (7,8,7) (6,3,6) (10,1,10) (11,3,7) 示例 () ?對當(dāng)前可行流生成新的擴(kuò)展費(fèi)用圖為 ?求出了增廣鏈 vs vt v2 v4 v3 v5 (4, 2) (3, 6) (3, 3) (5, 5) (4, 9) (7, 8) (6,3) (10, 1) (4, 3) (6, 6) (11, 2) (7, 3) 示例 () ?當(dāng)前流量為 17，在增廣鏈上調(diào)整流量，得 ?當(dāng)前可行流流量為 20，等于最大流量，不需要調(diào)整，當(dāng)前可行流就是最小費(fèi)用 最大流 vs vt v2 v4 v3 v5 (15,2,11) (9,6,9) (3,3,0) (5,5,3) (4,9,4) (7,8,7) (6,3,6) (10,1,10) (11,3,10) 作業(yè) (18) ?書上 220頁的 55 ?是一個最小費(fèi)用 最大流問題 。否則，若 k＜ n1， k=k+1，轉(zhuǎn)上一步；若k≥n1，說明存在負(fù)初等回路，最短路線不存在，算法停止 福德 (Ford)算法 (3) ?該算法可以判斷是否存在負(fù)初等回路，適用于任意權(quán)值的賦權(quán)連通有向圖或無向圖 ?所得的結(jié)果中包含了從 v1到其他任意點(diǎn)的最短距離 示例 () s a b c d t 5 8 3 9 1 4 9 5 4 3 ?路線圖如下所示，箭頭表示通行方向，線上數(shù)字表示道路長度，試用 Ford 算法求 s 到 t的最短路線 示例 () ????????? )1()1()1()1()1()1( ,8,5,0 tdcbas dddddd??????? )2()2()2()2()2()2( ,12,8,8,5,0 tdcbas dddddd17,11,8,8,5,0 )3()3()3()3()3()3( ?????? tdcbas dddddd16,11,8,8,5,0 )4()4()4()4()4()4( ?????? tdcbas dddddd16,11,8,8,5,0 )5()5()5()5()5()5( ?????? tdcbas dddddda b c d d 示
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1