[小學(xué)教育]第7講圖與網(wǎng)絡(luò)模型(參考版)
2024-10-19 18:12本頁(yè)面
【正文】 。 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)用最大流問(wèn)題 如果對(duì)例 7求一個(gè)最小費(fèi)用流的問(wèn)題：每小時(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所示。已經(jīng)找不到從 v1到 v7的每條弧容量都大于零的路了，故 已求得最小費(fèi)用最大流了。 5 最小費(fèi)用最大流問(wèn)題 ? 第六次迭代：找到最短路 v1 v2 v3 v5 v7 。 第五次迭代后總流量為 9，總 費(fèi)用 123。 (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)用最大流問(wèn)題 ? 第四次迭代：找到最短路 v1 v4 v3 v5 v7 。 第三次迭代后總流量為 5，總費(fèi)用 56。 (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)用最大流問(wèn)題 ? 第二次迭代：找到最短路 v1 v4 v7。 第一次迭代后總流量為 1，總 費(fèi)用 10。 (6,6) (3,4) (5,7) (2,5) (0,4) （ 2,3） (4,4) (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。 ? 用上述方法對(duì)例 7中的圖形進(jìn)行改進(jìn)，得圖如下頁(yè)： vi vj vi vj （ cij,bij ） （ 0,bij ） （ a） （ b） （ cij,bij ） （ cij,bij ） vi vj （ cji,bji ） （ cij,bij ） vi vj （ cji,bji ） （ 0,bji) （ 0,bji) （ c） （ d） 管 理 運(yùn) 籌 學(xué) 31 167。 管 理 運(yùn) 籌 學(xué) 30 167。求最小費(fèi)用流的問(wèn)題的線性規(guī)劃的模型只要把最小費(fèi)用最大流模型中的約束條件中的發(fā)點(diǎn)流量 F改為 f即可。 如果我們把例 7的問(wèn)題改為：每小時(shí)運(yùn)送 6萬(wàn)加侖的石油從采地 v1到銷地 v7最小費(fèi)用是多少？應(yīng)怎樣運(yùn)送？這就變成了一個(gè)最小費(fèi)用流的問(wèn)題。其最優(yōu)值 (最小費(fèi)用 )=145。 2 , 3 , 7 ) ,ijf i j?? ? ?管 理 運(yùn) 籌 學(xué) 29 167。 5 最小費(fèi)用最大流問(wèn)題 12 14 25 23 43( , )35 57 36 46 47 6712 1412 23 2514 43 46 4723 43 35 3625 35 5736 46 6757 67 47 12 14m in 6 3 4 5 24 7 3 3 8 4..10 ,, ( 1 , 2 , , 6 。 第二步，在最大流量 F的所有解中，找出一個(gè)最小費(fèi)用的解，我們來(lái)建立第二步中的線性規(guī)劃模型如下： 仍然設(shè)弧（ vi,vj）上的流量為 fij，這時(shí)已知網(wǎng)絡(luò)中最大流量為 F，只要在例 6的約束條件上，再加上總流量必須等于 F的約束條件： f12=f14=F,即得此線性規(guī)劃的約束條件，此線性規(guī)劃的目標(biāo)函數(shù)顯然是求其流量的最小費(fèi)用 。 解：我們用線性規(guī)劃來(lái)求解此題，可以分兩步走。 (6,6) (3,4) (5,7) (2,5) (2,4) （ 2,3） (4,4) (1,3) (2,8) （ 3,2） v1 v2 v5 v7 v4 v3 v6 (6,3) 管 理 運(yùn) 籌 學(xué) 27 167。如圖。 5 最小費(fèi)用最大流問(wèn)題 ? 最小費(fèi)用最大流問(wèn)題：給了一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，對(duì)每一條弧 （ vi,vj），除了給出容量 cij外，還給出了這條弧的單位流量的費(fèi)用 bij，要 求一個(gè)最大流 F，并使得總運(yùn)送費(fèi)用最小。 4 最大流問(wèn)題 “管理運(yùn)籌學(xué)軟件”中還有專門的子程序用于解決最大流問(wèn)題。得到最大流量為 10?；。? v2 , v3 ）的順流容 量為 2，決定了 pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖： 2 2 2 4 3 v1 v2 v5 v7 v4 v3 v6 1 0 0 0 0 1 2 0 3 2 0 3 3 3 5 0 3 1 2 0 0 2 3 1 3 2 2 v1 v2 v5
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1