應(yīng)用運(yùn)籌學(xué)-8- 網(wǎng)絡(luò)計(jì)劃- 2015

第五章網(wǎng)絡(luò)計(jì)劃 網(wǎng)絡(luò)圖 時(shí)間參數(shù)的計(jì)算 網(wǎng)絡(luò)計(jì)劃的優(yōu)化關(guān)鍵路線法，CPM(criticalpathmethod)計(jì)劃評(píng)審法，PERT(programevaluation&reviewtechnique)統(tǒng)籌法的基本原理從需要管理的任務(wù)的總進(jìn)度著眼，以任務(wù)中各工作所需的工時(shí)為時(shí)間因素，按工作的先后順序和相互關(guān)系作出網(wǎng)絡(luò)圖，以反映任務(wù)全貌，實(shí)現(xiàn)管理過(guò)程的模型化。進(jìn)行時(shí)間參數(shù)計(jì)算，找出計(jì)劃中的關(guān)鍵工作和關(guān)鍵路線，對(duì)任務(wù)的各項(xiàng)工作所需的人、財(cái)、物通過(guò)改善網(wǎng)絡(luò)計(jì)劃作出合理安排，得到最優(yōu)方案并付諸實(shí)施。對(duì)各種評(píng)價(jià)指標(biāo)進(jìn)行定量分析，在計(jì)劃實(shí)施過(guò)程中，進(jìn)行有效的監(jiān)督與控制，以保證任務(wù)優(yōu)質(zhì)優(yōu)量地完成。簡(jiǎn)介項(xiàng)目：一系列特定的能自行控制的工作，有明確的起始與結(jié)束時(shí)間。項(xiàng)目管理：計(jì)劃、組織和控制資源（人員、設(shè)備和物料），使其滿(mǎn)足項(xiàng)目的技術(shù)、成本和時(shí)間等要求。項(xiàng)目控制報(bào)告機(jī)制：項(xiàng)目進(jìn)展的信息收集處理系統(tǒng)。甘特圖、成本分解圖、時(shí)間進(jìn)度表…組織機(jī)制：項(xiàng)目的組織形式。組織結(jié)構(gòu)（職能、矩陣）、項(xiàng)目經(jīng)理、…項(xiàng)目管理背景網(wǎng)絡(luò)計(jì)劃制定的條件組成項(xiàng)目的各項(xiàng)活動(dòng)都可以作為實(shí)體加以識(shí)別（有清晰的開(kāi)始和結(jié)束時(shí)間，相互獨(dú)立）項(xiàng)目活動(dòng)序列的關(guān)系可以被確定和網(wǎng)絡(luò)化存在資源調(diào)整的可能性網(wǎng)絡(luò)計(jì)劃的編制工程任務(wù)分析（工序劃分、關(guān)系及時(shí)間估計(jì)）繪制網(wǎng)絡(luò)圖形（實(shí)、虛箭線、節(jié)點(diǎn)、線路）計(jì)算時(shí)間參數(shù)（最早、最晚開(kāi)始與結(jié)束時(shí)間）確定關(guān)鍵路線（總時(shí)差為零的工序?yàn)樽铋L(zhǎng)路線）網(wǎng)絡(luò)優(yōu)化調(diào)整（工期、時(shí)間－費(fèi)用、資源分析）項(xiàng)目網(wǎng)絡(luò)計(jì)劃網(wǎng)絡(luò)圖的構(gòu)成實(shí)箭線：表示一道具體的工序。箭頭方向表示工序進(jìn)行方向，箭尾位置表示工序開(kāi)始，箭頭位置表示工序結(jié)束。虛箭線：表示一道虛工序，虛工序僅僅表示工序與工序之間的關(guān)聯(lián)關(guān)系，不需要消耗時(shí)間和資源。工序名稱(chēng)或代碼工序時(shí)間工序名稱(chēng)或代碼網(wǎng)絡(luò)圖繪制1網(wǎng)絡(luò)圖的構(gòu)成節(jié)點(diǎn)：又稱(chēng)事項(xiàng)、事件等。表示一個(gè)工序的開(kāi)始或結(jié)束。用圓圈表示，在圈內(nèi)注上該節(jié)點(diǎn)的序號(hào)。整個(gè)網(wǎng)絡(luò)圖的開(kāi)始事項(xiàng)稱(chēng)起始節(jié)點(diǎn)，最后工序結(jié)束事項(xiàng)為結(jié)束節(jié)點(diǎn)。只有當(dāng)某一節(jié)點(diǎn)的所有緊前工序都完成后，它的緊后工序才能開(kāi)始.（A是B的緊前工序，B是A的緊后工序）路線：從起始節(jié)點(diǎn)沿箭頭方向連續(xù)不斷地到達(dá)終點(diǎn)的通路。路線有多條，路線的長(zhǎng)度為各工序的時(shí)間和，最長(zhǎng)的為關(guān)鍵路線。23AB網(wǎng)絡(luò)圖繪制繪制網(wǎng)絡(luò)圖的準(zhǔn)備工作確定目標(biāo)：以時(shí)間要求還是資源費(fèi)用要求為主工程分解：列出全部分解后的工序及代號(hào)清單工序關(guān)系：確定每一道工序的緊前工序是哪些工序時(shí)間：確定每一道工序的完成所需的時(shí)間一時(shí)估計(jì)法：僅估計(jì)一個(gè)完成工序的最大時(shí)間D三時(shí)估計(jì)法：樂(lè)觀時(shí)間a、悲觀時(shí)間b、最可能時(shí)間m網(wǎng)絡(luò)圖繪制網(wǎng)絡(luò)圖繪制規(guī)則方向、時(shí)序與節(jié)點(diǎn)編號(hào)

