管理運籌學(xué)-第7章--最短路實例PPT課件

1、1,2最短路問題,例 設(shè)備更新問題。某公司使用一臺設(shè)備，在每年年初，公司就要決定是購買新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購置新設(shè)備，就要支付一定的購置費，當然新設(shè)備的維修費用就低。如果繼續(xù)使用舊設(shè)備，可以省去購置費，但維修費用就高了。請設(shè)計一個五年之內(nèi)的更新設(shè)備的計劃，使得五年內(nèi)購置費用和維修費用總的支付費用最小。 已知：設(shè)備每年年初的價格表 設(shè)備維修費如下表,2,2最短路問題,解： 將問題轉(zhuǎn)化為最短路問題，如下圖： 用vi表示“第i年年初購進一臺新設(shè)備”,弧（vi,vj）表示第i年年初購進的設(shè)備一直使用到第j年年初。 把所有弧的權(quán)數(shù)計算如下表,3,2最短路問題,繼上頁) 把權(quán)數(shù)賦到圖中，再用D

2、ijkstra算法求最短路。 最終得到下圖，可知，v1到v6的距離是53，最短路徑有兩條： v1 v3 v6和 v1 v4 v6,4,3最小生成樹問題,樹是圖論中的重要概念，所謂樹就是一個無圈的連通圖,圖11-11中，(a)就是一個樹，而(b)因為圖中有圈所以就不是樹， (c)因為不連通所以也不是樹,5,3最小生成樹問題,給了一個無向圖G=(V,E)，我們保留G的所有點，而刪掉部分G的邊或者說保留一部分G的邊，所獲得的圖G，稱之為G的生成子圖。在圖11-12中，(b)和(c)都是(a)的生成子圖。 如果圖G的一個生成子圖還是一個樹，則稱這個生成子圖為生成樹，在圖11-12中，(c)就是(a)的

3、生成樹。 最小生成樹問題就是指在一個賦權(quán)的連通的無向圖G中找出一個生成樹，并使得這個生成樹的所有邊的權(quán)數(shù)之和為最小,a,b,c,6,3最小生成樹問題,一、求解最小生成樹的破圈算法 算法的步驟： 1、在給定的賦權(quán)的連通圖上任找一個圈。 2、在所找的圈中去掉一個權(quán)數(shù)最大的邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）。 3、如果所余下的圖已不包含圈，則計算結(jié)束，所余下的圖即為最小生成樹，否則返回第1步,7,3最小生成樹問題,例4 用破圈算法求圖（a）中的一個最小生成樹,圖11-13,8,3最小生成樹問題,例5、某大學(xué)準備對其所屬的7個學(xué)院辦公室計算機聯(lián)網(wǎng)，這個網(wǎng)絡(luò)的可能聯(lián)通的途

4、徑如下圖，圖中v1,v7 表示7個學(xué)院辦公室，請設(shè)計一個網(wǎng)絡(luò)能聯(lián)通7個學(xué)院辦公室，并使總的線路長度為最短,解：此問題實際上是求圖11-14的最小生成樹，這在例4中已經(jīng)求得，也即按照圖11-13的(f)設(shè)計，可使此網(wǎng)絡(luò)的總的線路長度為最短，為19百米。 “管理運籌學(xué)軟件”有專門的子程序可以解決最小生成樹問題,9,4最大流問題,最大流問題：給一個帶收發(fā)點的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，在不超過每條弧的容量的前提下，求出從發(fā)點到收點的最大流量。 一、最大流的數(shù)學(xué)模型 例6 某石油公司擁有一個管道網(wǎng)絡(luò)，使用這個網(wǎng)絡(luò)可以把石油從采地運送到一些銷售點，這個網(wǎng)絡(luò)的一部分如下圖所示。由于管道的直徑的變化，它

5、的各段管道（vi,vj）的流量cij（容量）也是不一樣的。cij的單位為萬加侖/小時。如果使用這個網(wǎng)絡(luò)系統(tǒng)從采地 v1向銷地 v7運送石油，問每小時能運送多少加侖石油,v5,10,4最大流問題,我們可以為此例題建立線性規(guī)劃數(shù)學(xué)模型： 設(shè)弧(vi,vj)上流量為fij，網(wǎng)絡(luò)上的總的流量為F，則有,11,4最大流問題,在這個線性規(guī)劃模型中，其約束條件中的前6個方程表示了網(wǎng)絡(luò)中的流量必須滿足守恒條件，發(fā)點的流出量必須等于收點的總流入量；其余的點稱之為中間點，它的總流入量必須等于總流出量。其后面幾個約束條件表示對每一條弧(vi,vj)的流量fij要滿足流量的可行條件，應(yīng)小于等于弧(vi,vj)的容量c

