運籌學-6(圖與網(wǎng)絡分析)

1、運籌學基礎教程運籌學基礎教程6黃桐城黃桐城 主編主編 趙弘志趙弘志 改編改編 主講主講 第六章第六章 圖與網(wǎng)絡分析圖與網(wǎng)絡分析l主要內容主要內容我們的教材我們的教材p-116 圖論的基本概念圖論的基本概念 最短路問題最短路問題 不重要內容不重要內容 最大流問題最大流問題 不重要內容不重要內容 網(wǎng)絡計劃網(wǎng)絡計劃6.1 6.1 圖論的基本概念圖論的基本概念 .1 引論引論 哥尼斯堡七橋問題哥尼斯堡七橋問題ABD CABCD簡捷表示事物之間的簡捷表示事物之間的本質聯(lián)系，歸納事物本質聯(lián)系，歸納事物之間的一般規(guī)律之間的一般規(guī)律引論引論 圖的用處圖的用處l A、B、C、D、E 某公司的某公

2、司的五支球隊進行循環(huán)賽五支球隊進行循環(huán)賽 組織機構設置圖組織機構設置圖ABCDE總公司總公司分公司分公司工廠或工廠或辦事處辦事處6.1.2 6.1.2 圖的基本概念圖的基本概念l 圖 是 由圖 是 由 點點 和和 線線 構 成 的 。構 成 的 。l 點 的 集 合點 的 集 合 V 表 示 ，表 示 ， V = v i l 不 帶 箭 頭 的 連 線 叫 做不 帶 箭 頭 的 連 線 叫 做 邊邊 ( e d g e ) ， 邊， 邊的 集 合 記 為的 集 合 記 為 E = e j ， 一 條 邊 可 以， 一 條 邊 可 以用 兩 點用 兩 點 v i , v j 表 示表 示 , e

3、 j = v i , v j .l 帶 箭 頭 的 連 線 叫 做帶 箭 頭 的 連 線 叫 做 弧弧 ( a r c ) , 弧 的 集 合弧 的 集 合記 為記 為 A ， A = a k , 一 條 弧 也 是 用 兩一 條 弧 也 是 用 兩點 表 示 ，點 表 示 ， a k = v i , v j , 弧 有 方 向 ：弧 有 方 向 ：v i 為 始 點 ，為 始 點 ， v j 為 終 點為 終 點圖的基本概念圖的基本概念( (續(xù)續(xù)) )l 由點和邊組成的圖叫做由點和邊組成的圖叫做無向圖無向圖，記為，記為G=（V，E）l 由點和弧組成的圖叫做由點和弧組成的圖叫做有向圖有向圖，記

4、為，記為D=（V，A）l 例例1.v1v2v3v4v1v2v3v4v5v6v7e1e2e3e4e5e6e7a1a2a8a4a3a5a6a9a7a10a11無向圖：點集、邊集無向圖：點集、邊集有向圖：點集、弧集有向圖：點集、弧集圖的基本概念圖的基本概念( (續(xù)續(xù)) )l 以點以點u u為端點的邊的條數(shù)，叫做點為端點的邊的條數(shù)，叫做點u u的的次次l 次為次為1 1的點叫做的點叫做懸掛點懸掛點；次為；次為0 0的點叫做的點叫做孤立點孤立點；次為奇數(shù)則稱次為奇數(shù)則稱奇奇點；次為偶數(shù)則稱點；次為偶數(shù)則稱偶偶點。點。l 點弧交替序列稱為點弧交替序列稱為鏈鏈；閉合的鏈稱為；閉合的鏈稱為圈圈l 首尾相接的鏈

