運籌學導論第八版6網(wǎng)絡(luò)模型

第6章網(wǎng)絡(luò)模型16.1網(wǎng)絡(luò)模型的應(yīng)用范圍和定義大量的運籌學問題都可以應(yīng)用網(wǎng)絡(luò)建模來求解：在墨西哥海灣上需要設(shè)計一個海面上的天然氣管道網(wǎng)絡(luò)，將各個井口鏈接到岸邊的運輸點，模型目標是最小化管道建設(shè)費用。在已經(jīng)存在的道路網(wǎng)絡(luò)中，求起訖點之間的最短路徑.求山西煤礦到北京的發(fā)電廠的煤漿管道網(wǎng)絡(luò)的最大運輸量給一個工程項目中的各項活動確定時間表2網(wǎng)絡(luò)模型的定義網(wǎng)絡(luò)是由節(jié)點(node)和弧(arc)集合組成，用符號(N,A)表示，其中N表示節(jié)點的集合，A表示弧的集合。14235N={1，2，3，4，5}A={(1,2),(1,3),(2,3),(2,5),(3,4),(3,5),(4,2),(4,5)}如果一條弧上的其中一個方向的流量是正數(shù)，相反方向就是為零，該弧是有向的(directed)，如果所有弧上的容量都是有向的，則網(wǎng)絡(luò)是有向網(wǎng)絡(luò)。將兩點之間鏈接起來，并經(jīng)過其他的一些節(jié)點的這一些列弧，稱之為路徑(path),如果經(jīng)過路徑又能回到自身，則這些路徑稱之為圈(Loop),如果網(wǎng)絡(luò)中沒有圈，網(wǎng)絡(luò)就是樹(tree),如果該樹包括了圖上所有的節(jié)點，則是生成樹。3歐拉(Euler)在1736年發(fā)表圖論方面的第一篇論文，解決了著名的哥尼斯堡七橋問題。哥尼斯堡城中有一條河叫普雷格爾河，該河中有兩個小島，河上有七座橋，參見圖5.1(a)。當時那里的居民熱衷于這樣的問題：一個散步者能否走過七座橋，且每座橋只走過一次，最后回到出發(fā)點。BACDBACD4例1是北京、上海等十個城市間的鐵路交通圖。與此類似的還有電話線分布圖、煤氣管道圖、航空路線圖等。北京天津濟南青島武漢南京上海鄭州連云港徐州5例2

分別用點v1,v2,v3,v4,v5分別代表甲、乙、丙、丁、戊五支球隊。若有兩支球隊之間比賽過，就在相應(yīng)的點之間聯(lián)一條線，且這條線不過其他點。如下圖所示：v1v2v3v4v5可知各隊之間的比賽情況如下：甲——乙、丙、丁、戊乙——甲、丙丙——甲、乙、丁丁——甲、丙、戊戊——甲、丁6例3“染色問題”儲存8種化學藥品，其中某些藥品不能存放在同一個庫房里。用v1,v2,…,v8分別代表這8種藥品。規(guī)定若兩種藥品不能存放在一起，則其相應(yīng)的點之間聯(lián)一條線。如下圖所示：v1v2v3v4v5v6v7v8可知需要4個庫房，其中一個答案是：

