工期網(wǎng)絡(luò)圖的時間-費(fèi)用優(yōu)化

1、某施工單位提交的一項(xiàng)目的網(wǎng)絡(luò)計(jì)劃資料如表1所示。如下：序活緊前正常作業(yè)時間（單位:天）最短時號動活動樂觀時間a.1最可能時間m.1悲觀時間b.1正常作業(yè)期望時間t1作業(yè)時間方差O1正常期望時間對應(yīng)直接費(fèi)用（百元）/,間tt1直接費(fèi)用（百元）f-i直接費(fèi)用率k113333012433CA44105124424DB55116124415MA,B310119161129126EC,M6666034727GC,M2910816/957838HD,E13534/9636求：（1）每項(xiàng)活動按正常平均時間作業(yè)，請繪制相應(yīng)的網(wǎng)絡(luò)計(jì)劃圖，指出此時的關(guān)鍵線路（在圖上用雙色線或色筆標(biāo)出），

2、并計(jì)算出工期。（2）接（1），如果考慮外部影響導(dǎo)致每項(xiàng)活動作業(yè)時間發(fā)生的隨機(jī)波動（見表1中悲觀時間和樂觀時間所在列），那么該項(xiàng)目完工概率要達(dá)到90%以上，則該工程工期不低于多少天？（3）接（1）。施工單位經(jīng)分析后，考慮有些工作可適當(dāng)趕工（見最短時間所在列），并估算出各工作每趕工1天所需增加的費(fèi)用（直接費(fèi)率，見表1最后一列），間接費(fèi)用為每天9百元。給出增加趕工費(fèi)最少的方案（要求寫出每步調(diào)整的工作，調(diào)整的天數(shù)及最后方案的網(wǎng)絡(luò)計(jì)劃，并在最后方案的網(wǎng)絡(luò)計(jì)劃中標(biāo)出關(guān)鍵線路）。（4）請建立第（3）問對應(yīng)的線性規(guī)劃模型。解：（1）以各工作的正常作業(yè)期望時間為工序時間，繪制網(wǎng)絡(luò)圖如下：13*事件i時間參數(shù)標(biāo)記

3、:4134F3F19104322196事件i最早時間tE（i）；13*事件i時間參數(shù)標(biāo)記:4134F3F19104322196事件i最早時間tE（i）；用事件i最遲時間tL（i）工作（i,j）時間參數(shù)標(biāo)記:最早開最早結(jié)總時差始時間束時間/%】（修）tEF3TF(i,j)ftLS(i,j)tLF(i,j)1FF(i,j)最遲開始時間最遲結(jié)束時間自由時差雙代號網(wǎng)絡(luò)圖的繪圖原則如下：（1）網(wǎng)絡(luò)圖是有方向的，不允許出現(xiàn)回路，不允許出現(xiàn)從右到左的箭頭。（2）直接連接兩個相鄰節(jié)點(diǎn)之間的活動只能有一個，如果實(shí)在要表示并列關(guān)系可用虛工序。（3）箭線首尾必有節(jié)點(diǎn)，不能從箭線中間引出另一條箭線。（4）網(wǎng)絡(luò)圖必須只

4、有一個網(wǎng)絡(luò)始點(diǎn)和一個終點(diǎn)。（5）各項(xiàng)活動之間的銜接必須按邏輯關(guān)系（緊前關(guān)系、緊后關(guān)系）進(jìn)行。（6）事件節(jié)點(diǎn)采用數(shù)字編號，在同一網(wǎng)絡(luò)圖中不允許重復(fù)使用，每條箭線箭頭節(jié)點(diǎn)的編號（）必須大于其箭尾節(jié)點(diǎn)的編號（）。（7）盡量避免箭線交叉（采用過橋法或指向處理法）。（8）標(biāo)注出各項(xiàng)工作的準(zhǔn)確歷時或時間期望值。（）虛工序用虛箭線表示，僅表達(dá)一種工作順序的先后依賴關(guān)系，有兩種作用：如果工序到工序之間順著箭頭方向僅隔一個虛工序，則仍是的緊前活動。如果、b三個活動共用一個開始節(jié)點(diǎn)i則可用虛工序表示這三個活動并行展開且三者都是末端活動。各活動的正常作業(yè)期望時間ti=（ai+4mi+bi）/6,方差2電一電2/36

5、,計(jì)算見表1第7、8列。25=(11-3)2/36=16/9。以活動M為例，計(jì)算如下：t5=(a5+4m25=(11-3)2/36=16/9。用圖上計(jì)算法求出各事件時間參數(shù)，然后再求出各工作時間參數(shù)，計(jì)算結(jié)果如上圖所示。其中總時差為0的活動組成關(guān)鍵路線（如上圖紅色箭線所示）：一一一一一;該項(xiàng)目期望完工工期為22天。（提問：某工序開始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)的最早時間與最遲時間相等，它就一定是關(guān)鍵活動嗎？答：不一定。比如圖中的活動滿足該條件但不是關(guān)鍵活動。）（）該工程按期望時間完工的工期=天，等于各關(guān)鍵活動期望完工時間之和9期望總工期的均方差.1i.；1HH6/m/9.795055假設(shè)工程工期服Eiij從