5、稱為首尾相接的鏈稱為路路；閉合的路稱回路；閉合的路稱回路l 任意兩點之間都有邊相連，稱為任意兩點之間都有邊相連，稱為連通圖連通圖節(jié)點與（有向）邊節(jié)點與（有向）邊 每一條邊和兩個節(jié)點關聯(lián)，一條每一條邊和兩個節(jié)點關聯(lián)，一條邊可以用兩個節(jié)點的標號表示（邊可以用兩個節(jié)點的標號表示（i，j）ji路徑（路徑（Path） 前后相繼并且方向相同的邊序列前后相繼并且方向相同的邊序列 P=(1,2),(2,3),(3,4)42314231網(wǎng)絡由節(jié)點和邊組成網(wǎng)絡由節(jié)點和邊組成圖的基本概念圖的基本概念( (續(xù)續(xù)) )回路（回路（Circuit） 起點和終點重合的路徑稱為起點和終點重合的路徑稱為回路回路 =(1,2),

6、(2,4),(4,1) 回路中各條邊方向相同回路中各條邊方向相同4231鏈（鏈（Chain） 前后相繼并且方向不一定相同的邊前后相繼并且方向不一定相同的邊序列稱為序列稱為鏈鏈 C=(1,2),(3,2),(3,4)4231連通圖連通圖 任意兩個節(jié)點之間至少有一條任意兩個節(jié)點之間至少有一條鏈的圖稱為鏈的圖稱為連通圖連通圖24351圈圈(Cycle) 起點和終點重合的鏈稱為起點和終點重合的鏈稱為圈圈 =(1,2),(2,4),(3,4),(1,3) 圈中各條邊方向不一定相同圈中各條邊方向不一定相同4231樹樹(Tree) 無圈的連通圖稱為無圈的連通圖稱為樹樹 樹中只與一條邊關聯(lián)的節(jié)點稱樹中只與一條

7、邊關聯(lián)的節(jié)點稱為為懸掛節(jié)點懸掛節(jié)點圖上作業(yè)法圖上作業(yè)法l已知如圖所示：三個工廠向四個市場配已知如圖所示：三個工廠向四個市場配送，請確定最佳配送路線。送，請確定最佳配送路線。 4B223A33B157B412131A1334B34A2先去掉兩個圈內路線最長的線，得到下列流量圖先去掉兩個圈內路線最長的線，得到下列流量圖B2(1)(2)A3(1)B1（3）B41213A13(1)B34A2135432374驗證：第一圈內總長：驗證：第一圈內總長：3+4+5+4+7=233+4+5+4+7=23第一圈逆時針內配送路長：第一圈逆時針內配送路長：3+4+5=1211.53+4+5=1211.5，則不是最優(yōu)

8、方案，則不是最優(yōu)方案第二圈內配送路長：第二圈內配送路長：4+2+3+4=134+2+3+4=13第二圈逆時針內配送路長：第二圈逆時針內配送路長：26.526.5，則是最優(yōu)方案。，則是最優(yōu)方案。第二圈順時針內配送路長：第二圈順時針內配送路長：36.536.5，則是最優(yōu)方案。，則是最優(yōu)方案。 修正第一圈內方案，取逆時針方向最小值修正第一圈內方案，取逆時針方向最小值1 1，然后逆時針方向配送路線，然后逆時針方向配送路線減去減去1 1，順時針方向配送及未走路線加上，順時針方向配送及未走路線加上1 1，則得到第一圈內配送路長：，則得到第一圈內配送路長：55總長一半，則是最優(yōu)方案。如圖所示：總長一半，則是

9、最優(yōu)方案。如圖所示：驗證：驗證：第一圈順時針內配送路長：第一圈順時針內配送路長：7+4=1111.57+4=1111.5，則是最優(yōu)方案；，則是最優(yōu)方案；第一圈逆時針內配送路長：第一圈逆時針內配送路長：511.5511.5，則是最優(yōu)方案。，則是最優(yōu)方案。第二圈順時針內配送路長：第二圈順時針內配送路長：36.536.5，則是最優(yōu)方案。，則是最優(yōu)方案。第二圈逆時針內配送路長：第二圈逆時針內配送路長：4+2=66.54+2=66.5，則是最優(yōu)方案。，則是最優(yōu)方案。計算運費：計算運費：1 1* *7+27+2* *5+15+1* *4+24+2* *3+13+1* *2=292=29A2(1)(2)A3

