[小學(xué)教育]第7講圖與網(wǎng)絡(luò)模型-資料下載頁(yè)
2024-10-16 18:12本頁(yè)面
【正文】 (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 管 理 運(yùn) 籌 學(xué) 32 167。 5 最小費(fèi)用最大流問題 用上述方法對(duì)例 7求解： ? 第一次迭代：找到最短路 v1 v4 v6 v7。 第一次迭代后總流量為 1，總 費(fèi)用 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 管 理 運(yùn) 籌 學(xué) 33 167。 5 最小費(fèi)用最大流問題 ? 第二次迭代：找到最短路 v1 v4 v7。 第二次迭代后總流量為 3，總費(fèi)用 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 管 理 運(yùn) 籌 學(xué) 34 167。 5 最小費(fèi)用最大流問題 ? 第三次迭代：找到最短路 v1 v4 v3 v6 v7 。 第三次迭代后總流量為 5，總費(fèi)用 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 管 理 運(yùn) 籌 學(xué) 35 167。 5 最小費(fèi)用最大流問題 ? 第四次迭代：找到最短路 v1 v4 v3 v5 v7 。 第四次迭代后總流量為 6，總費(fèi)用 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 管 理 運(yùn) 籌 學(xué) 36 167。 5 最小費(fèi)用最大流問題 ? 第五次迭代：找到最短路 v1 v2 v5 v7 。 第五次迭代后總流量為 9，總 費(fèi)用 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 管 理 運(yùn) 籌 學(xué) 37 167。 5 最小費(fèi)用最大流問題 ? 第六次迭代：找到最短路 v1 v2 v3 v5 v7 。 第六次迭代后總流量為 10，總費(fèi)用 145。已經(jīng)找不到從 v1到 v7的每條弧容量都大于零的路了，故 已求得最小費(fèi)用最大流了。 (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 管 理 運(yùn) 籌 學(xué) 38 167。 5 最小費(fèi)用最大流問題 如果對(duì)例 7求一個(gè)最小費(fèi)用流的問題：每小時(shí)運(yùn)送 6萬(wàn)加侖石油從 v1到v7的最小費(fèi)用是多少，或者每小時(shí)運(yùn)送 7萬(wàn)加侖呢？我們可以從第四次迭代及圖 1132即可得到運(yùn)送 6萬(wàn)加侖最小費(fèi)用 72百元，其運(yùn)送方式通過(guò)比較圖 1128及圖 1132即得圖 1136所示。 至于每小時(shí)運(yùn)送 7萬(wàn)加侖，我們可以在圖 1136的基礎(chǔ)上，再按第五次迭代所選的最短路運(yùn)送 1萬(wàn)加侖即得最小費(fèi)用： 72+1*17=89百元，其運(yùn)送方式如圖 1137所示。 3 5 1 2 3 1 2 6 v1 v2 v5 v4 v3 v6 10 3 4 2 v7 10 第六次迭代后總流量 圖 1135 管 理 運(yùn) 籌 學(xué) 39 167。 5 最小費(fèi)用最大流問題 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 注： “ 管理運(yùn)籌學(xué)軟件 ” 有專門的子程序用于解決這類問題。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1