6、正態(tài)分布，則完工的概率保證不小于的計(jì)算表達(dá)式為：P（U）BP（TKE）BP（Tk.2）B0.9。計(jì)算得到，三.天1.795055E（）直接費(fèi)用率,的直接費(fèi)用率百元天。iiiii1時間費(fèi)用優(yōu)化方法：【優(yōu)化原則】優(yōu)化時，首先選擇趕工費(fèi)用率最低的關(guān)鍵活動進(jìn)行趕工，非關(guān)鍵活動不需要趕工因?yàn)檫€可利用總時差；每趕工1天（單獨(dú)某活動趕工或者各關(guān)鍵活動同時趕工）增加的直接費(fèi)用不超過單位間接費(fèi)用，否則不值得趕工（原則1和原則4得以反映）。每一次允許的壓縮時間以符合以下全部原則為限度。原則1：該關(guān)鍵活動趕工費(fèi)用率不大于單位間接費(fèi)用，否則不值得壓縮；原則2：關(guān)鍵活動實(shí)際壓縮時間不大于自身趕工可壓縮時間極限；原則3：

7、壓縮允許時間不大于關(guān)鍵路線與次關(guān)鍵路線的工期之差。（理由：優(yōu)化只能使關(guān)鍵路線增多，而不能使之越來越少）；原則4：須同時壓縮的各并列關(guān)鍵活動趕工費(fèi)用率之和不大于單位間接費(fèi)用，并且不超過各并列關(guān)鍵活動的趕工壓縮時間極限。第一步：在關(guān)鍵路線上，直接費(fèi)用率最低的工作是（）6原則，它自身可以趕工天（，原則）。次關(guān)鍵路線是一一一一一和一一一一，時間長度都為，決定Y關(guān)鍵路線這一步只能趕工天（，原則）。因此，工作趕工天，剩余趕工時間為天（=）。這時，關(guān)鍵路線變?yōu)閮蓷l：一一一一一，一一一一，工期都為天，工作的天時差用完而成為關(guān)鍵活動；次關(guān)鍵路線為一一一一和一一一一，時間長度都為天。第二步：在上一步趕工以后得到的

8、兩條關(guān)鍵路線上，費(fèi)率最低的工作仍是（）原則，其并列關(guān)鍵活動自身允許趕工天（，原則后半句），因此和同時趕H（原則前半句）天,原則（原則）之后不能再趕工（）-不能再趕工。這時，關(guān)鍵路線仍為一一一一一，一一一一，工期都為天。次關(guān)鍵路線為一一一一一和一一一，時間長度都為天。第三步：在上一步趕工以后得到的兩條關(guān)鍵路線中，工作、能再趕工，唯有工作可以趕工（，原則，它自身可以趕工天關(guān)鍵路線決定了它只能趕工天（原則），之后、都不原則，但次的趕工時間還剩余天（-這之后，關(guān)鍵路線變?yōu)樗臈l：一一一一一、一一一一、一一一一一以及一一一一，工期都為天。次關(guān)鍵路線為兩條：一一一一和一一一，時間長度都為第四步：在上一步趕工

9、以后得到的四條關(guān)鍵路線中，工作、一都不能再趕工，關(guān)鍵和一一一，時間長度都為天。第三步：在上一步趕工以后得到的兩條關(guān)鍵路線中，工作、能再趕工，唯有工作可以趕工（，原則，它自身可以趕工天關(guān)鍵路線決定了它只能趕工天（原則），之后、都不原則，但次的趕工時間還剩余天（-這之后，關(guān)鍵路線變?yōu)樗臈l：一一一一一、一一一一、一一一一一以及一一一一，工期都為天。次關(guān)鍵路線為兩條：一一一一和一一一，時間長度都為第四步：在上一步趕工以后得到的四條關(guān)鍵路線中，工作、一都不能再趕工，關(guān)鍵和同時趕工原則1天。、一、原則前半句天原則原則后半句，（原則），則總費(fèi)用不變但工期縮短了。趕工以后，關(guān)鍵路線仍是上一步中所述的那四條。第

