山大《運(yùn)籌學(xué)》課件07網(wǎng)絡(luò)計(jì)劃技術(shù)

1、第一節(jié) 網(wǎng)絡(luò)計(jì)劃圖基本術(shù)語(yǔ)箭線圖 箭線圖的繪制 注意的問(wèn)題節(jié)點(diǎn)圖基本術(shù)語(yǔ)網(wǎng)絡(luò)計(jì)劃圖是在一個(gè)圖上標(biāo)注表示時(shí)間參數(shù)的進(jìn)度計(jì)劃圖，實(shí)質(zhì)上就是有時(shí)序的有向賦權(quán)圖。節(jié)點(diǎn)和箭線：節(jié)點(diǎn)和箭線是網(wǎng)絡(luò)的基本組成元素，箭線是一段帶箭頭的射線，節(jié)點(diǎn)是箭線的兩端連接點(diǎn)。工作(也稱工序、活動(dòng)或工作)： 是指將整個(gè)項(xiàng)目按需要的粗細(xì)程度分解成若干需要消耗時(shí)間或其他資源的子項(xiàng)目或單元，每個(gè)子項(xiàng)目或單元就看成是一項(xiàng)工作，工作是網(wǎng)絡(luò)圖的基本組成部分?；拘g(shù)語(yǔ)緊前工作(也叫前序工作)：工作A必須在工作B結(jié)束后開(kāi)始，則稱工作B是工作A的緊前工作。事件：標(biāo)志某項(xiàng)工作的開(kāi)始或結(jié)束，本身不消耗時(shí)間和資源，某一事件的發(fā)生標(biāo)志著一些工作的結(jié)束

2、和另一些工作的開(kāi)始。路線：是指從開(kāi)始事件到最終事件的由各項(xiàng)工作連貫組成的一條路。網(wǎng)絡(luò)計(jì)劃圖的關(guān)鍵問(wèn)題是描述各項(xiàng)工作以及各項(xiàng)工作之間的先后關(guān)系，根據(jù)描述方法的不同，網(wǎng)絡(luò)圖可以分為兩類：箭線圖和節(jié)點(diǎn)圖。續(xù)箭線圖的繪制在箭線圖中各項(xiàng)工作或活動(dòng)都用箭線表示，箭線的前后節(jié)點(diǎn)分別表示工作開(kāi)始時(shí)刻和結(jié)束時(shí)刻，箭頭邊的數(shù)字表示活動(dòng)的時(shí)間或成本，如下圖所示圖7.1.1 工作12a7箭線圖的繪制各項(xiàng)活動(dòng)或工作的前后關(guān)系，有箭頭的位置表示，例如圖中有a和b兩項(xiàng)工作，工作b須等待其前項(xiàng)工作完成后才能開(kāi)始，如下圖所示。圖7.1.2 箭線圖在整個(gè)箭線圖中每個(gè)節(jié)點(diǎn)代表著一個(gè)事件，只有一個(gè)節(jié)點(diǎn)表示項(xiàng)目開(kāi)始事件，一個(gè)節(jié)點(diǎn)表示項(xiàng)

3、目結(jié)束事件，把表示工作的箭線和表示事件的節(jié)點(diǎn)根據(jù)工作的先后關(guān)系連接起來(lái)就構(gòu)成了一個(gè)完整的箭線圖。 續(xù)12a3b例注意的問(wèn)題在箭線圖編制過(guò)程中迎注意以下幾個(gè)問(wèn)題：(1)在箭線圖中，除起點(diǎn)和終點(diǎn)外，其間各項(xiàng)工作都必須前后銜接，不可有中斷的缺口(2)網(wǎng)絡(luò)圖中，如果有循環(huán)現(xiàn)象，將造成邏輯上的錯(cuò)誤，致使某項(xiàng)工作永遠(yuǎn)無(wú)起點(diǎn)或終點(diǎn)。(3)虛擬工作的應(yīng)用 為了表達(dá)個(gè)別工作與其前項(xiàng)工作的關(guān)系，可以設(shè)計(jì)虛擬工作。 虛擬工作除了使工作間的關(guān)系表達(dá)清晰外，尚用于以下場(chǎng)合： 表示兩個(gè)工作可以同時(shí)開(kāi)始，或可以同時(shí)并行實(shí)施，待兩者完成后，再開(kāi)始另一工作。 表達(dá)整個(gè)計(jì)劃的完成或開(kāi)始。(4)節(jié)點(diǎn)編號(hào)一般采用偶數(shù)順序進(jìn)行，原因是

