運(yùn)籌學(xué)網(wǎng)絡(luò)計劃（專業(yè)應(yīng)用）

1、第六章 網(wǎng)絡(luò)計劃引例：沏茶1324燒水（10）備茶（3）沏茶（2）洗碗（2） 以網(wǎng)絡(luò)圖的形式制定計劃，求得計劃的最優(yōu)方案。并據(jù)以組織和計劃生產(chǎn)，達(dá)到預(yù)定目標(biāo)的一種科學(xué)的管理方法。1沐風(fēng)書苑r設(shè)：有一項(xiàng)工程，分為若干道工序；已知各工序 間的先后關(guān)系，以及各工序所需時間t。 問：（1）工程完工期T=？ （2）工程的關(guān)鍵工序有哪些？問題的一般提法關(guān)鍵工序：主矛盾工序，不能延期完工 路 線： 從始點(diǎn)到終點(diǎn)的一條路關(guān)鍵路線：由關(guān)鍵工序組成的路線，是所有路線中時間 最長的路線。關(guān)鍵工序的延誤將導(dǎo)致整個項(xiàng)目完 成時間延誤相關(guān)概念：1324燒水（10）備茶（3）沏茶（2）洗碗（2）2沐風(fēng)書苑r 兩種方法的原理

2、基本一致，都是用網(wǎng)絡(luò)表示工程項(xiàng)目，以確定關(guān)鍵路線；這兩種方法的主要區(qū)別是：CPM方法對工程中各工序完工時間的估計是確定的，而PERT方法對時間估計是概率型的； PERT方法主要注重計劃中的時間問題，CPM方法在把費(fèi)用概念引人計劃控制過程中，不僅注重時間問題，而且還考慮工程的費(fèi)用和成本問題，考慮工程時間的均衡問題求解方法： 關(guān)鍵路徑法(Critical Path Methd，簡稱CPM方法) 計劃評審技術(shù)(Program Evaluation and Review Technique ，簡稱PERT法）3沐風(fēng)書苑r2.解法關(guān)鍵路徑法（CPM）分為三步：繪制工程網(wǎng)絡(luò)圖標(biāo)號法求工期T標(biāo)號法求關(guān)鍵路線

3、4沐風(fēng)書苑r準(zhǔn)備工作:將整個工程分解為若干工序確定各工序的前后順序（緊前、緊后）確定工序完成時間三點(diǎn)估計法：最樂觀時間a、最可能時間m、最悲觀時間b 一點(diǎn)估計法p1355沐風(fēng)書苑r2）圖的結(jié)構(gòu)（1）繪制工程網(wǎng)絡(luò)圖弧(箭線)： 表示工序；為工序的起點(diǎn)、終點(diǎn)結(jié)點(diǎn)：表示相鄰工序的時間分界點(diǎn)，稱事項(xiàng)相鄰?。罕硎竟ば蚯昂筱暯雨P(guān)系，稱緊 前(后)工序；權(quán)：工序的完成時間1）順序：按工序先后從左至右；1324燒水（10）備茶（3）沏茶（2）洗碗（2）只有當(dāng)事項(xiàng)的所有緊前工序完成后，事項(xiàng)的緊后工序才能開始。連接箭尾的結(jié)點(diǎn)稱為該工序的緊前事項(xiàng)連接箭頭的結(jié)點(diǎn)稱為該工序的緊后事項(xiàng)。6沐風(fēng)書苑r缺口：多個始點(diǎn)或多個終

4、點(diǎn)的現(xiàn)象。 （應(yīng)當(dāng)只有一個始點(diǎn)和終點(diǎn)）回路：方向一致的閉合鏈。3）繪圖要求：圖中不得有缺口、回路和多重邊。多重邊的處理：（1）繪制工程網(wǎng)絡(luò)圖（續(xù)）一項(xiàng)工作只能用唯一的實(shí)箭線和唯一的雙號表示。處理方法：增加虛工序。12ab12a2bb 虛工序7沐風(fēng)書苑r3）繪圖要求：（1）繪制工程網(wǎng)絡(luò)圖（續(xù)）要盡量避免弧的交叉：12345678910111213141234567891011121314編號由左到右，不能重復(fù)(每條弧上起點(diǎn)的編號數(shù)小于終點(diǎn)的編號數(shù))P135方法：箭桿刪除法 給起點(diǎn)一個編號數(shù)1，設(shè)想將該點(diǎn)為起點(diǎn)的弧都去掉，從而又有新的起點(diǎn)，依次給新的起點(diǎn)編號，反復(fù)這樣做直到終點(diǎn)已經(jīng)編號為止。8沐風(fēng)

5、書苑r例1： 某工廠進(jìn)行技術(shù)改造，需要拆掉舊廠房、建造新廠房和安排設(shè)備。這項(xiàng)改建工程可以分解為7道工序，其相關(guān)資料如下表： 工序代號工序名稱緊前工序工序時間（周）A拆遷/2B工程設(shè)計/3C土建工程設(shè)計B2.5D采購設(shè)備B6E廠房土建C、A20F設(shè)備安裝D、E4G設(shè)備調(diào)試F29沐風(fēng)書苑r工序代號工序名稱緊前工序工序時間（周）A拆遷/2B工程設(shè)計/3C土建工程設(shè)計B2.5D采購設(shè)備B6E廠房土建C、A20F設(shè)備安裝D、E4G設(shè)備調(diào)試F2A（2）B (3)C (2.5)D (6)E (20)F (4)G (2)解：12345610沐風(fēng)書苑r工序ABCDEFGHIJKLMN緊前工序_DEAFGBHBH

6、IJGCIKL所需天數(shù)103127354436347CBAD2E3F4G5H6IJIKLIMN17891011用箭稈刪除法標(biāo)號（保證箭尾號大于箭頭號)11沐風(fēng)書苑r例2：繪制工程網(wǎng)絡(luò)圖工序代號緊前工序工序時間（周）A/2B/3C/2DA3EA4工序代號緊前工序工序時間（周）FB7GB6HD 、 E4IB 、 C10JG、I3續(xù)左表解：1A (2)D (3)C (2)2E (4)3F(7)B (0)G(6)46E (0)5I (10)7J (3)H (4)8B (3)12沐風(fēng)書苑r兩種情況需要引入虛工序：兩個工序A、B有相同的始點(diǎn)和終點(diǎn)（兩個或兩個以上的工序有相同的緊前工序，又同時作為另外一工序

