運(yùn)籌學(xué)11清華大學(xué)課件

1、第第十一十一章章章節(jié)大綱章節(jié)大綱1.工程計(jì)劃網(wǎng)絡(luò)圖的繪制工程計(jì)劃網(wǎng)絡(luò)圖的繪制2.網(wǎng)絡(luò)時(shí)間的計(jì)算網(wǎng)絡(luò)時(shí)間的計(jì)算3.關(guān)鍵路線與網(wǎng)絡(luò)優(yōu)化關(guān)鍵路線與網(wǎng)絡(luò)優(yōu)化一、工程計(jì)劃網(wǎng)絡(luò)問題（關(guān)鍵路徑法）一、工程計(jì)劃網(wǎng)絡(luò)問題（關(guān)鍵路徑法）1. 問題的一般提法 設(shè)：有一項(xiàng)工程，分為若干道工序；已知各工序 間的先后關(guān)系，以及各工序所需時(shí)間t。 問：（1）工程完工期t=？ （2）工程的關(guān)鍵工序有哪些？2.解法關(guān)鍵路徑法（cpm）（1）繪制工程網(wǎng)絡(luò)圖（2）求完工期（用標(biāo)號(hào)法）（3）求關(guān)鍵路（用標(biāo)號(hào)法）1.1 網(wǎng)絡(luò)計(jì)劃網(wǎng)絡(luò)計(jì)劃圖圖v 網(wǎng)絡(luò)計(jì)劃圖的基本思想是：首先應(yīng)用網(wǎng)絡(luò)計(jì)劃圖來表示首先應(yīng)用網(wǎng)絡(luò)計(jì)劃圖來表示工程項(xiàng)目中計(jì)劃要完成

2、的各項(xiàng)工作，完成各項(xiàng)工作必然工程項(xiàng)目中計(jì)劃要完成的各項(xiàng)工作，完成各項(xiàng)工作必然存在先后順序及其相互依賴的邏輯關(guān)系；這些關(guān)系用存在先后順序及其相互依賴的邏輯關(guān)系；這些關(guān)系用節(jié)節(jié)點(diǎn)、箭線來構(gòu)成網(wǎng)絡(luò)圖點(diǎn)、箭線來構(gòu)成網(wǎng)絡(luò)圖。網(wǎng)絡(luò)圖是由左向右繪制，表示。網(wǎng)絡(luò)圖是由左向右繪制，表示工作進(jìn)程。并標(biāo)注工作名稱、代號(hào)和工作持續(xù)時(shí)間等必工作進(jìn)程。并標(biāo)注工作名稱、代號(hào)和工作持續(xù)時(shí)間等必要信息。通過對(duì)網(wǎng)絡(luò)計(jì)劃圖進(jìn)行時(shí)間參數(shù)的計(jì)算，找出要信息。通過對(duì)網(wǎng)絡(luò)計(jì)劃圖進(jìn)行時(shí)間參數(shù)的計(jì)算，找出計(jì)劃中的關(guān)鍵工作和關(guān)鍵線路；通過不斷改進(jìn)網(wǎng)絡(luò)計(jì)劃，計(jì)劃中的關(guān)鍵工作和關(guān)鍵線路；通過不斷改進(jìn)網(wǎng)絡(luò)計(jì)劃，尋求最優(yōu)方案，以求在計(jì)劃執(zhí)行過程中對(duì)計(jì)劃