4、當(dāng)中間需要添加節(jié)點(diǎn)時(shí)有預(yù)留編號(hào)。節(jié)點(diǎn)圖箭線圖是統(tǒng)籌方法網(wǎng)絡(luò)圖的基本結(jié)構(gòu)，其應(yīng)用極為普遍。其最大的缺點(diǎn)是為了完整地表達(dá)前后銜接關(guān)系，有時(shí)需要增加虛擬工作。工作節(jié)點(diǎn)圖(Activity on Node Diagram簡(jiǎn)稱AND)是一種改進(jìn)的結(jié)構(gòu)，可以避免使用虛擬工作。這種方法以節(jié)點(diǎn)表示工作，以箭線表示緊前關(guān)系，如果工作a是工作b的緊前工作，就從節(jié)點(diǎn)a到節(jié)點(diǎn)b畫(huà)一條箭線。例如ab節(jié)點(diǎn)圖例7.1.1的節(jié)點(diǎn)圖如下圖所示：節(jié)點(diǎn)圖對(duì)于箭線圖而言結(jié)構(gòu)簡(jiǎn)單，編制方便，而且工作的先后關(guān)系一目了然。但其缺點(diǎn)是不能直接表示出項(xiàng)目開(kāi)始和結(jié)束的時(shí)刻以及不同工作的起始和結(jié)束的事件，在后面的事件計(jì)算中不很方便續(xù)AKJHIGD

5、FEBC第二節(jié) 時(shí)間參數(shù)和關(guān)鍵路線工作持續(xù)時(shí)間 單時(shí)估計(jì)法 三時(shí)估計(jì)法節(jié)點(diǎn)時(shí)間工作時(shí)間關(guān)鍵路線單時(shí)估計(jì)法Q：工作的工作量R：可投入人力和設(shè)備的數(shù)量S：每人或每臺(tái)設(shè)備每工作班能完成的工作量n：每天正常工作班數(shù)工作持續(xù)時(shí)間：D=Q/(R*S*n)三時(shí)估計(jì)法樂(lè)觀時(shí)間a：在一切都順利時(shí)，完成工作需要的最小時(shí)間最可能時(shí)間m： 在正常條件下，完成工作需要的時(shí)間悲觀時(shí)間b：在不順利條件下，完成工作需要最多的時(shí)間工作持續(xù)時(shí)間：D=(a+4m+b)/6方差：2=(b-a)/62節(jié)點(diǎn)時(shí)間節(jié)點(diǎn)時(shí)間：節(jié)點(diǎn)出現(xiàn)的最早時(shí)間和最晚時(shí)間最早時(shí)間ET：節(jié)點(diǎn)對(duì)應(yīng)事件可能發(fā)生的最早時(shí)間最晚時(shí)間LT：為了保證工期不推遲節(jié)點(diǎn)對(duì)應(yīng)事件允

6、許發(fā)生的最遲時(shí)間，或者說(shuō)節(jié)點(diǎn)出現(xiàn)的事件晚于該時(shí)間后整個(gè)工期必然推遲項(xiàng)目開(kāi)始節(jié)點(diǎn)的最早時(shí)間為0，則 其中Dij表示箭線(i,j)對(duì)應(yīng)工作的持續(xù)時(shí)間，A表示所有箭線集合。工作時(shí)間最早開(kāi)始時(shí)間ES：一項(xiàng)工作可以開(kāi)始的最早時(shí)間最早完成時(shí)間EF：一項(xiàng)工作最早開(kāi)始時(shí)間開(kāi)工，所能達(dá)到完成的完工時(shí)間最晚完成時(shí)間LF：一項(xiàng)工作按最晚開(kāi)始時(shí)間開(kāi)工，所能達(dá)到的完成時(shí)間最晚開(kāi)始時(shí)間LS：在不影響整個(gè)計(jì)劃完成時(shí)間的前提下，一項(xiàng)工作可以開(kāi)始的最晚時(shí)間關(guān)鍵路線關(guān)鍵工作：最早開(kāi)始時(shí)間和最晚開(kāi)始時(shí)間相等的工作關(guān)鍵路線：關(guān)鍵節(jié)點(diǎn)和關(guān)鍵工作順序連接形成的路線例7.1.1的關(guān)鍵路線如下圖所示01412108624AGFEDCBKJI

