【正文】 , Δ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 時間 — 費(fèi)用優(yōu)化 若加快活動 (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ì)劃 活動 (1, 3)加快 1天， P=4 活動 (4, 5)加快 1天， P=6 0 4 8 12 15 T=13, ΔZ=10. 0 4 7 11 13 80 時間 — 費(fèi)用優(yōu)化 時間 (工期 )—(直接 )費(fèi)用交換過程 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è)活動 (i, j)的時間 費(fèi)用呈連續(xù)單峰下凸曲線。 時間 — 費(fèi)用優(yōu)化的線性規(guī)劃 (LP)模型 0 dij tij Dij 活動時間 活動的直接費(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)用 正常時間 極限時間 82 時間 — 費(fèi)用優(yōu)化 的 LP模型 第一章 確定型網(wǎng)絡(luò)計(jì)劃 設(shè)優(yōu)化目標(biāo)： Z —總 (直接 )費(fèi)用 tij—活動 (i, j)的延續(xù)時間； Pij —活動 (i, j)的費(fèi)用變化率； dij—活動 (i, j)的最短延續(xù)時間； Dij—活動 (i, j)的正常延續(xù)時間； ZDij—活動 (i, j)的正常費(fèi)用； Ti —事項(xiàng)的發(fā)生時間 ， i=1,2,… ,n。 83 時間 — 費(fèi)用優(yōu)化 的 LP模型 第一章 確定型網(wǎng)絡(luò)計(jì)劃 則活動 (i, j)的加快時間為 (Dij – tij)； 活動 (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 時間 — 費(fèi)用優(yōu)化 的 LP模型 第一章 確定型網(wǎng)絡(luò)計(jì)劃 使項(xiàng)目的總 (直接 )費(fèi)用最小 ， 即 考慮約束條件 ， 對任意活動 (i, j)， 應(yīng)有 TTTtTTDtdnjijiijijij??????01)(min),(),(ijjiijDijjiij DPZtPZ ?? ????其中 T為項(xiàng)目要求的工期 。 85 時間 — 費(fèi)用優(yōu)化 的 LP模型 第一章 確定型網(wǎng)絡(luò)計(jì)劃 工程工期 —費(fèi)用優(yōu)化的 LP模型可表述為 )(min),(),(ijjiijDijjiij DPZtPZ ?? ???? 0, 0),( ),( ),( 0 ..1?????????????iijnijijijijjijiTtTTTTjidtjiDtjiTtTts為給定常數(shù)活動活動活動86 網(wǎng)絡(luò)計(jì)劃應(yīng)用 網(wǎng)絡(luò)計(jì)劃應(yīng)用的一般程序?yàn)椋? 1. 確定工程內(nèi)容，做準(zhǔn)備工作 (1) 決定對哪一種產(chǎn)品、哪一種工程采用網(wǎng)絡(luò)計(jì)劃。 (2) 調(diào)研：了解有關(guān)工程的技術(shù)經(jīng)濟(jì)條件，收集資料。 2. 進(jìn)行任務(wù)分解（活動分解） 原則：不易過細(xì)，也不易過粗。適中， (1) 不同執(zhí)行單位的活動分開（責(zé)任分清）； (2) 工作時間有先后差異的活動分開； (3) 使用不同機(jī)器設(shè)備的活動分開； (4) 工藝、工作方法不同的活動分開。 第一章 確定型網(wǎng)絡(luò)計(jì)劃 87 網(wǎng)絡(luò)計(jì)劃應(yīng)用 3. 任務(wù)分析，列出作業(yè)清單 活動名稱內(nèi)容、工作量 (時間 )、先后關(guān)系、消耗資源 …… 4. 繪制一般網(wǎng)絡(luò)圖 順推法、逆推法；要求邏輯關(guān)系準(zhǔn)確、符合繪圖規(guī)則； 5. 計(jì)算時間參數(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ò)圖對活動及其關(guān)系的表示方式不同 ， 但它們的基本原理 、 基本要素是完全一致的 ， 并可對同一問題得出完全相同的結(jié)果 。 89 模型 類型 箭線型網(wǎng)絡(luò) (2個節(jié)點(diǎn)表示一項(xiàng)活動 ) 節(jié)點(diǎn)型網(wǎng)絡(luò) (1個節(jié)點(diǎn)表示一項(xiàng)活動 ) i j A 節(jié)點(diǎn)型網(wǎng)絡(luò) 第一章 確定型網(wǎng)絡(luò)計(jì)劃 網(wǎng)絡(luò)計(jì)劃模型的構(gòu)成 枝線 活動 活動之 間的邏 輯關(guān)系 節(jié)點(diǎn) 活動之 間的邏 輯關(guān)系 活動 流 時間、費(fèi)用、資源等參數(shù) 時間、費(fèi)用、資源等參數(shù) 90 活動 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)活動 ， 關(guān)系如下表 ， 請繪制網(wǎng)絡(luò)圖 。 91 AON網(wǎng)絡(luò)的特點(diǎn)： 1. 不限于一個起點(diǎn)、一個終點(diǎn)； (工程的開工時間以最早開工的起點(diǎn)為準(zhǔn)，工程完工時間取決于最遲完工的終節(jié)點(diǎn) )； 2. 不需要設(shè)置虛活動； 3. 節(jié)點(diǎn)編號是活動代號，不要求從小號指向大號 (逆號存在不影響算法的執(zhí)行 )； 4. 可以表達(dá)網(wǎng)絡(luò)的搭接關(guān)系 。 對大規(guī)模的網(wǎng)絡(luò)，用 AON網(wǎng)絡(luò)表達(dá)更方便。兩種形式的軟件系統(tǒng)處于并存狀況。 節(jié)點(diǎn)型網(wǎng)絡(luò) 第一章 確定型網(wǎng)絡(luò)計(jì)劃 92 蒙塔板諾 (Montabalno) 方法 1. 正向時間 FTi (Forward Time) 活動 i 的正向時間就是從工程開始到該項(xiàng)活動的最長路線的時間 。 開始節(jié)點(diǎn) (活動 )的正向時間就是該活動的時間 ， 而工程終節(jié)點(diǎn) (活動 )中的最大的正向時間就是工程的周期 。 任一節(jié)點(diǎn) (活動 )的正向時間等于其各緊前活動的正向時間與該活動時間 ti 之和的最大值 ， 即 節(jié)點(diǎn)型網(wǎng)絡(luò)時間計(jì)算 第一章 確定型網(wǎng)絡(luò)計(jì)劃 ? ?, f or w a r k ik I PFT M ax FT t???93 2. 反向時間 BTj (Backward Time) 活動 j 的反向時間就是從該項(xiàng)活動開工到工程終點(diǎn)之間最長路線的時間 。 終節(jié)點(diǎn) (活動 )的反向時間就是該活動的時間 ， 而工程開始節(jié)點(diǎn) (活動 )中的最大的反向時間就是工程的周期 。 任一節(jié)點(diǎn) (活動 )的反向時間等于其各緊后活動的反向時間與該活動時間 tj 之和的最大值 ， 即 節(jié)點(diǎn)型網(wǎng)絡(luò)時間計(jì)算 第一章 確定型網(wǎng)絡(luò)計(jì)劃 ? ? , ba c kw a r d.j k jk I SBT M ax BT t??? 注：正向時間和反向時間的計(jì)算具有獨(dú)立性和對稱性 。 94 3. 其它時間參數(shù) 節(jié)點(diǎn)型網(wǎng)絡(luò)時間計(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ò)圖中各活動的正、反向時間。 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ò)時間計(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ò)圖中各活動的時間參數(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ò)時間計(jì)算 第一章 確定型網(wǎng)絡(luò)計(jì)劃 BT FT T=Max {FT}=Max {66, 63}=66 97 活動間的基本邏輯關(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