第2章 圖與網(wǎng)絡(luò)分析補充

1、第二章 圖論(t ln)與網(wǎng)絡(luò)分析補充 補充(bchng)內(nèi)容圖的基本概念應(yīng)用舉例最小支撐樹問題舉例運輸問題補充最短路徑問題舉例網(wǎng)絡(luò)最大流問題舉例網(wǎng)絡(luò)計劃補充例共六十九頁圖的基本概念應(yīng)用(yngyng)舉例共六十九頁共六十九頁最小支撐(zh chng)樹問題舉例 例今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS2222225452634531共六十九頁算法2（破圈法）： 在圖中找圈，并刪除其中(qzhng)最大邊。如此進行下去，

2、直至圖中不存在圈。55.5v1v2v3v4v53.57.5423共六十九頁 例今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字(shz)所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS2222225452634531共六十九頁 例今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字(shz)所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS22222245263453

3、1共六十九頁 例今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求(yoqi)設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS22222252634531共六十九頁 例今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上(bin shn)的數(shù)字所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS2222222634531共六十九頁 例今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各

4、用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求(yoqi)設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。ABCDEFGHIJKS2222222634531共六十九頁 例今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)(p sh)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。IABCDEFGHJKS222222234531共六十九頁 例今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用(fi yong)（單位：萬

5、元）如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用(fi yong)。IJABCDEFGHKS22222223431此即為最經(jīng)濟(jngj)的煤氣管道路線，所需的總費用為25萬元共六十九頁運輸問題補充：產(chǎn)銷(chnxio)不平衡問題1. 產(chǎn)大于銷 （ ） 模型(mxng)：增加松弛變量運輸表：B1BnBn+1A1x11x1nx1,n+1a1Amxm1xmnxm,n+1amb1bnbn+1實際意義：虛設(shè)一 個銷地運價為零共六十九頁2. 產(chǎn)小于銷 （ ） 模型：增加松弛變量運輸(ynsh)表：實際意義：虛設(shè)(xsh)一 個銷地B1BnA1x11x1na1Amxm1xmnam

6、Am+1xm+1，1xm+1,nam+1b1bn共六十九頁 運輸問題應(yīng)用舉例（生產(chǎn)與儲存問題） 例、某廠按合同規(guī)定須于當年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如右表。如果生產(chǎn)出來的柴油機當季不交貨，每臺每積壓(jy)一個季度需儲存、維護等費用0.15萬元。 試求在完成合同的情況下，使該廠全年生產(chǎn)總費用為最小的決策方案。生產(chǎn)能力單位成本（萬元）一季度2510.8二季度3511.1三季度3011.0四季度1011.3共六十九頁 應(yīng)用舉例（生產(chǎn)與儲存問題） 例、某廠按合同規(guī)定須于當年每個季度末分別提供10、15、25、20臺同一規(guī)

7、格的柴油機。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如右表。如果生產(chǎn)出來的柴油機當季不交貨，每臺每積壓一個季度需儲存、維護等費用0.15元。 試求在完成合同的情況下，使該廠全年生產(chǎn)總費用為最小的決策方案。產(chǎn)地銷地第一季度第二季度第三季度第四季度第一季度第二季度第三季度第四季度產(chǎn)量(chnling)銷量(xio lin)253530101015252010.9510.811.1011.2511.111.2511.4011.0011.1511.30MMMMMM分析：本問題可轉(zhuǎn)化為一運輸問題共六十九頁最短路問題舉例無向(w xin)圖情形求網(wǎng)絡(luò)(wnglu)中v1至v7的最短路。v1v2v3v

8、4v5v6v7225355715713共六十九頁課堂練習(xí) 無向(w xin)圖情形答案(d n)（1）：v1v2v3v4v5v6v72253557157130,v12,v13,v14,v2/ v47,v38,v513,v6共六十九頁課堂練習(xí) 無向(w xin)圖情形答案(d n)（2）：v1v2v3v4v5v6v72253557157130,v12,v13,v14,v2/ v47,v38,v513,v6共六十九頁最短路模型的應(yīng)用(yngyng)設(shè)備更新問題（P119 例 5.3）v2v1v3v4v5v6第i年12345價格ai1111121213使用壽命0112233445費用bj568111