10、B1(2)(1)B412131A133B3(1)54323474案例案例通俗思路解題通俗思路解題起點和終點不同的單一路線選擇起點和終點不同的單一路線選擇 例例1： 如圖如圖55所示，所示，A是一煤礦所在地，是一煤礦所在地，I是是煤炭需求地，煤炭需求地，B，C，D，E，F(xiàn)，G，H，I是由是由A到到J的可經過的城鎮(zhèn)。每兩節(jié)點之間的距離已經標的可經過的城鎮(zhèn)。每兩節(jié)點之間的距離已經標 出，現(xiàn)在要找出從出，現(xiàn)在要找出從A到到J之間的最短路線。這就是一之間的最短路線。這就是一個最短路問題。個最短路問題。步步驟驟已解點已解點候選點候選點相關相關成本成本第第n個個最近最近節(jié)點節(jié)點最小最小成本成本最新最新連接連

11、接A到各到各N節(jié)點節(jié)點最短最短路徑路徑1ABCD90,138,348B90AB AB2ABCDCE138,348156,174C138ACAC3ABCDEDF348174291,228E174BEABE步步驟驟已解點已解點候選點候選點相關相關成本成本第第n個個最近最近節(jié)點節(jié)點最小最小成本成本最新最新連接連接A到各到各N節(jié)點節(jié)點最短最短路徑路徑4ACEDD, FF, I348291, 228294, 258F228CFACF5ACEFDDIH, G348291258288, 360I258EIABEI6ACFIDDH, GH, J348291288, 360390, 384H288FHACFH步

12、步驟驟已解點已解點候選點候選點相關相關成本成本第第n個個最近最近節(jié)點節(jié)點最小最小成本成本最新最新連接連接A到各到各N節(jié)點節(jié)點最短最短路徑路徑7ACFIHDDGJG, J348291360384336, 414D291CDACD8FIHDGJJG360384414396J384IJABEIJ6.2 6.2 網(wǎng)絡計劃網(wǎng)絡計劃.1 基本概念基本概念p130網(wǎng)絡計劃網(wǎng)絡計劃是用網(wǎng)絡分析的方法編制的計劃是用網(wǎng)絡分析的方法編制的計劃杜邦公司杜邦公司關鍵路線法關鍵路線法CPMCPM美國海軍武器局美國海軍武器局計劃評審技術計劃評審技術PERTPERT網(wǎng)絡圖網(wǎng)絡圖（有向賦權圖）的構成（有向賦權圖

13、）的構成結點結點，也稱事項，一道工序的開始或結束，也稱事項，一道工序的開始或結束工序工序（?。?，相對獨立的活動，消耗資源（?。?，相對獨立的活動，消耗資源虛工序虛工序，只表示銜接關系，不消耗資源，只表示銜接關系，不消耗資源工序時間工序時間（權），完成工序的時間消耗（權），完成工序的時間消耗.2 網(wǎng)絡圖的繪制原則網(wǎng)絡圖的繪制原則l 只 能 有 一 個 始 點 事 項 和 一 個 終 點只 能 有 一 個 始 點 事 項 和 一 個 終 點 事 項事 項l 不 允 許 出 現(xiàn) 編 號 相 同 的不 允 許 出 現(xiàn) 編 號 相 同 的 箭 線箭 線l 不 允 許 出 現(xiàn)不 允 許 出

