運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃

1、 6.1 網(wǎng)絡(luò)計(jì)劃圖的繪制網(wǎng)絡(luò)計(jì)劃圖的繪制 6.2 時(shí)間參數(shù)計(jì)算與關(guān)鍵路線確定時(shí)間參數(shù)計(jì)算與關(guān)鍵路線確定 6.3 網(wǎng)絡(luò)圖的調(diào)整及優(yōu)化網(wǎng)絡(luò)圖的調(diào)整及優(yōu)化第六章第六章 網(wǎng)絡(luò)計(jì)劃（工程計(jì)劃問題）網(wǎng)絡(luò)計(jì)劃（工程計(jì)劃問題）運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃1.問題的一般提法：?jiǎn)栴}的一般提法： 設(shè)有一項(xiàng)工程，可分為若干道工序，已知各工序間設(shè)有一項(xiàng)工程，可分為若干道工序，已知各工序間的先后關(guān)系以及各工序所需時(shí)間的先后關(guān)系以及各工序所需時(shí)間t。問：?jiǎn)枺海?）工程完工期）工程完工期T？（2）工程的關(guān)鍵工序有哪些？）工程的關(guān)鍵工序有哪些？（3）若工序時(shí)間）若工序時(shí)間T具有隨機(jī)性，則期望完工期具有隨機(jī)性，則期望完工期TE=? 完

2、工期為某天的可能性多大？完工期為某天的可能性多大？（4）費(fèi)用優(yōu)化和資源平衡。）費(fèi)用優(yōu)化和資源平衡。運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃2.解法解法關(guān)鍵路徑法（關(guān)鍵路徑法（CPM方法）方法）計(jì)劃評(píng)審法（計(jì)劃評(píng)審法（PERT方法）方法）l相同點(diǎn)：相同點(diǎn)：l不同點(diǎn)：不同點(diǎn)：PERT法：注重于對(duì)工程安排的評(píng)價(jià)與審查。法：注重于對(duì)工程安排的評(píng)價(jià)與審查。CPM方法：注重于時(shí)間、成本和資源的優(yōu)化；方法：注重于時(shí)間、成本和資源的優(yōu)化；均是用網(wǎng)絡(luò)表示工程項(xiàng)目，以確定關(guān)鍵路線均是用網(wǎng)絡(luò)表示工程項(xiàng)目，以確定關(guān)鍵路線。運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃6.1 網(wǎng)絡(luò)計(jì)劃圖的繪制網(wǎng)絡(luò)計(jì)劃圖的繪制1.繪圖順序：按工序先后從左至右繪圖順序：按工序先后從左

3、至右2.網(wǎng)絡(luò)圖的組成要素網(wǎng)絡(luò)圖的組成要素 用用 表示。表示。 i j （1）?。▽?shí)箭線）弧（實(shí)箭線）表示工序，表示工序，（2）頂點(diǎn)（結(jié)點(diǎn)）：）頂點(diǎn)（結(jié)點(diǎn)）： 表示相鄰工序時(shí)間分界點(diǎn)，稱為事表示相鄰工序時(shí)間分界點(diǎn)，稱為事項(xiàng)，項(xiàng)， i用用 表示表示（3）相鄰?。海┫噜徎。?表示工序的前后銜接關(guān)系，稱為緊前表示工序的前后銜接關(guān)系，稱為緊前 （或緊后）關(guān)系。（或緊后）關(guān)系。如如 i Akj BA是是B的緊前工序，的緊前工序，B是是A的緊后工序。的緊后工序。A運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃（4）虛工序（虛箭線）虛工序（虛箭線）為表示工序前后銜接關(guān)系的需要而增加的。為表示工序前后銜接關(guān)系的需要而增加的。用用 表示。

4、表示。ij3.繪圖規(guī)則：繪圖規(guī)則：（1）圖中不能有缺口，多重邊和回路。）圖中不能有缺口，多重邊和回路。123456起點(diǎn)起點(diǎn)終點(diǎn)終點(diǎn)（缺口：有幾個(gè)總開工事項(xiàng)或幾個(gè)總完工事項(xiàng)）（缺口：有幾個(gè)總開工事項(xiàng)或幾個(gè)總完工事項(xiàng)）處理方法：在處理方法：在5、6之間加道虛工序之間加道虛工序A運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃（多重邊：兩點(diǎn)之間有多于一條邊）（多重邊：兩點(diǎn)之間有多于一條邊）處理方法：增加虛工序處理方法：增加虛工序（回路：工序循環(huán)進(jìn)行，永遠(yuǎn)不能完成不允（回路：工序循環(huán)進(jìn)行，永遠(yuǎn)不能完成不允許）許）（）（）（）（）（）（）（）（）（）（）運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃（2）網(wǎng)絡(luò)圖中的事項(xiàng)要從左至右統(tǒng)一編號(hào)，每道工序網(wǎng)絡(luò)圖中的

