運(yùn)籌學(xué)OR1-Ch10-網(wǎng)絡(luò)計劃課件

1、第十章 網(wǎng)絡(luò)計劃Network Programming10-1. 基本概念 Basic Concepts 10-2. 繪制網(wǎng)絡(luò)圖 Draw network plot10-3.網(wǎng)絡(luò)參數(shù) Network Parameter10-4. 隨機(jī)工序時間Random Activity Time10-5. 網(wǎng)絡(luò)的優(yōu)化 Optimization of Network 用網(wǎng)絡(luò)圖編制的計劃稱為網(wǎng)絡(luò)計劃，網(wǎng)絡(luò)計劃技術(shù)由計劃協(xié)調(diào)技術(shù)（Program Evaluation and Review Technique 簡寫為PERT）與關(guān)鍵路徑法（Critical Path Method 簡寫為CPM）組成，它特別廣泛應(yīng)用

2、于系統(tǒng)分析和計劃的目標(biāo)管理。 PERT最早應(yīng)用于美國海軍北極星導(dǎo)彈的研制系統(tǒng)，由于該導(dǎo)彈的系統(tǒng)非常龐大復(fù)雜,為找到一種有效的管理技術(shù),設(shè)計了PERT這種方法,并使北極星導(dǎo)彈的研制周期縮短了一年半時間。 PERT注重計劃的評價和審查，活動的時間往往是隨機(jī)的。 CPM是與PERT十分相似但又是獨(dú)立發(fā)展的另一種技術(shù)，是1957年美國杜邦公司的沃克（M.R.walker）和蘭德公司的小凱利(J.E.Kelley)共同研制的一種方法。它主要研究大型工程的費(fèi)用與工期的相互關(guān)系?；顒拥臅r間往往是確定的。什么是網(wǎng)絡(luò)計劃？10-1. 基本概念 Basic Concepts*Page 2 of 44 【例10.1

3、】（華羅庚：統(tǒng)籌方法平話及補(bǔ)充）某家庭有夫婦兩人安排家務(wù)，要求從上午11：30開始到下午2：00結(jié)束去上班，做下例3件事：工序 工時 代號洗衣 3小時 A燒飯 1小時 B吃飯 0.5小時 C 怎樣安排，使完成時間最短？A,3B,1C,0.54.5A,3B,1C,0.53.5A1,2A2,1C,0.5B,12.510-1. 基本概念 Basic Concepts*Page 3 of 44 1直觀清晰地反映計劃各部門或各項工作之間的相互聯(lián)系制約，便于掌握計劃的全盤情況； 2反映了某一部門或某一項工作在全局中的地位和影響，便于發(fā)現(xiàn)薄弱環(huán)節(jié)并進(jìn)行控制、管理；目前這種方法已廣泛應(yīng)用于大型建筑施工和新產(chǎn)品

4、的研制計劃、計算機(jī)系統(tǒng)的安裝調(diào)試、軍事指揮及各種大型復(fù)雜的控制管理。3這種計劃的編制可利用計算機(jī)進(jìn)行數(shù)據(jù)推理運(yùn)算，因此便于進(jìn)行各種方案的分析比較。一旦發(fā)現(xiàn)某項工作偏離計劃時，及時采取措施，保證整個計劃按時完成。 在計劃管理中，過去習(xí)慣采用的是甘特圖（Cantt chart）或稱橫道圖(bar chart)。計劃評審方法較之甘特圖有明顯示的優(yōu)點(diǎn)：10-1. 基本概念 Basic Concepts*Page 4 of 44 工序 或稱為作業(yè)、活動，指任何消耗時間或資源的活動，如新產(chǎn)品設(shè)計中的初步設(shè)計、技術(shù)設(shè)計、工裝制造等。根據(jù)需要，工序可以劃分得粗一些，也可以劃分得細(xì)一些。 事件 標(biāo)志工序的開始或