14、現(xiàn) 循 環(huán) 線 路循 環(huán) 線 路l 作 業(yè) 要 始 于 結 點 終 于作 業(yè) 要 始 于 結 點 終 于 結 點結 點網(wǎng)網(wǎng) 絡絡 規(guī)規(guī) 則（則（2 2）l 1 1、避免循環(huán)、不留缺口、避免循環(huán)、不留缺口l 2 2、一一對應：一道工序用兩個事項表示、一一對應：一道工序用兩個事項表示l 3 3 、從左向右依次展開、從左向右依次展開例：例：工工 序序ABCDEFGHI緊前工序緊前工序-ABBC、D C、DE、F G工序時間工序時間466 7 5 9748A, 4B, 6C, 6D, 7E, 5G, 7F, 9H,4I,8網(wǎng)絡圖的繪制網(wǎng)絡圖的繪制l 任務的分析與分解任務的分析與分解l 判定作業(yè)之間的邏

15、輯關系判定作業(yè)之間的邏輯關系l 依邏輯關系繪制網(wǎng)絡圖依邏輯關系繪制網(wǎng)絡圖作業(yè)作業(yè)A AB BC CD DE EF FGG緊前作業(yè)緊前作業(yè)A AA AC CBDBDD DEFEF.3 關鍵路線法關鍵路線法 CPM一、時間參數(shù)運算一、時間參數(shù)運算 什么是關鍵路線？什么是關鍵路線？1、作業(yè)時間作業(yè)時間t t（i，j），經驗數(shù)據(jù)、統(tǒng)計數(shù)據(jù)），經驗數(shù)據(jù)、統(tǒng)計數(shù)據(jù)2 2、事項最早時間事項最早時間 TE(j)max TE(i)+ t（i，j） 到齊上課，最后到者決定最早開課時間到齊上課，最后到者決定最早開課時間3 3、事項最遲時間事項最遲時間 TL(i)min TL(j)- t（i，j） 保

16、證保證1212點吃飯，路最遠者決定最遲下課時間點吃飯，路最遠者決定最遲下課時間4 4、工序最早可能開工時間、工序最早可能開工時間 TES(i,j) TE(i) = max TES(h,i)+ t（h,i ）5 5、工序最早可能完工時間、工序最早可能完工時間 TEF(i,j) TES(i,j)+ t（i，j）hij.6、工序最遲必須開工時間工序最遲必須開工時間 TLS（i,j) TL(j) t（i,j) minTLs(j,k)- t（i，j）7 7、工序最遲必須完工時間、工序最遲必須完工時間 TLF（i,j) TL(j) TLS（i,j)+ t（i,j)8 8、工序總時差：、工序總時差：在不影響

17、其緊后工序在不影響其緊后工序最遲必須最遲必須開工時間的前提開工時間的前提下，本工序可以推遲的時間下，本工序可以推遲的時間 R（i,j） TLS(i,j) TES(i,j) TLF(i,j) TEF(i,j) minTLS(j,k) TEF（i,j）9 9、工序單時差：、工序單時差：在不影響其緊后工序在不影響其緊后工序最早可能最早可能開工時間的前提開工時間的前提下，本工序可以推遲的時間下，本工序可以推遲的時間 r （i,j） minTES(j,k) TEF（i,j） kk.4時間參數(shù)圖解時間參數(shù)圖解.解上例：解上例：計算事項計算事項 時間參數(shù)時間參數(shù) TESTLSTEFTLFTE

18、STLSTEFTLSr(i,j)R（i,j）A4B 6C6G7D7E5F9H4I 80047613222028282024136關鍵路線關鍵路線：由總時差為零的工序構成：由總時差為零的工序構成 B D G It（i,j)t（j,k).l 解上例解上例 計算工序時間參數(shù)計算工序時間參數(shù) 工序工序ijt(i,j) ESEFLSLFRrA4043730B6060600C641071333D761361300E561119241311F91322152420G71320132000H42226242822I82028202800.5計劃評審技術計劃評審技術PERTl PERT的產生的產

