運(yùn)籌學(xué)課件：6網(wǎng)絡(luò)計(jì)劃a

1、第6章 網(wǎng)絡(luò)計(jì)劃引例：沏茶1324燒水（10）備茶（3）沏茶（2）洗碗（2）第6章 網(wǎng)絡(luò)計(jì)劃網(wǎng)絡(luò)計(jì)劃方法一般由兩個(gè)階段組成：初始計(jì)劃階段和計(jì)劃方案調(diào)整階段。初始計(jì)劃階段將工程項(xiàng)目劃分為多個(gè)相互銜接的工序，估計(jì)工序的完工時(shí)間，然后用網(wǎng)絡(luò)圖表示，按計(jì)劃時(shí)間參數(shù)確定完成項(xiàng)目的個(gè)關(guān)鍵工序及由其組成的關(guān)鍵線路，擬定一初始計(jì)劃方案。該階段包括網(wǎng)絡(luò)圖繪制和關(guān)鍵線路確定兩個(gè)環(huán)節(jié)。計(jì)劃方案調(diào)整階段根據(jù)要求，綜合考慮時(shí)間、費(fèi)用、資源等目標(biāo)，對(duì)初始計(jì)劃方案進(jìn)行調(diào)整改善，直至得出一滿意的計(jì)劃方案。一、工序時(shí)間確定的工程計(jì)劃網(wǎng)絡(luò)問(wèn)題 問(wèn)題的一般提法 設(shè)：有一項(xiàng)工程，包括許多彼此關(guān)聯(lián)的獨(dú)立活動(dòng)組成，這些活動(dòng)稱為工序；已知

2、各工序間的先后關(guān)系，以及各工序所需時(shí)間t。 問(wèn)：（1）工程完工期T=？ （2）工程的關(guān)鍵工序有哪些？第6章 網(wǎng)絡(luò)計(jì)劃求解方法關(guān)鍵路徑法（CPM）分為三步： 繪制工程網(wǎng)絡(luò)圖 標(biāo)號(hào)法求工期 T 標(biāo)號(hào)法求關(guān)鍵路線雙代號(hào)網(wǎng)絡(luò)圖示例ij工序名稱(工序持續(xù)時(shí)間)單代號(hào)網(wǎng)絡(luò)圖示例工作代號(hào)工作名稱持續(xù)時(shí)間1.1 構(gòu)成網(wǎng)絡(luò)圖的三要素：（雙代號(hào)）（1）箭線（工序，工作）在網(wǎng)絡(luò)圖中，帶箭頭的線段，稱箭線。箭線表示的具體內(nèi)容取決于網(wǎng)絡(luò)圖的祥略程度。箭線代表整個(gè)工序的全過(guò)程，要消耗時(shí)間及各種資源，一般在網(wǎng)絡(luò)圖上表注的是消耗時(shí)間的數(shù)量。 實(shí)箭線表示具體工序，虛箭線表示虛工序，僅表示工序與工序之間的關(guān)聯(lián)，不需要消耗時(shí)間、費(fèi)

3、用和資源。（2）結(jié)點(diǎn)（事項(xiàng)）前后兩工序的交點(diǎn)，表示工序的開(kāi)始、結(jié)束和連接關(guān)系。是瞬間概念，不消耗時(shí)間和資源。用 表示。第一個(gè)節(jié)點(diǎn)，稱始結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)稱終結(jié)點(diǎn)；其它節(jié)點(diǎn)稱中間結(jié)點(diǎn)。節(jié)點(diǎn)沿箭線由左到右從小到大。i前后兩工序的交點(diǎn)，表示工序的開(kāi)始、結(jié)束和連接關(guān)系。是瞬間概念，不消耗時(shí)間和資源。用 表示。第一個(gè)節(jié)點(diǎn)，稱始結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)稱終結(jié)點(diǎn)；其它節(jié)點(diǎn)稱中間結(jié)點(diǎn)。節(jié)點(diǎn)沿箭線由左到右從小到大。i一項(xiàng)工序中與箭尾銜接的結(jié)點(diǎn)，稱工序的緊前事項(xiàng)。 一項(xiàng)工序中與箭頭銜接的結(jié)點(diǎn)，稱工序的緊后事項(xiàng)。工序的緊前工序：A工序的箭頭與B工序的緊前事項(xiàng)銜接，則A為B的緊前工序。工序的緊后工序：B工序的箭尾與A工序的

