《運籌學(xué)網(wǎng)絡(luò)計劃》課件

1、Chapter 7 網(wǎng)絡(luò)計劃Network Programming7.1 繪制網(wǎng)絡(luò)圖 Draw network plot7.2網(wǎng)絡(luò)參數(shù) Network Parameter7.3 網(wǎng)絡(luò)的優(yōu)化 Optimization of Network 運 籌 學(xué) Operations Research 7.1 繪制網(wǎng)絡(luò)圖 Draw network plot23 九月 2022網(wǎng)絡(luò)還是進行計劃工作的有效工具凡事“預(yù)則立”！23 九月 2022橫道圖時間3月4月5月6月開題報告英文翻譯文獻查閱論文撰寫論文答辯優(yōu)點：直觀、易懂、便于檢查缺點：不能反映相互之間聯(lián)系和影響，無法找出關(guān)鍵工作。23 九月 2022 用網(wǎng)

2、絡(luò)圖編制的計劃稱為網(wǎng)絡(luò)計劃，網(wǎng)絡(luò)計劃技術(shù)由計劃協(xié)調(diào)技術(shù)（Program Evaluation and Review Technique 簡寫為PERT）與關(guān)鍵路徑法（Critical Path Method 簡寫為CPM）組成。7.1.1項目網(wǎng)絡(luò)圖的基本概念 PERT主要針對完成工作的時間不能確定而是一個隨機變量時的計劃編制方法，活動的完成時間通常用三點估計法，注重計劃的評價和審查。7.1 繪制網(wǎng)絡(luò)圖 Draw network plot CPM以經(jīng)驗數(shù)據(jù)確定工作時間，看作是確定的數(shù)值，主要研究項目的費用與工期的相互關(guān)系。通常將這兩種方法融為一體，統(tǒng)稱為網(wǎng)絡(luò)計劃、網(wǎng)絡(luò)計劃技術(shù)(PERT/CPM)

3、。23 九月 2022 網(wǎng)絡(luò)計劃主要應(yīng)用于新產(chǎn)品研制與開發(fā)、大型工程項目的計劃編制與計劃的優(yōu)化，是項目管理和項目安排領(lǐng)域目前比較科學(xué)的一種計劃編制方法，比甘特圖（Cantt chart）或稱橫道圖(bar chart)計劃方法有許多優(yōu)點。 網(wǎng)絡(luò)計劃有利于對計劃進行控制、管理、調(diào)整和優(yōu)化，更清晰地了解工作之間的相互聯(lián)系和相互制約的邏輯關(guān)系，掌握關(guān)鍵工作和計劃的全盤情況。 PERT最早應(yīng)用于美國海軍北極星導(dǎo)彈的研制系統(tǒng)，由于該導(dǎo)彈的系統(tǒng)非常龐大復(fù)雜,為找到一種有效的管理技術(shù),設(shè)計了PERT這種方法,并使北極星導(dǎo)彈的研制周期縮短了一年半時間。 CPM是與PERT十分相似但又是獨立發(fā)展的另一種技術(shù)，是

