網(wǎng)絡(luò)計(jì)劃的優(yōu)化課堂

1、網(wǎng)絡(luò)計(jì)劃技術(shù),網(wǎng)絡(luò)計(jì)劃的優(yōu)化,王秀菊,網(wǎng)絡(luò)計(jì)劃的優(yōu)化是指在一定約束條件下,按既定目標(biāo)對網(wǎng)絡(luò)計(jì)劃進(jìn)行不斷改進(jìn)，以,尋求滿意方案的過程,網(wǎng)絡(luò)計(jì)劃優(yōu)化的目標(biāo)包括工期目標(biāo)、費(fèi)用,目標(biāo)和資源目標(biāo),網(wǎng)絡(luò)計(jì)劃的優(yōu)化分為工期優(yōu)化、費(fèi)用優(yōu)化,和資源優(yōu)化三種,工期優(yōu)化,當(dāng)網(wǎng)絡(luò)計(jì)劃的計(jì)算工期不滿足要求工期時(shí),就需要通過壓縮關(guān)鍵工作的持續(xù)時(shí)間來滿,足工期目標(biāo)的過程,在工期優(yōu)化過程中要注意以下兩點(diǎn),不能將關(guān)鍵工作壓縮成非關(guān)鍵工作；在壓縮過,程中，會出現(xiàn)關(guān)鍵線路的變化（轉(zhuǎn)移或增加條,數(shù)），必須保證每一步的壓縮都是有效的壓縮,在優(yōu)化過程中如果出現(xiàn)多條關(guān)鍵路線時(shí)，必須,考慮壓縮公用的關(guān)鍵工作，或?qū)⒏鳁l關(guān)鍵線路,上的關(guān)鍵工作都

2、壓縮同樣的數(shù)值，否則，不能,有效地將工期壓縮,工期優(yōu)化的步驟,將優(yōu)先壓縮的關(guān)鍵工作壓縮到最短的工作持續(xù)時(shí),間，并找出關(guān)鍵線路和計(jì)算出網(wǎng)絡(luò)計(jì)劃的工期,如果被壓縮的工作變成了非關(guān)鍵工作，則應(yīng)將其,工作持續(xù)時(shí)間延長，使之仍然是關(guān)鍵工作,若已經(jīng)達(dá)到工期要求，則優(yōu)化完成。若計(jì)算工期,仍超過計(jì)劃工期，則按上述步驟依次壓縮其它關(guān),鍵工作，直到滿足工期要求或工期已不能再壓縮,為止,當(dāng)所有關(guān)鍵工作的工作持續(xù)時(shí)間均已經(jīng)達(dá)到最短,而工期仍不能滿足要求時(shí)，應(yīng)對計(jì)劃的技術(shù)、組,織方案進(jìn)行調(diào)整，或?qū)τ?jì)劃工期重新審訂,已知某工程雙代號網(wǎng)絡(luò)計(jì)劃如圖所示，圖,中箭線下方括號外數(shù)字為工作的正常持續(xù),時(shí)間，括號內(nèi)數(shù)字為最短持續(xù)時(shí)間

3、,箭線上方括號內(nèi)數(shù)字為優(yōu)選系數(shù)，該系數(shù),綜合考慮質(zhì)量、安全和費(fèi)用增加情況而確,定,現(xiàn)假設(shè)要求工期為,15,試對其進(jìn)行工期優(yōu),化,1,根據(jù)各項(xiàng)工作的正常持續(xù)時(shí)間，用標(biāo),號法確定網(wǎng)絡(luò)計(jì)劃的計(jì)算工期和關(guān)鍵線路,此時(shí)關(guān)鍵線路為,2,由于此時(shí)關(guān)鍵工作為工作,A,工作,D,和工作,H,而其中工作,A,優(yōu)選系數(shù)最小，故應(yīng)將工作,A,作為優(yōu)先,壓縮對象,3,將關(guān)鍵工作,A,的持續(xù)時(shí)間壓縮至最短持續(xù)時(shí)間,3,利,用標(biāo)號法確定新的計(jì)算工期和關(guān)鍵線路,此時(shí)，關(guān)鍵工作,A,被壓縮成非關(guān)鍵工作，故將其持續(xù)時(shí)間,3,延長為,4,使之成為關(guān)鍵工作。工作,A,恢復(fù)為關(guān)鍵工作之后,網(wǎng)絡(luò)計(jì)劃中出現(xiàn)兩條關(guān)鍵線路，即,和,4,由于此