10、五步：在四條關(guān)鍵路線中，所有關(guān)鍵活動都不能再趕工，所以優(yōu)化過程結(jié)束。綜上所述，在第四步趕工優(yōu)化以后，各工作的正常工作時間（同原始數(shù)據(jù)）和趕工后的由于趕工導(dǎo)致直接費(fèi)用增加額=（4-2）由于趕工導(dǎo)致直接費(fèi)用增加額=（4-2）X6+（3-2）X3+（6-4）X2+（8-7）X3=22（百元），導(dǎo)致間接費(fèi)用節(jié)約額=（22-18）X9=36（百元），所以該項(xiàng)目的總費(fèi)用降低了14百元（=36-22）。因此優(yōu)化后的總費(fèi)用TCi=TCq-14=229+z（-14=198+（4+1+2+2+12+3+5+6）-14=219（百元）。設(shè)節(jié)點(diǎn)i的實(shí)際開始時間為第t.+l天初,t7為項(xiàng)目的最早完成時刻；設(shè)工序（i-j

11、）3yH123yH122H1235657712130,t22Si_、.ty三4,712130,t22Si_、.ty三4,y4211212ty三3,y3311313253656.lity三，y5TOC o 1-5 h z522525ty三，y6633636.nt三0,y04224stJJnt三0,y0s”14334nty三9,y99544545ty三6,y6655656ty三6,y8755757ty三3,y4300+（54X100=30（元。附錄1、雙代號網(wǎng)絡(luò)圖的繪圖原則如下：（1）網(wǎng)絡(luò)圖是有方向的,不允許出現(xiàn)回路,不允許出現(xiàn)從右到左的箭頭。（2）直接連接兩個相鄰節(jié)點(diǎn)之間的活動只能有一個,如果實(shí)

12、在要表示并列關(guān)系可用虛工序。（3）箭線首尾必有節(jié)點(diǎn),不能從箭線中間引出另一條箭線。（4）網(wǎng)絡(luò)圖必須只有一個網(wǎng)絡(luò)始點(diǎn)和一個終點(diǎn)。（5）各項(xiàng)活動之間的銜接必須按邏輯關(guān)系（緊前關(guān)系、緊后關(guān)系）進(jìn)行。（6）事件節(jié)點(diǎn)采用數(shù)字編號,在同一網(wǎng)絡(luò)圖中不允許重復(fù)使用,每條箭線箭頭節(jié)點(diǎn)的編號（）必須大于其箭尾節(jié)點(diǎn)的編號（）。（7）盡量避免箭線交叉（采用過橋法或指向處理法）。（8）標(biāo)注出各項(xiàng)工作的準(zhǔn)確歷時或時間期望值。（）虛工序用虛箭線表示，僅表達(dá)一種工作順序的先后依賴關(guān)系，有兩種作用：如果工序到工序之間順著箭頭方向僅隔一個虛工序，則仍是的緊前活動。如果、b三個活動共用一個開始節(jié)點(diǎn)，則可用虛工序表示這三個活動并行展

13、開且三者都是末端活動。2、時間費(fèi)用優(yōu)化,即如何趕工需要綜合考慮的幾個原則,如下：在關(guān)鍵路線上，選擇趕工費(fèi)用率（即直接費(fèi)用率）最低的活動，首先看其趕工費(fèi)用率是否不超過每天的間接費(fèi)用，如果是那么它值得趕工；否則，會導(dǎo)致總費(fèi)用增加。是否值得趕工，還要看其與之并列的關(guān)鍵活動，即該活動的趕工費(fèi)用率與并列關(guān)鍵活動的趕工費(fèi)用率之和不超過每天間接費(fèi)用，才能導(dǎo)致總費(fèi)用不上升。當(dāng)然如果項(xiàng)目方不在乎總費(fèi)用上升（可能項(xiàng)目方會因此得到另外的別的獎勵）的話，前面兩步的確定的關(guān)鍵活動也是可以趕工的。如果前兩步通過了，請繼續(xù)看：觀察上述選定關(guān)鍵活動自身的趕工時間極限，即目前工作時間與最短工作時間的差值，記為a如果該關(guān)鍵活動有并列關(guān)鍵活動，也要看它們的趕工時間極限。取這些趕工時間極限的最小值，記為。如果并列活動都是非關(guān)鍵活動，那么這一條就不看了，因?yàn)樗鼈兇藭r可以利用總時差而不存在趕工的問題。觀察目前關(guān)鍵路線長度與次關(guān)鍵路線長度的時間差，記為。選定活動的趕工時間也不能超過之。所以，某選定關(guān)鍵活動這一步的實(shí)際趕工時間就是=a后面幾條是對前面原則的提示，并非優(yōu)化原則：注意該選定活動如果有并列關(guān)鍵活動，那么它們必須同時趕工相同的時間；否則只考慮本活動的單獨(dú)趕工就可以了。在每一次趕工壓縮時間以后，都要觀察關(guān)鍵路線和次關(guān)鍵路線是否有變化。一個規(guī)律是關(guān)鍵路線只會越來越多，而