19、生 關鍵路線法中，工序時間是確定值，而對研究性的工關鍵路線法中，工序時間是確定值，而對研究性的工序來說，序來說， t（i，j）是隨機的。）是隨機的。1958年美國海軍武器局年美國海軍武器局研制北極星導彈時提出，重點在于計劃的評審。研制北極星導彈時提出，重點在于計劃的評審。l PERT的時間估計的時間估計 采用三種時間估計法采用三種時間估計法a最最樂觀時間，樂觀時間，b最悲觀時間，最悲觀時間，m最可能時間，則最可能時間，則 工序期望時間工序期望時間 te 方差方差 e2（ ）2a+4m+b 6ba6時時 間間 優(yōu)優(yōu) 化化 網(wǎng) 絡 圖網(wǎng) 絡 圖 P E R T 技 術 的 優(yōu) 化技 術 的 優(yōu) 化

20、 , , 分 多 種 ：分 多 種 ： 有有時 間 優(yōu) 化 、 時 間時 間 優(yōu) 化 、 時 間 費 用 優(yōu) 化 和 時 間 費 用 費 用 優(yōu) 化 和 時 間 費 用 資 源 利 用 優(yōu) 化資 源 利 用 優(yōu) 化 等 。等 。 我 們 在我 們 在 這 里 簡 單 介 紹這 里 簡 單 介 紹 時 間時 間優(yōu) 化優(yōu) 化 和 時 間和 時 間 費 用 優(yōu) 化 費 用 優(yōu) 化 。 時 間。 時 間 優(yōu) 化 主 要優(yōu) 化 主 要 是是 在在以 下以 下 兩 方 面 進 行兩 方 面 進 行 工 作工 作 ： 向 關 鍵 線 路 要 時 間 ： 盡 可 能 節(jié) 省 時 間 ；向 關 鍵 線 路 要

21、時 間 ： 盡 可 能 節(jié) 省 時 間 ； 向 非 關 鍵 線 路 要 資 源 ： 在 非 關 鍵 線 路向 非 關 鍵 線 路 要 資 源 ： 在 非 關 鍵 線 路 調調整 人 員 、 資 金整 人 員 、 資 金 、 物 資 等 ， 集 中 到 關 鍵 線 路、 物 資 等 ， 集 中 到 關 鍵 線 路 ，使 得 關 鍵 線 路使 得 關 鍵 線 路 有 所有 所 突 破突 破 。時時 間間 費費 用用 優(yōu)優(yōu) 化化l 時間和費用雙目標優(yōu)化時間和費用雙目標優(yōu)化，一般來講二者是矛盾的。通過，一般來講二者是矛盾的。通過仔細分析，尋找既省時又省錢的方案，即最低成本日程仔細分析，尋找既省時又省錢

22、的方案，即最低成本日程。l 費用費用：直接費用和間接費用：直接費用和間接費用l 直接費用直接費用：建造工程本身所需材料、人工：建造工程本身所需材料、人工l 間接費用間接費用：工程所需管理費用、設備租金：工程所需管理費用、設備租金ct間接費用間接費用總費用總費用直接費用直接費用趕工趕工：直接費用增加，間接：直接費用增加，間接費用減少。間接費用是常量費用減少。間接費用是常量直接費用簡化為常量處理。直接費用簡化為常量處理。則：則：趕工直接費用率趕工直接費用率費用差費用差時間差時間差課課 后后 作作 業(yè)業(yè) 請請 同學們根據(jù)網(wǎng)絡關鍵路線法求出下面網(wǎng)絡計劃圖的關同學們根據(jù)網(wǎng)絡關鍵路線法求出下面網(wǎng)絡計劃圖的