{v1}{v2,v4,v7}{v3,v5}{v6,v8}還有其他的答案。7從以上幾個例子可見可以用由點及點與點的聯(lián)線所構(gòu)成的網(wǎng)絡(luò)，去反映實際生活中，某些對象之間的某個特定的關(guān)系，通常用點代表研究的對象（如城市、球隊、藥品等等），用點與點的聯(lián)線表示這兩個對象之間有特定的關(guān)系（如兩個城市間有鐵路線、兩個球隊比賽過、兩種藥品不能存放在同一個庫房里等）。網(wǎng)絡(luò)是反映對象之間關(guān)系的一種工具因此，可以說，在一般情況下，網(wǎng)絡(luò)中點的相對位置如何，點與點之間聯(lián)線的長短曲直，對于反映對象之間的關(guān)系，并不是重要的，例如哥尼斯堡七橋問題。如例2，也可以用網(wǎng)絡(luò)去反映五個球隊的比賽情況，這與例3沒有本質(zhì)的區(qū)別。所以，圖論中的圖與幾何圖、工程圖等是不同的。86.2最小生成樹算法最小生成樹算法是以來鏈接一個網(wǎng)絡(luò)所有的節(jié)點，使得樹上邊的總長度最小。例如，在幾個城鎮(zhèn)之間修路，使得任意兩個城鎮(zhèn)之間都有路相連，之間可以穿過其他城鎮(zhèn)那么最經(jīng)濟的道路網(wǎng)絡(luò)設(shè)計方案就是道路里程最小。令N={1,2,…,n}是網(wǎng)絡(luò)中節(jié)點的集合，定義：9最小生成樹算法步驟：第0步令第1步從中的任意一個節(jié)點i開始，令C1={i},那么，設(shè)定k=2.一般的第k步在還沒有連接的節(jié)點集合中選擇一個節(jié)點j*，使得j*到Ck-1中某個節(jié)點之間的弧長最小，然后將j*放在Ck-1，從中刪除j*，即10例中西部有線電視公司正在計劃為5個新的居民區(qū)提供有線電視服務(wù)，下圖給出了小區(qū)之間可以鋪設(shè)電纜的情況以及相應(yīng)的距離。確定最經(jīng)濟的電纜鋪設(shè)方案，使得5個小區(qū)可以連接起來。2413561478351096351124356179241356148356324135614786324135614796315555迭代1迭代2迭代3迭代4C1C2C3C412241356143535241356143510635迭代5迭代6（最小生成樹）C5可選邊最小生成樹算法在第6步給出了問題的解，要服務(wù)的電視網(wǎng)絡(luò)線纜長度為1+3+4+3+5=16136.3最短路徑問題6.3.1最短路應(yīng)用實例RentCar公司開展了一項4年一周期的汽車更換政策，在每一年的開始，消費者都可以選擇繼續(xù)使用購買的汽車，也可以選擇更換汽車。一輛汽車最少使用1年，最多3年，下表給出了汽車更換的費用，它取決于車輛購置時的年數(shù)以及使用年限。客戶該如何更換汽車？開始購買汽車的年數(shù)給定年限的更換費用12314000540098002430062008700348007100—44900——14該問題可以描述為網(wǎng)絡(luò)模型，節(jié)點1到5表示第1年到第5年每年的開始。與節(jié)點1(第1年)有弧相連的節(jié)點只有2,3,4,因為按照軌道汽車的使用年限為1到3年。同理，可以推斷出從其他節(jié)點出發(fā)的弧。每條弧的長度等于更換費用。那么問題等價于求一條從節(jié)點1到5的最短路徑。12345980054007100620087004000430048004900可以知道，最短路是1→3→5.這個解說明汽車在第1年購買，然后使用2年，在第3年開始的時候更換新的汽車，一直使用到年底。15例Smart每天開車去工作，如果找最短走，會被限速因此行程時間不是最短，如果超速會被罰款，所以最短路對smart而言不是最好選擇.假設(shè)已知各個路段相應(yīng)不被罰款的概率已知，如下圖。他想選擇一條不被警察罰款的概率最大的路徑，該如何選擇？123450.20.80.350.5670.90.30.25一條路徑不被罰款的概率是這條路徑上每一段上不被罰款的概率的乘積。例如對于1→3→5→7不被罰款的概率為0.9×0.3×0.25=0.0670.60.10.416由于不被罰款的概率為，那么取對數(shù)之后是因此，通過對數(shù)變化，這個問題可以轉(zhuǎn)化為最短路問題，也就是將概率乘積轉(zhuǎn)為對數(shù)概率之和。從數(shù)學角度來看，p1k的最大化等價于lgp1k的最大化，由于lgp1k≤0，所以lgp1k的最大化等價于-lgp1k的最小化123450.69870.96910.455930.30103670.045760.522880.602060.2218510.39794求解結(jié)果表明，節(jié)點1,3,5,7是最短的路徑，長度為1.1707(=lgp17)，其概率為0.0675176.3.2最短路徑算法Dijkstra算法用ui表示從原點1到節(jié)點i的最短距離，定義dij(≥0)為弧(i,j)的長度，那么即可得到節(jié)點j的標號為[uj,i]=[ui+dij,i],dij≥0開始的節(jié)點標號為[0,-].在Dijkstra算法中涉及兩種類型的標號：暫時的和永久的標號。對于暫時標號，如果這個節(jié)點找到更短的路徑，那么標號改變，如果找不到更短的路徑，標號變成永久的。常用的最短路算法有2種，Dijkstra算法和Floyd算法，Dijkstra算法可以求網(wǎng)絡(luò)中原點到其他任意一個節(jié)點的最短路徑。而Floyd算法可以求網(wǎng)絡(luò)中任意兩點之間的最短路徑18算法步驟第0步對原點(節(jié)點1)給出永久的標號[0,—].令i=1.第1步(a)計算節(jié)點i有邊相連的每一個節(jié)點j(j沒有被永久標號)的暫時標號[ui+dij,i].如果節(jié)點j已經(jīng)通過另外一個節(jié)點k被標號為[uj,k],如果ui+dij<

