第21講網(wǎng)絡(luò)優(yōu)化

網(wǎng)絡(luò)圖的優(yōu)化1.時(shí)間—資源的優(yōu)化資源優(yōu)化的要求：保證關(guān)鍵線路上的資源；利用非關(guān)鍵線路上工序的總時(shí)差調(diào)整平衡資源；在資源受到限制時(shí)，可適當(dāng)推遲完工時(shí)間。2.時(shí)間—費(fèi)用的優(yōu)化最小直接費(fèi)用的關(guān)鍵工序調(diào)整法

教材P78例2.3

教材單代號網(wǎng)絡(luò)圖2.16中，已以計(jì)算出關(guān)鍵線路為A→D→E→G,總工期為11天?！鹬袨楣ば虼?，○上方標(biāo)注的數(shù)字為工序工時(shí)，○下方標(biāo)注的數(shù)字為每天所需人力數(shù)，現(xiàn)有工人數(shù)為10人，并假設(shè)這些工人可以完成所有工序中的任何一個(gè)工序。試對此人力資源分配進(jìn)行優(yōu)化。人力資源的網(wǎng)絡(luò)方案圖例5.4ABDCFEG26492733353441工序代號工序工時(shí)工序所需人力數(shù)S工程進(jìn)度表(單位：天)工序工時(shí)t總時(shí)差TF工程進(jìn)度(天)1234567891011A2066B479999———————C31333—D2077E30555F31444—G401111—：為總時(shí)差，人力限制10人。各工序所需人力資源－時(shí)間圖工程進(jìn)度表的調(diào)整(單位：天)工序工時(shí)t總時(shí)差TF工程進(jìn)度(天)1234567891011A2066B479999———————C31333—D2077E30555F31444—G401111—：為總時(shí)差，人力限制10人。調(diào)整中工序不間斷。99994999調(diào)整后的工程進(jìn)度表(單位：天)工序工時(shí)t總時(shí)差TF工程進(jìn)度(天)1234567891011A2066B47———————9999C21333—D3077E30555F31—444G401111—：為總時(shí)差，人力限制10人。調(diào)整后各工序所需人力資源－時(shí)間圖

時(shí)間—費(fèi)用的優(yōu)化最小直接費(fèi)用的關(guān)鍵工序調(diào)整法：費(fèi)用分為：間接費(fèi)用和直接費(fèi)用。1.直接費(fèi)用：包括直接生產(chǎn)工人的工資及附加費(fèi)，設(shè)備能源、工具及材料消耗等直接與完成工序有關(guān)的費(fèi)用。為了縮短工作的作業(yè)時(shí)間，須采用一些技術(shù)組織措施，相應(yīng)會增加一些費(fèi)用，在一定范圍內(nèi)，工作的時(shí)間越短，直接費(fèi)用越大。2.間接費(fèi)用：包括管理費(fèi)、辦公費(fèi)等。間接費(fèi)用常按任務(wù)期的長短分?jǐn)?，在一定條件下，工期越長，間接費(fèi)用越大。費(fèi)用與工期的關(guān)系總費(fèi)用直接費(fèi)用間接費(fèi)用極限時(shí)間正常時(shí)間T′工程(工序)費(fèi)用T′：為使得工程費(fèi)用最低的工程完工時(shí)間工期完成各項(xiàng)工作所需的人力、資源、設(shè)備的費(fèi)用。包括管理費(fèi)、辦公費(fèi)等。直接費(fèi)用與工序所需工時(shí)的關(guān)系直接費(fèi)用A(極限工序)B(正常工序)工時(shí)Didi從正常工時(shí)每縮短一個(gè)單位時(shí)間所增加的費(fèi)用例：設(shè)備維修問題要求：10日內(nèi)完工，應(yīng)該采用什么措施？工序內(nèi)容緊前工序正常時(shí)間突擊時(shí)間直接費(fèi)用率（元/天）ABCDE檢查Ⅰ調(diào)節(jié)Ⅰ檢查Ⅱ調(diào)節(jié)Ⅱ測試系統(tǒng)—A—BB，D7363242411100150200150250

單代號網(wǎng)絡(luò)圖ABCDEST單代號網(wǎng)絡(luò)圖求CPM工序緊前工序DiESEFLSLFTF總時(shí)差SABCDET—A—BB，DE07363200070610120710691212007171012071071012120001100YesYesYes工期：12〔天〕

