圖與網(wǎng)絡(luò)模型的基本概念(參考版)
2025-01-20 11:58本頁面
【正文】 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 注：“管理運籌學(xué)軟件”有專門的子程序用于解決這類問題。 至于每小時運送 7萬加侖，我們可以在圖 1136的基礎(chǔ)上，再按第五次迭代所選的最短路運送 1萬加侖即得最小費用： 72+1*17=89百元，其運送方式如圖 1137所示。 (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。 第六次迭代后總流量為 10，總費用 145。 (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 v5 v7 。 第四次迭代后總流量為 6，總費用 72。 (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 v6 v7 。 第二次迭代后總流量為 3，總費用 32。 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 最小費用最大流問題 用上述方法對例 7求解： ? 第一次迭代：找到最短路 v1 v4 v6 v7。 5 最小費用最大流問題 ? 求最小費用最大流的基本算法 在對弧的標(biāo)號作了改進(jìn)的網(wǎng)絡(luò)圖上求最小費用最大流的基本算法與求 最大流的基本算法完全一樣，不同的只是在步驟（ 1）中要選擇一條總的 單位費用最小的路，而不是包含邊數(shù)最小的路。 5 最小費用最大流問題 二、最小費用最大流的網(wǎng)絡(luò)圖論解法 ? 對網(wǎng)絡(luò)上?。?vi,vj）的（ cij,bij）的表示作如下改動，用 (b)來表示 (a)。在例 6中只要把f12+f14=F改為 f12+f14=f=6得到了最小費用流的線性規(guī)劃的模型了。一般來說，所謂最小費用流的問題就是：在給定了收點和發(fā)點并對每條弧 (vi,vj)賦權(quán)以容量 cij及單位費用 bij的網(wǎng)絡(luò)中，求一個給定值 f的流量的最小費用，這個給定值 f的流量應(yīng)小于等于最大流量 F，否則無解。對照前面例 6的結(jié)果，可對最小費用最大流的概念有一個深刻的理解。 5 最小費用最大流問題 用管理運籌學(xué)軟件，可求得如下結(jié)果： f12=4,f14=6, f25=3,f23=1,f43=3,F57=5,f36=2,f46=1,f47=2,f67=3,f35=2。ijij ijv v Aij ijf b f f f f ff f f f f fstf f Ff f ff f f ff f f ff f ff f ff f f f ff c i j?? ? ? ? ? ? ? ?? ? ? ? ?? ? ???? ? ?? ? ?????? ? ? ??? 2 , 3 , 7 ) ,0 , ( 1 , 2 , , 6 。 由此得到線性規(guī)劃模型如下： ( , )ijij ijv v Afb???27 167。 第一步，先求出此網(wǎng)絡(luò)圖中的最大流量 F，這已在例 6中建立了線性規(guī)劃的模型，通過管理運籌學(xué)軟件已經(jīng)獲得結(jié)果。 5 最小費用最大流問題 這個最小費用最大流問題也是一個線性規(guī)劃的問題。從采地 v1向銷地 v7運送石 油，怎樣運送才能運送最多的石油并使得總的運送費用最??？求出最大流 量和最小費用。 一、最小費用最大流的數(shù)學(xué)模型 例 7 由于輸油管道的長短不一，所以在例 6中每段管道（ vi,vj ）除 了有不同的流量限制 cij外，還有不同的單位流量的費用 bij ， cij的單位為萬 加侖 /小時， bij的單位為百元 /萬加侖。 25 167。 最大流量圖如下圖： 2 2 v1 v2 v5 v7
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1