5、事項(xiàng)要從左至右統(tǒng)一編號(hào)，每道工序 的箭尾事項(xiàng)號(hào)應(yīng)小于箭頭事項(xiàng)號(hào)。的箭尾事項(xiàng)號(hào)應(yīng)小于箭頭事項(xiàng)號(hào)。12 正確正確21錯(cuò)誤錯(cuò)誤（3）盡量避免箭桿交叉。）盡量避免箭桿交叉。1234567處理方法：先畫草圖，再整理。處理方法：先畫草圖，再整理。1234567運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃4.繪圖準(zhǔn)備工作繪圖準(zhǔn)備工作（1）確定目標(biāo)）確定目標(biāo)（以誰為主）（以誰為主）時(shí)間時(shí)間資源資源費(fèi)用費(fèi)用（2）工程任務(wù)的分解和分析；）工程任務(wù)的分解和分析；分析工程由哪些工序組成并列出全部工序及代號(hào)清單。分析工程由哪些工序組成并列出全部工序及代號(hào)清單。（3）確定各工序之間先后順序及銜接關(guān)系；）確定各工序之間先后順序及銜接關(guān)系；要確定每

6、道工序開工之前有哪些工序必須先期完成。要確定每道工序開工之前有哪些工序必須先期完成。（4）確定各工序時(shí)間。）確定各工序時(shí)間。要確定每道工序的完成所需時(shí)間。要確定每道工序的完成所需時(shí)間。運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃例例1（P13例）某工廠進(jìn)行技術(shù)改造的工作表如下：例）某工廠進(jìn)行技術(shù)改造的工作表如下：工序代號(hào)工序代號(hào)工序名稱工序名稱緊前工序緊前工序工作時(shí)間工作時(shí)間（周）（周）A拆遷拆遷/2B工程設(shè)計(jì)工程設(shè)計(jì)/3C土建工程土建工程設(shè)計(jì)設(shè)計(jì)B2.5D采購設(shè)備采購設(shè)備B6E廠房土建廠房土建C，A20F設(shè)備安裝設(shè)備安裝D，E4G設(shè)備調(diào)試設(shè)備調(diào)試F2運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃1A(2)3B(3)2C(2.5)4D(6)E

7、(20)5F(4)6G(2)運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃6.2 時(shí)間參數(shù)計(jì)算與關(guān)鍵路線確定時(shí)間參數(shù)計(jì)算與關(guān)鍵路線確定CPM方法方法一、求完工期一、求完工期T（標(biāo)號(hào)從前往后）標(biāo)號(hào)從前往后）1.標(biāo)出各事項(xiàng)的最早開始時(shí)間標(biāo)出各事項(xiàng)的最早開始時(shí)間tE(i)i20表示第表示第i個(gè)事項(xiàng)最早在第個(gè)事項(xiàng)最早在第20天才開始。天才開始。（1）給始點(diǎn)）給始點(diǎn) 標(biāo)標(biāo)10（2）給任意事項(xiàng)）給任意事項(xiàng) 標(biāo)標(biāo)jtE(j)運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃（3）終點(diǎn)）終點(diǎn) 的的 即為完工期即為完工期T（最快的完工期）最快的完工期）n)( jtE),()(maxjititE=max以以 為箭頭（終點(diǎn)）的各箭的箭尾為箭頭（終點(diǎn)）的各箭的箭尾 + 箭

8、長(zhǎng)箭長(zhǎng) tij j8510L(3)K(6)25173131=max25+6,17+3表示第表示第10個(gè)事項(xiàng)最早在第個(gè)事項(xiàng)最早在第31天開始。天開始。之所以取最大，因?yàn)樵诘谥匀∽畲?，因?yàn)樵诘?0天，天，L工序工序已完成，但已完成，但k工序未完成。工序未完成。tE(n)運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃二、求關(guān)鍵路（關(guān)鍵工序）（標(biāo)號(hào)從后往前）二、求關(guān)鍵路（關(guān)鍵工序）（標(biāo)號(hào)從后往前）1.標(biāo)出各事項(xiàng)的最遲開始時(shí)間標(biāo)出各事項(xiàng)的最遲開始時(shí)間tL( i )（1）給終點(diǎn)）給終點(diǎn) 標(biāo)號(hào)標(biāo)號(hào)nT（2）給任一事項(xiàng)）給任一事項(xiàng) 標(biāo)號(hào)標(biāo)號(hào)itL( i )tL(i)= mintL(j)-t(i,j)i=min以以 為箭尾（起點(diǎn)）的

9、各箭的箭頭為箭尾（起點(diǎn)）的各箭的箭頭 - 箭長(zhǎng)箭長(zhǎng)tij（3）給始點(diǎn)）給始點(diǎn) 標(biāo)號(hào)標(biāo)號(hào)00運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃567K(6)L(3)10484=min10-6,8-3表示第表示第5個(gè)事項(xiàng)最晚第個(gè)事項(xiàng)最晚第4天開始。之所以天開始。之所以取最小，保證時(shí)間最長(zhǎng)的工序取最小，保證時(shí)間最長(zhǎng)的工序K能完工能完工。2.計(jì)算各工序計(jì)算各工序 的時(shí)差的時(shí)差ijR(i,j)= 的的 - tij- 的的ji表示這道工序的松弛時(shí)間。表示這道工序的松弛時(shí)間。如如ijA(3)2125R(i,j)=25-3-21=1表示表示A工序最晚結(jié)束時(shí)間在第工序最晚結(jié)束時(shí)間在第25天，最早天，最早開工時(shí)間在第開工時(shí)間在第21天，工時(shí)為