4、時(shí)計(jì)算工期為,18,仍大于要求工期，故,需繼續(xù)壓縮,T=3,有以下五個(gè)壓縮方案,同時(shí)壓縮工作,A,和工作,B,組合優(yōu)選系數(shù)為,2+8=10,同時(shí)壓縮工作,A,和工作,E,組合優(yōu)選系數(shù)為,2+4=6,同時(shí)壓縮工作,B,和工作,D,組合優(yōu)選系數(shù)為,8+5=13,同時(shí)壓縮工作,D,和工作,E,組合優(yōu)選系數(shù)為,5+4=9,壓縮工作,H,優(yōu)選系數(shù)為,10,在上述壓縮方案中，由于工作,A,和工作,E,的組合優(yōu)選系,數(shù)最小，故應(yīng)選擇同時(shí)壓縮工作,A,和工作,E,的方案。將,這兩項(xiàng)工作的持續(xù)時(shí)間各壓縮,1,壓縮至最短），再,用標(biāo)號法確定計(jì)算工期和關(guān)鍵線路。此時(shí)，關(guān)鍵線路,仍為兩條，即,和,在圖中，關(guān)鍵工作,A

5、,和,E,的持續(xù)時(shí)間已達(dá)最短，不,能再壓縮，它們的優(yōu)選系數(shù)變?yōu)闊o窮大,5,由于此時(shí)計(jì)算工期為,17,仍大于要求工期,故需繼續(xù)壓縮,T2=2,在上圖所示網(wǎng)絡(luò)計(jì)劃中,由于關(guān)鍵工作,A,和,E,已不能再壓縮，故此時(shí)只有兩個(gè),壓縮方案,同時(shí)壓縮工作,B,和工作,D,組合優(yōu)選系數(shù)為,8+5=13,壓縮工作,H,優(yōu)選系數(shù)為,10,在上述壓縮方案中，由于工作,H,的優(yōu)選系數(shù)最小,故應(yīng)選擇壓縮工作,H,的方案。將工作,H,的持續(xù)時(shí)間縮,短,2,再用標(biāo)號法確定計(jì)算工期和關(guān)鍵線路。此時(shí),計(jì)算工期為,15,已等于要求工期，故為優(yōu)化方案,例題：已知網(wǎng)絡(luò)計(jì)劃如下圖所示，箭線下方括號,外為正常持續(xù)時(shí)間，括號內(nèi)為最短工作歷

6、時(shí)，假,定計(jì)劃工期為,100,天，試對該網(wǎng)絡(luò)計(jì)劃進(jìn)行工期優(yōu),化,費(fèi)用優(yōu)化,工程網(wǎng)絡(luò)計(jì)劃一經(jīng)確定（工期確定），其所包含,的總費(fèi)用也就確定下來。網(wǎng)絡(luò)計(jì)劃所涉及的總費(fèi),用是由直接費(fèi)和間接費(fèi)兩部分組成,直接費(fèi)由人工費(fèi)、材料費(fèi)和機(jī)械費(fèi)組成，它是隨,工期的縮短而增加,間接費(fèi)屬于管理費(fèi)范疇，它是隨工期的縮短而減,小,由于直接費(fèi)隨工期縮短而增加，間接費(fèi)隨工期縮,短而減小，兩者進(jìn)行疊加，必有一個(gè)總費(fèi)用最少,的工期，這就是費(fèi)用優(yōu)化所要尋求的目標(biāo),費(fèi)用優(yōu)化的基本思想,不斷地從工作的時(shí)間和費(fèi)用關(guān)系中，找出能使,工期縮短而又能使直接費(fèi)增加最少的工作，縮,短其持續(xù)時(shí)間,同時(shí)，再考慮間接費(fèi)隨工期縮短而減小的情況,把不同工期

