1、燕山大學(xué)經(jīng)濟(jì)管理學(xué)院燕山大學(xué)經(jīng)濟(jì)管理學(xué)院運(yùn)籌學(xué)課程教學(xué)課題組編制運(yùn)籌學(xué)課程教學(xué)課題組編制2第八章第八章網(wǎng)絡(luò)計(jì)劃網(wǎng)絡(luò)計(jì)劃一、網(wǎng)絡(luò)計(jì)劃原理一、網(wǎng)絡(luò)計(jì)劃原理 1. 概念概念：以網(wǎng)絡(luò)圖的形式制定計(jì)劃，求：以網(wǎng)絡(luò)圖的形式制定計(jì)劃，求得計(jì)劃的最優(yōu)方案。并據(jù)以組織和計(jì)劃生得計(jì)劃的最優(yōu)方案。并據(jù)以組織和計(jì)劃生產(chǎn)，達(dá)到預(yù)定目標(biāo)的一種科學(xué)的管理方法。產(chǎn)，達(dá)到預(yù)定目標(biāo)的一種科學(xué)的管理方法。 2. 原理原理：利用網(wǎng)絡(luò)圖表達(dá)計(jì)劃任務(wù)的進(jìn)：利用網(wǎng)絡(luò)圖表達(dá)計(jì)劃任務(wù)的進(jìn)度安排及各項(xiàng)工作之間的相互關(guān)系，并進(jìn)度安排及各項(xiàng)工作之間的相互關(guān)系，并進(jìn)行網(wǎng)絡(luò)分析。通過相應(yīng)的網(wǎng)絡(luò)時(shí)間值的計(jì)行網(wǎng)絡(luò)分析。通過相應(yīng)的網(wǎng)絡(luò)時(shí)間值的計(jì)算，找出影響全

2、局的算，找出影響全局的關(guān)鍵工作關(guān)鍵工作和和關(guān)鍵線路關(guān)鍵線路，利用時(shí)間差，不斷改善網(wǎng)絡(luò)計(jì)劃，求得工利用時(shí)間差，不斷改善網(wǎng)絡(luò)計(jì)劃，求得工期、成本、資源的優(yōu)化方案。期、成本、資源的優(yōu)化方案。二、網(wǎng)絡(luò)圖的繪制二、網(wǎng)絡(luò)圖的繪制 1. 網(wǎng)絡(luò)圖的構(gòu)成網(wǎng)絡(luò)圖的構(gòu)成 （1）作業(yè)：）作業(yè)：代號或工作名稱代號或工作名稱需要的資源或時(shí)間需要的資源或時(shí)間ji C 37846（2） 事項(xiàng)：事項(xiàng)：i （3） 線路：從始點(diǎn)事項(xiàng)開始，順箭線方線路：從始點(diǎn)事項(xiàng)開始，順箭線方向連續(xù)不斷的到達(dá)終點(diǎn)事項(xiàng)的一條通道。向連續(xù)不斷的到達(dá)終點(diǎn)事項(xiàng)的一條通道。2. 繪制網(wǎng)絡(luò)圖需注意：繪制網(wǎng)絡(luò)圖需注意：（1）只有一個(gè)源，一個(gè)匯）只有一個(gè)源，一個(gè)匯

3、1675342ABCDEF2. 繪制網(wǎng)絡(luò)圖需注意：繪制網(wǎng)絡(luò)圖需注意：（1）只有一個(gè)源，一個(gè)匯）只有一個(gè)源，一個(gè)匯17532ABCDEF（2）箭線方向一律由左向右，不得反向）箭線方向一律由左向右，不得反向（3）節(jié)點(diǎn)保證）節(jié)點(diǎn)保證 ijj i（4）編號不準(zhǔn)相同，可以連續(xù)編，也可以）編號不準(zhǔn)相同，可以連續(xù)編，也可以不連續(xù)編。不連續(xù)編。（5）各作業(yè)之間有先后平行關(guān)系，但不）各作業(yè)之間有先后平行關(guān)系，但不允許有回路。允許有回路。1243ABDC15432ABCD（6）箭線首尾必須有結(jié)點(diǎn)）箭線首尾必須有結(jié)點(diǎn)（7）進(jìn)入一個(gè)節(jié)點(diǎn)的箭線有多條，但相鄰的）進(jìn)入一個(gè)節(jié)點(diǎn)的箭線有多條，但相鄰的兩個(gè)節(jié)點(diǎn)之間只能由一條箭

4、線。若相鄰兩結(jié)兩個(gè)節(jié)點(diǎn)之間只能由一條箭線。若相鄰兩結(jié)點(diǎn)間有多條箭線，除一條外，其余用虛箭線點(diǎn)間有多條箭線，除一條外，其余用虛箭線予以分開。予以分開。 （8）網(wǎng)絡(luò)圖中不允許由雙向箭線，無箭頭）網(wǎng)絡(luò)圖中不允許由雙向箭線，無箭頭箭線。箭線。（9）應(yīng)盡量減少交叉和不必要的需箭線。）應(yīng)盡量減少交叉和不必要的需箭線。3. 繪制網(wǎng)絡(luò)圖舉例繪制網(wǎng)絡(luò)圖舉例 例例1：作業(yè)作業(yè)代號代號ABDECFG后續(xù)后續(xù)作業(yè)作業(yè)BCDEFGFG-123456ABCDEFG作業(yè)作業(yè)代號代號ABDECFG后續(xù)后續(xù)作業(yè)作業(yè)BCDEFGFG-3. 繪制網(wǎng)絡(luò)圖舉例繪制網(wǎng)絡(luò)圖舉例 例例2：代碼代碼ABCDEFG緊前工作緊前工作-ACBCDE