10、天，工時(shí)為3天，故有天，故有1天天的松弛量。的松弛量。運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃3.關(guān)鍵工序關(guān)鍵工序工序時(shí)差為工序時(shí)差為0的工序（的工序（R(i,j)=0）如：如：ijA(3)222525-3-22=0表示表示A工序的開工和結(jié)束時(shí)間不能工序的開工和結(jié)束時(shí)間不能延后，否則整個(gè)工期延后一關(guān)鍵延后，否則整個(gè)工期延后一關(guān)鍵工序。工序。4.關(guān)鍵路關(guān)鍵路由關(guān)鍵工序組成的由起點(diǎn)到終點(diǎn)的路。由關(guān)鍵工序組成的由起點(diǎn)到終點(diǎn)的路。運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃例例2 求例求例1的關(guān)鍵工序及關(guān)鍵路。的關(guān)鍵工序及關(guān)鍵路。132456A（2）B（3）E（20）D（6）F（4）G（2）C（2.5）05.5325.529.531.505.5

11、325.529.531.5RA=3.5,RB=0,RC=0,RD=16.5,RE=0,RF=0,RG=0運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃總工期總工期: T=31.5（周）周）注：注：1.關(guān)鍵工序關(guān)鍵工序 箭頭箭尾均有箭頭箭尾均有 = 反之不成立。反之不成立。2.關(guān)鍵工序時(shí)間之和關(guān)鍵工序時(shí)間之和=完工期完工期T關(guān)鍵路：關(guān)鍵路： （不一定唯一）（不一定唯一）123456 關(guān)鍵工序：關(guān)鍵工序：B-C-E-F-G運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃所有時(shí)間參數(shù) (j)最早完成時(shí)間=(i)最早開始時(shí)間-t(i,j) (i)最遲完成時(shí)間=(j)最遲開始時(shí)間-t(i,j) 工序(i,j)的總時(shí)差=(j)最遲開始時(shí)間-t(i,j) -(

12、i)最早開始時(shí)間 工序(i,j)的自由時(shí)差=(j）最早開始時(shí)間- (i）最早完成時(shí)間運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃例例3（P136）某項(xiàng)課題研究工作分解的作業(yè)表如下。根某項(xiàng)課題研究工作分解的作業(yè)表如下。根據(jù)此表繪制此項(xiàng)科研工作的網(wǎng)絡(luò)圖，計(jì)算時(shí)間參數(shù)，據(jù)此表繪制此項(xiàng)科研工作的網(wǎng)絡(luò)圖，計(jì)算時(shí)間參數(shù)，并確定關(guān)鍵路線。并確定關(guān)鍵路線。工序代號(hào)工序代號(hào)工序工序緊前工序緊前工序工序時(shí)間工序時(shí)間A系統(tǒng)提出和研究問題系統(tǒng)提出和研究問題無無4B研究選點(diǎn)問題研究選點(diǎn)問題A7C準(zhǔn)備調(diào)研方案準(zhǔn)備調(diào)研方案A10D收集資料工作安排收集資料工作安排B8E挑實(shí)地訓(xùn)練工作人員挑實(shí)地訓(xùn)練工作人員B，C12F準(zhǔn)備收集資料用表格準(zhǔn)備收集資料用

13、表格C7G實(shí)地調(diào)查實(shí)地調(diào)查D，E，F(xiàn)5H分析準(zhǔn)備調(diào)查報(bào)告分析準(zhǔn)備調(diào)查報(bào)告G4I任務(wù)結(jié)束任務(wù)結(jié)束H0運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃E(12)124536789A(4)B(7)C(10)B(0)C(0)D(8)F(7)G(5)H(4)I(0)04141411263135350414263135351414關(guān)鍵工序：A-C-C-E-G-H-I關(guān)鍵路：12456789運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃6.3 網(wǎng)絡(luò)圖的調(diào)整及優(yōu)化網(wǎng)絡(luò)圖的調(diào)整及優(yōu)化6.3.1 縮短工程工期問題縮短工程工期問題工期優(yōu)化工期優(yōu)化所謂工期優(yōu)化，就是在編制網(wǎng)絡(luò)計(jì)劃時(shí)，如何加快工所謂工期優(yōu)化，就是在編制網(wǎng)絡(luò)計(jì)劃時(shí)，如何加快工程進(jìn)度，縮短工程的工期。一般可以

14、從以下兩個(gè)方面程進(jìn)度，縮短工程的工期。一般可以從以下兩個(gè)方面進(jìn)行：進(jìn)行：（1）壓縮關(guān)鍵工序的工序時(shí)間）壓縮關(guān)鍵工序的工序時(shí)間對(duì)關(guān)鍵工序增加新設(shè)備，采用新工藝，新技術(shù)等措施；對(duì)關(guān)鍵工序增加新設(shè)備，采用新工藝，新技術(shù)等措施；或?qū)ば驎r(shí)間較長(zhǎng)的關(guān)鍵工序采用平行作業(yè)或交叉作業(yè)或?qū)ば驎r(shí)間較長(zhǎng)的關(guān)鍵工序采用平行作業(yè)或交叉作業(yè)等措施，以達(dá)到提高工效、縮短關(guān)鍵工序時(shí)間的目的。等措施，以達(dá)到提高工效、縮短關(guān)鍵工序時(shí)間的目的。（2）在非關(guān)鍵工序上盡量挖掘潛力）在非關(guān)鍵工序上盡量挖掘潛力利用非關(guān)鍵工序的時(shí)差進(jìn)行合理調(diào)度，抽調(diào)人力、物力利用非關(guān)鍵工序的時(shí)差進(jìn)行合理調(diào)度，抽調(diào)人力、物力支援關(guān)鍵工序，縮短關(guān)鍵工序時(shí)間。

