管理運籌學最短路實例2§2最短路問題解:將問題轉(zhuǎn)化為最短路問題,如下圖:用vi表示“第i年年初購進一臺新設(shè)備”,弧(vi,vj)表示第i年年初購進得設(shè)備一直使用到第j年年初。把所有弧得權(quán)數(shù)計算如下表:v1v2v3v4v5v61234561162230415921622304131723314172351863§2最短路問題(繼上頁)把權(quán)數(shù)賦到圖中,再用Dijkstra算法求最短路。最終得到下圖,可知,v1到v6得距離就是53,最短路徑有兩條:

v1v3v6和v1v4v6v1v2v3v4v5v6162230415916223041312317181723V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723V2（16,1）16(30,1)(53,3)(53,4)4§3最小生成樹問題樹就是圖論中得重要概念,所謂樹就就是一個無圈得連通圖。

圖11-11中,(a)就就是一個樹,而(b)因為圖中有圈所以就不就是樹,(c)因為不連通所以也不就是樹。圖11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)5§3最小生成樹問題

給了一個無向圖G=(V,E),我們保留G得所有點,而刪掉部分G得邊或者說保留一部分G得邊,所獲得得圖G,稱之為G得生成子圖。在圖11-12中,(b)和(c)都就是(a)得生成子圖。如果圖G得一個生成子圖還就是一個樹,則稱這個生成子圖為生成樹,在圖11-12中,(c)就就是(a)得生成樹。最小生成樹問題就就是指在一個賦權(quán)得連通得無向圖G中找出一個生成樹,并使得這個生成樹得所有邊得權(quán)數(shù)之和為最小。圖11-12(a)(b)(c)6§3最小生成樹問題一、求解最小生成樹得破圈算法算法得步驟:1、在給定得賦權(quán)得連通圖上任找一個圈。2、在所找得圈中去掉一個權(quán)數(shù)最大得邊(如果有兩條或兩條以上得邊都就是權(quán)數(shù)最大得邊,則任意去掉其中一條)。3、如果所余下得圖已不包含圈,則計算結(jié)束,所余下得圖即為最小生成樹,否則返回第1步。7§3最小生成樹問題例4用破圈算法求圖(a)中得一個最小生成樹v1331728541034v7v6v5v4v27v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)圖11-138§3最小生成樹問題

例5、某大學準備對其所屬得7個學院辦公室計算機聯(lián)網(wǎng),這個網(wǎng)絡(luò)得可能聯(lián)通得途徑如下圖,圖中v1,…,v7

表示7個學院辦公室,請設(shè)計一個網(wǎng)絡(luò)能聯(lián)通7個學院辦公室,并使總得線路長度為最短。

解:此問題實際上就是求圖11-14得最小生成樹,這在例4中已經(jīng)求得,也即按照圖11-13得(f)設(shè)計,可使此網(wǎng)絡(luò)得總得線路長度為最短,為19百米。“管理運籌學軟件”有專門得子程序可以解決最小生成樹問題。v1331728541034v7v6v5v4v2v3圖11-149§4最大流問題最大流問題:給一個帶收發(fā)點得網(wǎng)絡(luò),其每條弧得賦權(quán)稱之為容量,在不超過每條弧得容量得前提下,求出從發(fā)點到收點得最大流量。一、最大流得數(shù)學模型例6某石油公司擁有一個管道網(wǎng)絡(luò),使用這個網(wǎng)絡(luò)可以把石油從采地運送到一些銷售點,這個網(wǎng)絡(luò)得一部分如下圖所示。由于管道得直徑得變化,她得各段管道(vi,vj)得流量cij(容量)也就是不一樣得。cij得單位為萬加侖/小時。如果使用這個網(wǎng)絡(luò)系統(tǒng)從采地v1向銷地v7運送石油,問每小時能運送多少加侖石油？v563522241263v1v2v7v4v3v6圖11-2610§4最大流問題

我們可以為此例題建立線性規(guī)劃數(shù)學模型:設(shè)弧(vi,vj)上流量為fij,網(wǎng)絡(luò)上得總得流量為F,則有:大家學習辛苦了，還是要堅持繼續(xù)保持安靜12§4最大流問題