7、的緊前工序）四個工序A、B、X、Y有如下關(guān)系： A是X的緊前工序，A和B同時又是Y的緊前工序P134 圖6.2P134 圖6.1123456ABXYA 虛工序13沐風(fēng)書苑r工序ABCDEFGH緊前工序-AA、BBD、ED、CG、F工序時間(天)24936242練習(xí)：123467895A (2)B (4)C (9)D (3)E (6)G (4)F (2)H (2)14沐風(fēng)書苑r（2）用標(biāo)號法求工期T1）標(biāo)出各事項(xiàng)的最早開始時間 ， -給始點(diǎn) 標(biāo) ；10jEjj-給任意點(diǎn) 標(biāo) , Ej=Max以 為箭頭的各箭之 “箭尾 +箭長tij”0263136162) 終點(diǎn) 的 中的T即完工期。nT1A (2

8、)D (3)C (2)2E (4)3F(7)B (0)G(6)45E(0)6I (10)7J(3)H (4)8B (3)315沐風(fēng)書苑r0028336123313136121616（3）求關(guān)鍵路（用標(biāo)號法）1）標(biāo)出各事項(xiàng)的最晚開始時間 ，iLii - 給任意點(diǎn) 標(biāo) , Li=Min以 為箭尾的各箭之 “箭頭 - 箭長tij”nT - 給終點(diǎn) 標(biāo) ； 1A (2)D (3)C (2)2E (4)3F(7)B (0)G(6)45E(0)6I (10)7J(3)H (4)8B (3)16沐風(fēng)書苑r2）計算各工序 的總時差 R(i,j)= 的 -tij - 的 。ijji3）關(guān)鍵路徑：由R(i,j)=

