1、2022-3-16管理運籌學 圖的基本概念圖的基本概念 網絡分析網絡分析最小支撐樹問題最小支撐樹問題 最短路徑問題最短路徑問題網絡最大流問題網絡最大流問題網絡計劃問題網絡計劃問題2022-3-16管理運籌學ABCDACBD圖論起源圖論起源哥尼斯堡七橋問題哥尼斯堡七橋問題結論：結論：每個結點關聯的邊數均為偶數。每個結點關聯的邊數均為偶數。問題：問題：一個散步者能否從任一塊陸地出發，走過七一個散步者能否從任一塊陸地出發，走過七座橋，且每座橋只走過一次，最后回到出發點？座橋，且每座橋只走過一次，最后回到出發點？2022-3-16管理運籌學1 圖的基本概念圖的基本概念由點和邊組成，記作由點和邊組成，記

2、作G=(V，E)，其中，其中V=v1，v2，vn為結點的集合，為結點的集合，E=e1，e2，em 為邊的集合。為邊的集合。點表示研究對象點表示研究對象邊表示表示研究對象之間的特定關系邊表示表示研究對象之間的特定關系1. 圖圖2022-3-16管理運籌學圖圖無向圖，記作無向圖，記作G=(V，E)有向圖，記作有向圖，記作D=(V，A)例例1：哥尼斯堡橋問題的圖為一個無向圖。：哥尼斯堡橋問題的圖為一個無向圖。有向圖的邊有向圖的邊稱為稱為弧弧。例例2：五個球隊的比賽情況，：五個球隊的比賽情況，v1v2表示表示v1勝勝v2。v1v2v3v4v52、圖的分類、圖的分類2022-3-16管理運籌學v1v2v

3、3v4v53、鏈與路、圈與回路、鏈與路、圈與回路鏈鏈點邊交錯的序列點邊交錯的序列圈圈起點起點=終點的鏈終點的鏈路路點弧交錯的序列點弧交錯的序列回路回路起點起點=終點的路終點的路v1v2v3v4v5無向圖：無向圖：有向圖：有向圖：2022-3-16管理運籌學4、連通圖、連通圖任何兩點之間至少存在一條鏈的圖稱為連通圖，任何兩點之間至少存在一條鏈的圖稱為連通圖，否則稱為不連通圖。否則稱為不連通圖。G1G2G1為不連通圖，為不連通圖， G2為連通圖為連通圖例例 ：2022-3-16管理運籌學5、支撐子圖、支撐子圖圖圖G=(V，E)和和G=(V ，E )，若，若V =V 且且E E ，則稱，則稱G 為為

4、G的的支撐子圖支撐子圖。G2為為G1的支撐子圖的支撐子圖v1v2v3v4v5G1v1v2v3v4v5G2例例 ：2022-3-16管理運籌學6、賦權圖（網絡）、賦權圖（網絡）圖的每條邊都有一個表示一定實際含義的圖的每條邊都有一個表示一定實際含義的權數，稱為權數，稱為賦權圖賦權圖。記作。記作D=(V，A，C)。55.5v1v2v3v4v53.57.5423例例 ：2022-3-16管理運籌學2 最小支撐樹問題最小支撐樹問題本節主要內容：本節主要內容：樹樹支撐樹支撐樹最小支撐樹最小支撐樹 例例今有煤氣站今有煤氣站A，將給一居民區供應煤氣，居民區各，將給一居民區供應煤氣，居民區各用戶所在位置如圖所示

5、，鋪設各用戶點的煤氣管道所需用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。一個最經濟的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS22222254526345312022-3-16管理運籌學1、樹中任兩點中有且僅有一條鏈；、樹中任兩點中有且僅有一條鏈；2、樹任刪去一邊則不連通，故樹是使圖保持連通且具有最少邊、樹任刪去一邊則不連通，故樹是使圖保持連通且具有最少邊數的一種圖形。數的一種圖形。3、邊數、邊數 = 頂點數頂點數 1。樹樹無圈連通

6、圖無圈連通圖(A)(B)(C)樹的性質：樹的性質：例例 判斷下面圖形哪個是樹：判斷下面圖形哪個是樹：一、樹的概念與性質一、樹的概念與性質2022-3-16管理運籌學 若一個圖若一個圖 G =（V , E）的支撐子圖）的支撐子圖 T=（V , E ） 構成樹，則稱構成樹，則稱 T 為為G的支撐樹的支撐樹，又稱，又稱生成樹生成樹、部分樹部分樹。二、二、圖的支撐樹圖的支撐樹(G)(G1)(G2)(G3)(G4)例例2022-3-16管理運籌學例例 某地新建某地新建5處居民點，擬修處居民點，擬修道路連接道路連接5處，經勘測其道路可鋪處，經勘測其道路可鋪成如圖所示。為使成如圖所示。為使5處居民點都有處居