uj,那么就用標號[ui+dij,i]代替[uj,k].(b)如果所有的節(jié)點都得到了永久的標號，那么停止.否則從所有暫時標號的節(jié)點中選擇具有最短距離(=ur)的標號[ur,s],令i=r，然后重復(fù)執(zhí)行第i步19例下圖給出了從城市1(節(jié)點1)和其他4個城市(節(jié)點2到節(jié)點5)之間可能的路線以及每條邊的長度，求城市1到其他4個城市的最短路徑.24315100155060302010迭代0

給出節(jié)點1分配永久標號[0,─].20迭代0

給出節(jié)點1分配永久標號[0,─].迭代1

節(jié)點1(永久標號節(jié)點)可以直接到達節(jié)點2和3，那么下表給出了節(jié)點新的標號(暫時的和永久的)：節(jié)點標號標號狀態(tài)1[0,─]永久2[0+100,1]=[100,1]暫時3[0+30,1]=[30,1]暫時上表中有兩個暫時的標號[100,1]和[30,1]，節(jié)點3的距離較小(u3=30).因此，把節(jié)點3的標號狀態(tài)變成永久的。21迭代2

節(jié)點3可以直接到達節(jié)點4和5，那么下表給出了各個節(jié)點新的標號(暫時的和永久的)為：節(jié)點標號標號狀態(tài)1[0,─]永久2[100,1]暫時3[30,1]永久4[30+10,3]=[40,3]暫時5[30+60,3]=[90,3]暫時將暫時標號為[40,3]的節(jié)點4的標號狀態(tài)轉(zhuǎn)變?yōu)橛谰玫?u4=40)22迭代3

節(jié)點4可以直接到達節(jié)點2和5，那么新的標號為：節(jié)點標號標號狀態(tài)1[0,─]永久2[40+15,4]=[55,4]暫時3[30,1]永久4[40,3]永久5[90,3]或[40+50,3]=[90,4]暫時對于節(jié)點2，在迭代1得到的暫時標號為[100,1],而此時通過節(jié)點4找到了一條更短的路徑，所以將節(jié)點2的標號更改為[55,4].同樣在這次迭代后，節(jié)點5有了兩個可以選擇的標號，并且標號對應(yīng)的距離相等(u5=40).通過比較，這一次迭代選擇節(jié)點2，并將節(jié)點2的標號變成永久的。23迭代4

此時節(jié)點2只可以到達節(jié)點3，然而節(jié)點3已經(jīng)是永久性標號了，不能給予重新標號了。所以這一代迭代的標號除了將節(jié)點2的標號變?yōu)橛谰玫囊酝猓渌呐c迭代3的標號相同。這樣節(jié)點5是僅有的暫時標號，又因為節(jié)點5沒有子節(jié)點，所以節(jié)點5的標號自動變成永久的。整個過程結(jié)束。節(jié)點標號標號狀態(tài)1[0,─]永久2[40+15,4]=[55,4]永久3[30,1]永久4[40,3]永久5[90,3]或[90,4]永久24這個算法的計算過程可以很容易的在網(wǎng)絡(luò)上得以實現(xiàn)，如下圖所示。24315100155060302010[0,-](1)[55,4](3)[100,1](1)[40,3](2)[30,1](1)[90,4](3)[90,3](2)迭代次數(shù)25從節(jié)點1到其他任何一個節(jié)點的最短路徑可以通過這個節(jié)點的永久標號中的信息采用一步步回溯的辦法得到，例如，節(jié)點1到節(jié)點2的最短路徑可以通過下面回溯方法找到：(2)→[55,4]→(4)→[40,3]→(3)→[30,1]→(1)那么所求的最短路徑是1→3→4→2，總長度55節(jié)點標號標號狀態(tài)1[0,─]永久2[40+15,4]=[55,4]永久3[30,1]永久4[40,3]永久5[90,3]或[90,4]永久2632865417121225862413765習題求節(jié)點4和8之間的最短路徑27Floyd算法Floyd算法比Dijkstra算法更加一般的算法，因為它可以給出網(wǎng)絡(luò)中任意兩個節(jié)點之間的最短路徑。算法首先將n個節(jié)點的網(wǎng)絡(luò)表示成一個n行n列的矩陣，矩陣中的元素(i,j)表示從節(jié)點i到節(jié)點j的距離dij，如果i,j之間沒有邊相連，那么相應(yīng)的元素為無窮.Floyd算法的思想很直觀，如下圖，給定3個節(jié)點i,j,k,以及它們之間的距離，如果滿足