網(wǎng)絡(luò)圖是有向圖，按流程的順序，規(guī)定工序從左向右排列。網(wǎng)絡(luò)圖中的各個(gè)節(jié)點(diǎn)都有一個(gè)時(shí)間（某一個(gè)或若干個(gè)工序開(kāi)始或結(jié)束時(shí)間），一般按節(jié)點(diǎn)的時(shí)間順序編號(hào)（從左到右，從上到下），箭尾節(jié)點(diǎn)編號(hào)應(yīng)小于箭頭節(jié)點(diǎn)編號(hào)。始節(jié)點(diǎn)編號(hào)為1。網(wǎng)絡(luò)圖中不能出現(xiàn)缺口和回路二個(gè)節(jié)點(diǎn)之間只能有一個(gè)直接的工序

兩條箭線不能有同樣的始末節(jié)點(diǎn)，若二個(gè)事項(xiàng)之間有幾個(gè)平行進(jìn)行的工序，不許直接連接，而需要引入虛工序。

網(wǎng)絡(luò)圖繪制網(wǎng)絡(luò)圖繪制規(guī)則平行作業(yè)

有幾個(gè)工序平行作業(yè)結(jié)束后轉(zhuǎn)入下一個(gè)工序的情況下，考慮到計(jì)算網(wǎng)絡(luò)時(shí)間的方便，選擇在平行作業(yè)的幾個(gè)工序中所需時(shí)間最長(zhǎng)的一個(gè)工序，直接與其緊后工序銜接，而其它工序則通過(guò)虛工序與其緊后工序銜接。交叉作業(yè)

對(duì)需要較長(zhǎng)時(shí)間才能完成的一些工序，在工藝流程與生產(chǎn)組織條件允許的情況下，可以不必等待工序全部結(jié)束后再轉(zhuǎn)入其緊后工序，而是分期分批的轉(zhuǎn)入。分批轉(zhuǎn)入時(shí)需增加虛工序。網(wǎng)絡(luò)圖繪制網(wǎng)絡(luò)圖繪制規(guī)則始點(diǎn)和終點(diǎn)

為表示工程的開(kāi)始和結(jié)束，在網(wǎng)絡(luò)圖中只能有一個(gè)始點(diǎn)和一個(gè)終點(diǎn)。當(dāng)工程開(kāi)始時(shí)有幾個(gè)平行工序或結(jié)束時(shí)有幾個(gè)平行工序，而又不能用一個(gè)始節(jié)點(diǎn)或一個(gè)終節(jié)點(diǎn)表示時(shí)，需用虛工序把它們與始節(jié)點(diǎn)或終節(jié)點(diǎn)連接。網(wǎng)絡(luò)圖布局

