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