5、F代碼代碼ABCDEFG緊前工作緊前工作-ACBCDEF142AB3567CDEFG28312443一、工作時(shí)間一、工作時(shí)間t ( i , j )的確定的確定ijt ( i , j )確定型確定型 t ( i , j )概率型概率型 t ( i , j )=(a+4m+b)/6 a 最樂觀時(shí)間最樂觀時(shí)間 m 最大可能時(shí)間最大可能時(shí)間 b 最悲觀時(shí)間最悲觀時(shí)間第二節(jié)第二節(jié) 網(wǎng)絡(luò)時(shí)間值的計(jì)算網(wǎng)絡(luò)時(shí)間值的計(jì)算二、二、 事項(xiàng)時(shí)間參數(shù)計(jì)算事項(xiàng)時(shí)間參數(shù)計(jì)算( (已知已知 t（i , j） ) 1. 1. 事項(xiàng)最早時(shí)間事項(xiàng)最早時(shí)間: : 表示以它為始點(diǎn)的各工作最早可能開始時(shí)間，表示以它為始點(diǎn)的各工作最早可能

6、開始時(shí)間，也表示以它為終點(diǎn)的各工作最早可能結(jié)束時(shí)間。也表示以它為終點(diǎn)的各工作最早可能結(jié)束時(shí)間。tE(i)tE(1)=0tE(n)=總最早完工工期總最早完工工期142AB3567CDEFG28312443025817212424211717520作業(yè)最遲開始時(shí)間作業(yè)最遲開始時(shí)間5 175 172 52 50 89 170 20 221 2421 2417 2117 218 1217 21作業(yè)最遲開始時(shí)間作業(yè)最遲開始時(shí)間tLS(i, j) = tLF(i, j) -tijjk1ik2t ijt j k2t jk1tLS(j , kl)tLS(j,k2)tES(i, j)tEF(i, j)tLS(i

7、, j)tLF(i, j)tLS(i, j)=mintLS(j,k)-tjk (5) 作業(yè)總時(shí)差作業(yè)總時(shí)差: 在不影響總工期的前提下，某工作可以在不影響總工期的前提下，某工作可以延遲其開始時(shí)間的最大幅度。延遲其開始時(shí)間的最大幅度。 R(i, j)作業(yè)總時(shí)差作業(yè)總時(shí)差R(i, j)=tLS(i, j)-tES(i, j)=tLF(i, j)-tEF(i, j)tES(i, j)tEF(i, j)tLS(i, j)tLF(i, j)ij作業(yè)總時(shí)差作業(yè)總時(shí)差142AB3567CDEFG283124430258172124242117175205 175 172 52 50 89 170 20 221

8、 2421 2417 2117 218 1217 210000099 (6) 作業(yè)單時(shí)差：作業(yè)單時(shí)差： 不影響緊后工作最早開始時(shí)間的條不影響緊后工作最早開始時(shí)間的條件下，此工作可以延遲開始時(shí)間的最大幅件下，此工作可以延遲開始時(shí)間的最大幅度度。r(i, j)=tES(j, k)-tEF(i, j) = tES(j, k)-(tES(i, j)+tij)tES(i, j)tEF(i, j)tLS(i, j)tLF(i, j)ij jktES(j, k) tEF(j, k)tLS(j, k)tLF(j, k)tE (j)tL (j)142AB3567CDEFG28312443025817212424

9、2117175205 175 172 52 50 89 170 20 221 2421 2417 2117 218 1217 210作業(yè)單時(shí)差作業(yè)單時(shí)差142AB3567CDEFG283124430258172124242117175205 175 172 52 50 89 170 20 221 2421 2417 2117 218 1217 210000009作業(yè)單時(shí)差作業(yè)單時(shí)差四、關(guān)鍵線路與工期四、關(guān)鍵線路與工期 關(guān)鍵線路：總時(shí)差為關(guān)鍵線路：總時(shí)差為0的工作鏈。的工作鏈。 工期：關(guān)鍵線路上各項(xiàng)活動作業(yè)時(shí)工期：關(guān)鍵線路上各項(xiàng)活動作業(yè)時(shí)間之和。間之和。142AB3567CDEFG2831244

10、30258172124242117175205 175 172 52 50 89 170 20 221 2421 2417 2117 218 2117 210000099142AB3567CDEFG283124430258172124242117175205 175 172 52 50 89 170 20 221 2421 2417 2117 218 2117 21000009912598763452323124001第三節(jié)第三節(jié) 網(wǎng)絡(luò)計(jì)劃的其它問題網(wǎng)絡(luò)計(jì)劃的其它問題一、網(wǎng)絡(luò)計(jì)劃的優(yōu)化一、網(wǎng)絡(luò)計(jì)劃的優(yōu)化1. 將串聯(lián)工作改變?yōu)槠叫泄ぷ骰蚪徊婀ぷ鲗⒋?lián)工作改變?yōu)槠叫泄ぷ骰蚪徊婀ぷ?. 利用時(shí)差利用時(shí)差3. 有限資源的合理分配有限資源的合理分配142AB3567CDEFG283124430258172124242117175202498122124. 時(shí)間時(shí)間-費(fèi)用優(yōu)化費(fèi)用優(yōu)化兩