數(shù)據(jù)挖掘--網(wǎng)絡(luò)分析

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

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

3、1675342ABCDEF2. 繪制網(wǎng)絡(luò)圖需注意：繪制網(wǎng)絡(luò)圖需注意：（1）只有一個源，一個匯）只有一個源，一個匯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)入一個節(jié)點(diǎn)的箭線有多條，但相鄰的）進(jìn)入一個節(jié)點(diǎn)的箭線有多條，但相鄰的兩個節(jié)點(diǎn)之間只能由一條箭

4、線。若相鄰兩結(jié)兩個節(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一、工作時間一、工作時間t ( i , j )的確定的確定ijt ( i , j )確定型確定型 t ( i , j )概率型概率型 t ( i , j )=(a+4m+b)/6 a 最樂觀時間最樂觀時間 m 最大可能時間最大可能時間 b 最悲觀時間最悲觀時間第二節(jié)第二節(jié) 網(wǎng)絡(luò)時間值的計算網(wǎng)絡(luò)時間值的計算二、二、 事項時間參數(shù)計算事項時間參數(shù)計算( (已知已知 t（i , j） ) 1. 1. 事項最早時間事項最早時間: : 表示以它為始點(diǎn)的各工作最早可能開始時間，表示以它為始點(diǎn)的各工作最早可能

6、開始時間，也表示以它為終點(diǎn)的各工作最早可能結(jié)束時間。也表示以它為終點(diǎn)的各工作最早可能結(jié)束時間。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è)單時差四、關(guān)鍵線路與工期四、關(guān)鍵線路與工期 關(guān)鍵線路：總時差為關(guān)鍵線路：總時差為0的工作鏈。的工作鏈。 工期：關(guān)鍵線路上各項活動作業(yè)時工期：關(guān)鍵線路上各項活動作業(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)絡(luò)計劃的其它問題網(wǎng)絡(luò)計劃的其它問題一、網(wǎng)絡(luò)計劃的優(yōu)化一、網(wǎng)絡(luò)計劃的優(yōu)化1. 將串聯(lián)工作改變?yōu)槠叫泄ぷ骰蚪徊婀ぷ鲗⒋?lián)工作改變?yōu)槠叫泄ぷ骰蚪徊婀ぷ?. 利用時差利用時差3. 有限資源的合理分配有限資源的合理分配142AB3567CDEFG283124430258172124242117175202498122124. 時間時間-費(fèi)用優(yōu)化費(fèi)用優(yōu)化兩