9、80,v116,v122,v130,v141,v153,v3/v416分析(fnx)：結(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）年里的維修費3022415916223041172331172318共六十九頁v2v1v3v4v5v60,v116,v122,v130,v141,v153,v3/v4163022415916223041172331172318共六十九頁截集概念(ginin)復(fù)習(xí)例. 如圖所示的網(wǎng)絡(luò)中，弧旁數(shù)字為(cij ,fij)

10、v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）確定所有的截集；（2）求最小截集的容量(rngling)；（3）證明圖中的流為最大流；最大流問題舉例共六十九頁v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有(suyu)的截集： V1=vs，截集為(vs,v1), (vs,v2)，截量為：6共六十九頁v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有(suyu)的截集： V1=vs，截集為(vs,v1), (vs,v2)，截量為：6V1=vs ,v

11、1，截集為(vs,v2), (v1,vt)，截量為：7共六十九頁v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有(suyu)的截集： V1=vs，截集為(vs,v1), (vs,v2)，截量為：6V1=vs ,v1，截集為(vs,v2), (v1,vt)，截量為：7V1=vs ,v2，截集為，截量為：7共六十九頁v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有(suyu)的截集： V1=vs，截集為(vs,v1), (vs,v2)，截量為：6V1=vs ,v1，截集為(vs,v2), (v1

12、,vt)，截量為：7V1=vs ,v2，截集為，截量為：7V1=vs ,v3，截集為，截量為：12共六十九頁v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有(suyu)的截集： V1=vs，截集為(vs,v1), (vs,v2)，截量為：6V1=vs ,v1，截集為(vs,v2), (v1,vt)，截量為：7V1=vs ,v2，截集為，截量為：7V1=vs ,v3，截集為，截量為：12V1=vs ,v1,v2，截集為，截量為：5共六十九頁v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有(su

13、yu)的截集： V1=vs，截集為(vs,v1), (vs,v2)，截量為：6V1=vs ,v1，截集為(vs,v2), (v1,vt)，截量為：7V1=vs ,v2，截集為，截量為：7V1=vs ,v3，截集為，截量為：12V1=vs ,v1,v2，截集為，截量為：5共六十九頁v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（2）最小截量min C (V1,V2)= 5；（3）v(f*)=5= min C (V1,V2) f*是最大流。共六十九頁例 有三個發(fā)電站v1,v2,v3，發(fā)電能力分別(fnbi)為15、10和40兆瓦，經(jīng)輸電網(wǎng)可把電力送到8號

14、地區(qū)，電網(wǎng)能力如圖所示。求三個發(fā)電站輸?shù)皆摰貐^(qū)的最大電力。v2v1v3v4v5v6v7v8401530154510151020v01015401020151515 10201020201535共六十九頁例、圖中A、B、C、D、E、F分別表示陸地和島嶼，表示橋梁及其編號(bin ho)。河兩岸分別互為敵對的雙方部隊占領(lǐng)，問至少應(yīng)切斷幾座橋梁（具體指出編號(bin ho)）才能達到阻止對方部隊過河的目的。試用圖論方法進行分析。ABDEFC共六十九頁分析：轉(zhuǎn)化為一個(y )網(wǎng)絡(luò)圖，弧的容量為兩點間的橋梁數(shù)。則問題(wnt)為求最小截。ABDEFCABCDEF211111222222共六十九頁分析：轉(zhuǎn)

15、化為一個(y )網(wǎng)絡(luò)圖，弧的容量為兩點間的橋梁數(shù)。則問題(wnt)為求最小截。答案：最小截為AE、CD、CFABDEFCABCDEF211111222222共六十九頁例、有一批人從我國A城赴俄羅斯B城，可能的旅行(lxng)路線如圖： 邊防隊擬建立(jinl)足夠數(shù)量檢查站以便使每輛汽車至少必經(jīng)過一個檢查站，建立(jinl)檢查站的費用根據(jù)各路段條件有所不同（如圖數(shù)字所示），求最小費用解。aBAbcdefg468232573843764（分析：最小截問題）共六十九頁例、過紐約ALBANY的北-南高速公路，路況通過能力如下圖所示，圖中弧上數(shù)字單位(dnwi)：千輛/小時。求（1）該路網(wǎng)能承受的北

16、-南向最大流量；（2）若要擴充通過能力，應(yīng)在那一組路段上擴充，說明原因。2143562366241331進入Albany（北）離開Albany（南）共六十九頁案例：垃圾處理問題 某地區(qū)有3個城鎮(zhèn)，各城鎮(zhèn)每天產(chǎn)生(chnshng)的垃圾要運往該地區(qū)的4個垃圾處理場處理，現(xiàn)考慮各城鎮(zhèn)到各處理場的道路對各城鎮(zhèn)垃圾外運的影響。假設(shè)各城鎮(zhèn)每日產(chǎn)生(chnshng)的垃圾量、各處理場的日處理能力及各條道路（可供運垃圾部分）的容量（其中容量為0表示無此直接道路）如右表所示，試用網(wǎng)絡(luò)流方法分析目前的道路狀況能否使所有垃圾都運到處理場得到處理，如果不能，應(yīng)首先拓寬哪條道路。處理場城鎮(zhèn)1234垃圾量1302010

17、05020020407035040205080處理量60409030共六十九頁共六十九頁共六十九頁共六十九頁共六十九頁共六十九頁參考答案：本題可化為最大流問題，先構(gòu)造如下網(wǎng)絡(luò)圖，圖中si表示(biosh)第i天可提供3車的“源”。 現(xiàn)該公司接到在今后(jnhu)4天內(nèi)為A、B、C三個項目運送T的任務(wù)，三個項目對T的需求量分別為3、4、5車。受交通限制，第1天去B的道路不通行；第2天去A的道路不通行；第3天去C的道路不通行；另每天至多有2臺車為一個項目運送T。 共六十九頁用觀察法得到可行流，進一步用標號(bioho)法得到最大流，可滿足三個項目的需求，即能完成任務(wù)。運輸方案見圖中各弧上的流量（不

18、帶括弧的數(shù)字）。本題有多個最優(yōu)解，下圖只是其一。 共六十九頁網(wǎng)絡(luò)(wnglu)計劃補充例共六十九頁共六十九頁(1) 繪制(huzh)的網(wǎng)絡(luò)圖如下：共六十九頁共六十九頁另一補充(bchng)例共六十九頁共六十九頁共六十九頁共六十九頁共六十九頁共六十九頁共六十九頁補充(bchng)練習(xí)共六十九頁共六十九頁共六十九頁共六十九頁共六十九頁補充(bchng)練習(xí)共六十九頁共六十九頁共六十九頁(1) 共六十九頁(2)方案2網(wǎng)絡(luò)計劃圖（圖中結(jié)點(ji din)時間只供閱卷參考），關(guān)鍵線路B-E-A-D-H，計算工期43天。共六十九頁(3)將比原計劃(jhu)拖后1天；(4)工作D趕工(n n)（縮短）1天，工作F趕工(n n)（縮短）1天。共六十九頁共六十九頁共六十九頁共六十九頁內(nèi)容摘要第二章 圖論與網(wǎng)絡(luò)分析補充。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求