7、民點都有道路相連，問至少要鋪幾條路？道路相連，問至少要鋪幾條路？解：解：該問題實為求圖該問題實為求圖的支撐樹問題，的支撐樹問題，共需鋪共需鋪4條路。條路。v1v2v3v4v5 圖的支撐樹的應用舉例圖的支撐樹的應用舉例v1v2v3v4v555.57.53.54232022-3-16管理運籌學問題：問題：求網絡的支撐樹，使其權和最小。求網絡的支撐樹，使其權和最小。三、最小支撐樹問題三、最小支撐樹問題55.5v1v2v3v4v57.53.5423算法算法1（避圈法）：（避圈法）：把邊按權從小到大依次把邊按權從小到大依次添入圖中，若出現圈，則刪去其中最大邊，添入圖中，若出現圈，則刪去其中最大邊，直至填

8、滿直至填滿n-1條邊為止（條邊為止（n為結點數）為結點數） 。例例 求上例中的最小支撐樹求上例中的最小支撐樹解：解：3v12v4v545v23.5v32022-3-16管理運籌學算法算法2（破圈法）：（破圈法）： 在圖中找圈，并刪除其中最大邊。如此進行下去，直在圖中找圈，并刪除其中最大邊。如此進行下去，直至圖中不存在圈。至圖中不存在圈。55.5v1v2v3v4v57.53.54232022-3-16管理運籌學算法算法2（破圈法）：（破圈法）： 在圖中找圈，并刪除其中最大邊。如此進行下去，直在圖中找圈，并刪除其中最大邊。如此進行下去，直至圖中不存在圈。至圖中不存在圈。55.5v1v2v3v4v5

9、3.54232022-3-16管理運籌學算法算法2（破圈法）：（破圈法）： 在圖中找圈，并刪除其中最大邊。如此進行下去，直在圖中找圈，并刪除其中最大邊。如此進行下去，直至圖中不存在圈。至圖中不存在圈。5v1v2v3v4v53.54232022-3-16管理運籌學算法算法2（破圈法）：（破圈法）： 在圖中找圈，并刪除其中最大邊。如此進行下去，直在圖中找圈，并刪除其中最大邊。如此進行下去，直至圖中不存在圈。至圖中不存在圈。5v1v2v3v4v53.5232022-3-16管理運籌學 例例今有煤氣站今有煤氣站A，將給一居民區供應煤氣，居民區各，將給一居民區供應煤氣，居民區各用戶所在位置如圖所示，鋪設

10、各用戶點的煤氣管道所需用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。一個最經濟的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS22222254526345312022-3-16管理運籌學 例例今有煤氣站今有煤氣站A，將給一居民區供應煤氣，居民區各，將給一居民區供應煤氣，居民區各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計的費用（單位：萬元）

11、如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。一個最經濟的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS2222224526345312022-3-16管理運籌學 例例今有煤氣站今有煤氣站A，將給一居民區供應煤氣，居民區各，將給一居民區供應煤氣，居民區各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。一個最經濟的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHI

12、JKS222222526345312022-3-16管理運籌學 例例今有煤氣站今有煤氣站A，將給一居民區供應煤氣，居民區各，將給一居民區供應煤氣，居民區各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。一個最經濟的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS22222226345312022-3-16管理運籌學 例例今有煤氣站今有煤氣站A，將給一居民區供應煤氣，居民區各，將給一居民區供應煤氣

13、，居民區各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。一個最經濟的煤氣管道路線，并求所需的總費用。ABCDEFGHIJKS22222226345312022-3-16管理運籌學 例例今有煤氣站今有煤氣站A，將給一居民區供應煤氣，居民區各，將給一居民區供應煤氣，居民區各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求

14、設計的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。一個最經濟的煤氣管道路線，并求所需的總費用。IABCDEFGHJKS2222222345312022-3-16管理運籌學 例例今有煤氣站今有煤氣站A，將給一居民區供應煤氣，居民區各，將給一居民區供應煤氣，居民區各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。一個最經濟的煤氣管道路線，并求所需的總費用。IJABCD

