管理運籌學(xué)課件第二章_圖論

1、第二章 圖論與網(wǎng)絡(luò)分析 圖的基本概念 網(wǎng)絡(luò)分析最小支撐樹問題 最短路徑問題網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)計劃問題7/19/2022管理運籌學(xué)ABCDACBD圖論起源哥尼斯堡七橋問題結(jié)論：每個結(jié)點關(guān)聯(lián)的邊數(shù)均為偶數(shù)。問題：一個散步者能否從任一塊陸地出發(fā)，走過七座橋，且每座橋只走過一次，最后回到出發(fā)點？7/19/2022管理運籌學(xué)1 圖的基本概念由點和邊組成，記作G=(V，E)，其中V=v1，v2，vn為結(jié)點的集合，E=e1，e2，em 為邊的集合。點表示研究對象邊表示表示研究對象之間的特定關(guān)系1. 圖7/19/2022管理運籌學(xué)圖無向圖，記作G=(V，E)有向圖，記作D=(V，A)例1：哥尼斯堡橋問題的圖為

2、一個無向圖。有向圖的邊稱為弧。例2：五個球隊的比賽情況，v1v2表示v1勝v2。v1v2v3v4v52、圖的分類7/19/2022管理運籌學(xué)v1v2v3v4v53、鏈與路、圈與回路鏈點邊交錯的序列圈起點=終點的鏈路點弧交錯的序列回路起點=終點的路v1v2v3v4v5無向圖：有向圖：7/19/2022管理運籌學(xué)4、連通圖任何兩點之間至少存在一條鏈的圖稱為連通圖，否則稱為不連通圖。G1G2G1為不連通圖， G2為連通圖例 ：7/19/2022管理運籌學(xué)5、支撐子圖圖G=(V，E)和G=(V ，E )，若V =V 且E E ，則稱G 為G的支撐子圖。G2為G1的支撐子圖v1v2v3v4v5G1v1v

3、2v3v4v5G2例 ：7/19/2022管理運籌學(xué)6、賦權(quán)圖（網(wǎng)絡(luò)）圖的每條邊都有一個表示一定實際含義的權(quán)數(shù)，稱為賦權(quán)圖。記作D=(V，A，C)。55.5v1v2v3v4v53.57.5423例 ：7/19/2022管理運籌學(xué)2 最小支撐樹問題本節(jié)主要內(nèi)容：樹支撐樹最小支撐樹 例今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟(jì)的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS22222254526345317/19/2022管理運籌學(xué)1、樹中任兩點中有且僅有一條鏈；2、樹任刪去

4、一邊則不連通，故樹是使圖保持連通且具有最少邊數(shù)的一種圖形。3、邊數(shù) = 頂點數(shù) 1。樹無圈連通圖(A)(B)(C)樹的性質(zhì)：例 判斷下面圖形哪個是樹：一、樹的概念與性質(zhì)7/19/2022管理運籌學(xué) 若一個圖 G =（V , E）的支撐子圖 T=（V , E） 構(gòu)成樹，則稱 T 為G的支撐樹，又稱生成樹、部分樹。二、圖的支撐樹(G)(G1)(G2)(G3)(G4)例7/19/2022管理運籌學(xué)例 某地新建5處居民點，擬修道路連接5處，經(jīng)勘測其道路可鋪成如圖所示。為使5處居民點都有道路相連，問至少要鋪幾條路？解：該問題實為求圖的支撐樹問題，共需鋪4條路。v1v2v3v4v5 圖的支撐樹的應(yīng)用舉例v

5、1v2v3v4v555.57.53.54237/19/2022管理運籌學(xué)問題：求網(wǎng)絡(luò)的支撐樹，使其權(quán)和最小。三、最小支撐樹問題55.5v1v2v3v4v57.53.5423算法1（避圈法）：把邊按權(quán)從小到大依次添入圖中，若出現(xiàn)圈，則刪去其中最大邊，直至填滿n-1條邊為止（n為結(jié)點數(shù)） 。例 求上例中的最小支撐樹解：3v12v4v545v23.5v37/19/2022管理運籌學(xué)算法2（破圈法）： 在圖中找圈，并刪除其中最大邊。如此進(jìn)行下去，直至圖中不存在圈。55.5v1v2v3v4v57.53.54237/19/2022管理運籌學(xué)算法2（破圈法）： 在圖中找圈，并刪除其中最大邊。如此進(jìn)行下去，直