4、緊后事項(xiàng)銜接，則B為A的緊后工序。 事項(xiàng)的緊前工序：用箭頭與事項(xiàng)連接的工序。事項(xiàng)的緊后工序：用箭尾與事項(xiàng)連接的工序。（3）線路 指網(wǎng)絡(luò)圖中從始節(jié)點(diǎn)到終節(jié)點(diǎn)之間可連通的線路。1324燒水（10）備茶（3）沏茶（2）洗碗（2）1）順序：按工序先后從左至右；2）要求：圖中不得有缺口、回路和多重邊。缺口：多個(gè)始點(diǎn)或多個(gè)終點(diǎn)的現(xiàn)象。 （應(yīng)當(dāng)只有一個(gè)始點(diǎn)和終點(diǎn)）1.2 網(wǎng)絡(luò)圖的繪制：（雙代號(hào)）多重邊：兩點(diǎn)間有多于一條的邊。AB處理方法：增加虛工序。AAB回路：方向一致的閉合鏈。處理方法：增加虛工序。多個(gè)始點(diǎn)或多個(gè)終點(diǎn)：例 P134 表6.123674589A B C D E G F H 1工作ABCDEF

5、GH緊前工作-AA,BB D,ED,CG,F工序代號(hào)緊前工序工序時(shí)間（周）A/2B/3C/2DA3EA4工序代號(hào)緊前工序工序時(shí)間（周）FB7GB6HD 、 E4IB 、 C10JG、I3例：繪制工程網(wǎng)絡(luò)圖續(xù)左表解：1A (2)D (3)C (2)2E (4)3F(7)B (0)G(6)45E(0)6I (10)7J(3)H (4)8B (3)練習(xí) 為籌建某餐館，需制定計(jì)劃。將工程分為14道工序，各工序需時(shí)及先后關(guān)系如下表。試?yán)L制工程網(wǎng)絡(luò)圖。工序內(nèi)容緊前工序所需天數(shù)A購(gòu)買爐灶及材料10B購(gòu)買室內(nèi)設(shè)備3C招集工人1D選擇開(kāi)業(yè)地點(diǎn)2E申請(qǐng)?jiān)S可得到執(zhí)照D7F修理門窗、粉刷墻壁E3G砌爐灶、水池A、F5

6、H接通上下水道G4I安裝室內(nèi)設(shè)備B、H4J做好室內(nèi)裝飾B、H3K購(gòu)進(jìn)米面及副食品I、J6L張貼開(kāi)業(yè)廣告G3M人員訓(xùn)練C、I4N開(kāi)業(yè)前操作試驗(yàn)K、L7工序ABCDEFGHIJKLMN緊前工序_DEAFGBHBHIJGCIKL所需天數(shù)1031273544363471CBAD2E3F4G5H6IJ7I8KL9IM10N111234569781011網(wǎng)絡(luò)圖編號(hào)方法 箭桿刪除法：首先給起點(diǎn)（總開(kāi)工事項(xiàng)）以編號(hào)1，接著設(shè)想從起點(diǎn)流出的箭線刪除，得到一個(gè)或幾個(gè)不為任何有向邊終點(diǎn)的結(jié)點(diǎn)（不為任何箭線箭頭的結(jié)點(diǎn)），對(duì)它們逐一順序編號(hào)（這些結(jié)點(diǎn)之間的編號(hào)大小的順序是無(wú)關(guān)緊要的），然后把這些新編號(hào)結(jié)點(diǎn)流出的箭線刪除

