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

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

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

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

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

6、開始時間，也表示以它為終點的各工作最早可能結束時間。也表示以它為終點的各工作最早可能結束時間。tE(i)tE(1)=0tE(n)=總最早完工工期總最早完工工期142AB3567CDEFG28312443025817212424211717520作業(yè)最遲開始時間作業(yè)最遲開始時間5 175 172 52 50 89 170 20 221 2421 2417 2117 218 1217 21作業(yè)最遲開始時間作業(yè)最遲開始時間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è)總時差作業(yè)總時差: 在不影響總工期的前提下，某工作可以在不影響總工期的前提下，某工作可以延遲其開始時間的最大幅度。延遲其開始時間的最大幅度。 R(i, j)作業(yè)總時差作業(yè)總時差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è)總時差作業(yè)總時差142AB3567CDEFG283124430258172124242117175205 175 172 52 50 89 170 20 221

8、 2421 2417 2117 218 1217 210000099 (6) 作業(yè)單時差：作業(yè)單時差： 不影響緊后工作最早開始時間的條不影響緊后工作最早開始時間的條件下，此工作可以延遲開始時間的最大幅件下，此工作可以延遲開始時間的最大幅度度。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è)單時差作業(yè)單時差142AB3567CDEFG283124430258172124242117175205 175 172 52 50 89 170 20 221 2421 2417 2117 218 1217 210000009作業(yè)單時差作業(yè)單時差四、關鍵線路與工期四、關鍵線路與工期 關鍵線路：總時差為關鍵線路：總時差為0的工作鏈。的工作鏈。 工期：關鍵線路上各項活動作業(yè)時工期：關鍵線路上各項活動作業(yè)時間之和。間之和。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)絡計劃的其它問題網(wǎng)絡計劃的其它問題一、網(wǎng)絡計劃的優(yōu)化一、網(wǎng)絡計劃的優(yōu)化1. 將串聯(lián)工作改變?yōu)槠叫泄ぷ骰蚪徊婀ぷ鲗⒋?lián)工作改變?yōu)槠叫泄ぷ骰蚪徊婀ぷ?. 利用時差利用時差3. 有限資源的合理分配有限資源的合理分配142AB3567CDEFG283124430258172124242117175202498122124. 時間時間-費用優(yōu)化費用優(yōu)化兩