天津大學(xué)管理運(yùn)籌學(xué)課件第二章-圖論【VIP專享】

1、2022-3-16管理運(yùn)籌學(xué) 圖的基本概念圖的基本概念 網(wǎng)絡(luò)分析網(wǎng)絡(luò)分析最小支撐樹問題最小支撐樹問題 最短路徑問題最短路徑問題網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)計(jì)劃問題網(wǎng)絡(luò)計(jì)劃問題2022-3-16管理運(yùn)籌學(xué)ABCDACBD圖論起源圖論起源哥尼斯堡七橋問題哥尼斯堡七橋問題結(jié)論：結(jié)論：每個(gè)結(jié)點(diǎn)關(guān)聯(lián)的邊數(shù)均為偶數(shù)。每個(gè)結(jié)點(diǎn)關(guān)聯(lián)的邊數(shù)均為偶數(shù)。問題：問題：一個(gè)散步者能否從任一塊陸地出發(fā)，走過七一個(gè)散步者能否從任一塊陸地出發(fā)，走過七座橋，且每座橋只走過一次，最后回到出發(fā)點(diǎn)？座橋，且每座橋只走過一次，最后回到出發(fā)點(diǎn)？2022-3-16管理運(yùn)籌學(xué)1 圖的基本概念圖的基本概念由點(diǎn)和邊組成，記作由點(diǎn)和邊組成，記

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20、 v11, v13, v15, v36, v210v2v1v3v4v5v6v7v8v916322226613310442022-3-16管理運(yùn)籌學(xué)0, v11, v13, v15, v36, v29, v510v2v1v3v4v5v6v7v8v916322226613310442022-3-16管理運(yùn)籌學(xué)0, v11, v13, v15, v36, v29, v510, v510v2v1v3v4v5v6v7v8v916322226613310442022-3-16管理運(yùn)籌學(xué)0, v11, v13, v15, v36, v29, v510, v512, v5此時(shí)終點(diǎn)此時(shí)終點(diǎn)v9已標(biāo)號已標(biāo)號12,

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

22、, v66, v2v2v1v5v4v3v6v8v7v943232.5335234212022-3-16管理運(yùn)籌學(xué)課堂練習(xí)課堂練習(xí) 無向圖情形無向圖情形求網(wǎng)絡(luò)中求網(wǎng)絡(luò)中v1至至v7的最短路。的最短路。v1v2v3v4v5v6v72253557157132022-3-16管理運(yùn)籌學(xué)課堂練習(xí)課堂練習(xí) 無向圖情形無向圖情形答案（答案（1）：）：v1v2v3v4v5v6v72253557157130,v12,v13,v14,v2/ v47,v38,v513,v62022-3-16管理運(yùn)籌學(xué)課堂練習(xí)課堂練習(xí) 無向圖情形無向圖情形答案（答案（2）：）：v1v2v3v4v5v6v72253557157130,

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

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

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

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

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