7、，又得一些不為任何箭線終點(diǎn)的結(jié)點(diǎn)，同樣逐一編號(hào)，如此繼續(xù)進(jìn)行，直到最后一個(gè)結(jié)點(diǎn)（即總完工事項(xiàng)）被編上號(hào)為止。練習(xí) P150習(xí)題6.1160234756891011121314abcdefghijklmnopq142030211071225510601015257f b 1.3時(shí)間參數(shù)計(jì)算與關(guān)鍵路線確定工序（i，j）的時(shí)間參數(shù)：最早開(kāi)始時(shí)間 ESi-j （Earliest Start Time）最早完成時(shí)間 EFi-j （Earliest Finish Time）最遲完成時(shí)間 LFi-j （Latest Finish Time）最遲開(kāi)始時(shí)間 LSi-j （Latest Start Time）總時(shí)

8、差 TFi-j （Total Floating Time）自由時(shí)差 FFi-j （Free Floating Time）最早開(kāi)始時(shí)間 ESi-j （Earliest Start Time） 工序（i，j）在其所有的緊前工序都完成而可以開(kāi)始的最早時(shí)間最早完成時(shí)間 EFi-j （Earliest Finish Time） 工序（i，j）在其所有的緊前工序都完成而可以完成的最早時(shí)間EFi-j =ESi-j+Di-j例:計(jì)算23674589A2B4C9D3E6G4F2H2100244111015ES練習(xí)：P137圖6.8例:計(jì)算23674589A2B4C9D3E6G4F2H21241171015121

9、7最后結(jié)束工序的最早完成時(shí)間稱為計(jì)算工期，記Tc。還可以利用公式：EFi-j =ESi-j+Di-jTc=17EF練習(xí)：P137圖6.8最遲完成時(shí)間 LFi-j （Latest Finish Time） 在不影響工期的前提下，工序（i，j）最遲必須完成的時(shí)間最遲開(kāi)始時(shí)間 LSi-j （Latest Start Time） 在不影響工期的前提下，工序（i，j）最遲必須開(kāi)始的時(shí)間LSi-j =LFi-j-Di-j例:計(jì)算23674589A2B4C9D3E6G4F2H2117Tc=17151513111127LF練習(xí)：P137圖6.8例:計(jì)算23674589A2B4C9D3E6G4F2H2115Tc

10、S練習(xí)：P137圖6.8總時(shí)差 TFi-j （Total Floating Time） 在不影響工期的前提下，工序（i，j）所具有的機(jī)動(dòng)時(shí)間TFi-j = LFi-j - ESi-j-Di-j = LFi-j -EFi-j自由時(shí)差 FFi-j （Free Floating Time） 在不影響緊后工序最早開(kāi)始的前提下，工序（i，j）所具有的機(jī)動(dòng)時(shí)間FFi-j =（緊后工序最早開(kāi)始時(shí)間的最小值）-ESi-j-Di-j = （緊后工序最早開(kāi)始時(shí)間的最小值）-EFi-j例:計(jì)算23674589A2B4C9D3E6G4F2H21171515131111270024411101

11、523674589A2B4C9D3E6G4F2H21LFES00304303TFTFi-j=LFi-j-ESi-j-Di-j例如：工序D的最早開(kāi)始時(shí)間是第4天，最遲完成時(shí)間是第11天，D需要3天完成，因此D具有11-4-3天的機(jī)動(dòng)時(shí)間。練習(xí)：P137圖6.8例:計(jì)算23674589A2B4C9D3E6G4F2H2100244111015241171015121723674589A2B4C9D3E6G4F2H21ESEF0003003FF0FFi-j =（緊后工序最早開(kāi)始時(shí)間的最小值）-EFi-j例如：工序D的后續(xù)工序有G和F，其最早開(kāi)始時(shí)間分別問(wèn)第11天和第10天，因此在不影響工序F最早開(kāi)始的

