《管理運(yùn)籌學(xué)》07-網(wǎng)絡(luò)規(guī)劃

第七章網(wǎng)絡(luò)規(guī)劃,第七章網(wǎng)絡(luò)規(guī)劃,第一節(jié)：現(xiàn)實(shí)中的網(wǎng)絡(luò)規(guī)劃問題第二節(jié)：圖的基本概念第三節(jié)：樹第四節(jié)：最大流問題第五節(jié)：最短路徑問題第六節(jié)：最小費(fèi)用最大流問題第七節(jié)：網(wǎng)絡(luò)計劃技術(shù)第八節(jié)：網(wǎng)絡(luò)規(guī)劃的應(yīng)用,7.7網(wǎng)絡(luò)計劃技術(shù),當(dāng)系統(tǒng)決策之后，面臨的問題就是制定計劃和組織實(shí)施。網(wǎng)絡(luò)計劃技術(shù)就是在制定計劃和組織實(shí)施過程中采用的一種科學(xué)方法。本節(jié)主要對目前管理中常用的網(wǎng)絡(luò)計劃方法做一系統(tǒng)的介紹。網(wǎng)絡(luò)計劃技術(shù)利用網(wǎng)絡(luò)圖對計劃任務(wù)的進(jìn)度、費(fèi)用及其組成部分之間的相互關(guān)系進(jìn)行計劃、檢查和控制，以使系統(tǒng)協(xié)調(diào)運(yùn)轉(zhuǎn)的科學(xué)方法。由于這種方法的主要特點(diǎn)是統(tǒng)籌安排，為了突出這一特點(diǎn)，我國把各種不同的網(wǎng)絡(luò)計劃方法統(tǒng)稱為統(tǒng)籌法。,一、系統(tǒng)管理的網(wǎng)絡(luò)計劃技術(shù),（一）甘特圖法該方法是科學(xué)管理的奠基人泰勒的學(xué)生、美國福蘭克兵工廠顧問甘特于20世紀(jì)40年代開發(fā)的一種計劃與管理技術(shù)。它以時間為橫坐標(biāo)，以工序?yàn)榭v坐標(biāo)，以線條的長短表示一項(xiàng)工作或作業(yè)的開始和完成時刻以及工作的進(jìn)展情況。由于它以條形圖進(jìn)行系統(tǒng)計劃與管理，故又稱橫道圖、條形圖等，圖7-28即是一份簡化的現(xiàn)場準(zhǔn)備作業(yè)的條形圖。,甘特圖,平整場地建休息室建材料庫設(shè)備安裝材料進(jìn)場施工,一、系統(tǒng)管理的網(wǎng)絡(luò)計劃技術(shù),（二）關(guān)鍵線路法關(guān)鍵線路法（CriticalPathMethod，CPM）是美國杜邦公司為建造新工廠從事計劃與管理的研究而提出的，并在1958年的建廠工作中發(fā)揮了很大作用，使工程工期提前兩個月，初步顯示出其優(yōu)越性。而后，杜邦公司不僅把CPM法應(yīng)用于大型工程，而且也應(yīng)用于小型工程和維修工程，都同樣收到了良好的效果。美國加泰迪克公司在47項(xiàng)工程中使用CPM法，平均節(jié)約時間22%，節(jié)約資金15%，其效果是顯著的。,一、系統(tǒng)管理的網(wǎng)絡(luò)計劃技術(shù),（三）計劃評審技術(shù)計劃評審技術(shù)（ProgramEvaluationandReviewTeacnique，PERT，也稱計劃協(xié)調(diào)技術(shù)）是由美國海軍特種計劃局和洛克希德公司、漢米爾頓公司于1958年1月聯(lián)合開發(fā)的一種新的計劃管理方法。它的首次應(yīng)用使美國“北極星”導(dǎo)彈潛艇工程的工期由原計劃的十年縮短為八年。由于它的成功，自1962年起美國政府規(guī)定一切新開發(fā)的工程項(xiàng)目必須采用這種方法。我國的很多大型開發(fā)性工程也都應(yīng)用了這種方法，收到了良好的效果。,一、系統(tǒng)管理的網(wǎng)絡(luò)計劃技術(shù),（四）決策關(guān)鍵線路法任何一項(xiàng)工作都可用多種方案進(jìn)行計劃和管理，因此需要在多種方案的比較中進(jìn)行決策。然而CPM和PERT二種方法雖然先進(jìn)，但卻只能考慮完成任務(wù)的一種方案，對不同方案必須畫出不同的網(wǎng)絡(luò)圖，不僅增大繪制網(wǎng)絡(luò)圖的工作量，而且，在比較和分析時也不能一目了然。為了克服這種局限性，又開發(fā)了決策關(guān)鍵線路法（DecisionCriticalPathMethod，DCPM）。,一、系統(tǒng)管理的網(wǎng)絡(luò)計劃技術(shù),（五）圖解評審技術(shù)上述各種方法中各工序均屬確定型工序，但實(shí)踐中存在隨機(jī)工序，如檢驗(yàn)工序后的返修工序，這類工序應(yīng)用上述各種方法很難解決，圖解評審技術(shù)（GraphicalevaluationandReviewTechnique，GERT）是一種廣義網(wǎng)絡(luò)計劃法，是解決這類問題的一種方法。,二、網(wǎng)絡(luò)計劃技術(shù)應(yīng)用的程序,（一）、網(wǎng)絡(luò)計劃技術(shù)應(yīng)用的一般程序,二、網(wǎng)絡(luò)計劃技術(shù)應(yīng)用的程序,（一）、網(wǎng)絡(luò)計劃技術(shù)應(yīng)用的一般程序,（二）、網(wǎng)絡(luò)圖的繪制,1、網(wǎng)絡(luò)圖的組成,任務(wù),工作,線路,起點(diǎn)開始沿箭線方向連續(xù)通過一系列箭線和節(jié)點(diǎn)最后到達(dá)終點(diǎn)所經(jīng)過的路線,指一項(xiàng)有目的、有開始和結(jié)束標(biāo)志的許多相互關(guān)聯(lián)且有不同指標(biāo)要求的工作所組成,為完成某項(xiàng)任務(wù)在工藝和組織管理上相互獨(dú)立的活動（子任務(wù)）,緊前工作,緊后工作,（二）、網(wǎng)絡(luò)圖的繪制,2、網(wǎng)絡(luò)圖的繪制,（1）任務(wù)的分解和分析,（二）、網(wǎng)絡(luò)圖的繪制,2、網(wǎng)絡(luò)圖的繪制,（2）畫網(wǎng)絡(luò)圖,單代號網(wǎng)絡(luò)圖,（二）、網(wǎng)絡(luò)圖的繪制,2、網(wǎng)絡(luò)圖的繪制,（2）畫網(wǎng)絡(luò)圖,雙代號網(wǎng)絡(luò)圖,雙代號（AOA）網(wǎng)絡(luò)圖（activityonarrownetwork）是用有向箭線及其兩端的兩個節(jié)點(diǎn)編號表示工作的網(wǎng)絡(luò)圖。在雙代號網(wǎng)絡(luò)圖中，每一項(xiàng)工作都用一根有向箭線和箭線兩端的兩個節(jié)點(diǎn)來表示，每個節(jié)點(diǎn)都編以號碼，箭線兩端的兩個節(jié)點(diǎn)的號碼即代表該箭線所表示的工作,三、雙代號網(wǎng)絡(luò)圖的繪制,1.雙代號網(wǎng)絡(luò)圖的組成,由工作、節(jié)點(diǎn)（事件）和線路三部分組成。,節(jié)點(diǎn),線路,3,5,2,3,6,4,虛工作,關(guān)鍵線路,2.雙代號網(wǎng)絡(luò)圖的繪制,（1）雙代號網(wǎng)絡(luò)圖各種邏輯關(guān)系的正確表示方法,該工作必須在哪些工作之前進(jìn)行？該工作必須在哪些工作之后進(jìn)行？該工作可以與哪些工作平行進(jìn)行？,虛工作一般起聯(lián)系、區(qū)分和斷開三個作用,詳見P231的表7-8,2.雙代號網(wǎng)絡(luò)圖的繪制,（2）雙代號網(wǎng)絡(luò)圖的繪制規(guī)則,必須正確表達(dá)已定的工作間的邏輯關(guān)系。,網(wǎng)絡(luò)圖中，嚴(yán)禁出現(xiàn)循環(huán)回路。,嚴(yán)禁出現(xiàn)雙向箭頭箭線和無箭頭連線。,嚴(yán)禁出現(xiàn)沒有箭頭節(jié)點(diǎn)的箭線或沒有箭尾節(jié)點(diǎn)的箭線,當(dāng)某節(jié)點(diǎn)有多條外向箭線或有多條內(nèi)向箭線時，可采用母線法繪圖，允許多條箭線經(jīng)一條共用母線引出或引入節(jié)點(diǎn),應(yīng)盡量避免箭線交叉，當(dāng)箭線交叉不可避免時，可采用過橋法或指向法。,只能有一個起點(diǎn)節(jié)點(diǎn)；在不分期完成任務(wù)的網(wǎng)絡(luò)圖中，應(yīng)只有和一個終點(diǎn)節(jié)點(diǎn)；其他所有節(jié)點(diǎn)均為中間節(jié)點(diǎn)。,任意兩個節(jié)點(diǎn)之間只能有一條唯一的箭線，不得有兩個或兩個以上的箭線從同一節(jié)點(diǎn)出發(fā)且同時指向同一節(jié)點(diǎn)。,詳見P234、5的圖,2.雙代號網(wǎng)絡(luò)圖的繪制,（3）雙代號網(wǎng)絡(luò)圖的節(jié)點(diǎn)編號,箭尾節(jié)點(diǎn)的號編碼應(yīng)小于箭頭節(jié)點(diǎn)的號碼。,在一個網(wǎng)絡(luò)圖中，所有的節(jié)點(diǎn)不能出現(xiàn)重復(fù)的編號。,（4）雙代號網(wǎng)絡(luò)圖的繪制步驟,分解任務(wù)，劃分施工工作，制定完成任務(wù)的全部工作結(jié)構(gòu)分解表。,確定全部工作的邏輯關(guān)系，繪制工作邏輯關(guān)系表（矩陣表）,確定每一工作的持續(xù)時間，制定最終的工程分析表,根據(jù)工程分析表繪制并修改網(wǎng)絡(luò)圖。,2.雙代號網(wǎng)絡(luò)圖的繪制,（5）雙代號網(wǎng)絡(luò)圖的繪制方法,繪制沒有緊前工作的工作箭線，使他們具有相同的開始節(jié)點(diǎn)，以保證網(wǎng)絡(luò)圖只有一個起點(diǎn)節(jié)點(diǎn)。依次繪制其他工作箭線。當(dāng)各項(xiàng)工作箭線都繪制出來以后，應(yīng)合并那些沒有緊后工作的工作箭線的箭頭節(jié)點(diǎn)，以保證網(wǎng)絡(luò)圖只有一個終點(diǎn)節(jié)點(diǎn)。,無緊前工作的工作（即雙代號網(wǎng)絡(luò)圖開始的第一項(xiàng)工作），其開始節(jié)點(diǎn)位置號為零；有緊前工作的工作，其開始節(jié)點(diǎn)位置號等于其緊前工作的開始節(jié)點(diǎn)位置號的最大值加1；有緊后工作的工作，其結(jié)束節(jié)點(diǎn)位置號等于其緊后工作的開始節(jié)點(diǎn)位置號的最小值；無緊后工作的工作（即雙代號網(wǎng)絡(luò)圖開始的最后一項(xiàng)工作），其結(jié)束節(jié)點(diǎn)位置號等于網(wǎng)絡(luò)圖中各工作的結(jié)束節(jié)點(diǎn)位置號的最大值加1。,節(jié)點(diǎn)編號：,第7章網(wǎng)絡(luò)規(guī)劃,21,例7-9已知某任務(wù)的工作構(gòu)成及其邏輯關(guān)系如表7-6所示，試?yán)L制雙代號網(wǎng)絡(luò)圖。,解：用矩陣表確定緊后（前）工作,確定各工作的開始節(jié)點(diǎn)位置號和結(jié)束節(jié)點(diǎn)位置號,第7章網(wǎng)絡(luò)規(guī)劃,22,第7章網(wǎng)絡(luò)規(guī)劃,23,例7-10已知某項(xiàng)目的工作構(gòu)成及其邏輯關(guān)系如表7-9所示，試?yán)L制雙代號網(wǎng)絡(luò)圖。,根據(jù)工序之間的關(guān)系初步繪制如圖7-47。,簡化為圖7-48。,四、雙代號網(wǎng)絡(luò)圖的時間參數(shù)計算,（一）、時間參數(shù)的概念,1、工作持續(xù)時間,（1）定額計算法（確定型）：,Dij工作ij的持續(xù)時間Qij工作ij的工程量S產(chǎn)量定額（m3/工日、m2/工日、T/工日、m3/臺班）R工人數(shù)（機(jī)械臺班數(shù)）H時間定額(H1S),四、雙代號網(wǎng)絡(luò)圖的時間參數(shù)計算,（一）、時間參數(shù)的概念,1、工作持續(xù)時間,（2）三時估算法：,Dij工作ij的持續(xù)時間a工作ij的樂觀持續(xù)時間估計值(Optimistictime)b工作ij的悲觀持續(xù)時間估計值(Pessimistictime)；m工作ij的最可能持續(xù)時間估計值(MostLikelytime)。,四、雙代號網(wǎng)絡(luò)圖的時間參數(shù)計算,（一）、時間參數(shù)的概念,2、工期,（1）計算工期：根據(jù)網(wǎng)絡(luò)計劃的時間參數(shù)計算出來的工期，用Tc表示。（2）要求工期：任務(wù)委托人提出的所要求的工期，用Tr表示。（3）計劃工期：在要求工期和計算工期的基礎(chǔ)上綜合考慮需要和可能而確定的工期，用Tp表示。,3、工作最早時間,最早開始時間：是指在緊前工作的約束條件下，本工作可能開始的最早時刻，用ESi-j表示。最早完成時間：是指在緊前工作的約束條件下，本工作可能完成的最早時刻，用EFi-j表示。,四、雙代號網(wǎng)絡(luò)圖的時間參數(shù)計算,（一）、時間參數(shù)的概念,4、工作最遲時間,最遲開始時間：是指在不影響整個任務(wù)按期完成的前提下，本工作最遲必須開始的時刻，用LSi-j表示。最遲完成時間：是指在不影響整個任務(wù)按期完成的前提下，本工作最遲必須完成的時刻，用LFi-j表示。,5、工作的時差,總時差(TotalFloatTime)：在不影響總工期的前提下，本工作可以利用的機(jī)動時間，用TFi-j表示。自由時差(FreeFloatTime)：在不影響緊后工作最早開始時間的前提下，本工作可以利用的機(jī)動時間，用FFi-j表示。,四、雙代號網(wǎng)絡(luò)圖的時間參數(shù)計算,（三）、時間參數(shù)的計算（圖上計算法）,1、按工作計算法計算時間參數(shù),（1）工作的最早開始時間和最早完成時間,沒有緊前工作的工作ij（以起點(diǎn)節(jié)點(diǎn)為箭尾節(jié)點(diǎn)的工作)ESij=0,有緊前工作的工作ij，當(dāng)工作ij只有一項(xiàng)緊前工作hi時ESijEShiDhi,當(dāng)工作ij有多項(xiàng)緊前工作時ESijMaxEShiDhi,工作ij的最早完成時間應(yīng)按下式計算：EFijESijDij,四、雙代號網(wǎng)絡(luò)圖的時間參數(shù)計算,（三）、時間參數(shù)的計算（圖上計算法）,1、按工作計算法計算時間參數(shù),（2）網(wǎng)絡(luò)計劃工期的計算,網(wǎng)絡(luò)計劃的計算工期當(dāng)終點(diǎn)節(jié)點(diǎn)為n時，箭頭指向終點(diǎn)節(jié)點(diǎn)的所有工作的最早完成時間的最大值即為網(wǎng)絡(luò)計劃的計算工期Tc，其計算公式為：Tc=MaxEFmn,網(wǎng)絡(luò)計劃的計劃工期網(wǎng)絡(luò)計劃的計劃工期Tp的確定應(yīng)按下述規(guī)定：當(dāng)已規(guī)定了要求工期Tr時：TpTr當(dāng)未規(guī)定要求工期時，可令計劃工期等于計算工期：TpTc,四、雙代號網(wǎng)絡(luò)圖的時間參數(shù)計算,（三）、時間參數(shù)的計算（圖上計算法）,1、按工作計算法計算時間參數(shù),（3）工作的最遲完成時間和最遲開始時間,工作ij的最遲完成時間LFij應(yīng)從網(wǎng)絡(luò)計劃的終點(diǎn)節(jié)點(diǎn)開始，逆著箭線方向逐項(xiàng)計算，并符合下列規(guī)定：,沒有緊后工作的工作mn（以終點(diǎn)節(jié)點(diǎn)為箭頭節(jié)點(diǎn)的工作），其最遲必須完成時間LFmn應(yīng)按網(wǎng)絡(luò)計劃的計劃工期Tp確定，即：LFmn=Tp,有緊后工作的工作，當(dāng)工作ij只有一項(xiàng)緊后工作jk時，其最遲必須完成時間LFij為：LFijLFjkDjk,當(dāng)工作ij有多項(xiàng)緊后工作jk時，其最遲必須完成時間LFij應(yīng)為：LFij=MinLFjkDjk,工作ij的最遲必須開始時間LSij應(yīng)按下式計算：LSijLFijDij,四、雙代號網(wǎng)絡(luò)圖的時間參數(shù)計算,（三）、時間參數(shù)的計算（圖上計算法）,1、按工作計算法計算時間參數(shù),（4）工作的總時差,根據(jù)總時差TFij的定義TFijLSijESijTFijLFijEFij,（5）工作的自由時差,FFijESjkEFij,FFmnTpEFmn,（6）按工作計算法計算時間參數(shù)示例,例7-11已知某項(xiàng)目的有關(guān)資料如下表所示:,0,11,1,1,1,2,3,4,5,6,A,B,C,D,E,F,H,I,5,3,6,2,5,5,3,1,0,2,1,0,0,16,11,16,11,0,0,5,11,5,0,0,5,0,5,0,8,3,1,11,9,8,3,10,5,13,8,1,2,14,11,16,13,2,2,11,11,13,13,0,1,4,1,5,2,1,TP=16,關(guān)鍵路線,四、雙代號網(wǎng)絡(luò)圖的時間參數(shù)計算,（三）、時間參數(shù)的計算（圖上計算法）,2、按節(jié)點(diǎn)計算法計算時間參數(shù),節(jié)點(diǎn)最早時間：是指雙代號網(wǎng)絡(luò)計劃中，以該節(jié)點(diǎn)為開始節(jié)點(diǎn)的各項(xiàng)工作的最早能夠開始的時間，用ETi表示。,節(jié)點(diǎn)最遲時間：是指雙代號網(wǎng)絡(luò)計劃中，以該節(jié)點(diǎn)為完成節(jié)點(diǎn)的各項(xiàng)工作的最遲必須完成的時間，用LTi表示。,2、按節(jié)點(diǎn)計算法計算時間參數(shù),（1）節(jié)點(diǎn)最早時間的計算,當(dāng)起點(diǎn)節(jié)點(diǎn)i未規(guī)定其最早開始時間時，ETi其值應(yīng)等于0，即：ETi0,當(dāng)節(jié)點(diǎn)j只有一條內(nèi)向箭線時，其最早時間ETj為：ETjETiDij,當(dāng)節(jié)點(diǎn)j有多條內(nèi)向箭線時，其最早時間ETj為：ETjMaxETiDij,（2）網(wǎng)絡(luò)計劃工期的計算,TcETn,（3）節(jié)點(diǎn)最遲時間的計算,終點(diǎn)節(jié)點(diǎn)n的最遲時間LTn應(yīng)按網(wǎng)絡(luò)計劃的計劃工期Tp確定：LTn=Tp,當(dāng)節(jié)點(diǎn)i只有一條外向箭線時，其最遲時間LTi為：LTiLTjDij,當(dāng)節(jié)點(diǎn)i有多條外向箭線時，其最遲時間LTi為：LTiMinLTjDij,2、按節(jié)點(diǎn)計算法計算時間參數(shù),（4）工作時間參數(shù)的計算,ESijETi,EFijETiDij,LFijLTj,LSijLTjDij,TFijLTjETiDij,FFijETjETiDij,例7-13按工作計算法計算時間參數(shù)示例,1,2,3,4,5,6,A,B,C,D,E,F,H,I,30,50,20,30,10,8,9,G,10,10,10,20,20,30,J,10,0,20,30,40,50,50,70,120,130,130,120,70,90,70,40,50,70,10,0,7,例7-13按工作計算法計算時間參數(shù)示例,0,0,10,10,20,70,30,50,40,40,50,70,50,90,70,70,120,120,130,130,（四）、表上計算法,五、網(wǎng)絡(luò)圖的優(yōu)化,（一）、工期優(yōu)化,工期優(yōu)化也稱時間優(yōu)化，就是當(dāng)初始網(wǎng)絡(luò)計劃的計算工期大于要求工期時，通過壓縮關(guān)鍵線路上工作的持續(xù)時間或調(diào)整工作關(guān)系，以滿足工期要求的過程。,壓縮關(guān)鍵線路方法,調(diào)整工作關(guān)系的方法,（二）、資源優(yōu)化,資源(人力、材料、機(jī)具設(shè)備、資金等)的優(yōu)化，就是要解決網(wǎng)絡(luò)計劃實(shí)施中的資源供求矛盾或?qū)崿F(xiàn)資源的均衡利用，以保證工程的順利完成，并取得良好的技術(shù)經(jīng)濟(jì)效果。通常，資源優(yōu)化有兩種不同的目標(biāo)：資源有限，工期最短；工期一定，實(shí)現(xiàn)資源的需求均衡。資源有限使工期最短的優(yōu)化是指在資源供應(yīng)有限的前提下，保持各個工作的每日資源需求量(強(qiáng)度)是常數(shù)，合理地安排資源分配，尋找最短計劃工期的過程。,（三）、最優(yōu)工期,工期-成本優(yōu)化的目的在于：(1)尋求直接費(fèi)與間接費(fèi)總和即成本最低的最優(yōu)工期TS，以及與此相對應(yīng)的網(wǎng)絡(luò)計劃中各工作的進(jìn)度安排。(2)在工期規(guī)定(Ti)的條件下，尋求與此相對應(yīng)的最低成本，以及網(wǎng)絡(luò)中各工作的進(jìn)度安排。,優(yōu)化的思路,縮短工期,縮短關(guān)鍵工作的時間,縮短費(fèi)用率最小的關(guān)鍵工作的時間,(1)當(dāng)關(guān)鍵線路只有一條時，首先將這條線。路上費(fèi)用率ei-j最小的工作的持續(xù)時間縮短t。此時，應(yīng)滿足,(3)步驟(1)或步驟(2)的工作應(yīng)進(jìn)行多次，以逐步縮短工期，使計劃工期滿足規(guī)定的要求，并計算出相應(yīng)的直接費(fèi)總和及各工作的時間參數(shù)。,且保持被縮短持續(xù)時間的工作i-j仍為關(guān)鍵工作（即其壓縮幅度小于或等于工作的總時差）。,(2)如果關(guān)鍵線路有兩條以上時，那么每條線路都需要縮短持續(xù)時間t，才能使計劃工期也相應(yīng)縮短t。為此，必須找出費(fèi)用率總和ei-j為最小的工作組合，我們把這種工作組合稱為“最小切割”。,優(yōu)化示例,例7-15某網(wǎng)絡(luò)計劃中各工作的工期成本數(shù)據(jù)列于表，給出了各工作的正常持續(xù)時間D，加快的持續(xù)時間d，及與其相應(yīng)的直接費(fèi)用M和，計算后所得的費(fèi)用率e也列在表中。假定每周的間接費(fèi)用為1.5萬元。試進(jìn)行工期-成本優(yōu)化,1,3,2,5,4,6,6，6,30，0,24，12,18，6,30，12,36，0,30，0,12，48,96,0.57,1,3,2,5,4,6,6，6,30，0,24，0,18，6,30，0,36，0,18，0,12，48,84,4-6縮短12天,總費(fèi)用減少：-1.5X12+0.57X12=-11.16,1-3縮短6天,1,3,2,5,4,6,6，0,24，0,24，0,18，0,30，0,36，0,18，0,12，42,78,4-6與3-5同時縮短2天,總費(fèi)用減少：-1.5X6+1X6=-3,1,3,2,5,4,