15、支援關(guān)鍵工序，縮短關(guān)鍵工序時(shí)間。運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃6.3.2 工程的時(shí)間費(fèi)用分析工程的時(shí)間費(fèi)用分析工期工期-成本優(yōu)化成本優(yōu)化（費(fèi)用優(yōu)化）（費(fèi)用優(yōu)化）所謂工期成本優(yōu)化，就是在編制網(wǎng)絡(luò)計(jì)劃中所謂工期成本優(yōu)化，就是在編制網(wǎng)絡(luò)計(jì)劃中，如何使工程的完成既快又省。，如何使工程的完成既快又省。一一.費(fèi)用構(gòu)成費(fèi)用構(gòu)成1.直接費(fèi)用直接費(fèi)用工資、設(shè)備、原材料等（直接與完成工序有工資、設(shè)備、原材料等（直接與完成工序有關(guān)的費(fèi)用）關(guān)的費(fèi)用）運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃CDA(壓縮時(shí)間壓縮時(shí)間)B(正常完成時(shí)間正常完成時(shí)間)時(shí)間時(shí)間直接費(fèi)用直接費(fèi)用稱稱 為直接（趕工）費(fèi)用率為直接（趕工）費(fèi)用率ABCD（表示縮短工序一天，工期增

16、加的直接費(fèi)用）（表示縮短工序一天，工期增加的直接費(fèi)用）即直接費(fèi)用率即直接費(fèi)用率= 平均單位時(shí)間的趕工費(fèi)用平均單位時(shí)間的趕工費(fèi)用趕工時(shí)間正常時(shí)間正常費(fèi)用趕工時(shí)費(fèi)用運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃2.間接費(fèi)用間接費(fèi)用管理費(fèi)等（不直接參加生產(chǎn)的費(fèi)用）管理費(fèi)等（不直接參加生產(chǎn)的費(fèi)用）間接費(fèi)用間接費(fèi)用AB稱單位時(shí)間的間接費(fèi)用為間接費(fèi)用率。稱單位時(shí)間的間接費(fèi)用為間接費(fèi)用率?？傎M(fèi)用總費(fèi)用=直接費(fèi)用直接費(fèi)用+間接費(fèi)用間接費(fèi)用工期直接費(fèi)用直接費(fèi)用間接費(fèi)用間接費(fèi)用總費(fèi)用總費(fèi)用費(fèi)用費(fèi)用t*（最小工期時(shí)間）最小工期時(shí)間）時(shí)間時(shí)間運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃二二.求最低成本工期求最低成本工期方法：方法：1.求出正常工期和關(guān)鍵工序（用求出正

17、常工期和關(guān)鍵工序（用CPM方法）方法）2.比較關(guān)鍵工序的直接費(fèi)用率與間接費(fèi)用率比較關(guān)鍵工序的直接費(fèi)用率與間接費(fèi)用率（1）若直接費(fèi)用率）若直接費(fèi)用率 間接費(fèi)用率間接費(fèi)用率則正常工期為最低成本工期。則正常工期為最低成本工期。（2）若）若存在存在直接費(fèi)用率直接費(fèi)用率間接費(fèi)用率間接費(fèi)用率則在關(guān)鍵工序上壓縮，先壓縮直接費(fèi)用率最小則在關(guān)鍵工序上壓縮，先壓縮直接費(fèi)用率最小的方案，并確定該方案可能縮短的時(shí)間。的方案，并確定該方案可能縮短的時(shí)間。t=mint=min, , =min壓縮工序的正常時(shí)間壓縮工序的正常時(shí)間-趕工時(shí)間趕工時(shí)間=min所有非關(guān)鍵工序的時(shí)差所有非關(guān)鍵工序的時(shí)差運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃（3）按照