盡可能將關(guān)鍵線路布置在中心位置，盡量將聯(lián)系緊密的工作布置在相近的位置；盡量用水平線或具有一段水平線的折線。網(wǎng)絡(luò)圖繪制6554虛工序應(yīng)用12AB321ABDCB4A213網(wǎng)絡(luò)圖繪制虛工序應(yīng)用12AB321ABDCBA5213546DCBA2143網(wǎng)絡(luò)圖繪制13212A12435A3A2A1444BBA:修路基B:鋪軌道A=A1+A2+A3B=B1+B2+B31212178642A1B2B1A3A2B35364312A1B2B1A3A2B35網(wǎng)絡(luò)圖繪制例5.1某化工廠管道安裝的工程進(jìn)度表:網(wǎng)絡(luò)圖繪制例5.1某化工廠管道安裝的網(wǎng)絡(luò)圖先畫(huà)出沒(méi)有緊前工序的工作A,在A后畫(huà)出緊前工序?yàn)锳的各工作,即B,C,E,F。ABCEF網(wǎng)絡(luò)圖繪制例5.1網(wǎng)絡(luò)圖的繪制在表中查出B,C為D的緊前工序，F(xiàn)為G的緊前工序，則在F工序后畫(huà)出G，在B,C工序后面畫(huà)出D。GDABCEF網(wǎng)絡(luò)圖繪制例5.1網(wǎng)絡(luò)圖的繪制畫(huà)出H,I,J的工序如下：ABCEFGDHIJH緊前：D、E、GI緊前：D、EJ緊前：H、IH除J外已沒(méi)有緊后工序網(wǎng)絡(luò)圖繪制例5.1網(wǎng)絡(luò)圖的繪制畫(huà)出K,L工序，K,L的緊前工序均為J。ABCEFGDHIJLK網(wǎng)絡(luò)圖繪制例5.1網(wǎng)絡(luò)圖的繪制在K,L后畫(huà)出M,N,P：ABCEFGDHIJLKNMPM緊前：K、LN緊前：KP緊前：M、N網(wǎng)絡(luò)圖繪制練習(xí)：畫(huà)出以下網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖繪制練習(xí)答案：15387642AHELKGDFCB60451810204015302535網(wǎng)絡(luò)圖繪制符號(hào)約定

iE(i)L(i)S(i)jE(j)L(j)S(j)KD(i,j)LFijEFijLSijESijE(1)=0L(j)E(j)L(n)=E(n)SijRij時(shí)間參數(shù)計(jì)算節(jié)點(diǎn)（事項(xiàng)）時(shí)間

節(jié)點(diǎn)本身不占用時(shí)間，它只表示某項(xiàng)工作應(yīng)在某一時(shí)刻開(kāi)始或結(jié)束，因此，節(jié)點(diǎn)參數(shù)主要只有兩個(gè)：最早實(shí)現(xiàn)時(shí)間（最早時(shí)間）和最遲實(shí)現(xiàn)時(shí)間（最遲時(shí)間）。最早時(shí)間：以該節(jié)點(diǎn)結(jié)束的工作最早可能結(jié)束的時(shí)間，或以該節(jié)點(diǎn)開(kāi)始的工作最早可能開(kāi)始的時(shí)間。E(1)=0,E(n)為工程時(shí)間，從左往右計(jì)算。最遲時(shí)間：允許所有后續(xù)工序都能及時(shí)開(kāi)始的最晚時(shí)間。L(n)=E(n),L(1)=0，從右往左計(jì)算。時(shí)間參數(shù)計(jì)算節(jié)點(diǎn)（事項(xiàng)）時(shí)間計(jì)算節(jié)點(diǎn)最早時(shí)間E(j)的計(jì)算E(1)=0E(j)=max[E(i)+D(i,j)],i=2,3,4,……98767E(7)=5E(8)=6E(9)=MAX[E(7)+6,E(8)+7)]=13時(shí)間參數(shù)計(jì)算節(jié)點(diǎn)（事項(xiàng)）時(shí)間計(jì)算節(jié)點(diǎn)最遲時(shí)間L(i)的計(jì)算L(n)=E(n)L(i)=MIN[L(j)-D(i,j)],j=n-1,n-2,……911102012L(10)=70L(11)=89L(9)=MIM[L(10)-20,L(11)-12)]=50時(shí)間參數(shù)計(jì)算543561267243EDCBAF1點(diǎn)的開(kāi)始時(shí)刻為0；2點(diǎn)的最早時(shí)間為2；3點(diǎn)的最早時(shí)間為5；4點(diǎn)的最早時(shí)間為6；5點(diǎn)的最早時(shí)間為12；6點(diǎn)的最早時(shí)間為19；6點(diǎn)的最遲時(shí)間為19；5點(diǎn)的最遲時(shí)間為12；3點(diǎn)的最遲時(shí)間為7；4點(diǎn)的最遲時(shí)間為6；2點(diǎn)的最遲時(shí)間為2；1點(diǎn)的最遲時(shí)間為0。

00

22

1212

5

7

191966例5.2節(jié)點(diǎn)時(shí)間計(jì)算工序時(shí)間參數(shù)計(jì)算