3、進(jìn)行有效尋求最優(yōu)方案，以求在計(jì)劃執(zhí)行過程中對(duì)計(jì)劃進(jìn)行有效的控制與監(jiān)督，保證合理地使用人力、物力和財(cái)力，以的控制與監(jiān)督，保證合理地使用人力、物力和財(cái)力，以最小的消耗取得最大的經(jīng)濟(jì)效果。最小的消耗取得最大的經(jīng)濟(jì)效果。v網(wǎng)絡(luò)計(jì)劃圖是在網(wǎng)絡(luò)圖上標(biāo)注時(shí)標(biāo)和時(shí)間參數(shù)的進(jìn)度計(jì)劃圖，實(shí)質(zhì)上是有時(shí)序的有向賦權(quán)圖。表述關(guān)鍵路線法（cpm）和計(jì)劃評(píng)審技術(shù)（pert）的網(wǎng)絡(luò)計(jì)劃圖沒有本質(zhì)的區(qū)別，它們的結(jié)構(gòu)和術(shù)語(yǔ)是一樣的。僅前者的時(shí)間參數(shù)是確定型的，而后者的時(shí)間參數(shù)是不確定型的。1.1 網(wǎng)絡(luò)計(jì)劃網(wǎng)絡(luò)計(jì)劃圖圖工工 序序v 在網(wǎng)絡(luò)計(jì)劃圖中，用箭線表示工作，箭尾的節(jié)點(diǎn)表示在網(wǎng)絡(luò)計(jì)劃圖中，用箭線表示工作，箭尾的節(jié)點(diǎn)表示工作的開

4、始點(diǎn)，箭頭的節(jié)點(diǎn)表示工作的完成點(diǎn)。用工作的開始點(diǎn)，箭頭的節(jié)點(diǎn)表示工作的完成點(diǎn)。用（i-ji-j）兩個(gè)代號(hào)及箭線表示一項(xiàng)工作。在箭線上標(biāo)）兩個(gè)代號(hào)及箭線表示一項(xiàng)工作。在箭線上標(biāo)記必須的信息，如下圖：記必須的信息，如下圖： ji持續(xù)時(shí)間工作名稱或代號(hào)箭箭尾尾事事項(xiàng)項(xiàng)箭箭頭頭事事項(xiàng)項(xiàng)工序之間的關(guān)系工序之間的關(guān)系v緊前工序：緊前工序：緊排在本工作之前的工作；緊排在本工作之前的工作；且開始且開始或完成后，才能開始本工作或完成后，才能開始本工作。v緊后工序：緊后工序：緊排在本工作之后的工作；緊排在本工作之后的工作；本工作本工作開始或結(jié)束后，才能開始或結(jié)束的工作。開始或結(jié)束后，才能開始或結(jié)束的工作。v虛工序

5、：虛工序：不占用時(shí)間和不消耗人力，資金等的不占用時(shí)間和不消耗人力，資金等的虛設(shè)的工作。虛工序只表示相鄰工序之間的邏虛設(shè)的工作。虛工序只表示相鄰工序之間的邏輯關(guān)系。輯關(guān)系。網(wǎng)絡(luò)圖的要求網(wǎng)絡(luò)圖的要求v相鄰節(jié)點(diǎn)只能是一個(gè)工序的相關(guān)事項(xiàng)；相鄰節(jié)點(diǎn)只能是一個(gè)工序的相關(guān)事項(xiàng)；v網(wǎng)絡(luò)圖中不能有缺口和回路網(wǎng)絡(luò)圖中不能有缺口和回路應(yīng)改正為ts1234abc123456dabce1）順序：按工序先后從左至右；2）圖中?。€）：表示工序； 頂點(diǎn)（結(jié)點(diǎn)）：表示相鄰工序的時(shí)間分 界點(diǎn)，稱事項(xiàng)，用 表示。 相鄰?。罕硎竟ば蚯昂筱暯雨P(guān)系，稱緊 前（后）工序；3）要求：圖中不得有缺口、回路和多重邊。i缺口：多個(gè)始點(diǎn)或多個(gè)終