雙代號網(wǎng)絡(luò)圖23415ABCDE73362雙代號圖計(jì)算事項(xiàng)最早時(shí)間23415ABCDE733620761012工期：12雙代號圖計(jì)算事項(xiàng)最遲時(shí)間23415ABCDE7336207610121210770工序的總時(shí)差工序總時(shí)差TF〔i,j〕:指在不影響整個(gè)工期的前提下，工序最早開始〔或結(jié)束〕的時(shí)間可以推遲的時(shí)間。工序總時(shí)差=最遲開工時(shí)間-最早開工時(shí)間=最遲完工時(shí)間-最早完工時(shí)間TF〔i,j〕=tLF(i,j)-tEF(i,j)=tLF(i,j)-[tE(i)+t(i,j)]=tL(j)-tE(i)-t(i,j)=箭頭事項(xiàng)最遲時(shí)間-箭尾事項(xiàng)最早時(shí)間–工序作業(yè)時(shí)間計(jì)算總時(shí)差，確定關(guān)鍵工序23415ABCDE733620761012121077000110工期：12方案一：突擊工序A緊縮2天23415ABCDE533620569111工期：11關(guān)鍵工序？試求以下方案的關(guān)鍵工序方案一：突擊工序A緊縮2天；方案二：突擊工序A，B，D各緊縮1天；方案三：突擊工序A緊縮2天，突擊工序D緊縮1天；哪個(gè)方案是10天完工的最正確方案？本問題的最正確方案是否唯一？教材P101例5.3假設(shè)公司能提前完成工程的話，有可能得到獎勵(lì)。下表為建筑工程中每項(xiàng)工序的時(shí)間本錢平衡的數(shù)據(jù)，現(xiàn)在的問題是：1.假設(shè)要用額外的資金來加速工程進(jìn)度的話，怎樣才能以最低的本錢在40周內(nèi)完工？2.假設(shè)要把工程完成時(shí)間下降到40周之內(nèi)，那么對一些工序進(jìn)行應(yīng)急處理最節(jié)省的途徑是什么?建筑工程中每項(xiàng)工序的時(shí)間本錢平衡的數(shù)據(jù)工序(紅色為關(guān)鍵工序)時(shí)間(周)成本(萬元)每周的應(yīng)急成本正常應(yīng)急正常應(yīng)急A21182810(6#)B4232425(3#)C10762868(5#)D6426344E43415716(7#)F5318264(2#)G74901024H9620386I7521273J8643493(1#)K4316204L5325355(3#)M21102010N6333516(4#)在關(guān)鍵線路上確定縮短工期〔工作的延續(xù)時(shí)間可在一定條件下和一定范圍內(nèi)以增加費(fèi)用為代價(jià)而縮短〕J工期8→6單代號網(wǎng)絡(luò)圖時(shí)間參數(shù)的計(jì)算計(jì)算順序指標(biāo)↓↓↑↑↓工序代號工序名稱緊前工序后續(xù)工序工期DiESEFLSLFTF0S—A0000001A—B2020202BAC4262603CBD,E,I10616616/20(18)/18=1604DCG6162220→1826→244(2)5ECF,H416201633(31)/20=2006FEJ52025202507GDH7222926→2433→314(2)8HE,GM920/29=293833→3142→403(2)9ICJ716231825210JF,IK,L8→625/23=2533→312534/33=33(32/31=31)011KJN433→3137→3534→3238→36112LJN533→3138→3633→3138→36013MHT2384042→4044→424(2)14NK,LT637(35)/38(36)=38(36)44→4238(36)44→42015TN044→4244→4244→4244→420F工期5→3原來的關(guān)鍵路線已改變〔有四條〕，且總工期為40周STIMHGDLANKJFCEB作業(yè)預(yù)習(xí)：第5章圖的根本概念與建模。作業(yè)：習(xí)題5.1〔要求：雙代號與單代號兩種方法〕習(xí)題2.1習(xí)題2.3習(xí)題2.4習(xí)題2.5〔要求：整數(shù)規(guī)劃與動態(tài)規(guī)劃兩種方法〕

特別提醒：下周星期二〔4.28〕交作業(yè)以及期中測驗(yàn)！期中測驗(yàn)題目1。習(xí)題1.4〔建模以及求解〕2。習(xí)題2.6〔建模以及求解〕3。習(xí)題5.12〔只建模〕4。畫出下表所示的網(wǎng)絡(luò)圖,計(jì)算各種必要的時(shí)間參數(shù)并確定工期與關(guān)鍵路線，指出在不影響整個(gè)工期的情況下每道工序允許延誤的時(shí)間〔單位：天〕。工序時(shí)間緊前工序工序時(shí)間緊前工序A2—E4B，CB6—F3B，CC3AG3D，ED5AH2D，E，F(xiàn)

謝謝！

再見！2.2概率型網(wǎng)絡(luò)圖在不具備定額和類似工序作業(yè)時(shí)間消耗的統(tǒng)計(jì)資料，且作業(yè)時(shí)間較長，未知的和難估計(jì)的因素較多的情況下，對完成工序可估計(jì)三種時(shí)間，之后計(jì)算它們的平均時(shí)間作為該工序的作業(yè)時(shí)間。三種時(shí)間是1.樂觀時(shí)間：ta2.最可能時(shí)間：tm3.悲觀時(shí)間：tb工序的作業(yè)時(shí)間(期望)與方差概率型網(wǎng)絡(luò)圖假設(shè)：1.各工序的時(shí)間分布相互隨機(jī)獨(dú)立；2.關(guān)鍵線路一直比其他任何線路所需時(shí)間都長；3.工程時(shí)間的概率分布是一個(gè)正態(tài)分布。工程工程(工序)時(shí)間的概率分布〔一：正態(tài)分布〕ta

tb

tm

計(jì)算過程查標(biāo)準(zhǔn)正態(tài)分布表得：0.5871。即工程在60天完成的概率