一個(gè)工序可以從箭尾節(jié)點(diǎn)的最早時(shí)間開(kāi)始作業(yè)，也可以適當(dāng)推遲開(kāi)始，但須在箭頭節(jié)點(diǎn)的最遲時(shí)間內(nèi)完工才不至于延誤后續(xù)工序，因此工序時(shí)間就包括最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間，加上或減去該工序的作業(yè)時(shí)間，相應(yīng)地還有最早結(jié)束時(shí)間和最遲結(jié)束時(shí)間。最早開(kāi)始時(shí)間:ESij=E(i)最早結(jié)束時(shí)間：EFij=ESij+D(i,j)最遲結(jié)束時(shí)間：LFij=L(j)最遲開(kāi)始時(shí)間：LSij=LFij-D(i,j)時(shí)間參數(shù)計(jì)算時(shí)差及計(jì)算節(jié)點(diǎn)時(shí)差：最遲與最早時(shí)間差

S(i)=L(i)－E(i)工序總時(shí)差：不影響工期(最早結(jié)束時(shí)間）的該工序可松動(dòng)的時(shí)間（可以推遲開(kāi)始的時(shí)間）.Sij=LSij－ESij=LFij－EFij

=L(j)－E(i)－D(i,j)（總浮動(dòng)）工序單時(shí)差：不影響緊后工序最早可能開(kāi)始條件下，工序最早可能完工時(shí)間可以推遲的時(shí)間.Rij=E(j)－EFij（自由浮動(dòng)）時(shí)間參數(shù)計(jì)算工序及時(shí)差關(guān)系工序AES工序A的緊后工序ESEFLFLFEFLSLS總時(shí)差SA單時(shí)差RA(自由浮動(dòng))D時(shí)間參數(shù)計(jì)算關(guān)鍵線路關(guān)鍵線路的長(zhǎng)度決定了工程周期，關(guān)鍵線路可以有多條，計(jì)劃安排得越緊湊，關(guān)鍵線路越多。關(guān)鍵線路的確定破“圈”法：在“圈”中去掉最短的一個(gè)工序。圖上作業(yè)法：標(biāo)注節(jié)點(diǎn)時(shí)間，通常情況下，節(jié)點(diǎn)時(shí)差為0的節(jié)點(diǎn)組成關(guān)鍵線路。表上作業(yè)法：計(jì)算工序時(shí)間，總時(shí)差為0的工序組成關(guān)鍵線路。線性規(guī)劃法：最大允許時(shí)間法和影子價(jià)格法關(guān)鍵線路的確定破圈法：15387642AHELKGDFCB60451810204015302535關(guān)鍵線路A-D-G-K-L(1-2-4-6-7-8),長(zhǎng)度為170例5.4關(guān)鍵線路的確定圖上標(biāo)注法15387642AHELKGDFCB60451810204015302535060708010011013517017013511012080117600關(guān)鍵線路的確定表上作業(yè)法關(guān)鍵線路的確定參照最短路徑的方法，假設(shè)網(wǎng)絡(luò)圖中的總流量為1，將每個(gè)工序的作業(yè)時(shí)間作為單位流量費(fèi)用，求這一個(gè)流量通過(guò)網(wǎng)絡(luò)的最大費(fèi)用，所經(jīng)過(guò)的弧即為關(guān)鍵工序，按順序連在一起即為關(guān)鍵路徑，求得的最大費(fèi)用（最長(zhǎng)距離）即為項(xiàng)目的最早完工時(shí)間。根據(jù)各個(gè)節(jié)點(diǎn)的凈流量條件，目標(biāo)為總經(jīng)過(guò)的時(shí)間最長(zhǎng)。線性規(guī)劃法求關(guān)鍵線路(1)15387642AHELKGDFCB60451810204015302535例5.4線性規(guī)劃法確定關(guān)鍵線路例5.4：設(shè)fij表示通過(guò)節(jié)點(diǎn)(i,j)的流量，根據(jù)題意求關(guān)鍵線路的線性規(guī)劃模型(1)畫(huà)出網(wǎng)絡(luò)圖例5.4決策變量：各節(jié)點(diǎn)的發(fā)生時(shí)間（項(xiàng)目起始時(shí)刻為0，節(jié)點(diǎn)的最早時(shí)間）；目標(biāo)函數(shù)：最后一個(gè)節(jié)點(diǎn)的發(fā)生（完成）時(shí)間最早；約束條件：各個(gè)活動(dòng)的實(shí)際持續(xù)時(shí)間應(yīng)不小于完成活動(dòng)所需時(shí)間；某活動(dòng)實(shí)際持續(xù)時(shí)間＝某活動(dòng)結(jié)束時(shí)間－開(kāi)始時(shí)間線性規(guī)劃法求關(guān)鍵線路(2)例5.4：設(shè)xi表示通過(guò)節(jié)點(diǎn)i的最早時(shí)間，根據(jù)題意求關(guān)鍵線路的線性規(guī)劃模型(2)建立活動(dòng)--節(jié)點(diǎn)矩陣，對(duì)任一節(jié)點(diǎn)，箭頭進(jìn)入為+1，箭頭流出為-1。利用該矩陣元素與相應(yīng)變量之間的乘積和計(jì)算各工序的時(shí)間。關(guān)鍵線路判斷：作業(yè)時(shí)間影子價(jià)格為1的工序（為什么？）或?qū)嶋H持續(xù)時(shí)間與完成活動(dòng)所需時(shí)間相等的工序?yàn)殛P(guān)鍵線路上的工序。線性規(guī)劃法求關(guān)鍵線路(2)線性規(guī)劃方法求關(guān)鍵線路舉例網(wǎng)絡(luò)圖的調(diào)整及優(yōu)化縮短工程計(jì)劃工期問(wèn)題

