運籌學(xué)第六章圖與網(wǎng)絡(luò)分析

1、第六章 圖與網(wǎng)絡(luò)分析 6.1 圖的基本概念與數(shù)學(xué)模型 6.2 樹圖和圖的最小部分樹 6.3 最短路問題 6.4 中國郵路問題 6.5 網(wǎng)絡(luò)最大流問題 6.6 網(wǎng)絡(luò)模型的實際應(yīng)用第六章 圖與網(wǎng)絡(luò)分析 圖是一種模型，如公路、鐵路交通圖，通訊網(wǎng)絡(luò)圖等。 圖是對現(xiàn)實的抽象，以點和線段的連接組合表示。6.1 圖的基本概念和模型一、概念（1）圖：點V和邊E的集合，用以表示對某種現(xiàn)實事物的抽象。記作 G=V,E, V=v1,v2,vn, E=e1,e2,em點：表示所研究的事物對象； 邊：表示事物之間的聯(lián)系。v1v2v3v4v0e1e2e3e4e5e6e7e0（2）若邊e的兩個端點重合，則稱e為環(huán)。（3）多

2、重邊：若某兩端點之間多于一條邊，則稱為多重邊。（4）簡單圖：無環(huán)、無多重邊的圖稱為簡單圖。（5）鏈：點和邊的交替序列，其中點可重復(fù)，但邊不能重復(fù)。（6）路：點和邊的交替序列，但點和邊均不能重復(fù)。（7）圈：始點和終點重合的鏈。（8）回路：始點和終點重合的路。（9）連通圖：若一個圖中，任意兩點之間至少存在一條鏈，稱這樣的圖為連通圖。（10）子圖，部分圖：設(shè)圖G1=V1,E1, G2=V2,E2, 如果有V1V2，E1E2，則稱G1是G2的一個子圖；若V1=V2，E1E2，則稱G1是G2的一個部分圖。（11）次：某點的關(guān)聯(lián)邊的個數(shù)稱為該點的次，以d(vi)表示。二、圖的模型 例：有甲、乙、丙、丁、戊

3、、己六名運動員報名參加A、B、C、D、E、F六個項目的比賽。如表中所示，打“”的項目是各運動員報名參加比賽的項目。問：六個項目的比賽順序應(yīng)如何安排，才能做到使每名運動員不連續(xù)地參加兩項比賽？甲 乙 丙 丁 戊 己項目人ABCDEF 建立模型：解：項目作為研究對象，排序。設(shè) 點：表示運動項目。邊：若兩個項目之間無同一名運動員參加。ABCDEFACDEFBAFEDCBACBFEDAFBCDE順序：6.2 樹圖和圖的最小部分樹（1）樹：無圈的連通圖稱為樹圖，簡稱為樹。一、樹圖的概念（2）樹的特性： 樹是邊數(shù)最多的無圈連通圖。在樹中任加一條邊，就會形成圈。 樹是邊數(shù)最少的連通圖。在樹中任減一條邊，則不

4、連通。（3）圖的最小部分樹：定義：若G1是G2的一個部分圖，且為樹圖，則稱G1是G2的一個部分樹。G2：ABCD547365576G1：ACBD定義：樹枝總長為最短的部分樹稱為圖的最小部分樹。二、最小部分樹的求法例：要在下圖所示的各個位置之間建立起通信網(wǎng)絡(luò)， 試確定使總距離最佳的方案。樹枝：樹圖中的邊稱為樹枝。SABCDET252414317557最小部分樹長Lmin=141. 避圈法1. 避圈法：將圖中所有的點分V為V兩部分，V最小部分樹內(nèi)點的集合V非最小部分樹內(nèi)點的集合 任取一點vi加粗，令viV， 取V中與V相連的邊中一條最短的邊(vi,vj)， 加粗(vi,vj)，令vjV 重復(fù) ，至

5、所有的點均在V之內(nèi)。2. 破圈法： 任取一圈，去掉其中一條最長的邊， 重復(fù)，至圖中不存在任何的圈為止。SABCDET252414317557 最小部分樹長Lmin=142. 破圈法6.3 最短路問題 在圖示的網(wǎng)絡(luò)圖中，從給定的點S出發(fā)，要到達目的地T。問：選擇怎樣的行走路線，可使總行程最短？方法：Dijkstra（D氏）標號法按離出發(fā)點的距離由近至遠逐漸標出最短距離和最佳行進路線。S1求某兩點間最短距離的D（Dijkstra）氏標號法247SABCDET25241431755702447891413594 最短路線：S AB E D T最短距離：Lmin=132求任意兩點間最短距離的矩陣算法