7、的直接費(fèi)與間接費(fèi)分別疊加，從而,求出工程費(fèi)用最低時(shí)相應(yīng)的最優(yōu)工期或工期指,定時(shí)相應(yīng)的最低工程費(fèi)用,費(fèi)用優(yōu)化的步驟,1,算出工程總直接費(fèi)。工程總直接費(fèi)等于組成,該工程的全部工作的直接費(fèi)（正常情況）的總,和,2,算出直接費(fèi)的費(fèi)用率（趕工費(fèi)用率,直接費(fèi)用率是指縮短工作每單位時(shí)間所需增加的直,接費(fèi)，工作,i-j,的直接費(fèi)率用,表示。直接費(fèi)用率等,于最短時(shí)間直接費(fèi)與正常時(shí)間直接費(fèi)所得之差除以,正常工作歷時(shí)減最短工作歷時(shí)所得之差的商值,3,確定出間接費(fèi)的費(fèi)用率,工作,i-j,的間接費(fèi)的費(fèi)用率用,其值根據(jù)實(shí)際情況,確定,4,找出網(wǎng)絡(luò)計(jì)劃中的關(guān)鍵線路和計(jì)算出計(jì)算工,期,5,在網(wǎng)絡(luò)計(jì)劃中找出直接費(fèi)用率（或組合費(fèi)

8、用,率）最低的一項(xiàng)關(guān)鍵工作（或一組關(guān)鍵工作,作為壓縮的對象,6,壓縮被選擇的關(guān)鍵工作（或一組關(guān)鍵工作）的,持續(xù)時(shí)間，其壓縮值必須保證所在的關(guān)鍵線路仍,然為關(guān)鍵線路，同時(shí)，壓縮后的工作歷時(shí)不能小,于極限工作歷時(shí),7,計(jì)算相應(yīng)的費(fèi)用增加值和總費(fèi)用值（總費(fèi)用必,須是下降的），總費(fèi)用值可按下式計(jì)算,8,重復(fù)以上步驟，直至費(fèi)用不再降低為止,在優(yōu)化過程中，當(dāng)直接費(fèi)用率（或組合費(fèi)率）小于間,接費(fèi)率時(shí)，總費(fèi)用呈下降趨勢,當(dāng)直接費(fèi)用率（或組合費(fèi)率）大于間接費(fèi)率時(shí)，總費(fèi),用呈上升趨勢,所以，當(dāng)直接費(fèi)用率（或組合費(fèi)率）等于或略小于間,接費(fèi)率時(shí)，總費(fèi)用最低,已知某工程雙代號網(wǎng)絡(luò)計(jì)劃如圖所示，圖,中箭線下方括號外數(shù)字為

9、工作的正常時(shí)間,括號內(nèi)數(shù)字為最短持續(xù)時(shí)間,箭線上方括號外數(shù)字為工作按正常持續(xù)時(shí),間完成時(shí)所需的直接費(fèi)，括號內(nèi)數(shù)字為工,作按最短持續(xù)時(shí)間完成時(shí)所需的直接費(fèi),該工程的間接費(fèi)用率為,0.8,萬元天，試對,其進(jìn)行費(fèi)用優(yōu)化,1,根據(jù)各項(xiàng)工作的正常持續(xù)時(shí)間，用標(biāo)號法,確定網(wǎng)絡(luò)計(jì)劃的計(jì)算工期和關(guān)鍵線路，如圖,計(jì)算工期為,19,天，關(guān)鍵線路有兩條，即,和,2,計(jì)算各項(xiàng)工作的直接費(fèi)用率,C,1-2,7.4-7.0,4-2,0.2,萬元,天,C,1-3,11.0-9.0,8-6,1.0,萬元,天,C,1-2,7.4-7.0,4-2,0.2,萬元,天,C,2-3,0.3,萬元,天,C,2-4,0.5,萬元,天,C,

10、3-4,0.2,萬元,天,C,3-5,0.8,萬元,天,C,4-5,0.7,萬元,天,C,4-6,0.5,萬元,天,C,5-6,0.2,萬元,天,3,計(jì)算工程總費(fèi)用,直接費(fèi)總和,C,d,7.0+9.0+5.7+5.5+8.0+8.0+5.0+7.5+6.5,62.2,萬元,間接費(fèi)總和,C,i,0.8,19=15.2,萬元,工程總費(fèi)用,C,t,C,d,C,i,62.2+15.2=77.4,萬元,1,第一次壓縮,從圖可知，該網(wǎng)絡(luò)計(jì)劃中有兩條關(guān)鍵線路,為了同時(shí)縮短兩條關(guān)鍵線路的總持續(xù)，有以,下四個(gè)壓縮方案,壓縮工作,B,直接費(fèi)用率為,1.0,萬元天,壓縮工作,E,直接費(fèi)用率為,0.2,萬元天,同時(shí)壓