5、結(jié)束，本身不消耗時間或資源，或相對作業(yè)講，消耗量可以小得忽略不計。某個事件的實現(xiàn)，標(biāo)志著在它前面各頂作業(yè)（緊前工序）的結(jié)束，又標(biāo)志著在它之后的各項作業(yè)（緊后工序）的開始。如機(jī)械造業(yè)中，只有完成鑄鍛件毛坯后才能開始機(jī)加工；各種零部件都完成后，才能進(jìn)行總裝等。 網(wǎng)絡(luò)圖 由工序、事件及標(biāo)有完成各道工序所需時間所構(gòu)成的連通有向圖。路 從起點(diǎn)延箭頭方向到終點(diǎn)的有向路。緊前工序 緊接某項工序的先行工序；緊后工序 緊接某項工序的后續(xù)工序 虛工序 虛設(shè)的工序。用來表達(dá)相鄰工序之間的銜接關(guān)系，不需要時間和資源。10-1. 基本概念 Basic Concepts*Page 5 of 44 2天3天5天4天1天2天

6、3天6天12ABCDEFGH在下圖中，A是D、E的緊前工序，D、E是A的緊后工序，F(xiàn)是A的后續(xù)工序但不是A的緊后工序；A是D、E、F的前道工序但不是 F 的緊前工序。注意緊前工序、緊后工序、前道工序和后續(xù)工序之間的關(guān)系。10-1. 基本概念 Basic Concepts*Page 6 of 44 1.本節(jié)的主要概念 網(wǎng)絡(luò)計劃、計劃網(wǎng)絡(luò)圖、甘特圖、PERT、CPM 結(jié)點(diǎn)圖、箭示圖、工序、事件、緊前工序、緊后工序2.區(qū)分緊前工序、緊后工序、前道工序和后續(xù)工序之間的關(guān)系10-1. 基本概念 Basic Concepts*Page 7 of 44 網(wǎng)絡(luò)圖中工序間的表達(dá)方式abc1.當(dāng)工序a完工后b和c

7、可以開工abc2.當(dāng)工序a和b完工后c才能開工3.工序c在工序a完工后就可以開工，但工序d必須在a和b都完工后才能開工acbd 4.當(dāng)工序a和b完工后c和d可以開工abcd 10-2. 繪制網(wǎng)絡(luò)圖Draw network plot*Page 8 of 44 繪制網(wǎng)絡(luò)圖的規(guī)則:1.事件的編號應(yīng)遵循箭頭編號大于箭尾編號，即(i，j)，ij錯誤的畫法正確的畫法2.一對事件編號表示唯一一道工序錯誤的畫法正確的畫法虛工序10-2. 繪制網(wǎng)絡(luò)圖Draw network plot*Page 9 of 44 3.不能有回路錯誤的畫法4.不能有缺口，即從網(wǎng)絡(luò)的起點(diǎn)經(jīng)過任意一條路都能達(dá)到終點(diǎn)缺口錯誤的畫法10-2

8、. 繪制網(wǎng)絡(luò)圖Draw network plot*Page 10 of 44 5.盡量避免箭線交叉，做到美觀清晰調(diào)整后10-2. 繪制網(wǎng)絡(luò)圖Draw network plot*Page 11 of 44 6489(a)3111213106591147(b)8合并與簡化364891112138106591147(c)a、b的合并c 的簡化(d)12138101516717710-2. 繪制網(wǎng)絡(luò)圖Draw network plot*Page 12 of 44 工 序ABCDEFGHI緊前工序AABCCD、EFG、HABCDEFGHI23456781【例10.2】已知某工程的工序之間的關(guān)系如下表，試

9、繪制計劃網(wǎng)絡(luò)圖【解】計劃網(wǎng)絡(luò)圖如下：10-2. 繪制網(wǎng)絡(luò)圖Draw network plot*Page 13 of 44 【例10.3】繪制下列計劃網(wǎng)絡(luò)圖工 序ABCDEFGHI緊前工序AABCCD、ED、E、FG、HABCDEFGHI12345678【解】網(wǎng)絡(luò)圖如下：J9-2. 繪制網(wǎng)絡(luò)圖Draw network plot*Page 14 of 44 工 序ABCDEFGHI緊前工序ABED、FD、FH工序時間2444.77.226.244.3A，2D，4.7E,7.2B,4G,6.2H,4C,4I,4.3F,22345671【例10.4】10-2. 繪制網(wǎng)絡(luò)圖Draw network pl