18、工作的新工時(shí)，重新計(jì)算網(wǎng)絡(luò)計(jì)劃的關(guān)鍵）按照工作的新工時(shí)，重新計(jì)算網(wǎng)絡(luò)計(jì)劃的關(guān)鍵 路線及關(guān)鍵工序。路線及關(guān)鍵工序。（4）再比較關(guān)鍵工序的直接費(fèi)用率與間接費(fèi)用率。）再比較關(guān)鍵工序的直接費(fèi)用率與間接費(fèi)用率。不斷重復(fù)，直到使總費(fèi)用上升為止。不斷重復(fù)，直到使總費(fèi)用上升為止。（直接費(fèi)用率（直接費(fèi)用率間接費(fèi)用率）間接費(fèi)用率）注：若壓縮引起出現(xiàn)多于一條新的關(guān)鍵路線時(shí)，需同注：若壓縮引起出現(xiàn)多于一條新的關(guān)鍵路線時(shí)，需同時(shí)壓縮各關(guān)鍵路線時(shí)壓縮各關(guān)鍵路線.（因?yàn)椴煌瑫r(shí)壓，則工期不能縮短，（因?yàn)椴煌瑫r(shí)壓，則工期不能縮短，工期工期=關(guān)鍵工序上工時(shí)之和）關(guān)鍵工序上工時(shí)之和）運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃例例4 設(shè)某工程有關(guān)資料如表

19、：設(shè)某工程有關(guān)資料如表：工序工序 緊前工序緊前工序工序時(shí)間工序時(shí)間直接費(fèi)用直接費(fèi)用率率可壓天數(shù)可壓天數(shù)A-3-BA731CA443DC562間接費(fèi)用率為間接費(fèi)用率為5求最低成本工期。求最低成本工期。運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃解解：（1）求工期及關(guān)鍵工序。）求工期及關(guān)鍵工序。1324A（3）C（4）B（7）D（5）0731212730工期：工期：T=12,關(guān)鍵工序：關(guān)鍵工序：A-C-D運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃（2）因?yàn)橹苯淤M(fèi)用率不全）因?yàn)橹苯淤M(fèi)用率不全5，故應(yīng)在關(guān)鍵工序上壓縮，故應(yīng)在關(guān)鍵工序上壓縮先壓縮先壓縮C（直接費(fèi)用率最?。┲苯淤M(fèi)用率最小）壓一天能節(jié)省費(fèi)用為壓一天能節(jié)省費(fèi)用為5-4=1=3（C的可壓天

20、數(shù)），的可壓天數(shù)），=R24=2 故故t=2t=2壓縮方案：壓縮方案：C壓縮壓縮2天，可減少費(fèi)用（天，可減少費(fèi)用（5-4）*2=2此時(shí)網(wǎng)絡(luò)圖為：此時(shí)網(wǎng)絡(luò)圖為：1324A（3）C（2）B（7）D（5）0531010530關(guān)鍵路有兩條：關(guān)鍵路有兩條： A-BA-C-D工期工期T=10RA=RB=RC=RD=0運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃若再各壓縮若再各壓縮1天天 則應(yīng)壓縮則應(yīng)壓縮B、C（同時(shí)壓）同時(shí)壓）此時(shí)的直接費(fèi)用率將是此時(shí)的直接費(fèi)用率將是3+4=75故最低成本工期為故最低成本工期為10天。天。注：注：（1）有時(shí)資料未給可壓縮時(shí)間，但給了正常工作時(shí)）有時(shí)資料未給可壓縮時(shí)間，但給了正常工作時(shí)間及最短工作時(shí)

21、間。則壓縮時(shí)間間及最短工作時(shí)間。則壓縮時(shí)間=正常工作時(shí)間正常工作時(shí)間-最短最短工作時(shí)間。工作時(shí)間。（2）當(dāng)網(wǎng)絡(luò)圖中工作很多，關(guān)鍵路線又不止一條，）當(dāng)網(wǎng)絡(luò)圖中工作很多，關(guān)鍵路線又不止一條，用觀察法來確定縮短工時(shí)所需直接費(fèi)用增加最少的用觀察法來確定縮短工時(shí)所需直接費(fèi)用增加最少的方案比較困難，這時(shí)可以使用求網(wǎng)絡(luò)最大流的標(biāo)號(hào)方案比較困難，這時(shí)可以使用求網(wǎng)絡(luò)最大流的標(biāo)號(hào)法來解決。法來解決。運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃方法：方法：將問題化為：在全部以關(guān)鍵工序組成的網(wǎng)絡(luò)上，將問題化為：在全部以關(guān)鍵工序組成的網(wǎng)絡(luò)上，每邊容量使用本工作的直接費(fèi)用率（若本工作已每邊容量使用本工作的直接費(fèi)用率（若本工作已不能縮短工時(shí)，容量

