《運(yùn)籌學(xué)》第3章 網(wǎng)絡(luò)計(jì)劃技術(shù)

第3章網(wǎng)絡(luò)計(jì)劃技術(shù)本章要點(diǎn)網(wǎng)絡(luò)圖的繪制規(guī)則時(shí)間參數(shù)的計(jì)算CPM方法的應(yīng)用PERT方法的特點(diǎn)網(wǎng)絡(luò)優(yōu)化的基本原理第1節(jié)網(wǎng)絡(luò)計(jì)劃原理甘特圖甘特圖的缺點(diǎn)甘特圖的改進(jìn)杜邦公司的CPM海軍武器局的PERT各自的特點(diǎn)第1節(jié)網(wǎng)絡(luò)計(jì)劃原理網(wǎng)絡(luò)計(jì)劃的流程：1.確定目標(biāo)2.分解工程項(xiàng)目，列出工序明細(xì)表3.繪制網(wǎng)絡(luò)圖4.網(wǎng)絡(luò)計(jì)劃方案的優(yōu)化第2節(jié)網(wǎng)絡(luò)圖的繪制基本概念：工序結(jié)點(diǎn)（事項(xiàng)）箭線式網(wǎng)絡(luò)圖結(jié)點(diǎn)式網(wǎng)絡(luò)圖虛工序路線關(guān)鍵路線第2節(jié)網(wǎng)絡(luò)圖的繪制網(wǎng)絡(luò)圖的繪制規(guī)則：1.網(wǎng)絡(luò)圖從左向右依次展開2.箭線與結(jié)點(diǎn)一一對應(yīng)3.虛工序的運(yùn)用：應(yīng)付不暇時(shí)出現(xiàn)4.不允許出現(xiàn)循環(huán)路線5.只有一個(gè)始點(diǎn)和一個(gè)終點(diǎn)第3節(jié)關(guān)鍵路線法（CPM）主旨：梳理工序關(guān)系明確工作要點(diǎn)抓緊關(guān)鍵環(huán)節(jié)控制工程工期啟示：“道”與“術(shù)”的關(guān)系——抓住關(guān)鍵路線是“道”，政治動(dòng)員、物質(zhì)刺激、改進(jìn)工藝是“術(shù)”例3.籌備餐館的網(wǎng)絡(luò)計(jì)劃例3.張生看好大學(xué)生的消費(fèi)潛力，準(zhǔn)備在校園旁邊開一個(gè)餐館。假定選址已經(jīng)完成，接下來需要做的事情：籌備資金、準(zhǔn)備文件、注冊公司、裝修門店、購置設(shè)備、人員培訓(xùn)、商品采購等。

