《運籌學(第三版)》第7章 網(wǎng)絡計劃技術

運籌帷幄之中決勝千里之外運籌學課件網(wǎng)絡計劃技術NetworkAnalysis第1頁第7章網(wǎng)絡計劃技術§7.1網(wǎng)絡計劃圖§7.2時間參數(shù)與關鍵路線§7.3網(wǎng)絡計劃的優(yōu)化2§7.1

網(wǎng)絡計劃圖1.基本術語2.箭線圖的繪制方法

箭線圖的繪制

例題

注意的問題3.節(jié)點圖

網(wǎng)絡計劃圖是在一個圖上標注表示時間參數(shù)的進度計劃圖，實質(zhì)上就是有時序的有向賦權圖。3節(jié)點和箭線：節(jié)點和箭線是網(wǎng)絡的基本組成元素，箭線是一段帶箭頭的射線，節(jié)點是箭線的兩端連接點。工作(也稱工序、活動或工作)：是指將整個項目按需要的粗細程度分解成若干需要消耗時間或其他資源的子項目或單元，每個子項目或單元就看成是一項工作，工作是網(wǎng)絡圖的基本組成部分。緊前工作（也叫前序工作）：工作A必須在工作B結束后開始，則稱工作B是工作A的緊前工作。事件：標志某項工作的開始或結束，本身不消耗時間和資源，某一事件的發(fā)生標志著一些工作的結束和另一些工作的開始。路線：是指從開始事件到最終事件的由各項工作連貫組成的一條路。網(wǎng)絡計劃圖的關鍵問題是描述各項工作以及各項工作之間的先后關系，根據(jù)描述方法的不同，網(wǎng)絡圖可以分為兩類：箭線圖和節(jié)點圖。******基本概念*****4----箭線圖的繪制方法

在箭線圖中各項工作或活動都用箭線表示，箭線的前后節(jié)點分別表示工作開始時刻和結束時刻，箭頭邊的數(shù)字表示活動的時間或成本，如圖7.1.1所示圖7.1.1工作§7.1

網(wǎng)絡計劃圖5各項活動或工作的前后關系，有箭頭的位置表示，例如圖中有a和b兩項工作，工作b須等待其前項工作完成后才能開始，如圖7.1.2所示。圖7.1.2箭線圖在整個箭線圖中每個節(jié)點代表著一個事件，只有一個節(jié)點表示項目開始事件，一個節(jié)點表示項目結束事件，把表示工作的箭線和表示事件的節(jié)點根據(jù)工作的先后關系連接起來就構成了一個完整的箭線圖。----箭線圖的繪制方法§7.1

網(wǎng)絡計劃圖6----例題7.1.1例7.1.1某項工程由11項工作組成（分別用代碼A，B，C，…，K表示），其中完成時間及相互關系如表7.1.1所示。試畫出該項目的箭線圖。工作ABCDEFGHIJK完成時間5101144152135251520緊前工作無無無BAC,DB,EB,EB,EF,G,IF,G§7.1

網(wǎng)絡計劃圖7----畫例題7.1.1中箭線圖的步驟解

第1步：畫出表示項目開始事件的節(jié)點。第2步：找出沒有緊前工作的工作，一開始事件的節(jié)點為起始節(jié)點，分別畫出表示這些工作的箭線。如圖7.1.3所示。圖7.1.3§7.1

網(wǎng)絡計劃圖8第3步:對于有緊前工作的工作，依次找出表示其緊前工作結束事件的節(jié)點，并依次節(jié)點為起始節(jié)點畫出表示該工作的箭線。為了表示幾個緊前工作同時結束事件，在圖中引入虛擬工作的概念，這種工作只是表示事件的前后關系，不消耗時間和資源。如圖7.1.4所示圖7.1.4----畫例題7.1.1中箭線圖的步驟§7.1

網(wǎng)絡計劃圖9第4步：引入最后節(jié)點表示項目結束事件，所有沒有后續(xù)箭線的節(jié)點通過虛擬工作與項目結束節(jié)點連接。如圖7.1.5所示。圖7.1.5----畫例題7.1.1中箭線圖的步驟§7.1

網(wǎng)絡計劃圖10第5步：刪除虛擬工作，或者對節(jié)點進行合并，把對應的虛擬工作去掉，并對節(jié)點重新編號，圖形進一步簡化為圖7.1.8。圖7.1.8----畫例題7.1.1中箭線圖的步驟§7.1

網(wǎng)絡計劃圖11-----注意的問題

在箭線圖編制過程中迎注意以下幾個問題：（1）在箭線圖中，除起點和終點外，其間各項工作都必須前后銜接，不可有中斷的缺口（2）網(wǎng)絡圖中，如果有循環(huán)現(xiàn)象，將造成邏輯上的錯誤，致使某項工作永遠無起點或終點。（3）虛擬工作的應用為了表達個別工作與其前項工作的關系，可以設計虛擬工作。虛擬工作除了使工作間的關系表達清晰外，尚用于以下場合：1表示兩個工作可以同時開始，或可以同時并行實施，待兩者完成后，再開始另一工作。2表達整個計劃的完成或開始。（4）節(jié)點編號一般采用偶數(shù)順序進行，原因是當中間需要添加節(jié)點時有預留編號?！?.1