6、點(diǎn)的現(xiàn)象。 （應(yīng)當(dāng)只有一個(gè)始點(diǎn)和終點(diǎn)）繪制工程網(wǎng)絡(luò)圖繪制工程網(wǎng)絡(luò)圖處理方法：增加虛工序。多重邊：兩點(diǎn)間有多于一條的邊。ab處理方法：增加虛工序。aab例例1 為籌建某餐館，需制定計(jì)劃。將工程分為為籌建某餐館，需制定計(jì)劃。將工程分為14道工序，各工序道工序，各工序需時(shí)及先后關(guān)系如下表。試求該工程完工期需時(shí)及先后關(guān)系如下表。試求該工程完工期t及關(guān)鍵路徑。及關(guān)鍵路徑。回路：方向一致的閉合鏈。1cbad2e3f4g5h6ij7i8kl9im10n11網(wǎng)絡(luò)計(jì)劃圖的時(shí)間參數(shù)計(jì)算網(wǎng)絡(luò)計(jì)劃圖的時(shí)間參數(shù)計(jì)算網(wǎng)絡(luò)圖中工作的時(shí)間參數(shù)。它們是網(wǎng)絡(luò)圖中工作的時(shí)間參數(shù)。它們是：v工作持續(xù)時(shí)間工作持續(xù)時(shí)間(d)(d)； v

7、工作最早開始時(shí)間（工作最早開始時(shí)間（eses）；）； v工作最早完成時(shí)間（工作最早完成時(shí)間（efef）；）；v工作最遲開始時(shí)間（工作最遲開始時(shí)間（lsls）；）；v工作最遲完成時(shí)間（工作最遲完成時(shí)間（lflf）；）；v工作總時(shí)差（工作總時(shí)差（tftf）；）；v工作自由時(shí)差（工作自由時(shí)差（ffff）。）。v工作持續(xù)時(shí)間工作持續(xù)時(shí)間(d)作業(yè)時(shí)間作業(yè)時(shí)間ti-j 單時(shí)估計(jì)法（定額法）單時(shí)估計(jì)法（定額法）v 每項(xiàng)工作只估計(jì)或規(guī)定一個(gè)確定的持續(xù)時(shí)間值的方法。一般具有每項(xiàng)工作只估計(jì)或規(guī)定一個(gè)確定的持續(xù)時(shí)間值的方法。一般具有工作的工作量，勞動(dòng)定額資料以及投入人力的多少等，計(jì)算各工工作的工作量，勞動(dòng)定額資料

8、以及投入人力的多少等，計(jì)算各工作的持續(xù)時(shí)間；作的持續(xù)時(shí)間； v 工作持續(xù)時(shí)間工作持續(xù)時(shí)間 nsrqdq 工作的工作量。以時(shí)間單位表示,如小時(shí);或以體積，重量，長(zhǎng)度等單位表示；r 可投入人力和設(shè)備的數(shù)量；s 每人或每臺(tái)設(shè)備每工作班能完成的工作量；n 每天正常工作班數(shù)?；蚓哂蓄愃乒ぷ鞯某掷m(xù)時(shí)間的歷史統(tǒng)計(jì)資料時(shí)，可以根據(jù)這些資料，采用分析對(duì)比的方法確定所需工作的持續(xù)時(shí)間。 三時(shí)估計(jì)法三時(shí)估計(jì)法v在不具備有關(guān)工作的持續(xù)時(shí)間的歷史資料時(shí)，在較在不具備有關(guān)工作的持續(xù)時(shí)間的歷史資料時(shí)，在較難估計(jì)出工作持續(xù)時(shí)間時(shí)，可對(duì)工作進(jìn)行估計(jì)三個(gè)難估計(jì)出工作持續(xù)時(shí)間時(shí)，可對(duì)工作進(jìn)行估計(jì)三個(gè)時(shí)間值，然后計(jì)算其平均值。這三個(gè)