15、EFGHKS22222223431此即為最經濟的煤氣管道路線，所需的總費用為此即為最經濟的煤氣管道路線，所需的總費用為25萬元萬元2022-3-16管理運籌學案例分析：案例分析：默登公司的聯網問題默登公司的聯網問題 默登（默登（ModernModern）公司的管理層決定鋪設最先進）公司的管理層決定鋪設最先進的光纖網絡，為它的主要中心之間提供高速通信。圖的光纖網絡，為它的主要中心之間提供高速通信。圖1 1中的節點顯示了該公司主要中心的分布圖。虛線是中的節點顯示了該公司主要中心的分布圖。虛線是鋪設光纜可能的位置。每條虛線旁邊的數字表示成本鋪設光纜可能的位置。每條虛線旁邊的數字表示成本（單位：百萬美

16、元）。（單位：百萬美元）。 問：問：需要鋪設哪些光纜使得總成本最低？需要鋪設哪些光纜使得總成本最低？ A AB BC CE EG GF FD D2 25 52 27 74 45 57 71 13 31 14 44 4圖圖1 1 光纜鋪設費用圖光纜鋪設費用圖2022-3-16管理運籌學案例分析：案例分析：默登公司的聯網問題默登公司的聯網問題ABCEGFD225131圖圖 1 光纜鋪設最小費用圖光纜鋪設最小費用圖2022-3-16管理運籌學問題：問題：求網絡中起點到其它點之間的一求網絡中起點到其它點之間的一條最短路線。條最短路線。v2v1v3v4v5v6v7v8v91632222661331010

17、44例例 求網絡中求網絡中v1到到v9的最短路的最短路2022-3-16管理運籌學算法：算法：Dijkstra（狄克斯拉）標號法（狄克斯拉）標號法基本思想：基本思想：從起點從起點vs開始，逐步給每個結開始，逐步給每個結點點vj標號標號dj，vi，其中，其中dj為起點為起點vs到到vj的的最短距離，最短距離，vi為該最短路線上的前一節點。為該最短路線上的前一節點。10v2v1v3v4v5v6v7v8v916322226613310440, v11, v1(1) 給起點給起點v1標號標號0, v1(3) 考慮所有這樣的邊考慮所有這樣的邊vi , vj，其中，其中viVA， vjVB，挑選，挑選其中

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

19、離最短（距離最短（mindi+cij）的）的vj，對，對vj進行標號進行標號(4) 重復重復(2)、( 3)，直至終點，直至終點vn標上號標上號dn, vi，則，則dn即為即為v1 vn的最短距離，反向追蹤可求出最短路。的最短距離，反向追蹤可求出最短路。步驟：步驟：(2) 把頂點集把頂點集V分成分成VA：已標號點集：已標號點集VB：未標號點集：未標號點集10v2v1v3v4v5v6v7v8v916322226613310442022-3-16管理運籌學0, v11, v13, v15, v310v2v1v3v4v5v6v7v8v916322226613310442022-3-16管理運籌學0,

20、 v11, v13, v15, v36, v210v2v1v3v4v5v6v7v8v916322226613310442022-3-16管理運籌學0, v11, v13, v15, v36, v29, v510v2v1v3v4v5v6v7v8v916322226613310442022-3-16管理運籌學0, v11, v13, v15, v36, v29, v510, v510v2v1v3v4v5v6v7v8v916322226613310442022-3-16管理運籌學0, v11, v13, v15, v36, v29, v510, v512, v5此時終點此時終點v9已標號已標號12,

21、 v5，則，則12即為即為v1 vn的最的最短距離，反向追蹤可求出最短路短距離，反向追蹤可求出最短路10v2v1v3v4v5v6v7v8v916322226613310442022-3-16管理運籌學0, v11, v13, v15, v36, v29, v510, v512, v5v1到到v9的最短路為：的最短路為：v1 v3 v2 v5 v9，最短距離為最短距離為1210v2v1v3v4v5v6v7v8v916322226613310442022-3-16管理運籌學課堂練習課堂練習 P129 習題習題5.30, v14, v13, v15, v26, v29, v77, v4/ v68.5

22、, v66, v2v2v1v5v4v3v6v8v7v943232.5335234212022-3-16管理運籌學課堂練習課堂練習 無向圖情形無向圖情形求網絡中求網絡中v1至至v7的最短路。的最短路。v1v2v3v4v5v6v72253557157132022-3-16管理運籌學課堂練習課堂練習 無向圖情形無向圖情形答案（答案（1）：）：v1v2v3v4v5v6v72253557157130,v12,v13,v14,v2/ v47,v38,v513,v62022-3-16管理運籌學課堂練習課堂練習 無向圖情形無向圖情形答案（答案（2）：）：v1v2v3v4v5v6v72253557157130,