10、ot*Page 15 of 44 工序ABCDEFGHIKLM緊前工序G、MHLCA、EB、CA、LF、IB、CC工序時間347355252173C，7H，5B，4E，5M，3G，2L，7A，3F，5I，2D，311K，1【例10.5】教材P307 T11.110-2. 繪制網(wǎng)絡(luò)圖Draw network plot*Page 16 of 44 1. 計劃網(wǎng)絡(luò)圖的編制規(guī)則及其方法。2. 掌握 虛工序的用法3. 編制網(wǎng)絡(luò)圖可以從左到右又可以從右到左或兩邊向中間畫圖4. 網(wǎng)絡(luò)圖初稿完成后對照工序明細(xì)表驗證緊前緊后工序關(guān)系是否正確作業(yè)：教材10-2. 繪制網(wǎng)絡(luò)圖Draw network plot*Pa

11、ge 17 of 44 工 序ABCDEFGHI緊前工序ABED、FD、FH工序時間2444.77.226.244.3A，2D，4.7E,7.2B,4G,6.2H,4C,4I,4.3F,22345671【例10.5】1. 繪制網(wǎng)絡(luò)圖；2. 計算網(wǎng)絡(luò)參數(shù)；3.求關(guān)鍵路線及關(guān)鍵工序【解】1. 繪制網(wǎng)絡(luò)圖如下：10-3.網(wǎng)絡(luò)參數(shù) Network Parameter*Page 18 of 44 事件 j 的最早時間表示以j為開工事件工序最早可能開工時間2.網(wǎng)絡(luò)參數(shù)事件的最早時間標(biāo)在距形框 中，事件的最遲時間標(biāo)在三角形框 中。事件 j 的最遲時間表示以i 為開工事件工序最遲必須開工時間A，2D，4.7E

12、,7.2B,4G,6.2H,4C,4I,4.3F,2234567107.229.2613.217.517.513.213.59.27.29.50EarliestLatest10-3.網(wǎng)絡(luò)參數(shù) Network Parameter*Page 19 of 44 工序的最早時間標(biāo)在距形框 中，工序的最遲時間標(biāo)在三角形框 中A，2D，4.7E,7.2B,4G,6.2H,4C,4I,4.3F,2234567107.229.2613.217.517.513.213.59.27.29.5007.529.54.511.37.2007.2013.569.29.29.213.213.2工序(i , j)的最遲必須開

13、工時間工序(i , j)的最早可能開工時間工程完工期網(wǎng)絡(luò)終點(diǎn)的最早時間或最遲時間，本例中 T17.5Earliest StartLatest Start10-3.網(wǎng)絡(luò)參數(shù) Network Parameter*Page 20 of 44 A，2D，4.7E,7.2B,4G,6.2H,4C,4I,4.3F,2234567107.229.2613.217.517.513.213.59.27.29.5007.529.54.511.37.2007.2013.569.29.29.213.213.2工序(i , j)的最遲必須完工時間工序(i , j)的最早可能完工時間工序(i , j)的總時差R(i,j)

14、=0 的工序稱為關(guān)鍵工序，由關(guān)鍵工序組成的從起點(diǎn)到終點(diǎn)的有向路稱為關(guān)鍵路線，關(guān)鍵路線可能不唯一。Earliest FinishLatest Finish10-3.網(wǎng)絡(luò)參數(shù) Network Parameter*Page 21 of 44 A，2D，4.7E,7.2B,4G,6.2H,4C,4I,4.3F,2234567107.229.2613.217.517.513.213.59.27.29.5007.529.54.511.37.2007.2013.569.29.29.213.213.2工序的單時差 工序的完工期可推遲多少，以致不影響下道工序 的最早開工時間：下圖中，r(1,4)=9.24.7=

15、4.5，r(4,7)=17.515.4=2.110-3.網(wǎng)絡(luò)參數(shù) Network Parameter*Page 22 of 44 以上參數(shù)可以填在一張表上，例9.5的計算如下表所示：工序（i,j)t(i,j)TES(i,j)TEF(i,j)TLS(i,j)TLF(i,j)R(i,j)r(i,j)A2027.59.57.50B4269.513.57.50C461013.517.57.57.5D4.704.74.59.24.54.5E7.207.207.200F27.29.27.29.200G6.29.215.411.317.52.12.1H49.213.29.213.200I4.313.217.