22、應(yīng)標(biāo)不能縮短工時(shí)，容量應(yīng)標(biāo) ）求網(wǎng)絡(luò)的最大流）求網(wǎng)絡(luò)的最大流，當(dāng)求出最大流時(shí)所得到的最小截，就是增加直，當(dāng)求出最大流時(shí)所得到的最小截，就是增加直接費(fèi)用最少的方案。接費(fèi)用最少的方案。1243)0 ,()0 , 3()0 ,6()0 ,4(,1v,1v, 32v運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃1243)3 ,()3 , 3()0 ,6()0 ,4(,1v,1v,42v,43v)4,6(1243)7 ,()3 , 3()4,4(,1v,1v工作組合（工作組合（2，4）（）（2，3）為費(fèi)用最低方案。）為費(fèi)用最低方案。 B C運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃三三.求規(guī)定工期的最小成本方案求規(guī)定工期的最小成本方案間接費(fèi)用是確定了

23、的，無需考慮，只需考慮直接費(fèi)用間接費(fèi)用是確定了的，無需考慮，只需考慮直接費(fèi)用盡量小。盡量小。方法：方法：1.求出正常工期和關(guān)鍵路線求出正常工期和關(guān)鍵路線2.在關(guān)鍵工序上壓，先壓縮直接費(fèi)用率最小的，壓縮在關(guān)鍵工序上壓，先壓縮直接費(fèi)用率最小的，壓縮天數(shù)也應(yīng)為天數(shù)也應(yīng)為t=min,.當(dāng)出現(xiàn)多于一條的關(guān)鍵路線當(dāng)出現(xiàn)多于一條的關(guān)鍵路線時(shí)要同時(shí)壓，直到滿足規(guī)定為止。時(shí)要同時(shí)壓，直到滿足規(guī)定為止。運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃例例5 建筑公司要裝水管線的工程，有關(guān)資料：建筑公司要裝水管線的工程，有關(guān)資料：工作工作緊前工作緊前工作正常情況正常情況應(yīng)急情況應(yīng)急情況時(shí)間（天）時(shí)間（天） 費(fèi)用（元）費(fèi)用（元） 時(shí)間（天）時(shí)間

24、（天） 費(fèi)用（元）費(fèi)用（元）a-11.7240-ba3.2752110ca25.24500157200da18.048017600ed9.05408710fb,c7.7166051800ge,f16.84000145700hg7.2160051775ie,f12.850091298運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃（1）按正常情況，畫出施工網(wǎng)絡(luò)圖，找出關(guān)鍵路，）按正常情況，畫出施工網(wǎng)絡(luò)圖，找出關(guān)鍵路，求完工期。求完工期。（2）現(xiàn)提出這項(xiàng)工程要）現(xiàn)提出這項(xiàng)工程要60天完成，求使總應(yīng)急費(fèi)用天完成，求使總應(yīng)急費(fèi)用最小的方案。最小的方案。18246735a(11.7)b(3.2)c(25.2)d(18.0)b(0)

25、f(7.7)e(9.0)g(16.8)h(7.2)i(12.8)011.729.714.936.944.661.468.668.661.444.635.636.936.911.70正常工期正常工期TE=68.6天天關(guān)鍵工序關(guān)鍵工序a-c-f-g-h解： （1）運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃（2）將每道工序的直接費(fèi)用率計(jì)算如下：）將每道工序的直接費(fèi)用率計(jì)算如下：工工作作abcdefghi可可壓壓工工期期1.210.2112.72.82.23.8直直接接費(fèi)費(fèi)用用率率29.17264.7112017044.4607.1479.55367.89運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃1）先壓f, =2.7;而Rb=22,Rd=3.

26、2,Rc=3.2,Ri=11.2,故=3.2。 因此,t=2.7011.729.714.936.941.958.765.965.958.741.932.936.936.911.70工期TE=65.9關(guān)鍵工序： a-c-f-g-h18246735a(11.7)b(3.2)c(25.2)d(18.0)b(0)f(5.0)e(9.0)g(16.8)h(7.2)i(12.8)運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃2）再壓h,=2.2;而Rb=22,Rd=3.2,Rc=3.2,Ri=11.2,故=3.2. 因此，t=2.218246735a(11.7)b(3.2)c(25.2)d(18.0)b(0)f(5.0)e(9.0

27、)g(16.8)h(5.0)i(12.8)011.729.714.936.941.958.763.763.758.741.932.936.936.911.70工期TE=63.7關(guān)鍵工序： a-c-f-g-h運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃3）再壓c,=3.7;而Rb=22,Rd=3.2,Re=3.2,Ri=9.0故=3.2. 因此，t=3.218246735a(11.7)b(3.2)c(22)d(18.0)b(0)f(5.0)e(9.0)g(16.8)h(5.0)i(12.8)011.729.714.933.738.755.560.560.555.538.729.733.733.711.70工期TE=60

28、.560關(guān)鍵工序： a-d-e-g-h a-c-f-g-h運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃4）可同時(shí)壓c,e各0.5天,=0.5;而Rb=18.8,Rc=3.0故=3.0. 因此，t=0.518246735a(11.7)b(3.2)c(21.5)d(18.0)b(0)f(5.0)e(8.5)g(16.8)h(5.0)i(12.8)011.729.714.933.238.255.0606055.038.229.733.233.211.70工期TE=60關(guān)鍵工序： 1 ）a-c-f-g-h 2 ）a-d-e-g-h運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃所以，工期60天時(shí)總應(yīng)急最小的方案為：工序abcdefghi工時(shí)11.73.

29、221.5188.55.016.85.012.8增加的最小應(yīng)急費(fèi)用壓縮天數(shù)率各壓縮工序的直接費(fèi)用312.13597.2645.01705.071.2642.355.792.24.447.2運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃6.3.3 工程的時(shí)間工程的時(shí)間資源優(yōu)化（工期資源優(yōu)化（工期資源優(yōu)化）資源優(yōu)化） 所謂工期所謂工期資源優(yōu)化，就是在有限資源的情況下資源優(yōu)化，就是在有限資源的情況下，如何合理地調(diào)配人力、材料、設(shè)備、能源等資源，如何合理地調(diào)配人力、材料、設(shè)備、能源等資源，使之既符合客觀條件限制，又盡量不誤工期（將資源使之既符合客觀條件限制，又盡量不誤工期（將資源適當(dāng)調(diào)整使資源利用得以平衡）。適當(dāng)調(diào)整使資源利用

30、得以平衡）。方法：方法：1.計(jì)算工程每單位時(shí)間內(nèi)所需資源量。計(jì)算工程每單位時(shí)間內(nèi)所需資源量。2.作出初始進(jìn)度橫道表作出初始進(jìn)度橫道表 3.進(jìn)行資源均衡調(diào)整求得新進(jìn)度。進(jìn)行資源均衡調(diào)整求得新進(jìn)度。4.評(píng)價(jià)工程進(jìn)度計(jì)劃對(duì)資源利用的均衡程度（計(jì)算單評(píng)價(jià)工程進(jìn)度計(jì)劃對(duì)資源利用的均衡程度（計(jì)算單位時(shí)間內(nèi)資源利用量的方差）。位時(shí)間內(nèi)資源利用量的方差）。運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃例例6 已知某工程有關(guān)資料如表：已知某工程有關(guān)資料如表：工序工序緊前工序緊前工序工序時(shí)間工序時(shí)間所需資源數(shù)所需資源數(shù)（人（人/天）天）A-49B-23C-26D-24EB38FC27GD，F(xiàn)32HE，G41運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃（1）繪制工

31、程網(wǎng)絡(luò)圖，求出工期與關(guān)鍵路線。）繪制工程網(wǎng)絡(luò)圖，求出工期與關(guān)鍵路線。（2）調(diào)整網(wǎng)絡(luò)，使資源盡量平衡（不能延誤工期）調(diào)整網(wǎng)絡(luò)，使資源盡量平衡（不能延誤工期）解：解： （1）162345A（4）B（2）C（2）D（2）E（3）F（2）G（3）H（4）02247111174240工期為工期為11天天關(guān)鍵工序：關(guān)鍵工序： C-F-G-H運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃（2）a）畫出橫道表畫出橫道表9 9 9 93 36 68 8 8 4 4 7 7 2 2 2 1 1 1 12411工序ABCDEFGH12345678910人數(shù)22222410221111運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃b)調(diào)整調(diào)整調(diào)整原則：調(diào)整原則：利用非