23、v12,v13,v14,v2/ v47,v38,v513,v6最短路模型的應用最短路模型的應用設備更新問題設備更新問題（P119 例例 5.3）v2v1v3v4v5v6第第i年年12345價格價格ai11 11121213使用壽命使用壽命 01 1223 34 45費用費用bj56811180,v116,v122,v130,v141,v153,v3/v416分析分析：結點結點：V=v1，v6， vi表示第表示第i年初；年初；邊邊： E=(vi，vj) 表示第表示第i年初購買，用至第年初購買，用至第j年初；年初；i= 1,5; j= 2,6權權cij： i年初年初 j年初的費用，即年初的費用，即

24、cij= i年初購買費年初購買費+（j-i）年里的維修費）年里的維修費30224159162230411723311723182022-3-16管理運籌學引例：下圖為引例：下圖為V1到到V6的一交通網，權表示相應運輸線的最的一交通網，權表示相應運輸線的最大通過能力，制定一方案，使從大通過能力，制定一方案，使從V1到到V6的產品數量最多。的產品數量最多。v2v1v3v4v5v6810417553116353122133622022-3-16管理運籌學設有網絡設有網絡D=(V, A, C)，其中，其中C=cij， cij為弧為弧(vi,vj)上的容量，現在上的容量，現在D上要通過一個流上要通過一個

25、流f=fij， fij為弧為弧(vi,vj)上的流量。上的流量。 問題：問題：如何安排如何安排fij，可使網絡，可使網絡D上的總流量上的總流量V最大？最大？v2v1v3v4v5v681041755311635312213362一、一般提法：一、一般提法：2022-3-16管理運籌學max v=v（f） ijijcf 0 tsitifvsifvffjjjiij,0)()(容量約束容量約束平衡約束平衡約束s.t.v2Vsv3v4v5Vt81041755311635312213362注：滿足約束條件的流注：滿足約束條件的流f稱為可行流稱為可行流2022-3-16管理運籌學飽和弧飽和弧 fij=cij

26、非飽和弧非飽和弧 fijp，則正常工期即為，則正常工期即為T*；v 否則，在關鍵工序上壓縮。先壓縮否則，在關鍵工序上壓縮。先壓縮q最小的，直至不最小的，直至不能再壓為止，再壓次小的，以此類推。直至能再壓為止，再壓次小的，以此類推。直至qp為止。為止。（注：注：當壓縮引起出現新的關鍵路線時，若壓要同時壓。）當壓縮引起出現新的關鍵路線時，若壓要同時壓。）v 壓縮時間壓縮時間t的確定：的確定：0),(),(min),(),(min,min),( jiRjiRjitjittIji ，其其中中：的的壓壓縮縮下下限限為為工工序序),(),(jijit若若t取值取值 ，則產生了，則產生了新的關鍵路線新的關鍵

27、路線2022-3-16管理運籌學例例：設某工程有關資料如表，間接費用率：設某工程有關資料如表，間接費用率p=5； 求最低費用工期。求最低費用工期。工序工序緊前緊前工序工序工序工序時間時間直接直接費用率費用率可壓可壓天數天數A/3/BA731CA443DC562解解：畫出網絡圖，：畫出網絡圖， T=12，關鍵路線：，關鍵路線：A-C-D。1234A(3)B(7)C(4)D(5) 先壓先壓C，在，在C上可壓縮上可壓縮可節省費用：可節省費用：2天，天，（5-4)2=2 此時出現兩條關鍵路線，此時出現兩條關鍵路線， T*=101234A(3)B(7)C(2)D(5)直接費用之和直接費用之和3+45，故不能再壓。，故不能再壓。此時需此時需B、C同時壓，但其同時壓，但其2022-3-16管理運籌學（3）求規定工期下的最小成本方案）求規定工期下的最小成本方案方法：方法： 求出正常工期和關鍵工序求出正常工期和關鍵工序 在關鍵工序上壓，先壓縮其中直接費用率最低的，在關鍵工序上壓，先壓縮其中直接費用率最低的，當出現多于一條的關鍵路線時要同時壓，直至滿足當出現多于一條的關鍵路線時要同時壓，直至滿足規定為止。規定為止。（間接費用率是確定的，與工序無關，只需考慮直接費用）（間接費用率是確定的，與工序無關，只需考慮直接費用）2022-3-