圖與網絡模型的基本概念-資料下載頁
2025-01-18 11:58本頁面
【正文】 (1,3) (2,8) （ 3,2） v1 v2 v5 v7 v4 v3 v6 (6,3) (0,3) (0,8) (0,3) （ 0,2） (0,6) (0,4) (0,5) （ 2,4） (0,7) (0,4) （ 0,3） 圖 1128 31 167。 5 最小費用最大流問題 用上述方法對例 7求解： ? 第一次迭代：找到最短路 v1 v4 v6 v7。 第一次迭代后總流量為 1，總 費用 10。 v5 (6,6) (3,4) (5,7) (2,5) (0,4) （ 2,3） (3,4) (0,3) (2,8) （ 3,2） v1 v2 v7 v4 v3 v6 (5,3) (1,3) (0,8) (1,3) （ 0,2） (0,6) (0,4) (0,5) （ 2,4） (0,7) (1,4) （ 0,3） 圖 1129 32 167。 5 最小費用最大流問題 ? 第二次迭代：找到最短路 v1 v4 v7。 第二次迭代后總流量為 3，總費用 32。 (6,6) (3,4) (5,7) (2,5) (0,4) （ 2,3） (3,4) (0,3) (0,8) （ 3,2） v1 v2 v5 v7 v4 v3 v6 (3,3) (3,3) (2,8) (1,3) （ 0,2） (0,6) (0,4) (0,5) （ 2,4） (0,7) (1,4) （ 0,3） 圖 1130 33 167。 5 最小費用最大流問題 ? 第三次迭代：找到最短路 v1 v4 v3 v6 v7 。 第三次迭代后總流量為 5，總費用 56。 (6,6) (3,4) (5,7) (2,5) (0,4) （ 0,3） (1,4) (0,3) (0,8) （ 1,2） v1 v2 v5 v7 v4 v3 v6 (1,3) (5,3) (2,8) (1,3) （ 2,2） (0,6) (0,4) (0,5) （ 2,4） (0,7) (3,4) （ 2,3） 圖 1131 34 167。 5 最小費用最大流問題 ? 第四次迭代：找到最短路 v1 v4 v3 v5 v7 。 第四次迭代后總流量為 6，總費用 72。 (6,6) (3,4) (4,7) (2,5) (1,4) （ 0,3） (1,4) (0,3) (0,8) （ 0,2） v1 v2 v5 v7 v4 v3 v6 (1,3) (6,3) (2,8) (1,3) （ 3,2） (0,6) (0,4) (0,5) （ 1,4） (1,7) (3,4) （ 2,3） 圖 1132 35 167。 5 最小費用最大流問題 ? 第五次迭代：找到最短路 v1 v2 v5 v7 。 第五次迭代后總流量為 9，總 費用 123。 (3,6) (0,4) (1,7) (2,5) (1,4) （ 0,3） (1,4) (0,3) (0,8) （ 0,2） v1 v2 v5 v7 v4 v3 v6 (0,3) (6,3) (2,8) (1,3) （ 3,2） (3,6) (3,4) (0,5) （ 1,4） (4,7) (3,4) （ 2,3） 圖 1133 36 167。 5 最小費用最大流問題 ? 第六次迭代：找到最短路 v1 v2 v3 v5 v7 。 第六次迭代后總流量為 10，總費用 145。已經找不到從 v1到 v7的每條弧容量都大于零的路了，故 已求得最小費用最大流了。 (3,6) (0,4) (1,7) (2,5) (1,4) （ 0,3） (1,4) (0,3) (0,8) （ 0,2） v1 v2 v5 v7 v4 v3 v6 (0,3) (6,3) (2,8) (1,3) （ 3,2） (3,6) (3,4) (0,5) （ 1,4） (4,7) (3,4) （ 2,3） 圖 1134 37 167。 5 最小費用最大流問題 如果對例 7求一個最小費用流的問題：每小時運送 6萬加侖石油從 v1到v7的最小費用是多少，或者每小時運送 7萬加侖呢？我們可以從第四次迭代及圖 1132即可得到運送 6萬加侖最小費用 72百元，其運送方式通過比較圖 1128及圖 1132即得圖 1136所示。 至于每小時運送 7萬加侖，我們可以在圖 1136的基礎上，再按第五次迭代所選的最短路運送 1萬加侖即得最小費用： 72+1*17=89百元，其運送方式如圖 1137所示。 3 5 1 2 3 1 2 6 v1 v2 v5 v4 v3 v6 10 3 4 2 v7 10 第六次迭代后總流量 圖 1135 38 167。 5 最小費用最大流問題 1 2 3 1 2 6 v1 v2 v5 v4 v3 v6 6 3 1 v7 圖 1136 1 2 1 2 3 1 2 6 v1 v2 v5 v4 v3 v6 3 1 1 v7 圖 1137 注：“管理運籌學軟件”有專門的子程序用于解決這類問題。 39
教學課件相關推薦
鄂ICP備17016276號-1