6、ij，并大于等于零，即0fij cij。我們把滿足守恒條件及流量可行條件的一組網(wǎng)絡(luò)流 fij稱之為可行流，（即線性規(guī)劃的可行解），可行流中一組流量最大（也即發(fā)出點總流出量最大）的稱之為最大流（即線性規(guī)劃的最優(yōu)解）。 我們把例6的數(shù)據(jù)代入以上線性規(guī)劃模型，用“管理運籌學(xué)軟件”，馬上得到以下的結(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,12,4最大流問題,二、最大流問題網(wǎng)絡(luò)圖論的解法 對網(wǎng)絡(luò)上弧的容量的表示作改進。為省去弧的方向，如下圖: (a)和 (b)、(c)和(d)的意義相

7、同。 用以上方法對例6的圖的容量標號作改進，得下圖,vi,vj,vi,vj,cij,0,a,b,cij,cij,vi,vj,cji,c,vi,vj,cij,cji,d,13,4最大流問題,求最大流的基本算法 （1）找出一條從發(fā)點到收點的路，在這條路上的每一條弧順流方向的容量都大于零。如果不存在這樣的路，則已經(jīng)求得最大流。 （2）找出這條路上各條弧的最小的順流的容量pf，通過這條路增加網(wǎng)絡(luò)的流量pf。 （3）在這條路上，減少每一條弧的順流容量pf ，同時增加這些弧的逆流容量pf，返回步驟（1）。 用此方法對例6求解： 第一次迭代：選擇路為v1 v4 v7 ?；。?v4 , v7 ）的順流容量為2

8、， 決定了pf=2，改進的網(wǎng)絡(luò)流量圖如下圖,14,4最大流問題,第二次迭代：選擇路為v1 v2 v5 v7 ?；。?v2 , v5 ）的順流容量為 3，決定了pf=3，改進的網(wǎng)絡(luò)流量圖如下圖： 第三次迭代：選擇路為v1 v4 v6 v7 ?；。?v4 , v6 ）的順流容量為 1，決定了pf=1，改進的網(wǎng)絡(luò)流量圖如下圖,15,第四次迭代：選擇路為v1 v4 v3 v6 v7 ?；。?v3 , v6 ）的順流容 量為2，決定了pf=2，改進的網(wǎng)絡(luò)流量圖如下圖： 第五次迭代：選擇路為v1 v2 v3 v5 v7 。?。?v2 , v3 ）的順流容 量為2，決定了pf=2，改進的網(wǎng)絡(luò)流量圖如下圖,4

9、最大流問題,16,經(jīng)過第五次迭代后在圖中已經(jīng)找不到從發(fā)點到收點的一條路，路上的每一條弧順流容量都大于零，運算停止。得到最大流量為10。 最大流量圖如下圖,4最大流問題,管理運籌學(xué)軟件”中還有專門的子程序用于解決最大流問題,17,5最小費用最大流問題,最小費用最大流問題：給了一個帶收發(fā)點的網(wǎng)絡(luò)，對每一條弧 （vi,vj），除了給出容量cij外，還給出了這條弧的單位流量的費用bij，要 求一個最大流F，并使得總運送費用最小。 一、最小費用最大流的數(shù)學(xué)模型 例7 由于輸油管道的長短不一，所以在例6中每段管道（ vi,vj ）除 了有不同的流量限制cij外，還有不同的單位流量的費用bij ，cij的單

10、位為萬 加侖/小時， bij的單位為百元/萬加侖。如圖。從采地 v1向銷地 v7運送石 油，怎樣運送才能運送最多的石油并使得總的運送費用最??？求出最大流 量和最小費用,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,18,5最小費用最大流問題,這個最小費用最大流問題也是一個線性規(guī)劃的問題。 解：我們用線性規(guī)劃來求解此題，可以分兩步走。 第一步，先求出此網(wǎng)絡(luò)圖中的最大流量F，這已在例6中建立了線性規(guī)劃的模型，通過管理運籌學(xué)軟件已經(jīng)獲得結(jié)果。 第二步，在最大流量F的所有解中，找出一個最小費用的解，我們來建立第二步中的

11、線性規(guī)劃模型如下： 仍然設(shè)?。╲i,vj）上的流量為fij，這時已知網(wǎng)絡(luò)中最大流量為F，只要在例6的約束條件上，再加上總流量必須等于F的約束條件：f12=f14=F,即得此線性規(guī)劃的約束條件，此線性規(guī)劃的目標函數(shù)顯然是求其流量的最小費用 。 由此得到線性規(guī)劃模型如下,19,5最小費用最大流問題,20,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。其最優(yōu)值(最小費用)=145。對照前面例6的結(jié)果，可對最小費用最大流的概念有一個深刻的理解。 如果我們把例7

12、的問題改為：每小時運送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ī)劃的模型了,21,5最小費用最大流問題,二、最小費用最大流的網(wǎng)絡(luò)圖論解法 對網(wǎng)絡(luò)上?。╲i,vj）的（c

13、ij,bij）的表示作如下改動，用(b)來表示(a)。 用上述方法對例7中的圖形進行改進，得圖如下頁,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,22,5最小費用最大流問題,求最小費用最大流的基本算法 在對弧的標號作了改進的網(wǎng)絡(luò)圖上求最小費用最大流的基本算法與求 最大流的基本算法完全一樣，不同的只是在步驟（1）中要選擇一條總的 單位費用最小的路，而不是包含邊數(shù)最小的路,23,5最小費用最大流問題,用上述方法對例7求解： 第一次迭代：找到最

14、短路v1 v4 v6 v7。第一次迭代后總流量為1，總 費用10,v5,24,5最小費用最大流問題,第二次迭代：找到最短路v1 v4 v7。第二次迭代后總流量為3，總費用 32,25,5最小費用最大流問題,第三次迭代：找到最短路v1 v4 v3 v6 v7 。第三次迭代后總流量為 5，總費用56,26,5最小費用最大流問題,第四次迭代：找到最短路v1 v4 v3 v5 v7 。第四次迭代后總流量為 6，總費用72,27,5最小費用最大流問題,第五次迭代：找到最短路v1 v2 v5 v7 。第五次迭代后總流量為9，總 費用123,28,5最小費用最大流問題,第六次迭代：找到最短路v1 v2 v3 v5 v7 。第六次迭代后總流量為 10，總費用145。已經(jīng)找不到從v1到v7的每條弧容量都大于零的路了，故 已求得最小費用最大流了,29,5最小費用最大流問題,如果對例7求一個最小費用流的問題：每小時運送