23、關鍵路線。鍵路線。164325426435404281015151110480（0）（3）（0）（3）（6）（0）（6）關鍵線路：時差為零的作業(yè)連接而成的線路關鍵線路：時差為零的作業(yè)連接而成的線路 答答 案案1.1.建立層次結構模型建立層次結構模型 該結構圖包括目標層，準則層，方案層。該結構圖包括目標層，準則層，方案層。層次分析法的基本步驟歸納如下層次分析法的基本步驟歸納如下3.3.計算單排序權向量并做一致性檢驗計算單排序權向量并做一致性檢驗2.2.構造成對比較矩陣構造成對比較矩陣從第二層開始用成對比較矩陣和從第二層開始用成對比較矩陣和1 19 9尺度。尺度。對每個成對比較矩陣計算最大特征值及

24、其對應的特征向量，對每個成對比較矩陣計算最大特征值及其對應的特征向量，利用一致性指標、隨機一致性指標和一致性比率做一致性利用一致性指標、隨機一致性指標和一致性比率做一致性檢驗。若檢驗通過，特征向量（歸一化后）即為權向量；檢驗。若檢驗通過，特征向量（歸一化后）即為權向量；若不通過，需要重新構造成對比較矩陣。若不通過，需要重新構造成對比較矩陣。目標層目標層選一領導干部選一領導干部 準則層準則層 1P2P3P 方案層方案層 健康狀況健康狀況業(yè)務知識業(yè)務知識口才口才寫作能力寫作能力工作作風工作作風政策水平政策水平建立層次結構模型建立層次結構模型1132221133/1113/13/115/14/14/

25、12/13512/112/1142112/114111A健康情況健康情況業(yè)務知識業(yè)務知識寫作能力寫作能力口才口才政策水平政策水平工作作風工作作風健康情況健康情況業(yè)務知識業(yè)務知識寫作能力寫作能力口才口才政策水平政策水平工作作風工作作風A的最大特征值的最大特征值,35. 6max相應的特征向量為：相應的特征向量為：TW)30. 0 ,12. 0 ,05. 0 ,19. 0 ,19. 0 ,16. 0()2(構造成對比較矩陣及構造成對比較矩陣及層次單排序層次單排序07.016635.6CI一致性指標一致性指標隨機一致性指標隨機一致性指標 RI=1.24 (查表查表)一致性比率一致性比率CR=0.07

26、/1.24=0.05650.1通過一致性檢驗通過一致性檢驗假設假設3人關于人關于6個標準的判斷矩陣為：個標準的判斷矩陣為：13/123142/14/11)3(1B健康情況健康情況1252/1144/14/11)3(2B業(yè)務知識業(yè)務知識113113/13/131)3(3B寫作能力寫作能力17/15/171353/11)3(4B口才口才17/17/1711711)3(5B政策水平政策水平15/19/1517/1971)3(6B工作作風工作作風由此可求得各屬性的最大特征值和相應的特征向量。由此可求得各屬性的最大特征值和相應的特征向量。特征值特征值健康情況健康情況 業(yè)務知識業(yè)務知識 寫作能力寫作能力

27、口才口才 政策水平政策水平 工作作工作作風風 3.02 3.02 3.05 3.05 3.00 3.02max各屬性的最大特征值各屬性的最大特征值05. 007. 007. 046. 057. 024. 017. 047. 065. 022. 033. 063. 077. 047. 028. 032. 010. 014. 0)3(W均通過一致性檢驗均通過一致性檢驗從而有從而有30. 012. 005. 019. 019. 016. 005. 007. 007. 046. 057. 024. 017. 047. 065. 022. 033. 063. 077. 047. 028. 032. 010. 014. 0)2()3(WWW26. 034. 040. 0W即在即在3人中應選擇人中應選擇A擔任領導職務。擔任領導職務。層次總排序及一致性檢驗層次總排序及一致性檢驗怎么樣選擇對象（項目）怎么樣選擇對象（項目）期望值期望值= 1A1 +2A2 + 3 A3 + 4 A4 +5 A5+ 6 A6 +7 A7 +8 A8期望值期望值= 1A1 +2A2 + 3 A3 + 4 A4 +5 A5+ 6 A6 +7 A7 +8 A8課堂復習與練習課堂復習與練習1 1、