12、前提下，D的機(jī)動(dòng)時(shí)間為10-7=3天。練習(xí)：P137圖6.8結(jié)點(diǎn)i的時(shí)間參數(shù)：最早時(shí)間 ETi 結(jié)點(diǎn)i所代表的事項(xiàng)最早可能發(fā)生的時(shí)間 最遲時(shí)間 LTi 結(jié)點(diǎn)i所代表的事項(xiàng)在不影響工期的前提下最遲必須發(fā)生的時(shí)間。求出工期后反推得到。結(jié)點(diǎn)i表示工序A和B完成而工序C和D開(kāi)始結(jié)點(diǎn)i的最早時(shí)間ETi等于以結(jié)點(diǎn)i為起始點(diǎn)的工序C和D的最早開(kāi)始時(shí)間，也等于以結(jié)點(diǎn)i為完成結(jié)點(diǎn)的工序A和B最早都完成時(shí)間（即A與B最早完成時(shí)間的最大值）iABCD結(jié)點(diǎn)i的最遲時(shí)間 LTi等于以結(jié)點(diǎn)i為完成結(jié)點(diǎn)的工序A和B的最遲完成時(shí)間；也等于以結(jié)點(diǎn)i為開(kāi)始結(jié)點(diǎn)的工序C和D的最遲開(kāi)始時(shí)間的最小值例計(jì)算最早時(shí)間 ET23674589

13、A2B4C9D3E6G4F2H210244111071517練習(xí)：P137圖6.8例 計(jì)算最遲時(shí)間 LT23674589A2B4C9D3E6G4F2H2117151111132780練習(xí)：P137圖6.8 工序（i，j）的最早開(kāi)始時(shí)間等于該工序開(kāi)始結(jié)點(diǎn)的最早時(shí)間，即ESi-j = ETi 工序（i，j）的最早完成時(shí)間等于該工序開(kāi)始結(jié)點(diǎn)的最早時(shí)間加上工序時(shí)間，即EFi-j = ETi + Di-j 工序（i，j）的最遲完成時(shí)間等于該工序完成結(jié)點(diǎn)的最遲時(shí)間，即LFi-j = LTj 工序（i，j）的最遲開(kāi)始時(shí)間等于該工序完成結(jié)點(diǎn)的最遲時(shí)間減去工序時(shí)間，即LSi-j = LTj - Di-j 工序（

14、i，j）的總時(shí)差等于該工序完成結(jié)點(diǎn)的最遲時(shí)間減去開(kāi)始結(jié)點(diǎn)的最早時(shí)間再減去工序時(shí)間，即 TFi-j = LTj - ETi - Di-j關(guān)鍵工序一個(gè)工序的總時(shí)差為0意味著該工序在不影響工期前提下機(jī)動(dòng)時(shí)間為0，即該工序的最早開(kāi)始時(shí)間也是最遲開(kāi)始時(shí)間，其開(kāi)始和結(jié)束時(shí)間沒(méi)有一點(diǎn)機(jī)動(dòng)的余地，它的工序時(shí)間的任何延長(zhǎng)都會(huì)引起工期的延后，這樣的工序稱為關(guān)鍵工序。關(guān)鍵線路由關(guān)鍵工序構(gòu)成的由網(wǎng)絡(luò)計(jì)劃始點(diǎn)到終點(diǎn)的線路稱為關(guān)鍵線路。關(guān)鍵線路也是從始點(diǎn)到終點(diǎn)時(shí)間最長(zhǎng)的線路，其長(zhǎng)度就是計(jì)算工期。2、用標(biāo)號(hào)法求工期 T步驟：（1）標(biāo)出各事項(xiàng)的最早時(shí)間（2）終點(diǎn)即為工期的標(biāo)號(hào)T1A (2)D (3)C (2)2E (4)3F

15、(7)B (0)G(6)45E(0)6I (10)7J(3)H (4)8B (3)0233ETj 、給任意事項(xiàng)標(biāo)， ETj =max以”為箭頭的各箭之“箭尾+箭長(zhǎng)Di-j661316、給始點(diǎn)標(biāo)03、用標(biāo)號(hào)法求關(guān)鍵路線步驟：1A (2)D (3)C (2)2E (4)3F(7)B (0)G(6)45E(0)6I (10)7J(3)H (4)8B (3)0233661316（1）標(biāo)出各事項(xiàng)的最遲時(shí)間T、給終點(diǎn)標(biāo)1612813330LTi=min以”為箭尾的各箭之“箭頭 箭長(zhǎng) 、給任意事項(xiàng)標(biāo)， 12LTiDi-j注：關(guān)鍵工序頭尾皆有=（反之未必成立）TFi-j =的的（2）計(jì)算各工序的總時(shí)差TFi-j ：則關(guān)鍵工序?yàn)門Fi-