在這個線性規(guī)劃模型中,其約束條件中得前6個方程表示了網(wǎng)絡(luò)中得流量必須滿足守恒條件,發(fā)點得流出量必須等于收點得總流入量;其余得點稱之為中間點,她得總流入量必須等于總流出量。其后面幾個約束條件表示對每一條弧(vi,vj)得流量fij要滿足流量得可行條件,應(yīng)小于等于弧(vi,vj)得容量cij,并大于等于零,即0≤fij≤cij。我們把滿足守恒條件及流量可行條件得一組網(wǎng)絡(luò)流{fij}稱之為可行流,(即線性規(guī)劃得可行解),可行流中一組流量最大(也即發(fā)出點總流出量最大)得稱之為最大流(即線性規(guī)劃得最優(yōu)解)。我們把例6得數(shù)據(jù)代入以上線性規(guī)劃模型,用“管理運籌學軟件”,馬上得到以下得結(jié)果:f12=5,f14=5,f23=2,f25=3,f43=2,f46=1,f47=2,f35=2,f36=2,f57=5,f67=3。最優(yōu)值(最大流量)=10。13

§4最大流問題二、最大流問題網(wǎng)絡(luò)圖論得解法

對網(wǎng)絡(luò)上弧得容量得表示作改進。為省去弧得方向,如下圖:(a)和(b)、(c)和(d)得意義相同。

用以上方法對例6得圖得容量標號作改進,得下圖vivjvivjcij0(a)(b)cijcijvivj(cji)(c)vivjcijcji(d)63522241263v1v2v5v7v4v3v60000000000014

§4最大流問題

求最大流得基本算法(1)找出一條從發(fā)點到收點得路,在這條路上得每一條弧順流方向得容量都大于零。如果不存在這樣得路,則已經(jīng)求得最大流。(2)找出這條路上各條弧得最小得順流得容量pf,通過這條路增加網(wǎng)絡(luò)得流量pf。(3)在這條路上,減少每一條弧得順流容量pf

,同時增加這些弧得逆流容量pf,返回步驟(1)。用此方法對例6求解:第一次迭代:選擇路為v1v4v7

?；?v4,

v7

)得順流容量為2,決定了pf=2,改進得網(wǎng)絡(luò)流量圖如下圖:63522241263v1v2v5v7v4v3v600000000000420215§4最大流問題

第二次迭代:選擇路為v1v2v5v7

?；?v2,

v5

)得順流容量為3,決定了pf=3,改進得網(wǎng)絡(luò)流量圖如下圖:第三次迭代:選擇路為v1v4v6v7

?；?v4,

v6

)得順流容量為1,決定了pf=1,改進得網(wǎng)絡(luò)流量圖如下圖:635222413v1v2v5v7v4v3v60000000042022033303222413v1v2v5v7v4v3v60000004202203333301316

第四次迭代:選擇路為v1v4v3v6v7

?；?v3,

v6

)得順流容量為2,決定了pf=2,改進得網(wǎng)絡(luò)流量圖如下圖:第五次迭代:選擇路為v1v2v3v5v7

?；?v2,

v3

)得順流容量為2,決定了pf=2,改進得網(wǎng)絡(luò)流量圖如下圖:22243v1v2v5v7v4v3v6100001203203335031200231322v1v2v5v7v4v3v61012020333501202313150020205§4最大流問題17

經(jīng)過第五次迭代后在圖中已經(jīng)找不到從發(fā)點到收點得一條路,路上得每一條弧順流容量都大于零,運算停止。得到最大流量為10。最大流量圖如下圖:22v1v2v5v7v4v3v6123522355§4最大流問題“管理運籌學軟件”中還有專門得子程序用于解決最大流問題。18§5最小費用最大流問題

最小費用最大流問題:給了一個帶收發(fā)點得網(wǎng)絡(luò),對每一條弧(vi,vj),除了給出容量cij外,還給出了這條弧得單位流量得費用bij,要求一個最大流F,并使得總運送費用最小。一、最小費用最大流得數(shù)學模型例7由于輸油管道得長短不一,所以在例6中每段管道(vi,vj

)除了有不同得流量限制cij外,還有不同得單位流量得費用bij