9、 0的關(guān)鍵工序組成的由 至 的路。n1（3）求關(guān)鍵路（用標(biāo)號法）（不影響總工期條件下，任務(wù)可以延遲的最大幅度）00283361233131361216161A (2)D (3)C (2)2E (4)3F(7)B (0)G(6)45E(0)6I (10)7J(3)H (4)8B (3)一個工序的總時差為0意味著該工序在不影響工期前提下機(jī)動時間為0，及工序的最早開始時間也是最遲開始時間，其開始和結(jié)束時間沒有一點(diǎn)機(jī)動的余地注：關(guān)鍵工序頭尾皆有=（反之未必成立）17沐風(fēng)書苑r工序ABCDEFGH緊前工序-AA、BBD、ED、CG、F工序時間(天)24936242練習(xí)：123467895A (2)B (

10、4)C (9)D (3)E (6)G (4)F (2)H (2)00472248111110137111515171718沐風(fēng)書苑r1 計算最早開始時間(ES)與最早完工(EF)時間 從網(wǎng)絡(luò)起點(diǎn)開始, 用下列公式計算最早開始時間(tES)和最早完工時間(tEF):最早開始時間 = (緊前活動的)最早結(jié)束時間的最大值 =開始結(jié)點(diǎn)的最早時間tES (i, j) = maxk tEF (k, i)=ETi最早完工時間 = 最早開始時間 + 活動持續(xù)時間 tEF(i, j) = tES (i, j) + t (i, j)工序時間參數(shù)的計算：19沐風(fēng)書苑r2 計算最晚開始時間與最晚結(jié)束時間 從最后活動開

11、始依次按下式計算每個活動最晚結(jié)束時間 tLF 和最晚開始時間tLS 最晚結(jié)束時間= (緊后活動的) 最晚開始時間的最小值 =完成結(jié)點(diǎn)的最晚時間 tLF (i, j) = mink tLS (j, k)=LTj 最晚開始時間 = 最晚結(jié)束時間活動持續(xù)時間tLS (i, j) = tLF (i, j) - t (i, j)工序時間參數(shù)的計算(續(xù)):20沐風(fēng)書苑r3 總時差 總時差: 不影響總工期條件下，任務(wù)可以延遲的最大幅度，用R (i, j)表示: 總時差 = 最晚開始時間 最早開始時間 = 最晚結(jié)束時間 最早結(jié)束時間 R (i, j) = tLS (i, j) - tES (i, j) = t

12、LF (i, j) - tEF (i, j)p144工序時間參數(shù)的計算(續(xù)):21沐風(fēng)書苑r作業(yè):工序代號工序緊前工序工序時間A系統(tǒng)提出和研究問題無4B研究選點(diǎn)問題A7C準(zhǔn)備調(diào)研方案A10D收集資料工作安排B8E挑選、實(shí)地訓(xùn)練工作人員B、C12F準(zhǔn)備收集資料用表格C7G實(shí)地調(diào)查D、E、F5H分析準(zhǔn)備調(diào)查報告G4I任務(wù)結(jié)束H022沐風(fēng)書苑r工序代號工序緊前工序工序時間A系統(tǒng)提出和研究問題無4B研究選點(diǎn)問題A7C準(zhǔn)備調(diào)研方案A10D收集資料工作安排B8E挑選、實(shí)地訓(xùn)練工作人員B、C12F準(zhǔn)備收集資料用表格C7G實(shí)地調(diào)查D、E、F5H分析準(zhǔn)備調(diào)查報告G4I任務(wù)結(jié)束H0關(guān)鍵路線邏輯關(guān)系圖網(wǎng)絡(luò)結(jié)構(gòu)圖 A