例3.籌備餐館的網(wǎng)絡(luò)計(jì)劃第一、梳理工序關(guān)系：最先開始做什么——起始工序隨后可以做什么——緊后工序如此遞推，直至結(jié)束——竣工典禮得到的結(jié)果是工序關(guān)系表工序代號緊前工序工序時(shí)間工序代號緊前工序工序時(shí)間準(zhǔn)備文件籌集資金登記注冊裝修門店ABCD----A,BA,B51076設(shè)備購置商品采購人員培訓(xùn)EFGBC,DD,E3412例3.籌備餐館的網(wǎng)絡(luò)計(jì)劃第二、繪制網(wǎng)絡(luò)圖①②A5B10③C7B’0D6E3④D’0D’’0⑤⑥⑦F4G12例3.籌備餐館的網(wǎng)絡(luò)計(jì)劃①③⑤④⑥②⑦A5D6B10B’0G12F4C7E3第三，計(jì)算事項(xiàng)時(shí)間參數(shù)的圖算法051010161716282824016161010D’0D’’0例3.籌備餐館的網(wǎng)絡(luò)計(jì)劃第四，找到關(guān)鍵路線：一般而言，最早時(shí)間與最遲時(shí)間相等的事項(xiàng)串聯(lián)起來，就是關(guān)鍵路線。但是不能一概而論，有時(shí)需要推算一下：箭頭事項(xiàng)最遲時(shí)間—工序時(shí)間=箭尾事項(xiàng)最遲時(shí)間如E工序就不是關(guān)鍵工序，因?yàn)?6—工序時(shí)間3≠事項(xiàng)②的事項(xiàng)⑥的10本例的關(guān)鍵路線是：B-D-G四、工序的時(shí)間參數(shù)計(jì)算工序的最早可能開工時(shí)間受緊前工序的制約，工序最早可能何時(shí)開工工序的最早可能完工時(shí)間最早可能開工時(shí)間+工序時(shí)間工序的最遲必須完工時(shí)間受緊后工序的制約，工序最遲必須何時(shí)完工工序的最遲必須開工時(shí)間最遲必須完工時(shí)間-工序時(shí)間工序的時(shí)間參數(shù)計(jì)算工序的總時(shí)差：在不影響緊后工序最遲必須開工時(shí)間的前提下，本工序的機(jī)動(dòng)時(shí)間工序最遲必須開工時(shí)間-最早可能開工時(shí)間工序的單時(shí)差：在不影響緊后工序最早可能開工時(shí)間的前提下，本工序的機(jī)動(dòng)時(shí)間緊后工序的最早可能開工時(shí)間-本工序的最早可能完工時(shí)間工序的時(shí)間參數(shù)計(jì)算t(i,j)t(i,j)TES(i,j)TLS(i,j)TEF(i,j)TLF(i,j)TES(j,k)TLS(j,k)TEF(j,k)TLF(j,k)t(j,k)t(j,k)r(i,j)R(i,j)工序時(shí)間參數(shù)關(guān)系示意圖工序時(shí)間參數(shù)的表算法1.看圖填表，得到Ⅰ、Ⅱ、Ⅲ、Ⅳ欄2.第Ⅴ欄：TES=緊前工序TES+t(i,j)，多中取大，即3.第Ⅵ欄：最早可能完工時(shí)間Ⅵ＝Ⅳ+Ⅴ4.第Ⅶ欄：從后向前推TLF(i,j)=TLF(j,k)-t(j,k)5.第Ⅷ欄：最遲必須開工時(shí)間Ⅷ＝Ⅶ－Ⅳ6.總時(shí)差：Ⅸ＝Ⅷ－Ⅴ或Ⅸ＝Ⅶ－Ⅵ7.單時(shí)差：緊后工序的TES減去本工序的TEF工序時(shí)間參數(shù)的表算法ⅠⅡⅢⅣⅤⅥⅦⅧⅨⅩ工序名稱ijt(i,j)TESTEFTLFTLSR(i,j)r(i,j)ABB’CDD’D’’EFG①①②③③④④②⑤⑥③②③⑤④⑤⑥⑥⑦⑦51007600341200101010161610171651010171616161321281010102416241616282850101710241613241650070803705000010370工序時(shí)間參數(shù)的計(jì)算機(jī)求解工序時(shí)間參數(shù)的計(jì)算機(jī)求解工序時(shí)間參數(shù)的計(jì)算機(jī)求解第4節(jié)計(jì)劃評審技術(shù)（PERT）計(jì)劃評審技術(shù)PERT屬于隨機(jī)型網(wǎng)絡(luò)，與關(guān)鍵路線法的應(yīng)用環(huán)境不同，專門針對工序時(shí)間不確定的工程項(xiàng)目。PERT在CPM的基礎(chǔ)上向前延伸，增加了對工序時(shí)間的處理；向后延伸，增加了工程工期的概率估計(jì)，但是方法的主體還是關(guān)鍵路線法。PERT是“包子”；CPM是“肉餡”第4節(jié)計(jì)劃評審技術(shù)（PERT）一、工序時(shí)間的處理三種時(shí)間估計(jì)法第4節(jié)計(jì)劃評審技術(shù)（PERT）二、概率估計(jì)數(shù)學(xué)上刻畫數(shù)據(jù)離散度的指標(biāo)是方差第4節(jié)計(jì)劃評審技術(shù)（PERT）PERT的功用：給定工期求概率給定概率求工期例4.PERT應(yīng)用德美化工受朝陽印染廠的委托，研發(fā)一種著色劑，約定3周內(nèi)提交解決方案。研發(fā)部將研制項(xiàng)目分為9道工序，網(wǎng)絡(luò)圖如下：16.6720.6717.67①②⑥④③⑦A6B2C5.17E3.17F9⑤G4H6.67I30621411.171120.6708.67614D8例4.PERT應(yīng)用由圖算法可知：關(guān)鍵路線為A-D-H查正態(tài)分布表，得如期完工的概率為57.5％。如若公司約定履約率必須達(dá)到90％，合同工期多少天？即簽署23天的合同便有90％以上的把握如期完工。四、PERT的計(jì)算機(jī)求解四、PERT的計(jì)算機(jī)求解四、PERT的計(jì)算機(jī)求解四、PERT的計(jì)算機(jī)求解第5節(jié)網(wǎng)絡(luò)優(yōu)化網(wǎng)絡(luò)優(yōu)化的內(nèi)涵:網(wǎng)絡(luò)銜接的能否優(yōu)化？在既定的銜接關(guān)系下，有沒有又省時(shí)間又省錢的方案？如何在各工序之間進(jìn)行資源均衡，使之成為可行解？一、網(wǎng)絡(luò)銜接的優(yōu)化網(wǎng)絡(luò)銜接的方式有時(shí)不是唯一的，這種情況下就有了優(yōu)化的空間。例如，內(nèi)、外裝修可以同步進(jìn)行，也就是所謂平行作業(yè)。布線和墻面裝修可以交叉作業(yè)①②③④⑥⑤布線1布線2墻面1墻面2二、時(shí)間—成本優(yōu)化一般來說，節(jié)省時(shí)間要多花錢，有沒有又省時(shí)間又省錢的工期方案？分析哲學(xué)直接費(fèi)用間接費(fèi)用二、時(shí)間—成本優(yōu)化時(shí)間成本總費(fèi)用直接費(fèi)用間接費(fèi)用例5.

最低成本日程某公司負(fù)責(zé)教學(xué)大樓的施工，平均每天辦公費(fèi)用5000元。各項(xiàng)費(fèi)用明細(xì)表：

工序正常工期（天）極限工期（天）關(guān)鍵工序趕工費(fèi)用：元/天ABCDEFGHJK6040354880154560502050403345701542564020√√√√7000∞800030005000∞600030008000∞例5.

最低成本日程分析：從表3-5看出：A、E、H、K為關(guān)鍵工序，正常的總工期220天，極限總工期196天。可以趕工的工序A、E、H，其中H工序趕工費(fèi)用3000元，小于每天的間接費(fèi)用，可以趕工4天；E工序趕工費(fèi)用5000，等于每天的間接費(fèi)用，可以趕工10天；A工序趕工費(fèi)用7000元，高于間接費(fèi)用，不宜趕工。最低成本日程是182天。三、時(shí)間－資源優(yōu)化主旨：尋求在給定時(shí)間內(nèi)最省資源的安排例6.某項(xiàng)工程的甘特圖如下，如何安排作業(yè)時(shí)間使得66個(gè)工人能夠如期完成施工任務(wù)？200407560A20天/58人D30天/42人E25天/26人B18天/22人C15天/39人三、時(shí)間－資源優(yōu)化例6求解：200