32、關(guān)鍵工序的時(shí)差利用非關(guān)鍵工序的時(shí)差Rij= 的的 -tij- 的的ji先找出那些具有最大總時(shí)差的工序在不拖延整個(gè)工先找出那些具有最大總時(shí)差的工序在不拖延整個(gè)工程完工期的情況下，盡量往后延。程完工期的情況下，盡量往后延。RA=11-4-0=7RB=4-2-0=2RE=7-3-2=3RD=4-2-0=2方案：方案：1）可將）可將A排在排在8-11周中。周中。2）將）將B，E整體后移整體后移2周：周：B排在排在3，4周周E排在排在5、6、7周周調(diào)整后結(jié)果，如下表：調(diào)整后結(jié)果，如下表：運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃9 9 9 93 36 68 8 8 4 4 7 7 2 2 2 1 1 1 12411工序ABC

33、DEFGH12345678910人數(shù)222224102211119 9 9 93 38 8 8 10 10 10 10 10 10 10 10 10 10 10運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃注：注：1.若對(duì)勞動(dòng)力有具體的要求，如每周不超過多少，還若對(duì)勞動(dòng)力有具體的要求，如每周不超過多少，還 可進(jìn)一步調(diào)?？蛇M(jìn)一步調(diào)。2.資源平衡結(jié)果不一定唯一，也不一定特別平衡。資源平衡結(jié)果不一定唯一，也不一定特別平衡。C）評(píng)價(jià)：評(píng)價(jià)：利用方差公式：利用方差公式：21)(12ETttET其中：其中：TE總工期總工期量時(shí)間單位對(duì)資源的需求第tt資源利用量的均值該進(jìn)度計(jì)劃下單位時(shí)間運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃)142372834262