16、513.217.50010-3.網(wǎng)絡(luò)參數(shù) Network Parameter*Page 23 of 44 工序ABCDEFGHIKLM緊前工序G、MHLCA、EB、CA、LF、IB、CC工序時間347355252173C，7H，5B，4E，5M，3G，2L，7A，3F，5I，2D，311K，1【例10.6】教材P307 T11.110-3.網(wǎng)絡(luò)參數(shù) Network Parameter*Page 24 of 44 工序的最遲必須開工時間工序的最早可能開工時間75453273523111000000077 7599111414161616141920201917171417179111089951

17、00HBGAFK 關(guān)鍵工序：H，B，G，A，F(xiàn)，K關(guān)鍵路線：5435111工程完工期為20。14210-3.網(wǎng)絡(luò)參數(shù) Network Parameter*Page 25 of 44 1.本節(jié)介紹了網(wǎng)絡(luò)參數(shù)的計算，共有8個公式，現(xiàn)綜合如下：事件j 的最早時間表示以j為開工事件工序最早可能開工時間事件 i 的最遲時間表示以i為開工事件工序最遲必須開工時間工序(i , j)的最早可能開工時間工序(i , j)的最遲必須開工時間工序(i , j)的最早可能完工時間工序(i , j)的最遲必須完工時間工序(i , j)的總時差工序的單時差 工序的完工期可推遲多少，以致不影響下道工序的最早開工時間：作業(yè)：

18、教材2.掌握用軟件計算網(wǎng)絡(luò)參數(shù)10-3.網(wǎng)絡(luò)參數(shù) Network Parameter*Page 26 of 44 當(dāng)工序時間不能準(zhǔn)確確定時，一般地，用三點(diǎn)估計法估計工序的時間：最樂觀時間：在順利情況下，完成工序的最短時間，用a表示最保守時間：在不順利情況下，完成工序的最長時間，用b表示最可能時間：在正常情況下，完成工序的時間，用 m 表示工序的期望時間是：方差為均方差為10-4. 隨機(jī)工序時間 Random Activity Time*Page 27 of 44 【例10.7】下表是四道工序的三種估計時間及其期望值方差和均方差工序緊前工序三種估計時間(天)期望值t(i,j)方差均方差ambA1

19、2320.1110.333B341151.7781.333CB561371.7781.333DA,C2685.711EB9101310.30.4440.667FD,E68128.311A,2B,5C,7D,5.7E,10.3F,8.32610-4. 隨機(jī)工序時間 Random Activity Time*Page 28 of 44 由三點(diǎn)估計法估計的工序時間其工程的完工期（關(guān)鍵工序的期望時間之和）是一期望值，帶有隨機(jī)性。設(shè)Xk為關(guān)鍵工序 k 所需時間的隨機(jī)變量，則 xk 相互獨(dú)立，工序工的期望時間及方差為工程完工期的期望值及方差為設(shè)關(guān)鍵工序數(shù)為 n，工程的完工期是一隨機(jī)變量10-4. 隨機(jī)工序