6、構(gòu)造任意兩點間直接到達的最短距離矩陣D（0）= dij（0） S A B C D E T S 0 2 5 4 A 2 0 2 7 B 5 2 0 1 5 3 C 4 1 0 4 D 7 5 0 1 5 E 3 4 1 0 7 T 5 7 0D（0）= 構(gòu)造任意兩點間直接到達、或者最多經(jīng)過1個中間點到達的最短距離矩陣D（1）= dij（1）其中 dij（1）= min dir（0）+ drj（0） ， S A B C D E T S 0 2 4 4 9 8 A 2 0 2 3 7 5 12 B 4 2 0 1 4 3 10 C 4 3 1 0 5 4 11 D 9 7 4 5 0 1 5 E 8

7、 5 3 4 1 0 6 T 12 10 11 5 7 0D（1）=irjdir（0）drj（0）rdSE（1）= min dSS（0）+dSE（0）, dSA（0）+dAE（0）, dSB（0）+dBE（0）, dSC（0）+dCE（0）, dSD（0）+ dDE（0） , dSE（0）+ dEE（0）, dST（0）+ dTE（0） =8例如其中 dij（2）= min dir（1）+ drj（1） S A B C D E T S 0 2 4 4 8 7 14 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5

8、 E 7 5 3 4 1 0 6 T 14 11 9 10 5 6 0D（2）=irjdir（1）drj（1）r 構(gòu)造任意兩點間最多可經(jīng)過3個中間點到達的最短距離矩陣 D（2）= dij（2）其中 dij（3）= min dir（2）+ drj（2） S A B C D E T S 0 2 4 4 8 7 13 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 13 11 9 10 5 6 0D（3）=irjdir（2）drj（2）r 構(gòu)造任意兩點間最多可經(jīng)過7個中間點到達的最

9、短距離矩陣 D（3）= dij（3）說明：一般，對于D（k）= dij（k），其中 dij（k）= min dir（k-1）+ drj（k-1） ，k=0，1，2，3， 最多可經(jīng)過2k-1個中間點： 其數(shù)列為 0，1，3，7，15，31， 2k-1， 收斂條件： 當(dāng) D（k+1）= D（k）時，計算結(jié)束； 設(shè)網(wǎng)絡(luò)中有p個點，即有p-2個中間點，則 2k-1-1 p-2 2k-1 k-1log2 (p-1) k Klog2(p-1)+1，計算到 k=lg(p-1)/lg2 +1時，收斂，計算結(jié)束。例：有7個村鎮(zhèn)要聯(lián)合建立一所小學(xué)，已知各村鎮(zhèn)小學(xué)生的人數(shù)大致為S30人， A40人，B20人，C15

10、人，D35人，E25人， T50人。問：學(xué)校應(yīng)建在那一個地點，可使學(xué)生總行程最少？ S A B C D E T S 0 2 4 4 8 7 13 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 13 11 9 10 5 6 0L=30 40 20 15 35 25 50人數(shù)= 1325 1030 880 1035 910 865 1485T解：6.4 中國郵路問題問題：一名郵遞員從郵局出發(fā)，試選擇一條最短的投遞路線？v1v2v3v4v5v6v8v7v9v10v11v12v13

11、郵局44455124125447422奇點：圖中次為奇數(shù)的點稱為奇點。偶點：圖中次為偶數(shù)的點稱為偶點。結(jié)論：結(jié)論：最短投遞路線應(yīng)具有下述特征： 若圖中所有的點均為偶點，則可不重復(fù)走遍所有街道； 重復(fù)走的路線長度應(yīng)不超過所在回路總長度的一半。步驟：1. 兩兩連接所有的奇點，使之均成為偶點；2. 檢查重復(fù)走的路線長度，是否不超過其所在回路總長的一半，若超過，則調(diào)整連線，改走另一半。v1v2v3v4v5v6v8v7v9v10v11v12v13郵局44455124125447422投遞距離：L=60+18=786.5 網(wǎng)絡(luò)最大流問題一、網(wǎng)絡(luò)最大流中有關(guān)概念 有向圖：含有以箭頭指示方向的邊的網(wǎng)絡(luò)圖。 弧