9、時(shí)間值是：時(shí)間值，然后計(jì)算其平均值。這三個(gè)時(shí)間值是：v樂觀時(shí)間。在一切都順利時(shí)，完成工作需要的最少樂觀時(shí)間。在一切都順利時(shí)，完成工作需要的最少時(shí)間，記作時(shí)間，記作a。v最可能時(shí)間。在正常條件下，完成工作所需要時(shí)間。最可能時(shí)間。在正常條件下，完成工作所需要時(shí)間。記作記作m。v悲觀時(shí)間。在不順利條件下，完成工作需要最多時(shí)悲觀時(shí)間。在不順利條件下，完成工作需要最多時(shí)間，記作間，記作b。v 顯然上述三種時(shí)間發(fā)生都具有一定的概率，根據(jù)經(jīng)驗(yàn)，顯然上述三種時(shí)間發(fā)生都具有一定的概率，根據(jù)經(jīng)驗(yàn)，這些時(shí)間的概率分布認(rèn)為是正態(tài)分布。一般情況下，通這些時(shí)間的概率分布認(rèn)為是正態(tài)分布。一般情況下，通過專家估計(jì)法，給出三時(shí)

10、估計(jì)的數(shù)據(jù)。可以認(rèn)為：工作過專家估計(jì)法，給出三時(shí)估計(jì)的數(shù)據(jù)?？梢哉J(rèn)為：工作進(jìn)行時(shí)出現(xiàn)最順利和最不順利的情況比較少。較多是出進(jìn)行時(shí)出現(xiàn)最順利和最不順利的情況比較少。較多是出現(xiàn)正常的情況。按平均意義可用以下公式計(jì)算工作持續(xù)現(xiàn)正常的情況。按平均意義可用以下公式計(jì)算工作持續(xù)時(shí)間值：時(shí)間值： 226;64abbmad方差v工作最早開始時(shí)間工作最早開始時(shí)間es和工作最早完成時(shí)間和工作最早完成時(shí)間ef工作的最早開始時(shí)間工作的最早開始時(shí)間es是緊前工序最早結(jié)束時(shí)間。是緊前工序最早結(jié)束時(shí)間。es=te（i） ef=es+tijv工作最遲開始時(shí)間工作最遲開始時(shí)間ls與工作最遲完成時(shí)間與工作最遲完成時(shí)間lf 工作的

11、最遲完成時(shí)間工作的最遲完成時(shí)間lf是工作在不影響工期下最遲是工作在不影響工期下最遲結(jié)束時(shí)間。結(jié)束時(shí)間。lf=tl（j） ls=lf-tl(j)v最后一項(xiàng)工作的最遲完成時(shí)間最后一項(xiàng)工作的最遲完成時(shí)間lf等于其最早完成等于其最早完成時(shí)間時(shí)間ef工序工序(i, j)的時(shí)間參數(shù)的時(shí)間參數(shù)xy事件最早事件最早可能發(fā)生可能發(fā)生時(shí)間時(shí)間tei事件最遲事件最遲必須發(fā)生必須發(fā)生時(shí)間時(shí)間tl網(wǎng)絡(luò)時(shí)間的圖示法網(wǎng)絡(luò)時(shí)間的圖示法1. 節(jié)點(diǎn)時(shí)間（事件時(shí)間）節(jié)點(diǎn)時(shí)間（事件時(shí)間）事件最早可能發(fā)生時(shí)間事件最早可能發(fā)生時(shí)間te：順向求和取大：順向求和取大事件最遲必須發(fā)生時(shí)間事件最遲必須發(fā)生時(shí)間tl：反向求差取?。悍聪蚯蟛钊⌒e