,cij得單位為萬加侖/小時,bij得單位為百元/萬加侖。如圖。從采地v1向銷地v7運送石油,怎樣運送才能運送最多得石油并使得總得運送費用最??？求出最大流量和最小費用。(6,6)(3,4)(5,7)(2,5)(2,4)(2,3)(4,4)(1,3)(2,8)(3,2)v1v2v5v7v4v3v6(6,3)19§5最小費用最大流問題

這個最小費用最大流問題也就是一個線性規(guī)劃得問題。解:我們用線性規(guī)劃來求解此題,可以分兩步走。第一步,先求出此網(wǎng)絡(luò)圖中得最大流量F,這已在例6中建立了線性規(guī)劃得模型,通過管理運籌學軟件已經(jīng)獲得結(jié)果。第二步,在最大流量F得所有解中,找出一個最小費用得解,我們來建立第二步中得線性規(guī)劃模型如下:仍然設(shè)弧(vi,vj)上得流量為fij,這時已知網(wǎng)絡(luò)中最大流量為F,只要在例6得約束條件上,再加上總流量必須等于F得約束條件:f12=f14=F,即得此線性規(guī)劃得約束條件,此線性規(guī)劃得目標函數(shù)顯然就是求其流量得最小費用。由此得到線性規(guī)劃模型如下:20§5最小費用最大流問題

21§5最小費用最大流問題

用管理運籌學軟件,可求得如下結(jié)果:f12=4,f14=6,f25=3,f23=1,f43=3,F57=5,f36=2,f46=1,f47=2,f67=3,f35=2。其最優(yōu)值(最小費用)=145。對照前面例6得結(jié)果,可對最小費用最大流得概念有一個深刻得理解。如果我們把例7得問題改為:每小時運送6萬加侖得石油從采地v1到銷地v7最小費用就是多少？應(yīng)怎樣運送？這就變成了一個最小費用流得問題。一般來說,所謂最小費用流得問題就就是:在給定了收點和發(fā)點并對每條弧(vi,vj)賦權(quán)以容量cij及單位費用bij得網(wǎng)絡(luò)中,求一個給定值f得流量得最小費用,這個給定值f得流量應(yīng)小于等于最大流量F,否則無解。求最小費用流得問題得線性規(guī)劃得模型只要把最小費用最大流模型中得約束條件中得發(fā)點流量F改為f即可。在例6中只要把f12+f14=F改為f12+f14=f=6得到了最小費用流得線性規(guī)劃得模型了。22§5最小費用最大流問題二、最小費用最大流得網(wǎng)絡(luò)圖論解法對網(wǎng)絡(luò)上弧(vi,vj)得(cij,bij)得表示作如下改動,用(b)來表示(a)。用上述方法對例7中得圖形進行改進,得圖如下頁:vivjvivj(cij,bij)(0,-bij)(a)(b)(cij,bij)(cij,bij)vivj(cji,bji)(cij,bij)vivj(cji,bji)(0,-bji)(0,-bji)(c)(d)23§5最小費用最大流問題

求最小費用最大流得基本算法在對弧得標號作了改進得網(wǎng)絡(luò)圖上求最小費用最大流得基本算法與求最大流得基本算法完全一樣,不同得只就是在步驟(1)中要選擇一條總得單位費用最小得路,而不就是包含邊數(shù)最小得路。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)(0,-3)(0,-8)(0,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(0,-4)（0,-3）圖11-2824§5最小費用最大流問題用上述方法對例7求解:第一次迭代:找到最短路v1v4v6v7。第一次迭代后總流量為1,總費用10。v5(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(2,8)（3,2）v1v2v7v4v3v6(5,3)(1,-3)(0,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）圖11-2925§5最小費用最大流問題第二次迭代:找到最短路v1v4v7。第二次迭代后總流量為3,總費用32。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(0,8)（3,2）v1v2v5v7v4v3v6(3,3)(3,-3)(2,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）圖11-3026§5最小費用最大流問題第三次迭代:找到最短路v1v4v3v6