12、：有向圖上的邊稱為弧。用（vi,vj）表示。 弧的容量：弧上通過負載的最大能力，簡稱容量。以cij表示。 流：加在網(wǎng)絡(luò)每條弧上的一組負載量，以fij表示。 可行流：能夠通過網(wǎng)絡(luò)的負載量，通常應(yīng)滿足兩個條件： 容量限制條件：對所有的弧，0 fijcij 中間點平衡條件：對任何一個中間點，流入量=流出量 發(fā)點、收點、中間點：流的起源點稱發(fā)點，終到點稱收點，其余的點稱中間點。 最大流；能夠通過網(wǎng)絡(luò)的最大流量。 割集：一組弧的集合，割斷這些弧，能使流中斷。簡稱割。8(8)v1vsv2v3v4vt7(5)9(4)9(9)2(0)6(1)5(5)10(8)(0,+)(vs,2)(v2,2)(v1,2)(v

13、3,1)(v4,1)5(4)cijfij 割的容量：割集中各弧的容量之和。 最小割：所有割集中容量之和為最小的一個割集。 前向弧+：一條發(fā)點到收點鏈中，由發(fā)點指向收點的弧，又稱正向弧。 后向弧-：一條發(fā)點到收點鏈中，由收點指向發(fā)點的弧，又稱逆向弧。 增廣鏈：由發(fā)點到收點之間的一條鏈，如果在前向弧上滿足流量小于容量，即fij0，則稱這樣的鏈為增廣鏈。二、兩個定理定理：網(wǎng)絡(luò)的最大流量等于它的最小割集的容量。定理：當(dāng)網(wǎng)絡(luò)中不存在任何增廣鏈時，則網(wǎng)絡(luò)達到最大流狀態(tài)。st6(4)5(3)4(4)8(7)設(shè)有如下增廣鏈：f=1 該網(wǎng)絡(luò)沒有達到最大流狀態(tài)。三、網(wǎng)絡(luò)最大流的標號算法(Ford-Fulkerso

14、n標號算法)基本思想：尋找增廣鏈，改善流量分布；再重復(fù)，直到不 存在任何增廣鏈為止。步驟： 給始點標號：（0，+） 從已標號點i出發(fā)，看與其相關(guān)聯(lián)的未標號點j上的弧，對+，若有0fijcij，則可對j點標號，記（i, (j)），其中 (j)=min (i) ，cij - fij對-，若有0 fji cij，也可對j點標號，記（ i, (j)），其中 (j)=min (i) ，fji （注：若有多個可標號點，可任選其中之一。） 若標號中斷，則得到最大流狀態(tài)，否則，重復(fù)，繼續(xù)標號，至收點得到標號，轉(zhuǎn)。當(dāng)收點得到標號，則沿標號得到的增廣鏈進行流量調(diào)整：對+，fij = fij + (t)對-，fij

15、 = fij - (t) 其余弧上的流量不變。 重復(fù)上述過程。 最小割集：已標號點集合與未標號點集合相連接的弧中， 流量=容量的弧。8(8)v1vsv2v3v4vt7(6)9(5)9(9)2(0)6(0)5(5)10(9)5(3)(0,+)(vs,1)(v2,1)(v1,1)最大流量：fmax=14最小割集：(v3, vt), (v2, v4)6.6 網(wǎng)絡(luò)模型的實際應(yīng)用 例1：王經(jīng)理花費12000元購買了一臺微型車，以后年度的維護費用取決于年初時汽車的役齡，如表示。為避免使用舊車帶來較高的維護費用，王經(jīng)理可選擇賣掉舊車，購買新車使用的方案，舊車的預(yù)計收入如表示。為簡化計算，假定任何時刻購買新車都需花費12000元，王經(jīng)理的目標是使凈費用最?。ㄙ徶觅M+維護費-賣舊車收入）。役齡(年)年維護費預(yù)計收入單位：元012345200040005000900012000700060002000 1000 0解：用網(wǎng)絡(luò)圖模型描述，歸結(jié)為最短路問題。77777123