11、縮工作,H,和工作,I,組合直接費(fèi)用率為,0.7+0.5=1.2,萬元天,同時(shí)壓縮工作,I,和工作,J,組合直接費(fèi)用率為,0.5+0.2=0.7,萬元天,在上述壓縮方案中，由于工作,E,的直接費(fèi)用率最小,故應(yīng)選擇工作,E,為壓縮對象,工作,E,的直接費(fèi)用率,0.2,萬元天，小于間接費(fèi)用,率,0,8,萬元天，說明壓縮工作,E,可使工程總費(fèi)用,降低,將工作,E,的持續(xù)時(shí)間壓縮至最短持續(xù)時(shí)間,3,天，利,用標(biāo)號法重新確定計(jì)算工期和關(guān)鍵線路，如圖,9,所,示。此時(shí)，關(guān)鍵工作,E,被壓縮成非關(guān)鍵工作，故將,其持續(xù)時(shí)間延長為,4,天，使成為關(guān)鍵工作,第一次壓縮后的網(wǎng)絡(luò)計(jì)劃如圖,10,所示。圖中箭線,上方括

12、號內(nèi)數(shù)字為工作的直接費(fèi)用率,2,第二次壓縮,從圖可知，該網(wǎng)絡(luò)計(jì)劃中有三條關(guān)鍵線路，即,和,為了同,時(shí)縮短三條關(guān)鍵線路的總持續(xù)時(shí)間，有以下五個(gè)壓縮方案,壓縮工作,B,直接費(fèi)用率為,1.0,萬元天,同時(shí)壓縮工作,E,和工作,G,組合直接費(fèi)用率為,0.2+0.8=1.0,萬元天,同時(shí)壓縮工作,E,和工作,J,組合直接費(fèi)用率為,0.2+0.2=0.4,萬元天,同時(shí)壓縮工作,G,工作,H,和工作,J,組合直接費(fèi)用率為,0.8+0.7+0.5=2.0,萬元天,同時(shí)壓縮工作,I,和工作,J,組合直接費(fèi)用率為,0.5+0.2=0.7,萬元天,由于工作,E,的持續(xù)時(shí)間只能壓縮,1,天，工作,J,的持續(xù),時(shí)間也只

13、能隨之壓縮,1,天,工作,E,和工作,J,的持續(xù)時(shí)間同時(shí)壓縮,1,天后，利用標(biāo),號法重新確定計(jì)算工期和關(guān)鍵線路,此時(shí)，關(guān)鍵線路由壓縮前的三條變?yōu)閮蓷l，即,和,原來的關(guān)鍵工作,H,未經(jīng)壓縮而被動地變成了非關(guān)鍵,工作。第二次壓縮后的網(wǎng)絡(luò)計(jì)劃如圖所示。此時(shí),關(guān)鍵工作,E,的持續(xù)時(shí)間已達(dá)最短，不能再壓縮，故,其直接費(fèi)用率變?yōu)闊o窮大,3,第三次壓縮,從圖可知，由于工作,E,不能再壓縮，而為了同時(shí)縮,短兩條關(guān)鍵線路,和,的總持續(xù)時(shí)間，只有以下三個(gè)壓縮方案,壓縮工作,B,直接費(fèi)用率為,1.0,萬元天,同時(shí)壓縮工作,G,和工作,I,組合直接費(fèi)用率為,0.8+0.5 =1.3,萬元天,同時(shí)壓縮工作,I,和工作,