4、1957年美國杜邦公司的沃克（M.R.walker）和蘭德公司的小凱利(J.E.Kelley)共同研制的一種方法。它主要研究大型工程的費用與工期的相互關(guān)系。7.1 繪制網(wǎng)絡(luò)圖 Draw network plot23 九月 2022【例7.1】（華羅庚：統(tǒng)籌方法平話及補充）某家庭有夫婦兩人安排家務(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.57.1 繪制網(wǎng)絡(luò)圖 Draw network p

5、lot23 九月 2022 工序 或稱為作業(yè)、活動，指任何消耗時間或資源的活動，如新產(chǎn)品設(shè)計中的初步設(shè)計、技術(shù)設(shè)計、工裝制造等。根據(jù)需要，工序可以劃分得粗一些，也可以劃分得細一些。 事件 標志工序的開始或結(jié)束，本身不消耗時間或資源，或相對作業(yè)講，消耗量可以小得忽略不計。某個事件的實現(xiàn)，標志著在它前面各頂作業(yè)（緊前工序）的結(jié)束，又標志著在它之后的各項作業(yè)（緊后工序）的開始。如機械造業(yè)中，只有完成鑄鍛件毛坯后才能開始機加工；各種零部件都完成后，才能進行總裝等。 虛工序 虛設(shè)的工序。用來表達相鄰工序之間的銜接關(guān)系，不需要時間和資源。7.1 繪制網(wǎng)絡(luò)圖 Draw network plot23 九月 2

6、022虛工序21AB 不正確312BAC 正確23 九月 2022虛工序 不正確 正確ACADBABACDBACDE23 九月 2022 網(wǎng)絡(luò)圖 由工序、事件及標有完成各道工序所需時間所構(gòu)成的連通有向圖。路 從起點沿箭頭方向到終點的有向路。緊前工序 緊接某項工序的先行工序緊后工序 緊接某項工序的后續(xù)工序箭示網(wǎng)絡(luò)圖 用箭條表示工序的計劃網(wǎng)絡(luò)圖。本章講的就是箭示圖節(jié)點網(wǎng)絡(luò)圖 用節(jié)點表示工序的計劃網(wǎng)絡(luò)圖前道工序 某工序之前的所有工序7.1 繪制網(wǎng)絡(luò)圖 Draw network plot后續(xù)工序 某工序之后的所有工序23 九月 20222天3天5天4天1天2天3天6天12ABCDEFGH在下圖中，A是

7、D、E的緊前工序，D、E是A的緊后工序，F(xiàn)是A的后續(xù)工序但不是A的緊后工序；A是D、E、F的前道工序但不是 F 的緊前工序。注意緊前工序、緊后工序、前道工序和后續(xù)工序之間的關(guān)系。7.1 繪制網(wǎng)絡(luò)圖 Draw network plot23 九月 2022表7-1 工序明細表 序號代號工序名稱緊前工序時間(天)序號代號工序名稱緊前工序時間(天)1A基礎(chǔ)工程405E裝修工程C252B構(gòu)件安裝A506F地面工程D203C屋面工程B307G設(shè)備安裝B504D專業(yè)工程B208H試運轉(zhuǎn)E、F、G20ABCDGEFH4050302050252020圖71（a）箭線圖7.1 繪制網(wǎng)絡(luò)圖 Draw network

8、 plot【例7.1】某項目由8道工序組成，工序明細表見表7-1所示。分別用箭線法和節(jié)點法繪制該項目的項目網(wǎng)絡(luò)圖。 23 九月 2022表7-1 工序明細表 序號代號工序名稱緊前工序時間(天)序號代號工序名稱緊前工序時間(天)1A基礎(chǔ)工程405E裝修工程C252B構(gòu)件安裝A506F地面工程D203C屋面工程B307G設(shè)備安裝B504D專業(yè)工程B208H試運轉(zhuǎn)E、F、G20A4050302050252020BCDGEFH圖71（b）節(jié)點圖7.1 繪制網(wǎng)絡(luò)圖 Draw network plot23 九月 2022abc1.當工序a完工后b和c可以開工3.工序c在工序a完工后就可以開工，但工序d必須

9、在a和b都完工后才能開工acbd 2.當工序a和b完工后c和d可以開工4.事件i、j之間有多道工序時，添加虛工序(a)abcd (b)(c)(d)abc7.1.2 繪制網(wǎng)絡(luò)圖7.1 繪制網(wǎng)絡(luò)圖 Draw network plot23 九月 20227.1 繪制網(wǎng)絡(luò)圖 Draw network plotacbd acbd (e)(f)ee圖726. 網(wǎng)絡(luò)圖只有一個發(fā)點（項目的開始點）一個收點（項目的結(jié)束點）。如圖72（e）所示，則應(yīng)合成圖72（f）所示的一個始點及一個終點。5. 用弧(i，j)表示一道工序，事件i是工序的開始，事件j是工序的完成，規(guī)定i j。見下圖 ABCDGEFH4050302

10、05025202023 九月 2022繪制網(wǎng)絡(luò)圖的步驟1、分解任務(wù)，列出活動關(guān)系表2、做網(wǎng)絡(luò)圖3、結(jié)點編號23 九月 2022分解任務(wù)，列出活動關(guān)系表確定各活動的相互關(guān)系 緊前活動：只有活動A完成，才能開始活動B，則稱A為B的緊前活動； 緊后活動：B為A的緊后活動； 平行活動；若活動開始進行時，活動C也可以同時進行，則稱A和C為平行活動。 確定每項活動的活動時間23 九月 2022作網(wǎng)絡(luò)圖按時間順序從左到右地排列起始點在圖的最左邊，終點在圖的最右邊。23 九月 2022結(jié)點編號分級編號法零二一二三三四 1 2 4 3 5 6 723 九月 20227.1.3 工序時間的估計均方差為三點估計法是

11、事先估計出工序的三種可能完成時間，其期望值就作為工序時間的估計值。三種時間是：(1)完成工序（i，j）的最短時間，稱為樂觀時間，記為aij(2) 完成工序（i，j）的正常時間，稱為最可能時間,記為mij(3) 完成工序（i，j）的最長時間，稱為悲觀時間，記為bij三種時間發(fā)生的概率分別為1/6、4/6、1/6，則工序（i，j）完成時間的期望值和方差為：7.1 繪制網(wǎng)絡(luò)圖 Draw network plot23 九月 2022【例7.2】根據(jù)某項目作業(yè)明細表72的資料，繪制項目網(wǎng)絡(luò)圖 工序緊前工序工序時間(天)工序緊前工序工序時間(天)a6ga,b10b 9he,f12ca13id,h8dc5j

12、i17ec16kd,h,g20fa,b12lg25表72【解】計劃網(wǎng)絡(luò)圖如下：7.1 繪制網(wǎng)絡(luò)圖 Draw network plot工序緊前工序工序時間(天)工序緊前工序工序時間(天)a 6ga,b10b 9he,f12ca13id,h8dc5ji17ec16kd,h,g20fa,b12lg25a,61b,9c,13d,5e,16f,12h,12g,10i,8k,20j,17l,25圖73(a)箭線網(wǎng)絡(luò)圖123546710891123 九月 2022a6b9 c13 f12d5i8 e16 g10 h12 j17 k20 l25s0t0圖73(b)節(jié)點網(wǎng)絡(luò)圖工序緊前工序工序時間(天)工序緊前工

13、序工序時間(天)a 6ga,b10b 9he,f12ca13id,h8dc5ji17ec16kd,h,g20fa,b 12lg257.1 繪制網(wǎng)絡(luò)圖 Draw network plot【例7.3】根據(jù)下表作業(yè)明細表資料，繪制計劃網(wǎng)絡(luò)圖工序緊前工序工序的三種時間工序緊前工序工序的三種時間ambamba679fc182426b5810ge,303542c111214hd,202630da,b,c151719if141722ea91012jf283438a,7.171b,7.83c,12.17d,17e,10.17f,23.33h,25.67g,35.33i,17.33j,33.67圖74工序abc

14、defghij期望值7.177.8312.171710.1723.3335.3325.6717.3333.67方差0.250.690.250.440.251.7842.781.782.7823 九月 20223.計劃網(wǎng)絡(luò)圖的編制規(guī)則及其方法4.掌握 虛工序的用法5.編制網(wǎng)絡(luò)圖可以從左到右又可以從右到左或兩邊向中間畫圖6.網(wǎng)絡(luò)圖初稿完成后對照工序明細表驗證緊前緊后工序關(guān)系是否正確作業(yè)：教材P169 T 27.1 繪制網(wǎng)絡(luò)圖 Draw network plot1.本節(jié)的主要概念 網(wǎng)絡(luò)計劃、計劃網(wǎng)絡(luò)圖、甘特圖、PERT、CPM、 結(jié)點圖、箭示圖、工序、事件、緊前工序、緊后工序2.區(qū)分緊前工序、緊后工

15、序、前道工序和后續(xù)工序之間的關(guān)系7.三種時間估計公式， 工序的期望時間和方差下一講：網(wǎng)絡(luò)參數(shù) 7.2 網(wǎng)絡(luò)參數(shù) Network Parameter23 九月 2022（1）工序(i,j)的最早開始時間（Earliest start time for an activity）TES(i,j)。是指緊前工序的最早可能完工時間的最大值，計算公式為 （2）工序(i,j)的最早完工時間（Earliest finish time for an activity）TEF(i,j)。計算公式為 7.2 網(wǎng)絡(luò)參數(shù) Network Parameter7.2.1時間參數(shù)公式及其含義23 九月 2022(4) 工序(

16、i,j)的最遲必須結(jié)束時間(Latest finish time for an activity) TLF(i,j)。計算公式為 (3) 工序(i,j)的最遲必須開始時間（latest start time for an activity）TLS(i,j)。是指為了不影響緊后工序如期開工，工序最遲必須開工的時間，計算公式為 7.2 網(wǎng)絡(luò)參數(shù) Network Parameter23 九月 2022(6)工序的單時差或自由時間(Free for an activity) F(i，j)。在不影響緊后工序的最早開始時間的條件下，工序(i,j) 的開始時間可以推遲的時間。計算公式為 (5) 工序(i,j

17、)的總時差或松弛時間(Slack for an activity) S(i,j)。是工序(i,j)的最遲開始(結(jié)束)時間與最早開始(結(jié)束)時間之差，計算公式為 7.2 網(wǎng)絡(luò)參數(shù) Network Parameter23 九月 2022【例7.4】以網(wǎng)絡(luò)圖73為例。（1）在圖上計算各工序的最早開始和最遲開始時間。（2）用表格計算工序的6個時間參數(shù)。（3）指出項目的關(guān)鍵工序和關(guān)鍵路線。（4）求項目的完工時間。7.2 網(wǎng)絡(luò)參數(shù) Network Parameter圖75a,6111b,9c,13d,5e,16f,12h,12g,10i,8k,20j,17l,25000669919193519194747

18、47475572725552474752524742353719623231400【解】(1)最早開始和最遲開始時間見圖7523 九月 2022（2）表格形式見表7-5 表7-5工序 (i,j)tijTES(i,j)TEF(i,j)TLS(i,j)TLF(i,j)S(i,j)F(i,j)關(guān)鍵工序a(1,2)6060600是b(1,3)9091423140c(2,4)1361961900是d(4,7)5192442472323e(4,5)161935193500是f(3,5)1292123351414g(3,8)1091937472828h(5,6)123547354700是i(7,10)847

19、55475500是j(10,11)175572557200是k(9,11)204767527255l(8,11)251944477228287.2 網(wǎng)絡(luò)參數(shù) Network Parameter23 九月 2022a,6111b,9c,13d,5e,16f,12h,12g,10i,8k,20j,17l,2500066991919351919474747475572725552474752524742353719623231400(3)關(guān)鍵工序：a、c、e、h、i、j 關(guān)鍵路線： 11(4)工程的完工時間為72天7.2 網(wǎng)絡(luò)參數(shù) Network Parameter23 九月 2022工序時間是隨機

20、變量時，項目的完工期也是隨機變量設(shè)Xk為關(guān)鍵工序 k 所需時間的隨機變量，則 Xk 相互獨立，工序的期望時間及方差為工程完工期的期望值及方差為設(shè)關(guān)鍵工序數(shù)為n，工程的完工期是一隨機變量7.2.3項目完工的概率7.2 網(wǎng)絡(luò)參數(shù) Network Parameter23 九月 2022則由李雅普諾夫中心極限定理知(式中n為關(guān)鍵工序數(shù)）即當n很大時Zn近似服從N（0，1）分布，則有近似服從即7.2 網(wǎng)絡(luò)參數(shù) Network Parameter23 九月 2022設(shè)給定一個時間X0，則工程完工時間不超過X0的概率為要使工程完工的概率為p0，至少需要多少時間X0查正態(tài)分布表求出X，由得7.2 網(wǎng)絡(luò)參數(shù) N

21、etwork Parameter23 九月 2022a,7.171b,7.83c,12.17d,17e,10.17f,23.33h,25.67g,35.33i,17.33j,33.67【例7.5】對例7.3所示的資料：（1）求工序的最早開始和最遲開始時間。（2）求工程完工期的期望值及其概率。（3）要求完工的概率為0.95,至少需要多少天。00007.177.1712.1712.1712.1735.529.1717.3435.569.1769.1769.1733.8443.551.8435.569.1712.1726.523.6716.518.6700圖77【解】(1)工序的最早開始和最遲開始時

22、間見圖7726.526.57.2 網(wǎng)絡(luò)參數(shù) Network Parameter23 九月 2022 (2) 關(guān)鍵工序是c、f 和j，由表7-4及式(7.12)知，項目完工期的期望值、方差、標準差分別為 12.17+23.33+33.6769.1720.25+1.78+2.764.79， =2.1886（3）X072，(X0)/=(7269.17)/2.1886=1.293 （4）已知概率p0=0.98，由式(7.15)，查正態(tài)分布表有要使項目完工的概率為0.98，至少需要73.65天 7.2 網(wǎng)絡(luò)參數(shù) Network Parameter23 九月 20221.本節(jié)介紹了網(wǎng)絡(luò)參數(shù)的計算，共有8個

23、公式，現(xiàn)綜合如下：工序(i , j)的最早可能開工時間 工序(i , j)的最遲必須開工時間工序(i , j)的最早可能完工時間工序(i , j)的最遲必須完工時間工序(i , j)的總時差工序的單時差 工序的完工期可推遲多少，以致不影響下道工序的最早開工時間：7.2 網(wǎng)絡(luò)參數(shù) Network Parameter23 九月 2022作業(yè)：教材P169 T 3，4，5事件j 的最早時間表示以j為開工事件工序最早可能開工時間事件 i 的最遲時間表示以i為完工事件工序最遲必須完工時間下一講：網(wǎng)絡(luò)計劃的優(yōu)化與調(diào)整 2.三種時間估計公式， 工序的期望時間和方差3.要求工程完工時間不超過X0時，求完工的概

24、率p04.要使工程完工的概率為p0，求至少需要多少時間X07.2 網(wǎng)絡(luò)參數(shù) Network Parameter7.3 網(wǎng)絡(luò)的優(yōu)化 Optimization of Network23 九月 20227.3.1 時間成本控制7.3 網(wǎng)絡(luò)的優(yōu)化 Optimization of Network正常時間（Normal Time） 正常成本(Normal Cost) 應(yīng)急時間(Crash Time)應(yīng)急成本 (Crash Cost)總成本總應(yīng)急成本總應(yīng)急收益 總正常成本總應(yīng)急增加成本總應(yīng)急收益單位時間工序的應(yīng)急增加成本(成本斜率) (應(yīng)急成本正常成本)（正常時間應(yīng)急時間） 23 九月 2022【例7.6】

25、項目工序的正常時間、應(yīng)急時間及對應(yīng)的費用見表7-6。表中正常成本是在正常時間完成工序所需要的成本，應(yīng)急成本是在采取應(yīng)急措施時完成工序的成本。每天的應(yīng)急成本是工序縮短一天額外增加的成本 （1）繪制項目網(wǎng)絡(luò)圖，按正常時間計算完成項目的總成本和工期。（2）按應(yīng)急時間計算完成項目的總成本和工期。（3）按應(yīng)急時間的項目完工期，調(diào)整計劃使總成本最低。（4）已知項目縮短1天額外獲得獎金5萬元，減少間接費用1萬元，求總成本最低的項目完工期，也稱為最低成本日程。7.3 網(wǎng)絡(luò)的優(yōu)化 Optimization of Network工序緊前工序時間(天)成本(萬元)時間的最大縮量(天)應(yīng)急增加成本(萬元/天)正常應(yīng)急

26、正常應(yīng)急A1915528047BA21196290214CB2422243023DB25233860211EB2624182624FC25238810227GD,E2823193954HF232330300IG,H27264055115JI1814172141KI3530253552LJ28253060310MK3026455743NL2520182852總成本50671323 九月 2022【解】(1)項目網(wǎng)絡(luò)圖及時間參數(shù)見圖78。項目的完工期為210天，將表7-6正常成本一列相加得到總成本為506萬元 C,24H,23B,21E,26D,25J,18G,28A,19F,25I,27L,28

27、12K,35M,3013N,2511O,0001940404066646689112139210013915718517421018515718014513911284896440845958190圖787.3 網(wǎng)絡(luò)的優(yōu)化 Optimization of Network23 九月 2022C,22H,23B,19E,24D,23J,14G,23A,15F,23I,26L,2512K,30M,2613N,2011O,0001534343458565879102128187012814216715818716714216113112810279795634795655150圖79（2）項目網(wǎng)絡(luò)圖不

28、變，時間參數(shù)見圖79，完工期187天，將表7-6應(yīng)急成本一列相加得到總成本為713萬元 7.3 網(wǎng)絡(luò)的優(yōu)化 Optimization of Network23 九月 2022(3)圖79中，非關(guān)鍵工序是D、E、G、K和M，可以看出，將工序D、E、G按正常時間施工時，最早開始和最遲開始時間不相等，說明按正常時間施工不影響項目的完工期（187天），見圖710(a)。工序K和M按正常時間共要縮短時間6天，見圖710(b)。 E,26D,25G,28O,0343460607979545312K,35M,3013J,14L,2513N,2011應(yīng)急時間路長：59正常時間路長：6512K,30M,2613

29、應(yīng)急時間路長：56圖710(a)(b)7.3 網(wǎng)絡(luò)的優(yōu)化 Optimization of Network23 九月 2022則最優(yōu)的決策方案是：關(guān)鍵工序A、B、C、F、H、I、J、L、N全部按應(yīng)急時間施工，總成本等于各工序應(yīng)急成本之和；工序D、E、G按正常時間施工，成本等于各工序正常成本之和；工序K縮短5天工序M縮短1天，成本等于正常成本加應(yīng)急時間增加的成本。按項目完工期187天施工的最小成本是654萬元，成本分析見表7-7。調(diào)整后有兩條關(guān)鍵路線，見圖711 C,22H,23B,19E,26D,25J,14G,23A,15F,23I,26L,2512K,30M,2913N,2011O,0001

30、534343460566079102128187012814216715818716714215812812810279795634795653150圖7117.3 網(wǎng)絡(luò)的優(yōu)化 Optimization of Network23 九月 2022(4)考慮縮短關(guān)鍵工序的時間，選擇一天應(yīng)急增加的成本小于等于6的關(guān)鍵工序采取應(yīng)急措施來縮短時間，這樣的工序有C、J、N，工序C縮短2天，工序J縮短4天，工序N縮短2天。對圖78進行第一次調(diào)整得到圖712。得到兩條關(guān)鍵路線，工序K和M變?yōu)殛P(guān)鍵工序，項目完工期為202天，縮短了8天?？偝杀咀儎宇~為: 2341228634（萬元）C,22H,23B,21E,2

31、6D,25J,14G,28A,19F,25I,27L,2812K,35M,3013N,2311O,0001940404066626687110137202013715117917220217915117213713711082876240825756190圖7127.3 網(wǎng)絡(luò)的優(yōu)化 Optimization of Network23 九月 2022檢查圖712虛線圍起來的部分。要縮短工期必須兩條關(guān)鍵路線同時縮短時間，上面一條路線工序N還能縮短3天，因此下面一條路線只對工序K縮短3天，對圖712調(diào)整得到圖713。項目的完工期為199天，又縮短了3天，總成本變動額為 3232366（萬元） C,2

32、2H,23B,21E,26D,25J,14G,28A,19F,25I,27L,2812K,32M,3013N,2011O,0001940404066626687110137199013715117916919917915116913713711082876240825756190圖713繼續(xù)檢查發(fā)現(xiàn)，縮短任何關(guān)鍵工序都不能降低成本，則總成本最低的項目工期是199天，總成本為 506346466（萬元）7.3 網(wǎng)絡(luò)的優(yōu)化 Optimization of Network23 九月 20227.3.2 資源的合理配置(1) 資源一定，如何組織、安排和調(diào)配資源保證項目按期完成。(2) 資源不足時，如何協(xié)調(diào)內(nèi)部資源和采取應(yīng)急措施(加班、雇工、增加設(shè)備、改進施工工藝)保證項目按期完成。(3) 資源、時間和成本的整體調(diào)整和系統(tǒng)優(yōu)化 【例7.7】項目各工序的時間和資源如表78所示 （1）繪制項目網(wǎng)絡(luò)圖，按正常時間計算項目完工期，按期完工最多需要多少人。（2）保證按期完工，怎樣采取應(yīng)急措施，使總成本最小又