13、4(0,1)(4,1)(11,2)(14,2)(14,4)(26,5)(31,6)(35,7)B 7C10E12D 8F 7G5H412467853041126141431353531261414140423沐風(fēng)書苑r課堂練習(xí) P150習(xí)題6.1160234756891011121314abcdefghijklmnopq142030211071225510601015257f b 工序緊前工序工序時間工序緊前工序工序時間工序緊前工序工序時間a /60gb,c7mj,k5ba14he,f12ni,l15ca20if60on2da30jd,g10pm7ea21kh25qo,p5fa10lj,k10

14、繪制網(wǎng)絡(luò)圖，關(guān)鍵路線，工期，總時差24沐風(fēng)書苑r160234756891011121314abcdefghijklmnopq142030211071225510601015257b f 152課堂練習(xí) P150習(xí)題6.125沐風(fēng)書苑r練習(xí) 為籌建某餐館，需制定計劃。將工程分為14道工序，各工序需時及先后關(guān)系如下表。試求該工程完工期T及關(guān)鍵路徑。26沐風(fēng)書苑r工序內(nèi)容緊前工序所需天數(shù)A購買爐灶及材料10B購買室內(nèi)設(shè)備3C招集工人1D選擇開業(yè)地點(diǎn)2E申請?jiān)S可得到執(zhí)照D7F修理門窗、粉刷墻壁E3G砌爐灶、水池A、F5H接通上下水道G4I安裝室內(nèi)設(shè)備B、H4J做好室內(nèi)裝飾B、H3K購進(jìn)米面及副食品I、

15、J6L張貼開業(yè)廣告G3M人員訓(xùn)練C、I4N開業(yè)前操作試驗(yàn)K、L727沐風(fēng)書苑r工序ABCDEFGHIJKLMN緊前工序_DEAFGBHBHIJGCIKL所需天數(shù)1031273544363471CBAD2E3F4G5H6IJ7I8KL9IM10N1128沐風(fēng)書苑r（2）求完工期（用標(biāo)號法）1）標(biāo)出各事項(xiàng)的最早開始時間 ， -給始點(diǎn) 標(biāo) ； -給任意點(diǎn) 標(biāo) ,Ej=Max以 為箭頭的各箭之 “箭尾 +箭長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)

16、10N(7)11029121721252531253829沐風(fēng)書苑r（3）求關(guān)鍵路（用標(biāo)號法）2）計算各工序 的時差R(i,j)= 的 -tij - 的 。ijji1）標(biāo)出各事項(xiàng)的最晚開始時間 ， -給終點(diǎn) 標(biāo) ； -給任意點(diǎn) 標(biāo) ,Li=Min以 為箭尾的各箭之 “箭頭 -箭長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)1102912172125253125383825342521311712920

17、30沐風(fēng)書苑r1C(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)1102912172125253125383825342521311712920完工期T=38（天）；關(guān)鍵路：D-E-F-G-H-I-K-N。由本例可見：關(guān)鍵工序 頭尾皆有 = ，但反之未必。 關(guān)鍵工序時間之和=工期T。 31沐風(fēng)書苑r二、工程完工期的概率分析 （計劃評審技術(shù)PERT）1、PERT與 CPM的區(qū)別：工程工期的概率分析是是時間不確定情況下PERT的主要工作CPM工序時間是確定的32沐風(fēng)書苑r 期望工期 TE =關(guān)鍵工

18、序的平均工序時間之和； 工期方差 =關(guān)鍵工序時間方差之和。由概率論的中心極限定理總工期確定平均工序時間的三點(diǎn)估計法：標(biāo)準(zhǔn)化33沐風(fēng)書苑r方法：首先計算1、 給定時間T*，求工期TT*內(nèi)完工的概率然后查表求。34沐風(fēng)書苑r例15、已知某工程網(wǎng)絡(luò)圖，以及各工序的時間參數(shù)。求工程在43天內(nèi)完工的概率。工序ambA101315B5810C7810D7911E246F81014G101215H911130.44/1.00/0.25/0.691112.1710.33498.177.8312.83tijABCDEFGH2135764TE=42.33關(guān)鍵路線I為:ACFH；解：912.837.838.1741