6、至圖中不存在圈。55.5v1v2v3v4v53.54237/19/2022管理運籌學(xué)算法2（破圈法）： 在圖中找圈，并刪除其中最大邊。如此進(jìn)行下去，直至圖中不存在圈。5v1v2v3v4v53.54237/19/2022管理運籌學(xué)算法2（破圈法）： 在圖中找圈，并刪除其中最大邊。如此進(jìn)行下去，直至圖中不存在圈。5v1v2v3v4v53.5237/19/2022管理運籌學(xué) 例今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟(jì)的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS222222

7、54526345317/19/2022管理運籌學(xué) 例今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟(jì)的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS2222224526345317/19/2022管理運籌學(xué) 例今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟(jì)的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS222222526345317/19/2022管理運籌學(xué)

8、例今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟(jì)的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS22222226345317/19/2022管理運籌學(xué) 例今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟(jì)的煤氣管道路線，并求所需的總費用。ABCDEFGHIJKS22222226345317/19/2022管理運籌學(xué) 例今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖

9、所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟(jì)的煤氣管道路線，并求所需的總費用。IABCDEFGHJKS2222222345317/19/2022管理運籌學(xué) 例今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟(jì)的煤氣管道路線，并求所需的總費用。IJABCDEFGHKS22222223431此即為最經(jīng)濟(jì)的煤氣管道路線，所需的總費用為25萬元7/19/2022管理運籌學(xué)案例分析：默登公司的聯(lián)網(wǎng)問題 默登（Modern）公司的管理層決定鋪設(shè)最先進(jìn)的光纖網(wǎng)絡(luò)，

10、為它的主要中心之間提供高速通信。圖1中的節(jié)點顯示了該公司主要中心的分布圖。虛線是鋪設(shè)光纜可能的位置。每條虛線旁邊的數(shù)字表示成本（單位：百萬美元）。 問：需要鋪設(shè)哪些光纜使得總成本最低？ ABCEGFD252745713144圖1 光纜鋪設(shè)費用圖7/19/2022管理運籌學(xué)案例分析：默登公司的聯(lián)網(wǎng)問題ABCEGFD225131圖 1 光纜鋪設(shè)最小費用圖7/19/2022管理運籌學(xué)3 最短路問題問題：求網(wǎng)絡(luò)中起點到其它點之間的一條最短路線。v2v1v3v4v5v6v7v8v9163222266133101044例 求網(wǎng)絡(luò)中v1到v9的最短路7/19/2022管理運籌學(xué)算法：Dijkstra（狄克斯

11、拉）標(biāo)號法基本思想：從起點vs開始，逐步給每個結(jié)點vj標(biāo)號dj，vi，其中dj為起點vs到vj的最短距離，vi為該最短路線上的前一節(jié)點。7/19/2022管理運籌學(xué)10v2v1v3v4v5v6v7v8v916322226613310440, v11, v1(1) 給起點v1標(biāo)號0, v1(3) 考慮所有這樣的邊vi , vj，其中viVA， vjVB，挑選其中與起點v1距離最短（mindi+cij）的vj，對vj進(jìn)行標(biāo)號(4) 重復(fù)(2)、(3)，直至終點vn標(biāo)上號dn, vi，則dn即為v1 vn的最短距離，反向追蹤可求出最短路。步驟：(2) 把頂點集V分成VA：已標(biāo)號點集VB：未標(biāo)號點集7

12、/19/2022管理運籌學(xué)0, v11, v13, v1(1) 給起點v1標(biāo)號0, v1(3) 考慮所有這樣的邊vi , vj，其中viVA， vjVB，挑選其中與起點v1距離最短（mindi+cij）的vj，對vj進(jìn)行標(biāo)號(4) 重復(fù)(2)、( 3)，直至終點vn標(biāo)上號dn, vi，則dn即為v1 vn的最短距離，反向追蹤可求出最短路。步驟：(2) 把頂點集V分成VA：已標(biāo)號點集VB：未標(biāo)號點集10v2v1v3v4v5v6v7v8v916322226613310447/19/2022管理運籌學(xué)0, v11, v13, v15, v310v2v1v3v4v5v6v7v8v91632222661

13、3310447/19/2022管理運籌學(xué)0, v11, v13, v15, v36, v210v2v1v3v4v5v6v7v8v916322226613310447/19/2022管理運籌學(xué)0, v11, v13, v15, v36, v29, v510v2v1v3v4v5v6v7v8v916322226613310447/19/2022管理運籌學(xué)0, v11, v13, v15, v36, v29, v510, v510v2v1v3v4v5v6v7v8v916322226613310447/19/2022管理運籌學(xué)0, v11, v13, v15, v36, v29, v510, v512,