7、H4211541110515202535總結(jié)這樣的網(wǎng)絡(luò)具有以下兩個(gè)性質(zhì)：(1) 只有在某頂點(diǎn)所代表的事件發(fā)生后，從該頂點(diǎn)出發(fā)的各活動(dòng)才能開(kāi)始；(2) 只有在進(jìn)入某頂點(diǎn)的各活動(dòng)都已經(jīng)結(jié)束，該頂點(diǎn)所代表的事件才能發(fā)生。這樣的網(wǎng)絡(luò)（也稱AOE網(wǎng)絡(luò)）最關(guān)心的兩個(gè)問(wèn)題：(1) 完成整個(gè)工期至少需要多少時(shí)間，即整個(gè)工期所需的最短時(shí)間是多少，也就是找關(guān)鍵路徑；(2) 哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵，也就是說(shuō)這些活動(dòng)的延期將直接延長(zhǎng)工期，這些活動(dòng)叫關(guān)鍵活動(dòng)。第三節(jié) 網(wǎng)絡(luò)計(jì)劃的優(yōu)化網(wǎng)絡(luò)計(jì)劃的優(yōu)化縮短網(wǎng)絡(luò)圖上關(guān)鍵路線的持續(xù)時(shí)間可通過(guò)以下途徑實(shí)現(xiàn)：(1)檢查關(guān)鍵路線上各項(xiàng)作業(yè)的計(jì)劃時(shí)間是否訂的恰當(dāng)，如果訂得過(guò)長(zhǎng)，可適

8、當(dāng)縮短；(2)將關(guān)鍵路線上的作業(yè)進(jìn)一步分細(xì)，盡可能安排多工位或平行作業(yè)；(3)抽調(diào)非關(guān)鍵路線上的人力、物力支援關(guān)鍵路線上的作業(yè)；(4)有時(shí)也可通過(guò)重新制定工藝流程，也就是用改變網(wǎng)絡(luò)圖結(jié)構(gòu)的辦法來(lái)達(dá)到縮短時(shí)間的目的。列出所有可縮短工期的作業(yè)計(jì)算縮短單位工時(shí)所增加的費(fèi)用找出關(guān)鍵路線上縮短單位時(shí)間增加費(fèi)用最小的工作將該項(xiàng)工作縮短時(shí)間的值控制取下列三者的最小值：1 工期要求尚需縮短的時(shí)間2 該項(xiàng)作業(yè)最多可縮短的時(shí)間3 到出現(xiàn)新關(guān)鍵路線時(shí)可縮短的時(shí)間計(jì)算并累計(jì)增加的費(fèi)用是否滿足工期要求停是否網(wǎng)絡(luò)計(jì)劃的優(yōu)化例題7.3.1 假如例7.1.1所列的工程要求在49天完成為了加快進(jìn)度，下表列出了表7.1.1中可縮

9、短工時(shí)的所有工作，表明這些作業(yè)計(jì)劃完成時(shí)間，最短完成時(shí)間以及比原計(jì)劃縮短一天額外增加的費(fèi)用。問(wèn)應(yīng)如何安排，使額外增加的總費(fèi)用最小作業(yè)代號(hào)計(jì)劃完成時(shí)間(天)最短完成時(shí)間(天)縮短一天增加的費(fèi)用 (元)(1,3)(1,4)(2,5)(5,6)(5,8)(5,7)(7,8)(6,8)BCEGHIJK1011421352515208831630221216700400450600500300400500續(xù)解對(duì)應(yīng)的規(guī)劃min 700y2+400y3+450y5+600y7+500y8+300y9+400y10+500y11s.t. X749 X1+y15 X2+y210 X3+y310 X3-X2+y44 X4-X1+y54 X4-X20 X5-X3+y615對(duì)應(yīng)的規(guī)劃 X5-X4+y721 X7-X4+y835 X6-X4+y725 X6-X50 X7-X6+y1015 X7-X5+y1120 y10，y22，y33，y4