運籌學(xué)第06章圖論概述-資料下載頁
2025-05-14 22:15本頁面
【正文】 流量分布卻是不唯一的 ?如果已知流過弧 (vi , vj )的單位流量要發(fā)生 cij 的費用，要求使得總費用為最小的最大流流量分配方案，這種問題稱為最小費用 最大流問題 ?可以使用對偶法解決這個問題 最小費用 最大流問題 (2) ?對偶法原理 ?對原圖求出從 vs 到 vt 的所有初等路 ?將這些初等路按照單位流量費用之和從小到大排序，編號 1, 2, 3, … , m ?使第 1號初等路上的流量為最大 ?在余下的允許流量中，使第 2號初等路上的流量為最大 ?在余下的允許流量中，使第 3號初等路上的流量為最大 ?… ?在余下的允許流量中，使第 m號初等路上的流量為最大 ?此時，圖中的流量分布即為最小費用 最大流 ?在實際使用時，要對原圖求出從 vs 到 vt 的所有初等路有一定的難度，容易遺漏 最小費用 最大流問題 (3) ?因此，對偶法在實際操作時 ?求出最大流量，以 0流為初始可行流 ?對原圖求出從 vs 到 vt 的單位流量費用之和為最小的初等路 ?調(diào)整使得該初等路上的流量為最大，若當(dāng)前可行流的流量等于最大流量，則當(dāng)前可行流就是最小費用 最大流，否則進入下一步 ?對當(dāng)前可行流生成擴展費用圖。在擴展費用圖中，從原圖的允許流量中去掉當(dāng)前可行流的流量，將圖中某些弧的單位流量費用調(diào)整為 ∞ (這些弧的允許流量已經(jīng)減小為 0，使得此弧不通 ) ?在該擴展費用圖中，求出新的從 vs 到 vt 的單位流量費用之和為最小的初等路，轉(zhuǎn)向第三步 最小費用 最大流問題 (4) ?對偶法步驟 ?用標(biāo)號法求出最大流量 ?將原圖作為初始擴展費用圖，以 0流作為初始可行流 ?在擴展費用圖上，用 Ford 算法求出從 vs 到 vt 的單位流量費用之和為最小的初等路作為增廣鏈 ?按前面標(biāo)號法中調(diào)整流量的方法調(diào)整流量，得到一個新的可行流 ?若當(dāng)前可行流的流量等于最大流量，則當(dāng)前可行流就是最小費用 最大流，否則進入下一步 ?對當(dāng)前可行流生成新的擴展費用圖，轉(zhuǎn)向第三步 最小費用 最大流問題 (5) ?擴展費用圖的生成 ?在弧 (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 )不通，將其單位流量費用調(diào)整為 ∞ 示例 () ?求出從 vs 到 vt 的最小費用 最大流，圖中弧上數(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) 示例 () ?初始擴展費用圖如下所示 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)前可行流生成新的擴展費用圖為 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)前可行流生成新的擴展費用圖為 ?求出了增廣鏈 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)前可行流生成新的擴展費用圖為 ?求出了增廣鏈 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)前可行流就是最小費用 最大流 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 ?是一個最小費用 最大流問題
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1