19、0.3312.171135沐風(fēng)書苑r例2 某工程可分為11項(xiàng)工作，有關(guān)資料如下表：工作緊前工作工序時間ambABCDEFGHIJK-ABBCCG、HD、EF、I、J1111232111422210.55632424333171415109794（1）畫出施工網(wǎng)絡(luò)圖，確定關(guān)鍵路線及完工期TE；（2）估計工程在20周內(nèi)完工的概率。36沐風(fēng)書苑r工作緊前工作工序時間ambABCDEFGHIJK-ABBCCG、HD、EF、I、J1111232111422210.556324243331714151097942221067434340.330.330.332.672.002.001.331.331.00

20、1.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。37沐風(fēng)書苑r0.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。192038沐風(fēng)書苑r2、給定概率p，求完工可能性為p的工期方法：首先查表求，使；再由解出例、上例中，

21、求完工可能性達(dá)95%的工期。解：由，查表再由解出39沐風(fēng)書苑r壓縮工程工期思路：1.向關(guān)鍵工序要時間 2.在非關(guān)鍵工序挖潛力 趕工期問題中，只有壓縮關(guān)鍵工序才能引起總工期縮短。若網(wǎng)絡(luò)圖中同時有幾條關(guān)鍵路線，則幾條關(guān)鍵路線必須 同時在各自線路上壓縮一個關(guān)鍵工序，才能縮短總工期壓縮工期步驟： 一.選擇壓縮工序 二.確定壓縮量問題：保證質(zhì)量。不增加人力，物力盡量縮短工期40沐風(fēng)書苑r一.選擇壓縮工序的步驟 1.構(gòu)建關(guān)鍵路線網(wǎng)絡(luò)，賦權(quán)為壓縮費(fèi)用率（對不可壓縮工序賦權(quán)為M,表示壓縮費(fèi)用率很大） 2.求此網(wǎng)絡(luò)最小截 3.選擇最小截上工序同時進(jìn)行壓縮二.壓縮量確定： 1.壓縮量t不超過工序上允許壓縮限度 2

22、.壓縮量不超過關(guān)鍵路長與次關(guān)鍵路長之差值（一般限制壓縮量不超過非關(guān)鍵工序最小總時差）,即壓縮量t由下式確定：41沐風(fēng)書苑r3(4,2)J101234567893(4,2)N10(4,9)FDHL 1(3,0)M3(8,2)P1(4,0)8(7,7)GK5(1,4)5(4,4)I8(3,7)B5(5,4)A1(3,0)4(2,3)E5(1,4)C7(2,6)（1）關(guān)鍵路線與工期（2）工期壓縮為18天，應(yīng)如何選擇壓縮工序和壓縮天數(shù)？（3）工期壓縮到17天，通過在(1)中所選定的壓縮工序上壓 縮3天能否達(dá)到目的什么？ 例：下圖是某工程施工網(wǎng)絡(luò)，圖中單箭線表示普通工序，箭線上的tij(Cij, dij

23、)中，tij為工序時間，Cij為該工序上每壓縮一天所需的費(fèi)用，dij為可壓縮天數(shù)。 42沐風(fēng)書苑r關(guān)鍵路線：ACF,ADG,BEG 工期TE=20天 (1).計算關(guān)鍵路、工期、總時差工序HLJNPMKI總時差331313111122553(4,2)J101234567893(4,2)N10(4,9)FDHL 1(3,0)M3(8,2)P1(4,0)8(7,7)GK5(1,4)5(4,4)I8(3,7)B5(5,4)A1(3,0)4(2,3)E5(1,4)C7(2,6)0014417202088578191010121243沐風(fēng)書苑r101347810(4,9)FD8(7,7)G8(3,7)B5