保證質(zhì)量和不增加人力物力的前提下盡量縮短工期。注意關(guān)鍵線路的變化。壓縮關(guān)鍵工序的工序時(shí)間

在關(guān)鍵工序上采取改進(jìn)技術(shù)、工藝和設(shè)備等措施，優(yōu)先保證關(guān)鍵工序所需，矛盾時(shí)非關(guān)鍵線路應(yīng)盡可能讓路。在非關(guān)鍵工序上盡量挖掘潛力

利用非關(guān)鍵線路上的時(shí)差進(jìn)行合理調(diào)度，抽調(diào)資源支援關(guān)鍵線路。采用平行或交叉作業(yè)例5.5縮短計(jì)劃工期某工程有關(guān)的工序關(guān)系及時(shí)間如下：例5.5縮短計(jì)劃工期畫(huà)出網(wǎng)絡(luò)圖：153109742ALDMJFCHB264354524386GE1例5.5縮短計(jì)劃工期計(jì)算時(shí)間參數(shù)，確定關(guān)鍵線路：153109742ALDMJFCHB264354524386GE10182576119915181510101198520關(guān)鍵線路A-B-E-H-M(1-2-3-6-9-10),長(zhǎng)度為18例5.5縮短計(jì)劃工期現(xiàn)要求將整個(gè)計(jì)劃工期縮短3天。首先從關(guān)鍵線路上想辦法，能否縮短3天？也要考慮其它非關(guān)鍵線路上工時(shí)縮短的情況。具體做法如下：將圖中的最后一個(gè)節(jié)點(diǎn)的最遲時(shí)間設(shè)定為15倒退計(jì)算法求出各工作的時(shí)差找出所有時(shí)差為負(fù)值的工序?qū)ζ渲械年P(guān)鍵工序進(jìn)行協(xié)調(diào)，縮短工作時(shí)間，使總時(shí)間為15天重新計(jì)算時(shí)間，如仍有負(fù)時(shí)差工序，再考慮縮短該工序的時(shí)間，直到?jīng)]有負(fù)時(shí)差為止。例5.5縮短計(jì)劃工期將第10節(jié)點(diǎn)的最遲時(shí)間設(shè)定為15，計(jì)算各工序時(shí)差153109742ALDMJFCHB264354524386GE101525761199151812778652－1－3-3-2-1-30-2-30-2-3-31515例5.5縮短計(jì)劃工期從圖中可以看出：在原關(guān)鍵線路上各工序的總時(shí)差均為－3，因此需要在原來(lái)的關(guān)鍵線路上縮短3天。除了原先關(guān)鍵線路上是負(fù)時(shí)差外，在其它非關(guān)鍵線路上也出現(xiàn)負(fù)時(shí)差，在這些線路上也要進(jìn)行日期的縮短。共有以下幾條需要縮短：第一條：1－2－3－6－9－10縮短3天第二條：2－4－7－8－9縮短2天第三條：7－9縮短1天必須滿(mǎn)足以上條件才有可能縮短3天例5.5縮短計(jì)劃工期先考慮關(guān)鍵線路縮短3天，經(jīng)協(xié)調(diào)使B、M、E各減1天；B和M工序各縮短為2天；E工序縮短為5天重新計(jì)算時(shí)間例5.5縮短計(jì)劃工期關(guān)鍵路線工序時(shí)間縮短后，重新計(jì)算時(shí)間：153109742ALDMJFCHB26425452438