dik+dkj<dij那么從i經(jīng)過k到j(luò)更短.在這種情況下，用間接的路徑i→k→j代替路徑i→j.下面的步驟給出了這種三重操作替換應(yīng)用在網(wǎng)絡(luò)上的具體算法.ijkdikdikdij28算法步驟：第0步定義初始的距離矩陣D0和節(jié)點序列矩陣S0，如下表，對角線上用元素(-)表示不必要從自身到自身.令k=1.29算法步驟：一般的第k步令第

k行和第

k列為樞軸行和樞軸列.對于矩陣Dk-1

中的每一個元素dij做三重操作.如果滿足條件：dik+dkj<dij(i≠k,j≠k,i≠j)那么進行下面的轉(zhuǎn)化：

(a)用dik+dkj代替矩陣Dk-1中的元素dij，從而得到矩陣Dk(b)用k代替矩陣Sk-1中的元素sij，從而得到矩陣Sk.令k=k+1.如果k=n+1,停止；否則重復(fù)第k步.

30經(jīng)過n步之后，我們可以從矩陣Dn和Sn中按照下面的規(guī)則得到節(jié)點i和節(jié)點j之間的最短路徑：

(1)在矩陣Dn中，dij表示節(jié)點i與節(jié)點j之間的最短路徑長度.(2)在矩陣Sn中，可以確定中間節(jié)點k=sij(根據(jù)得到的路徑i→k→j).如果sik=k并且skj=j，停止，因為路徑中所有的中間節(jié)點都找到了.否則，在節(jié)點i與節(jié)點k之間，節(jié)點k與節(jié)點j之間重復(fù)上面的程序.31下圖給出了算法第k步對矩陣Dk-1的轉(zhuǎn)化過程，其中k行和k列是當前的樞軸行和樞軸列.第i行表示第1,2,┅,k-1行中的任意一個，第p行表示第k+1，k+2,┅,n行中的任意一個，第j列表示第1,2,┅,k-1行中的任意一個，第q列表示第k+1，k+2,┅,n列中的任意一個.三重操作可以按照下面的方法執(zhí)行：如果樞軸行和樞軸列上的元素(圖中正方形中的元素)之和小于相交元素(圖中圓形中的元素)的值，那么用這個和代替交叉元素的值就可以使最短距離得到優(yōu)化.dijdiqdpjdpqdikdpkdkjdkq樞軸行k行i行p列j列q樞軸列k32例下圖給出的網(wǎng)絡(luò)，求任意兩點之間的餓最短路徑.圖中弧上給出了相應(yīng)節(jié)點間的距離.弧(3,5)是有向的，因此不允許從節(jié)點5到節(jié)點3，其他邊是雙向的.1234535106154123451—310∞∞23—∞5∞310∞—6154∞56—45∞∞∞4—33迭代0

矩陣D0和S0代表初始的網(wǎng)絡(luò).除了d53=∞外(因為不允許從節(jié)點5到節(jié)點3)，D0是對稱的.123451—310∞∞23—∞5∞310∞—6154∞56—45∞∞∞4—123451—234521—345312—454123—551234—D0S0迭代1

令k=1.D0矩陣中的紅色字體的第1行和第1列為樞軸行和樞軸列，其中應(yīng)用三重操作可以改進的元素是d23和d32(圖中用深色陰影表示).然后根據(jù)下面的方法，從D0和和S0得到D1和S1：(1)用d21+d13=3+10=13代替d23，并令s23=1(2)用d31+d12=10+3=13代替d32，并令s32=134123451—310∞∞23—135∞31013—6154∞56—45∞∞∞4—123451—234521—145311—454123—551234—D1S1迭代2

令k=2.D1矩陣中的紅色字體的第1行和第1列為樞軸行和樞軸列，其中應(yīng)用三重操作可以改進的元素是d14和d41(圖中橙色部分).然后根據(jù)下面的方法，從D0和和S0得到D1和S1：(1)用d12+d24=3+5=8代替d14，并令s14=1(2)用d42+d21=3+5=8代替d41，并令s41=135123451—3108∞23—135∞31013—6154856—45∞∞∞4—123451—232521—145311—454223—551234—D2S2迭代3

令k=3.D2矩陣中的紅色字體的第3行和第3列為樞軸行和樞軸列，其中應(yīng)用三重操作可以改進的元素是d14和d41(圖中橙色部分).然后根據(jù)下面的方法，從D0和和S0得到D1和S1：(1)用