24、(5,4)A4(2,3)E5(1,4)C7(2,6)（2）構(gòu)建關(guān)鍵路線網(wǎng)絡(luò)(賦權(quán)值為費(fèi)用率)，確定最小割，選擇壓縮工序用最大流標(biāo)號法得最小割為(C, D, E)，所以選擇在工序C, D,E上壓縮時間根據(jù)非關(guān)鍵工序的總時差和壓縮工序的限制，確定壓縮量 得壓縮量為在C,D,E工序上各壓縮兩天，使總工期壓縮至18天44沐風(fēng)書苑r553(4,2)J101234567893(4,2)N10(4,9)FDHL 1(3,0)M3(8,2)P1(4,0)8(7,7)GK5(1,4)5(4,4)I8(3,7)B5(5,4)A1(3,0)2(2,1)E3(1,2)C5(2,4)001441518188855817

25、881010(3)工期壓縮2天后，關(guān)鍵路線已發(fā)生變化，所以不能在中選中的壓縮工序壓縮三天以達(dá)到工期成為17天的目的。重復(fù)上述步驟，得新的網(wǎng)絡(luò)，重新確定關(guān)鍵路線和非關(guān)鍵路線的總時差，如圖工序HLJNPM總時差3311119945沐風(fēng)書苑r1013457810(4,9)FD8(7,7)GK5(1,4)5(4,4)I8(3,7)B5(5,4)A2(2,1)E3(1,2)C5(2,4) 繼續(xù)構(gòu)建關(guān)鍵路線網(wǎng)路，確定最小割為C,D,E,K，作為壓縮工序。確定壓縮量根據(jù)非關(guān)鍵工序的總時差和壓縮工序的限制，確定壓縮量 最小時差 ，得壓縮量為在C,D,E,K工序上各壓縮1天，使總工期壓縮至17天46沐風(fēng)書苑r4

26、7沐風(fēng)書苑r工程費(fèi)用分析問題： 編制工程網(wǎng)絡(luò)計劃時，不僅要考慮工期時間，還應(yīng)到考慮工程造價 對一個工程來說，無論是以考慮工程費(fèi)用為主，還是以控制時間進(jìn)度為主，都必須對工程計劃進(jìn)行時間費(fèi)用分析，從而可綜合考慮制定最優(yōu)的計劃。48沐風(fēng)書苑r費(fèi)用概念直接費(fèi)用：指人工、材料、燃料等直接用來完成工程 任務(wù)的費(fèi)用。工序直接費(fèi)用率：指一道工序縮短單位時間所需增 加的費(fèi)用間接費(fèi)用：指管理人員的工資、辦公、采購等并非直 接用于完成工程任務(wù)的費(fèi)用。間接費(fèi)用率p:整個項(xiàng)目的工期每提前單位時間可節(jié) 約的費(fèi)用49沐風(fēng)書苑r工程的時間費(fèi)用關(guān)系圖費(fèi)用工期時間總費(fèi)用直接費(fèi)用曲線(工程的時間費(fèi)用曲線)間接費(fèi)用曲線最低成本工期TE總費(fèi)用曲線由同一工期下的直接費(fèi)用和間接費(fèi)用相加得到壓縮工期會增加直接費(fèi)用，但減少了間接費(fèi)用延長工期會增加間接費(fèi)用，但可能減少直接費(fèi)用 因此只有當(dāng)壓縮關(guān)鍵工序時間增加的直接費(fèi)用小于由此導(dǎo)致工期縮短而節(jié)約的間接費(fèi)用時，這一壓縮才進(jìn)行。50沐風(fēng)書苑r最低成本工期的確定：確定最低成本工期的步驟：一、繪制網(wǎng)絡(luò)圖，計算工序總時差R (i, j)，確定TE與關(guān)鍵路線，計算相應(yīng)工程費(fèi)用。二、在各關(guān)鍵路線上所有可壓縮的工序中，各確定一個本線路上費(fèi)用率最低的工序作為壓縮工序，這些壓縮工序之集合用I表示.一般可由1）.構(gòu)建關(guān)鍵路線網(wǎng)絡(luò)，賦權(quán)為壓縮費(fèi)用率（對不可壓縮工序賦權(quán)為M,表示壓縮費(fèi)用率很大）2）.求此網(wǎng)