【正文】 , ΔZ=12. 1 3 5 4 2 4, 5 7, 7 3, 2 1 8, 4 3, 3 5, 3 2, 6 0 4 7 10 13 0 4 8 11 13 tij, pij 1 3 5 4 2 3, 5 7, 7 3, 2 1 7, 4 3, 3 6, 3 3, 6 79 時(shí)間 — 費(fèi)用優(yōu)化 若加快活動(dòng) (1, 3)(4, 5)各 1天，仍有工期為 13天，但是 △ Z=10。 T=15 (正常工期 ), ΔZ=0. 1 3 5 4 2 4, 5 7, 7 3, 2 1 1 8, 4 4, 3 6, 3 3, 6 1 7, 7 1 3 5 4 2 4, 5 3, 2 7, 4 4, 3 6, 3 2, 6 第一章 確定型網(wǎng)絡(luò)計(jì)劃 活動(dòng) (1, 3)加快 1天， P=4 活動(dòng) (4, 5)加快 1天， P=6 0 4 8 12 15 T=13, ΔZ=10. 0 4 7 11 13 80 時(shí)間 — 費(fèi)用優(yōu)化 時(shí)間 (工期 )—(直接 )費(fèi)用交換過(guò)程 0 13 14 15 {tij} {tij} TD ZD (13, 12) (13, 10) (14, 3) (15, 0) 第一章 確定型網(wǎng)絡(luò)計(jì)劃 (T, △ Z) (14, 4) 81 設(shè)活動(dòng) (i, j)的時(shí)間 費(fèi)用呈連續(xù)單峰下凸曲線。 時(shí)間 — 費(fèi)用優(yōu)化的線性規(guī)劃 (LP)模型 0 dij tij Dij 活動(dòng)時(shí)間 活動(dòng)的直接費(fèi)用 Zdij Zij ZDij 極限點(diǎn) 正常點(diǎn) 第一章 確定型網(wǎng)絡(luò)計(jì)劃 △ Z Dij – tij Pij = Zdij ZDij Dij dij Pij = 極限費(fèi)用 正常費(fèi)用 正常時(shí)間 極限時(shí)間 82 時(shí)間 — 費(fèi)用優(yōu)化 的 LP模型 第一章 確定型網(wǎng)絡(luò)計(jì)劃 設(shè)優(yōu)化目標(biāo)： Z —總 (直接 )費(fèi)用 tij—活動(dòng) (i, j)的延續(xù)時(shí)間； Pij —活動(dòng) (i, j)的費(fèi)用變化率； dij—活動(dòng) (i, j)的最短延續(xù)時(shí)間； Dij—活動(dòng) (i, j)的正常延續(xù)時(shí)間； ZDij—活動(dòng) (i, j)的正常費(fèi)用； Ti —事項(xiàng)的發(fā)生時(shí)間 ， i=1,2,… ,n。 83 時(shí)間 — 費(fèi)用優(yōu)化 的 LP模型 第一章 確定型網(wǎng)絡(luò)計(jì)劃 則活動(dòng) (i, j)的加快時(shí)間為 (Dij – tij)； 活動(dòng) (i, j)的追加費(fèi)用 Pij (Dij – tij)； 項(xiàng)目的正常費(fèi)用 ZD = ∑Zdij； 項(xiàng)目的追加費(fèi)用 △ Z = ∑ Pij (Dij – tij) ； 故項(xiàng)目的總 (直接 )費(fèi)用為： )()(),(),(),(ijjiijDijjiijijijjiijDDPZtPtDPZZ??????????常數(shù) 84 時(shí)間 — 費(fèi)用優(yōu)化 的 LP模型 第一章 確定型網(wǎng)絡(luò)計(jì)劃 使項(xiàng)目的總 (直接 )費(fèi)用最小 ， 即 考慮約束條件 ， 對(duì)任意活動(dòng) (i, j)， 應(yīng)有 TTTtTTDtdnjijiijijij??????01)(min),(),(ijjiijDijjiij DPZtPZ ?? ????其中 T為項(xiàng)目要求的工期 。 85 時(shí)間 — 費(fèi)用優(yōu)化 的 LP模型 第一章 確定型網(wǎng)絡(luò)計(jì)劃 工程工期 —費(fèi)用優(yōu)化的 LP模型可表述為 )(min),(),(ijjiijDijjiij DPZtPZ ?? ???? 0, 0),( ),( ),( 0 ..1?????????????iijnijijijijjijiTtTTTTjidtjiDtjiTtTts為給定常數(shù)活動(dòng)活動(dòng)活動(dòng)86 網(wǎng)絡(luò)計(jì)劃應(yīng)用 網(wǎng)絡(luò)計(jì)劃應(yīng)用的一般程序?yàn)椋? 1. 確定工程內(nèi)容，做準(zhǔn)備工作 (1) 決定對(duì)哪一種產(chǎn)品、哪一種工程采用網(wǎng)絡(luò)計(jì)劃。 (2) 調(diào)研：了解有關(guān)工程的技術(shù)經(jīng)濟(jì)條件，收集資料。 2. 進(jìn)行任務(wù)分解（活動(dòng)分解） 原則：不易過(guò)細(xì)，也不易過(guò)粗。適中， (1) 不同執(zhí)行單位的活動(dòng)分開(kāi)（責(zé)任分清）； (2) 工作時(shí)間有先后差異的活動(dòng)分開(kāi)； (3) 使用不同機(jī)器設(shè)備的活動(dòng)分開(kāi)； (4) 工藝、工作方法不同的活動(dòng)分開(kāi)。 第一章 確定型網(wǎng)絡(luò)計(jì)劃 87 網(wǎng)絡(luò)計(jì)劃應(yīng)用 3. 任務(wù)分析，列出作業(yè)清單 活動(dòng)名稱內(nèi)容、工作量 (時(shí)間 )、先后關(guān)系、消耗資源 …… 4. 繪制一般網(wǎng)絡(luò)圖 順推法、逆推法；要求邏輯關(guān)系準(zhǔn)確、符合繪圖規(guī)則； 5. 計(jì)算時(shí)間參數(shù)（完工期、關(guān)鍵路線） 6. 優(yōu)化調(diào)整 明確優(yōu)化目標(biāo)，選擇最優(yōu)方案； 7. 實(shí)施最優(yōu)計(jì)劃 有效的監(jiān)督和控制，定期或不定期的檢查執(zhí)行情況，修改網(wǎng)絡(luò)計(jì)劃。 第一章 確定型網(wǎng)絡(luò)計(jì)劃 88 網(wǎng)絡(luò)計(jì)劃模型的兩種類型： 箭線型網(wǎng)絡(luò) (AOA, Activity on Arrow Network or Double symbol work) 節(jié)點(diǎn)型網(wǎng)絡(luò) (AON, Activity on Node Network or Single symbol work) 節(jié)點(diǎn)型網(wǎng)絡(luò) 第一章 確定型網(wǎng)絡(luò)計(jì)劃 盡管兩種類型的網(wǎng)絡(luò)圖對(duì)活動(dòng)及其關(guān)系的表示方式不同 ， 但它們的基本原理 、 基本要素是完全一致的 ， 并可對(duì)同一問(wèn)題得出完全相同的結(jié)果 。 89 模型 類型 箭線型網(wǎng)絡(luò) (2個(gè)節(jié)點(diǎn)表示一項(xiàng)活動(dòng) ) 節(jié)點(diǎn)型網(wǎng)絡(luò) (1個(gè)節(jié)點(diǎn)表示一項(xiàng)活動(dòng) ) i j A 節(jié)點(diǎn)型網(wǎng)絡(luò) 第一章 確定型網(wǎng)絡(luò)計(jì)劃 網(wǎng)絡(luò)計(jì)劃模型的構(gòu)成 枝線 活動(dòng) 活動(dòng)之 間的邏 輯關(guān)系 節(jié)點(diǎn) 活動(dòng)之 間的邏 輯關(guān)系 活動(dòng) 流 時(shí)間、費(fèi)用、資源等參數(shù) 時(shí)間、費(fèi)用、資源等參數(shù) 90 活動(dòng) A B C D E F G 緊前事件 A B B CD CDE AOA Network AON Network 1 2 3 4 5 6 G B C D E F A A C B D E F G 節(jié)點(diǎn)型網(wǎng)絡(luò) 第一章 確定型網(wǎng)絡(luò)計(jì)劃 例 . 某工程有 7項(xiàng)活動(dòng) ， 關(guān)系如下表 ， 請(qǐng)繪制網(wǎng)絡(luò)圖 。 91 AON網(wǎng)絡(luò)的特點(diǎn)： 1. 不限于一個(gè)起點(diǎn)、一個(gè)終點(diǎn)； (工程的開(kāi)工時(shí)間以最早開(kāi)工的起點(diǎn)為準(zhǔn)，工程完工時(shí)間取決于最遲完工的終節(jié)點(diǎn) )； 2. 不需要設(shè)置虛活動(dòng)； 3. 節(jié)點(diǎn)編號(hào)是活動(dòng)代號(hào)，不要求從小號(hào)指向大號(hào) (逆號(hào)存在不影響算法的執(zhí)行 )； 4. 可以表達(dá)網(wǎng)絡(luò)的搭接關(guān)系 。 對(duì)大規(guī)模的網(wǎng)絡(luò)，用 AON網(wǎng)絡(luò)表達(dá)更方便。兩種形式的軟件系統(tǒng)處于并存狀況。 節(jié)點(diǎn)型網(wǎng)絡(luò) 第一章 確定型網(wǎng)絡(luò)計(jì)劃 92 蒙塔板諾 (Montabalno) 方法 1. 正向時(shí)間 FTi (Forward Time) 活動(dòng) i 的正向時(shí)間就是從工程開(kāi)始到該項(xiàng)活動(dòng)的最長(zhǎng)路線的時(shí)間 。 開(kāi)始節(jié)點(diǎn) (活動(dòng) )的正向時(shí)間就是該活動(dòng)的時(shí)間 ， 而工程終節(jié)點(diǎn) (活動(dòng) )中的最大的正向時(shí)間就是工程的周期 。 任一節(jié)點(diǎn) (活動(dòng) )的正向時(shí)間等于其各緊前活動(dòng)的正向時(shí)間與該活動(dòng)時(shí)間 ti 之和的最大值 ， 即 節(jié)點(diǎn)型網(wǎng)絡(luò)時(shí)間計(jì)算 第一章 確定型網(wǎng)絡(luò)計(jì)劃 ? ?, f or w a r k ik I PFT M ax FT t???93 2. 反向時(shí)間 BTj (Backward Time) 活動(dòng) j 的反向時(shí)間就是從該項(xiàng)活動(dòng)開(kāi)工到工程終點(diǎn)之間最長(zhǎng)路線的時(shí)間 。 終節(jié)點(diǎn) (活動(dòng) )的反向時(shí)間就是該活動(dòng)的時(shí)間 ， 而工程開(kāi)始節(jié)點(diǎn) (活動(dòng) )中的最大的反向時(shí)間就是工程的周期 。 任一節(jié)點(diǎn) (活動(dòng) )的反向時(shí)間等于其各緊后活動(dòng)的反向時(shí)間與該活動(dòng)時(shí)間 tj 之和的最大值 ， 即 節(jié)點(diǎn)型網(wǎng)絡(luò)時(shí)間計(jì)算 第一章 確定型網(wǎng)絡(luò)計(jì)劃 ? ? , ba c kw a r d.j k jk I SBT M ax BT t??? 注：正向時(shí)間和反向時(shí)間的計(jì)算具有獨(dú)立性和對(duì)稱性 。 94 3. 其它時(shí)間參數(shù) 節(jié)點(diǎn)型網(wǎng)絡(luò)時(shí)間計(jì)算 第一章 確定型網(wǎng)絡(luò)計(jì)劃 TEF = FT TES =TEF t TLS = T BT TLF = TLS + t S = TLS TES =T LF T EF SF=Min(TES)TEF IS 95 例 . 計(jì)算下列節(jié)點(diǎn)型網(wǎng)絡(luò)圖中各活動(dòng)的正、反向時(shí)間。 B G A D C F E H 5 15 20 30 9 3 7 17 5 9 20 39 12 66 63 46 62 66 35 57 30 20 27 17 BT FT 節(jié)點(diǎn)型網(wǎng)絡(luò)時(shí)間計(jì)算 第一章 確定型網(wǎng)絡(luò)計(jì)劃 由此可得工程周期為 T=Max {FT}=Max {66, 63}=66 或 T=Max {BT}=Max {62, 66}=66 96 例 . 計(jì)算節(jié)點(diǎn)型網(wǎng)絡(luò)圖中各活動(dòng)的時(shí)間參數(shù)，求關(guān)鍵路線。 B G A D C F E H 5 15 20 30 9 3 7 17 5 9 20 39 12 66 63 46 62 66 35 57 30 20 27 17 EF LF ES LS EF=FT ES= EF t LS=T BT LF= LS + t S= LF EF= LS ES 5 9 20 39 12 66 63 46 0 0 5 9 9 46 46 39 4 0 31 9 36 46 49 39 9 9 46 39 39 66 66 46 S 4 0 26 0 27 0 3 0 9 30 7 20 關(guān)鍵路線 : G→C→E→D 節(jié)點(diǎn)型網(wǎng)絡(luò)時(shí)間計(jì)算 第一章 確定型網(wǎng)絡(luò)計(jì)劃 BT FT T=Max {FT}=Max {66, 63}=66 97 活動(dòng)間的基本邏輯關(guān)系： 依次關(guān)系 1 2 3 A B AOA work AON work A B 搭接網(wǎng)絡(luò)計(jì)劃模型 第一章 確定型網(wǎng)絡(luò)計(jì)劃 平行關(guān)系 AOA work 1 2 3 A B C 1 2 3 A B C AON wor