12、（j）=max(te(i)+tij)tl（i）ji箭尾箭尾事項(xiàng)事項(xiàng)箭頭箭頭事項(xiàng)事項(xiàng)a（d）tijabcdmax(+)min(-)te（1）=0tl（i）=min(tl(j)-tij)tl（n）=te(n)te(i)ij開始開始完成完成可能可能必須必須最早最早最遲最遲ji箭尾箭尾事項(xiàng)事項(xiàng)箭頭箭頭事項(xiàng)事項(xiàng)a（d）tijabcd2.工序時(shí)間工序時(shí)間工序工序a3.工作時(shí)差：工作時(shí)差：指工作有機(jī)動(dòng)時(shí)間。指工作有機(jī)動(dòng)時(shí)間。 工作總時(shí)差工作總時(shí)差tf（i-j） 在不影響工期的前提下，工作所具有的機(jī)動(dòng)時(shí)間ji箭尾箭尾事項(xiàng)事項(xiàng)箭頭箭頭事項(xiàng)事項(xiàng)a（d）tijabcdijdta總時(shí)差工序工序a總時(shí)差為零的工序即關(guān)鍵

13、工總時(shí)差為零的工序即關(guān)鍵工序序ls-es=lf-efji箭尾箭尾事項(xiàng)事項(xiàng)箭頭箭頭事項(xiàng)事項(xiàng)a（d）tijabcd（2）工作自由時(shí)差）工作自由時(shí)差ff（i-j）在不影響其緊后工作在不影響其緊后工作最早開始最早開始的前提下，工序最早可能完工時(shí)間所具有的前提下，工序最早可能完工時(shí)間所具有機(jī)動(dòng)時(shí)間機(jī)動(dòng)時(shí)間atcffijij)(自由時(shí)差工序工序aji箭尾箭尾事項(xiàng)事項(xiàng)箭頭箭頭事項(xiàng)事項(xiàng)a（d）tijabcd（3）工作安全時(shí)差）工作安全時(shí)差sf（i-j）在不影響其緊后工作的在不影響其緊后工作的最遲開始最遲開始的前提下，工作所具有機(jī)動(dòng)時(shí)間的前提下，工作所具有機(jī)動(dòng)時(shí)間btdij自由時(shí)差工序工序a（2）求完工期（用標(biāo)

14、號(hào)法）1）標(biāo)出各事項(xiàng)的最早開始最早開始時(shí)間 ， -給始點(diǎn) 標(biāo) ； -給任意點(diǎn) 標(biāo) ,ej=max以 為箭頭的各箭之 “箭尾 +箭長(zhǎng)tij”10jejj2) 終點(diǎn) 的 中的t即完工期。nt1c(1)b(3)a(10)d(2)2e(7)3f(3)4g(5)5h(4)6i(4)j(3)7i(0)8k(6)l(3)9i(0)m(4)10n(7)110291217212525312538順向求和取其大順向求和取其大（3）求關(guān)鍵路（用標(biāo)號(hào)法）2）計(jì)算各工序 的時(shí)差時(shí)差r(i,j)= 的 -tij - 的 。ijji1）標(biāo)出各事項(xiàng)的最晚開始時(shí)間 ， -給終點(diǎn) 標(biāo) ； -給任意點(diǎn) 標(biāo) ,li=min以 為箭尾

15、的各箭之 “箭頭 -箭長(zhǎng)tij”niliit3）關(guān)鍵路徑：由r(i,j)= 0的關(guān)鍵工序組成的由 至 的路。n191c(1)b(3)a(10)d(2)2e(7)3f(3)4g(5)5h(4)6i(4)j(3)7i(0)8k(6)l(3)i(0)m(4)10n(7)1102912172125253125383825342521311712920min(25,34)反向求差取其小反向求差取其小1791181062345a(10)b(3)c(1)d(2)e(7)f(3)g(5)h(4)i(4)j(3)l(3)k(6)m(4)n(7)3413300034253838229912123131171721