14、 v5此時終點v9已標(biāo)號12, v5，則12即為v1 vn的最短距離，反向追蹤可求出最短路10v2v1v3v4v5v6v7v8v916322226613310447/19/2022管理運籌學(xué)0, v11, v13, v15, v36, v29, v510, v512, v5v1到v9的最短路為：v1 v3 v2 v5 v9，最短距離為1210v2v1v3v4v5v6v7v8v916322226613310447/19/2022管理運籌學(xué)課堂練習(xí) P129 習(xí)題5.30, v14, v13, v15, v26, v29, v77, v4/ v68.5, v66, v2v2v1v5v4v3v6v8

15、v7v943232.5335234217/19/2022管理運籌學(xué)課堂練習(xí) 無向圖情形求網(wǎng)絡(luò)中v1至v7的最短路。v1v2v3v4v5v6v72253557157137/19/2022管理運籌學(xué)課堂練習(xí) 無向圖情形答案（1）：v1v2v3v4v5v6v72253557157130,v12,v13,v14,v2/ v47,v38,v513,v67/19/2022管理運籌學(xué)課堂練習(xí) 無向圖情形答案（2）：v1v2v3v4v5v6v72253557157130,v12,v13,v14,v2/ v47,v38,v513,v67/19/2022管理運籌學(xué)最短路模型的應(yīng)用設(shè)備更新問題（P119 例 5.3

16、）v2v1v3v4v5v6第i年12345價格ai1111121213使用壽命0112233445費用bj56811180,v116,v122,v130,v141,v153,v3/v416分析：結(jié)點：V=v1，v6， vi表示第i年初；邊： E=(vi，vj) 表示第i年初購買，用至第j年初；i= 1,5; j= 2,6權(quán)cij： i年初 j年初的費用，即cij= i年初購買費+（j-i）年里的維修費30224159162230411723311723187/19/2022管理運籌學(xué)4 網(wǎng)絡(luò)最大流問題引例：下圖為V1到V6的一交通網(wǎng)，權(quán)表示相應(yīng)運輸線的最大通過能力，制定一方案，使從V1到V6的

17、產(chǎn)品數(shù)量最多。v2v1v3v4v5v6810417553116353122133627/19/2022管理運籌學(xué)設(shè)有網(wǎng)絡(luò)D=(V, A, C)，其中C=cij， cij為弧(vi,vj)上的容量，現(xiàn)在D上要通過一個流f=fij， fij為弧(vi,vj)上的流量。 問題：如何安排fij，可使網(wǎng)絡(luò)D上的總流量V最大？v2v1v3v4v5v681041755311635312213362一、一般提法：7/19/2022管理運籌學(xué)二、最大流問題的模型max v=v（f） 容量約束平衡約束s.t.v2Vsv3v4v5Vt81041755311635312213362注：滿足約束條件的流f稱為可行流7/

18、19/2022管理運籌學(xué)三、基本概念與定理1. 弧按流量分為飽和弧 fij=cij非飽和弧 fijp，則正常工期即為T*； 否則，在關(guān)鍵工序上壓縮。先壓縮q最小的，直至不能再壓為止，再壓次小的，以此類推。直至qp為止。（注：當(dāng)壓縮引起出現(xiàn)新的關(guān)鍵路線時，若壓要同時壓。） 壓縮時間t的確定：若t取值 ，則產(chǎn)生了新的關(guān)鍵路線7/19/2022管理運籌學(xué)例：設(shè)某工程有關(guān)資料如表，間接費用率p=5； 求最低費用工期。工序緊前工序工序時間直接費用率可壓天數(shù)A/3/BA731CA443DC562解：畫出網(wǎng)絡(luò)圖，T=12，關(guān)鍵路線：A-C-D。1234A(3)B(7)C(4)D(5) 先壓C，在C上可壓縮可節(jié)省費用：2天，（5-4)2=2 此時出現(xiàn)兩條關(guān)鍵路線， T*=101234A(3)B(7)C(2)D(5)直接費用之和3+45，故不能再壓。此時需B、C同時壓，但其7/19/2022管理運籌學(xué)（3）求規(guī)定工期下的最小成本方案方法： 求出正常工期和關(guān)鍵工序 在關(guān)鍵工序上壓，先壓縮其中直接費用率最低的，當(dāng)出現(xiàn)多于一條的關(guān)鍵路線時要同時壓，直至滿足規(guī)定為止。（間接費用率是確定的，與工序無關(guān)，只需考慮直接費用）7/19/2022管理運籌學(xué)例、某建筑公司安裝水管的工程有關(guān)資料：工作緊前工作正常情況應(yīng)急情況時間（天）費用（元）時間（天）費用（元）a/11.7240/ba3.