14、J,組合直接費(fèi)用率為,0.5+0.2=0.7,萬元天,4,第四次壓縮,從圖,3-46,可知，由于工作,E,和工作不能再壓縮,而為了同時(shí)縮短兩條關(guān)鍵線路,和,的總持續(xù)時(shí)間，只有以下兩個(gè)壓,縮方案,壓縮工作,B,直接費(fèi)用率為,1.O,萬元天,同時(shí)壓縮工作,G,和工作,I,組合直接費(fèi)用率為,0.8+0.5=1.3,萬元,天,在上述壓縮方案中，由于工作,B,的直接費(fèi)用率最小,故應(yīng)選擇工作,B,作為壓縮對象。但是，由于工作,B,的直接費(fèi)用率,1.O,萬元,天，大于間接費(fèi)用率,0.8,萬元天，說明壓縮工作,B,會使工程總費(fèi)用增加,因此，不需要壓縮工作,B,優(yōu)化方案已得到，優(yōu)化,后的網(wǎng)絡(luò)計(jì)劃如圖所示。圖中箭

15、線上方括號內(nèi)數(shù),字為工作的直接費(fèi),5,計(jì)算優(yōu)化后的工程總費(fèi)用,直接費(fèi)總和,C,d0,7.0+9.0+5.7+5.5+8.4+8.0+5.0+8.0+6.9,63.5,萬元,間接費(fèi)總和,C,i0,0.8,16=12.8,萬元,工程總費(fèi)用,C,t0,C,d0,C,iO,63.5+12.8=76.3,萬元,例題：已知網(wǎng)絡(luò)計(jì)劃如下圖所示，箭線上方括號,外為正常直接費(fèi)，括號內(nèi)為最短時(shí)間直接費(fèi)，箭,線下方括號外為正常工作歷時(shí)，括號內(nèi)為最短工,作歷時(shí)。試對其進(jìn)行費(fèi)用優(yōu)化。間接費(fèi)率為,0.120,千元,天,資源優(yōu)化,資源優(yōu)化的目的是通過改變工作的開始時(shí),間和完成時(shí)間，使資源按照時(shí)間的分布符,合優(yōu)化目標(biāo),資源優(yōu)

16、化的類型,資源供應(yīng)有限制的條件下，尋求計(jì)劃的最短工,期，成為“資源有限，工期最短”的優(yōu)化,在工期規(guī)定的條件下，力求資源消耗均衡，稱,為“工期固定，資源均衡”的優(yōu)化,資源有限，工期最短”的基本假設(shè),優(yōu)化過程中各工作的持續(xù)時(shí)間保持不變,優(yōu)化過程中不改變工作間的邏輯關(guān)系,各工作每天的資源需要量均衡且在優(yōu)化過程中,不變,要求工作連續(xù)施工，不允許中斷,按各項(xiàng)工作的最早開始時(shí)間安排進(jìn)度計(jì)劃，并計(jì),算網(wǎng)絡(luò)計(jì)劃每個(gè)時(shí)間單位的資源需用量,從計(jì)劃開始日期，逐個(gè)檢查每個(gè)時(shí)段資源的需用,量是否超過所供應(yīng)的資源限量,分析超過資源限量的時(shí)段。選擇工期延長值最小,的安排,對調(diào)整后的網(wǎng)絡(luò)計(jì)劃安排重新計(jì)算單位時(shí)間的資,源需用量

17、,重復(fù)調(diào)整，直至每個(gè)時(shí)間單位的資源需用量滿足,資源限量為止,已知某工程雙代號網(wǎng)絡(luò)計(jì)劃如圖所示，圖中箭線,上方數(shù)字為工作的資源強(qiáng)度，箭線下方數(shù)字為工,作的持續(xù)時(shí)間。假定資源限量,R,a,12,試對其進(jìn)行,資源有限，工期最短”的優(yōu)化,1,計(jì)算網(wǎng)絡(luò)計(jì)劃每個(gè)時(shí)間單位的資源需用量，繪出,資源需用量動態(tài)曲線，如圖下方曲線所示,2,從計(jì)劃開始日期起，經(jīng)檢查發(fā)現(xiàn)第二個(gè)時(shí)段,3,4,存在資源沖突，即資源需用量超過資源限量，故應(yīng)首,先調(diào)整該時(shí)段,3,在時(shí)段,3,4,有工作,1-3,和工作,2-4,兩項(xiàng)工作平行,作業(yè)，利用公式計(jì)算,T,值，其結(jié)果見表,由表,2,可知,T,1,2,1,最小，說明將第,2,號工,作（工作,2-4,安排在第,1,號工作（工作,1-3,之后進(jìn)行，工期延長最短，只延長,1,因此,將工作,2-4,安排在工作,1-3,之