16、21252525253829342538383131完工期t=38（天）；關(guān)鍵路：d-e-f-g-h-i-k-n。由本例可見：關(guān)鍵工序 頭尾皆有 = ，但反之未必。 關(guān)鍵工序時(shí)間之和=工期t。 課堂習(xí)題課堂習(xí)題v求下面網(wǎng)絡(luò)計(jì)劃圖中的關(guān)鍵路徑和完工期。求下面網(wǎng)絡(luò)計(jì)劃圖中的關(guān)鍵路徑和完工期。v要求使用標(biāo)號(hào)法，給出節(jié)點(diǎn)的要求使用標(biāo)號(hào)法，給出節(jié)點(diǎn)的te和和tl，工序的，工序的es、ef、ls、lf以及總時(shí)差以及總時(shí)差tf和自由時(shí)差和自由時(shí)差ff125436789a(3)b(4)c(5)d(6)f(2)h(3)e(1)g(4)i(5)小結(jié)小結(jié)v虛工序的網(wǎng)絡(luò)時(shí)間也應(yīng)計(jì)算，以判斷其是否為關(guān)虛工序的網(wǎng)絡(luò)時(shí)間也

17、應(yīng)計(jì)算，以判斷其是否為關(guān)鍵工序。（虛工作為無機(jī)動(dòng)時(shí)間的關(guān)鍵工作；否鍵工序。（虛工作為無機(jī)動(dòng)時(shí)間的關(guān)鍵工作；否則該虛工作即為有機(jī)動(dòng)時(shí)間的非關(guān)鍵工作。）則該虛工作即為有機(jī)動(dòng)時(shí)間的非關(guān)鍵工作。）v關(guān)鍵工序有關(guān)鍵工序有2條：條：adegi和和adfhiv完工期完工期te為為19天。天。3300001100125436789b(4)c(5)d(6)f(2)h(3)e(1)g(4)i(5)0 03 39 99 910 1011 1110 1014 1419 1900000000000011a(3)ite tltfff二、工序時(shí)間不確定的工程計(jì)劃網(wǎng)絡(luò)問題二、工序時(shí)間不確定的工程計(jì)劃網(wǎng)絡(luò)問題 （計(jì)劃評(píng)審技術(shù)（

18、計(jì)劃評(píng)審技術(shù)pert）的區(qū)別僅在于：與cpm1.。，服從于近似認(rèn)為但由中心極限定理，可也是隨機(jī)的。期是隨機(jī)變量，從而完工工序時(shí)間)( 2的三時(shí)估計(jì)法：確定平均工序時(shí)間，最可能時(shí)間為，最悲觀時(shí)間為設(shè)工序最樂觀時(shí)間為226 ,64 的方差為則工期方差期望工期=關(guān)鍵工序的平均工序時(shí)間之和；=關(guān)鍵工序時(shí)間方差之和。天內(nèi)完工的概率求工程在222 (,),()() ()()1( )()2ekeekkekezxtn tttttp ttpttttp zzp zzedx 由標(biāo)準(zhǔn)正態(tài)分布數(shù)值表可查得：例例2 某工程可分為某工程可分為11項(xiàng)工作，有關(guān)資料如下表：項(xiàng)工作，有關(guān)資料如下表：工作緊前工作工序時(shí)間ambab

19、cdefghijk-abbccg、hd、ef、i、j1111232111422210.55632424333171415109794（1）畫出施工網(wǎng)絡(luò)圖，確定關(guān)鍵路線及完工期te；（2）估計(jì)工程在20周內(nèi)完工的概率。工作緊前工作工序時(shí)間ambabcdefghijk-abbccg、hd、ef、i、j1111232111422210.556324243331714151097942ij2221067434340.330.330.332.672.002.001.331.331.001.3300.110.110.117.134.004.001.771.771.001.7701b(2)a(2)c(2)2d(10)e(6)35f(7)4g(4)67h(3)8i(4)j(3)9k(4)19022212561519151211117620期望工期te=19；關(guān)鍵路：a-d-j-k。33.00101.332.670.33 (2)22220.31 0.32 0.33 0.34 0.350.6217 0.6255 0.6293 0.6331 0.6338標(biāo)準(zhǔn)正態(tài)分布數(shù)值表=0.6293工程在20周內(nèi)完工的概率為0.6293。19 20課后作業(yè)課后作業(yè)p307 11.1某項(xiàng)工程