網(wǎng)絡計劃圖12----節(jié)點圖箭線圖是統(tǒng)籌方法網(wǎng)絡圖的基本結構，其應用極為普遍。其最大的缺點是為了完整地表達前后銜接關系，有時需要增加虛擬工作。工作節(jié)點圖（ActivityonNodeDiagram簡稱AND）是一種改進的結構，可以避免使用虛擬工作。這種方法以節(jié)點表示工作，以箭線表示緊前關系，如果工作a是工作b的緊前工作，就從節(jié)點a到節(jié)點b畫一條箭線。例如§7.1

網(wǎng)絡計劃圖13例7.1.1的節(jié)點圖如圖7.1.13:圖7.1.13節(jié)點圖對于箭線圖而言結構簡單，編制方便，而且工作的先后關系一目了然。但其缺點是不能直接表示出項目開始和結束的時刻以及不同工作的起始和結束的事件，在后面的事件計算中不很方便----節(jié)點圖§7.1

網(wǎng)絡計劃圖14§7.2

時間參數(shù)與關鍵路線工作持續(xù)時間

單時估計法

三時估計法節(jié)點時間工作時間關鍵路線15工作持續(xù)時間—單時估計法16工作持續(xù)時間—三時估計法17節(jié)點時間18工作時間19關鍵路線

由關鍵節(jié)點和關鍵工作順序連接形成一條路線，稱為關鍵路線。例7.1.1的關鍵路線如圖7.2.4所示圖7.2.420關鍵路線的例題v2v1v3v4v5v8v6v7v9a1=6a4=1a7=8a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4v2v7v6v5v4v1v3v9v8ve[k]vl[k]0645771514181814161078660ve[k]是指從始點開始到頂點k的最大路徑長度.vl[k]是指在不推遲整個工期的前提下,事件k允許的最晚發(fā)生時間.21v2v1v3v4v5v8v6v7v9a1=6a4=1a7=8a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4e[i]:活動ai的最早開始時間e[i]=ve[j].l[i]:活動ai的最晚開始時間l[i]=vl[k]-len<vj,vk>a2a7a6a5a4a1a3a9a8e[i]l[i]0006457771078866320a10a1115141614設ai=<j,k>∈E（G）22v1v2v3v4v5v8v6v7v9a1=5a4=1a7=8a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4如果把a1=5，整個工期會縮短一天！??！23事件事件含義v1開工v2

活動a1完成，活動a4可以開始v3活動a2完成，活動a5可以開始v4活動a3完成，活動a6可以開始v5活動a4

和a5完成，活動a7和a8可以開始v6活動a6完成，活動a9可以開始v7活動a7完成，活動a10可以開始v8活動a8

和a9完成，活動a11可以開始v9活動a10

和a11完成，整個工程完成v1v2v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4具有最大路徑長度的路徑稱為關鍵路徑。24這樣的網(wǎng)絡（也稱AOE網(wǎng)絡）最關心的兩個問題：⑴完成整個工期至少需要多少時間，即整個工期所需的最短時間是多少，也就是找關鍵路徑；⑵哪些活動是影響工程進度的關鍵，也就是說這些活動的延期將直接延長工期，這些活動叫關鍵活動。這樣的網(wǎng)絡具有以下兩個性質(zhì)：⑴只有在某頂點所代表的事件發(fā)生后，從該頂點出發(fā)的各活動才能開始；⑵只有在進入某頂點的各活動都已經(jīng)結束，該頂點所代表的事件才能發(fā)生?？偨Y25§7.3

網(wǎng)絡計劃的優(yōu)化---網(wǎng)絡計劃優(yōu)化的途徑縮短網(wǎng)絡圖上關鍵路線的持續(xù)時間可通過以下途徑實現(xiàn)：（1）檢查關鍵路線上各項作業(yè)的計劃時間是否訂的恰當，如果訂得過長，可適當縮短；（2）將關鍵路線上的作業(yè)進一步分細，盡可能安排多共位或平行作業(yè)；（3）抽調(diào)非關鍵路線上的人力、物力支援關鍵路線上的作業(yè)；（4）有時也通過重新制定工藝流程，也就是用改變網(wǎng)絡圖結構的辦法來達到縮短時間的目的。26------------------------例題7.3.1----------------------

假如例7.1.1所列的工程要求在49天完成。為了加快進度，表7.3.1列出了表7.1.1中可縮短工時的所有工作，表明這些作業(yè)計劃完成時間，最短完成時間以及比原計劃縮短一天的費用。問應如何安排，使額外增加的總費用最小.§7.3

網(wǎng)絡計劃的優(yōu)化作業(yè)代號計劃完成時間(天)最短完成時間(天)縮短一天增加的費用（元）(1,3)(1,4)(2,5)(5,6)(5,8)(5,7)(7,8)(6,8)BCEGHIJK1011421352