20、時間 Random Activity Time*Page 29 of 44 則由李雅普諾夫中心極限定理知(式中n為關(guān)鍵工序數(shù)）即當(dāng)n很大時Zn近似服從N（0，1）分布，則有：近似服從即10-4. 隨機(jī)工序時間 Random Activity Time*Page 30 of 44 設(shè)給定一個時間X0，則工程完工時間不超過X0的概率為要使工程完工的概率為p0，至少需要多少時間X0查正態(tài)分布表求出X，由得10-4. 隨機(jī)工序時間 Random Activity Time*Page 31 of 44 【例10.8】在例10.7中，(1)求在30天內(nèi)完工的概率；(2)若要使工程完工的概率為0.9，問需要

21、多少天。A,2B,5C,7D,5.7E,10.3F,8.326【解】工程完工時間的期望值 ,均方差為(1) X0=30，則在30天內(nèi)完工的概率是0.776410-4. 隨機(jī)工序時間 Random Activity Time*Page 32 of 44 (2) p0 =0.9，查表得：X1.28若要使工程完工的概率為0.9，則至少需要33.3天10-4. 隨機(jī)工序時間 Random Activity Time*Page 33 of 44 1.三點(diǎn)估計公式 工序的期望時間和方差2.要求工程完工時間不超過X0時，求完工的概率p03.要使工程完工的概率為p0，求至少需要多少時間X010-4. 隨機(jī)工序

22、時間 Random Activity Time*Page 34 of 44 時間優(yōu)化 調(diào)動非關(guān)鍵工序的資源，縮短關(guān)鍵工序的作業(yè)時間，達(dá)到 縮短工程的完工期；關(guān)鍵工序的時間縮短后要重新計算參數(shù)，確定新的關(guān)鍵工序。時間資源優(yōu)化【例】現(xiàn)有65人要完成下例工程工 序作業(yè)時間(天)需要人數(shù)總時差d20580f182247g30420h153920k2526010-5. 網(wǎng)絡(luò)的優(yōu)化 Optimization of Network*Page 35 of 44 f (22人)d(58人)g(42人)k(26人)h(39人)203025181565f (22人)g(42人)d(58人18天20天12天h(39人

23、)k(26人)15天10天10-5. 網(wǎng)絡(luò)的優(yōu)化 Optimization of Network*Page 36 of 44 時間費(fèi)用的優(yōu)化總費(fèi)用直接費(fèi)用間接費(fèi)用直接費(fèi)用包括：生產(chǎn)工人的工資、設(shè)備、能源、工具及材料消耗等直接與完成工序有關(guān)的費(fèi)用，它與工序的作業(yè)時間成反比。間接費(fèi)用包括：管理人員的工資、管理費(fèi)、辦公費(fèi)等費(fèi)用，它與工序的作業(yè)時間成正比。工程總費(fèi)用總費(fèi)用正常時間間接費(fèi)用直接費(fèi)用最低成本日程：工程總費(fèi)用最低的工程完工時間。最低成本日程極限時間10-5. 網(wǎng)絡(luò)的優(yōu)化 Optimization of Network*Page 37 of 44 直接費(fèi)用率g=極限時間的工序直接費(fèi)用正常時間的

24、工序直接費(fèi)用正常時間極限時間a,60d,20e,40c,10g,30h,15b,45i,35f,18010080110170110801200701176060135135k,25170P29510-5. 網(wǎng)絡(luò)的優(yōu)化 Optimization of Network*Page 38 of 44 工序 正常情況下 采取各種措施后 縮短一天工期增加的直接費(fèi)用(費(fèi)用變動率g，元/天) 正常時間(天) 工序的直接費(fèi)用(元) 極限時間(天) 工序直接費(fèi)用(元) abcdefghkl 6045102040830152535 10000 4500 2800 7000 10000 3600 9000 3750

25、6250 12000 60 30 5 10 35 10 20 10 15 60 10000 6300 4300 11000 12500 5440 12500 5750 9150 12000 01203004005002303504002900直接費(fèi)用68900間接費(fèi)用40017068000 總費(fèi)用136900【例】教材10-5. 網(wǎng)絡(luò)的優(yōu)化 Optimization of Network*Page 39 of 44 a,60d,20e,40c,10g,30h,15b,45i,35f,18010080110170110801200701176060135135k,25170方案1：分別縮短g、k

26、 的時間10天(極限時間分別是20，15天)，則費(fèi)用變化：增加的直接費(fèi)用：29010350106400減少的間接費(fèi)用：400208000總費(fèi)用減少80006400160010-5. 網(wǎng)絡(luò)的優(yōu)化 Optimization of Network*Page 40 of 44 a,60d,20e,40c,10g,20h,15b,45i,35f,1801008010015010080100070976060115115k,15150方案2：如果再縮短工序d10天，h和e各縮短5天，完工期縮短10天，費(fèi)用的變動：直接費(fèi)用增加：40010400550058500間接費(fèi)用減少：400104000總費(fèi)用增加850040004500因此方案2最好，最低成