34、3294(111=10初始橫道表中：)101 ()101 ()101 ()101 ()102()102()1010()1024()1024()1022()1022(111222222222222=44.727運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃修訂后進(jìn)度計(jì)算表中：修訂后進(jìn)度計(jì)算表中：02故修訂后資源就更均衡了。故修訂后資源就更均衡了。運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃6.3.4 工程完工期的概率分布工程完工期的概率分布一一.確定平均工序時(shí)間確定平均工序時(shí)間t(i,j)的三時(shí)估計(jì)法的三時(shí)估計(jì)法設(shè)工序最樂觀時(shí)間為設(shè)工序最樂觀時(shí)間為aij設(shè)工序最保守時(shí)間為設(shè)工序最保守時(shí)間為bij設(shè)工序最可能時(shí)間為設(shè)工序最可能時(shí)間為mij64),

35、(ijijijbmajit則求均值求均值226ijijijab求方差求方差說明（華羅庚）：說明（華羅庚）：由實(shí)際工作情況表明，工作進(jìn)行時(shí)出現(xiàn)最順利和最不由實(shí)際工作情況表明，工作進(jìn)行時(shí)出現(xiàn)最順利和最不順利情況都比較少，更多的是在最可能完成時(shí)間內(nèi)完順利情況都比較少，更多的是在最可能完成時(shí)間內(nèi)完成。成。運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃設(shè)工時(shí)出現(xiàn)設(shè)工時(shí)出現(xiàn)m的可能性兩倍于出現(xiàn)的可能性兩倍于出現(xiàn)a或或b的可能性的可能性應(yīng)用加權(quán)平均法應(yīng)用加權(quán)平均法32),(mama間出現(xiàn)的平均值為工時(shí)在21P32),(bmbm間出現(xiàn)的平均值為工時(shí)在21P則平均期望工時(shí)：則平均期望工時(shí)：),(jit323221bmma64bma運(yùn)籌學(xué)

36、第六章網(wǎng)絡(luò)計(jì)劃工時(shí)的方差：工時(shí)的方差：2ij226432643221bmabmbmama26ab二二. 期望工期期望工期TE =關(guān)鍵路上工序平均時(shí)間之和關(guān)鍵路上工序平均時(shí)間之和工期的方差工期的方差2=關(guān)鍵路上工序方差之和關(guān)鍵路上工序方差之和運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃三.求工程在某天內(nèi)完工的概率),(2ETNT（因?yàn)橥旯て跒殛P(guān)鍵路線上各工序時(shí)間之和，由中心極限定理易知）)(KTTPEKTT例7 某工程網(wǎng)絡(luò)圖如下：1234567A10-13-15B5-8-10C7-8-10D7-9-15E2-4-6F8-10-14G10-12-15H9-11-13估計(jì)工程在40天內(nèi)完成的概率。運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃解：

37、（1）計(jì)算每一工序平均期望工時(shí)）計(jì)算每一工序平均期望工時(shí)t(i,j)并確定關(guān)鍵工序。并確定關(guān)鍵工序。工序工序ABCDEFGHt(i,j)12.837.838.179.67410.33 12(12.83)B(7.83)C(8.17)D(9.67)E(4)F(10.33)G(12.17)H(11)012.8320.662130.3331.3342.542.530.3331.521.1720.6612.830關(guān)鍵工序：A-B-D-G運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃（2）計(jì)算關(guān)鍵工序的方差。）計(jì)算關(guān)鍵工序的方差。工序工序ABDGt(i,j)12.837.839.6712.17ij20.6

38、90.691.770.69 TE = 12.83+7.83+9.67+12.17=1.9669.077.169.069.0)40(TPET4096.15 .42402755.128.11=1-0.8997 =0.1003=42.5運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃四四.求完工可能性達(dá)到求完工可能性達(dá)到95%的工期的工期)(KTTP96.15 .42KT%95645.196.15 .42KT7242.45KT（天）46運(yùn)籌學(xué)第六章網(wǎng)絡(luò)計(jì)劃u天津大學(xué)天津大學(xué)1999年博士生入學(xué)試題年博士生入學(xué)試題（15%）某工程可分為）某工程可分為14道工序，有關(guān)資料如下表：道工序，有關(guān)資料如下表：（1）請(qǐng)畫出該工程的網(wǎng)絡(luò)圖，按正常時(shí)間求出完工期）請(qǐng)畫出該工程的網(wǎng)絡(luò)圖，按正常時(shí)間求出完工期和關(guān)鍵路。和關(guān)鍵路。（2）如果要求工程在）如果要求工程在46周完成，求總趕工費(fèi)用最小的周完成，求總趕工費(fèi)用最小的趕工方案。趕工方案。（3）（）（2）中的問題能否采用）中的問題能否采用LP的方法解決？若能，的方法解決？若能，請(qǐng)建立此問題的請(qǐng)建立此問題的LP模型（不解）。模型（不