運籌學-網(wǎng)絡計劃課件

1、OPERATIONS RESE運 籌 學提醒：五月27、28日（即下周二、周三）的下午2：30到系機房上實驗課，不得缺席。OR3 1OPERATIONS RESE運 籌 學提醒：五 第五節(jié) 網(wǎng)絡計劃引言： 國外實踐證明：應用網(wǎng)絡計劃技術(shù)組織與管理生產(chǎn)和項目，一般能縮短工期20左右，降低成本10左右。 上海寶鋼煉鐵廠1號高爐土建工程施工中，應用網(wǎng)絡法，縮短工期21，降低成本9.8。OR3 2 第五節(jié) 網(wǎng)絡計劃引言：OR3 1、基本概念網(wǎng)絡圖（有向賦權(quán)圖）的構(gòu)成：節(jié)點和箭線節(jié)點：每個節(jié)點稱為事件，是箭線兩端的連接點。表示工序的開始或結(jié)束。剪線：代表工序。剪尾表示該工序的開始，箭頭表示該工序的結(jié)束。

2、工序：是組成整個任務的局部任務，需要消耗一定資源或占用一定時間。注意：與工序相比，節(jié)點不需要時間或所需要時間少到可以忽略不計。OR3 31、基本概念網(wǎng)絡圖（有向賦權(quán)圖）的構(gòu)成：節(jié)點和箭線OR3 例: 景泰藍的制作工序：制胎、掐絲、點藍、燒藍、打磨、鍍金。ij工作名稱或代號持續(xù)時間注意： 網(wǎng)絡計劃圖是有向、有序的賦權(quán)圖，應按項目的工作流程從左向右編制。在時序上反應各項工作的先后順序。節(jié)點編號必須是箭尾編號小于箭頭編號。1234567制胎掐絲點藍燒藍打磨鍍金0.511222OR3 4例: 景泰藍的制作工序：制胎、掐絲、點藍、燒藍、打磨2、畫網(wǎng)絡圖的基本規(guī)則1）網(wǎng)絡圖中只能有一個總起點節(jié)點和一個總終

3、點節(jié)點。總起點節(jié)點和總終點節(jié)點分別表示計劃的開始和結(jié)束。緊前工序：緊排在本工作之前的工作。緊后工序：指緊排在本工作之后的工序。1342567ABCDEFOR3 52、畫網(wǎng)絡圖的基本規(guī)則1）網(wǎng)絡圖中只能有一個總起點節(jié)點和一個2）網(wǎng)絡圖不允許出現(xiàn)循環(huán)回路。3)節(jié)點i,j之間不允許有兩道或兩道以上的工序。21312ABOR3 62）網(wǎng)絡圖不允許出現(xiàn)循環(huán)回路。21312ABOR3 4)需正確表示工序之間的前行后繼關(guān)系，工序之間的邏輯關(guān)系的分解圖歸納如下：（1）A完成后進行B和C。ABCOR3 74)需正確表示工序之間的前行后繼關(guān)系，工序之間的邏輯關(guān)系的分(2)A,B均完成后進行C。ABCOR3 8(2

4、)A,B均完成后進行C。ABCOR3 （3）A，B均完成后進行C和D。 ABCDOR3 9（3）A，B均完成后進行C和D。ABCDOR3 (4)A完成后進行C，A,B完成后進行D。虛工序：只表示相鄰工作之間的邏輯關(guān)系，不占用資源的虛設(shè)工序。ACBDOR3 10(4)A完成后進行C，A,B完成后進行D。ACBDOR3 （5）A，B均完成后進行C；B,D均完成后進行E。ACBDEOR3 11（5）A，B均完成后進行C；B,D均完成后進行E。ACBDE5)虛工序的運用：可以用于正確表示平行工序與交叉工序。平行工序：一道工序分為幾道工作同時進行，稱為平行工序。交叉工序：兩件或兩件以上的工序交叉進行，稱

5、為交叉工序。OR3 125)虛工序的運用：可以用于正確表示平行工序與交叉工序。OR3舉例挖溝：挖溝，埋鋼管。挖一段埋一段。24挖溝挖溝8挖溝8挖溝8a1a2a3b1b2b3十八崗拖拉機廠十五里河姚公廟OR3 13舉例挖溝：24挖溝挖溝8挖溝8挖溝8a1a2a3b1b2b3工 序ABCDEFGHI緊前工序-ABBC、DC、DE、FG工序時間466759748例題1：請按照下表編制該項目的網(wǎng)絡計劃圖A BCDEGH467675F94I8OR3 14工 序ABCDEFGHI緊前工序-ABB課堂練習：請編制下表的網(wǎng)絡計劃圖P287工序緊后工序工序時間AB,C,D,E60BL45CF10DG,H20EH

6、40FL18GK30HL15KL25L/35OR3 15課堂練習：請編制下表的網(wǎng)絡計劃圖P287工序緊后工序工序時間線路：網(wǎng)絡圖中，從起點節(jié)點沿箭線方向順序通過一系列箭線與節(jié)點，最后到達終點節(jié)點的通路。關(guān)鍵路線：即持續(xù)時間最長的路線。關(guān)鍵路線上的各工作叫做關(guān)鍵工作。A BCDEGH467675F94I8OR3 16線路：網(wǎng)絡圖中，從起點節(jié)點沿箭線方向順序通過一系列箭線與節(jié)點A BCDEGH467675F94I8網(wǎng)絡計劃圖的布局要求：盡可能將關(guān)鍵路線布置在網(wǎng)絡圖的中心位置，按工作的先后順序?qū)⒙?lián)系緊密的工作布置在臨近的位置；箭線應是水平或具有水平線的折線。A4C6B6D7G7I8F9E5H4OR3

7、 17A BCDEGH467675F94I8網(wǎng)絡計3、網(wǎng)絡計劃圖的時間參數(shù)計算1）工作持續(xù)時間的計算方法：（1）單時估計法。D工作的持續(xù)時間Q工作的工作量。R可投入人力和設(shè)備的數(shù)量S每人或每臺設(shè)備每工作班能完成的工作量。n-每天正常工作班次。OR3 183、網(wǎng)絡計劃圖的時間參數(shù)計算1）工作持續(xù)時間的計算方法：OR（2）三時估計法。先估計三種時間值，然后求其平均數(shù)。樂觀時間，記為a最可能時間，記為m悲觀時間，記為b工作持續(xù)時間：OR3 19（2）三時估計法。先估計三種時間值，然后求其平均數(shù)。OR3 2）其它時間的計算公式（1）工作最早開始時間（ES)；工作最早完成時間（EF） 從網(wǎng)絡圖的起點開始

8、進行計算。 第一項工作的最早開始時間為0，記為： ES1j0； 最早完成時間為：EF1j= ES1j+D 1j注意：前一項工序完成以后，其緊后的工序才能開始。前一項工作的最早完成時間是其緊后工序的最早開始時間。所以有：EFij= ESij+D ijOR3 202）其它時間的計算公式EFij= ESij+D ijO(2)工作最遲開始時間（LS）；工作最遲完成時間（LF）從網(wǎng)絡圖的終點開始采用逆序法進行計算。網(wǎng)絡圖中最后一項工序的最遲完成時間應為工程的計劃工期。若未給定計劃工期，則取其為最早完成時間。即LFi-n=EFi-n.，LSi-n= LFi-n- Di-n其它工序： LSi-j= LFi-

9、j- Di-j即LF=min(緊后工作的LS).OR3 21(2)工作最遲開始時間（LS）；工作最遲完成時間（LF）OR（3）工作時差 時差又叫機動時間或富余時間。常用的時差有兩種：a)工作總時差TFi-j。指在不影響工期的前提下，工作所具有的機動時間。計算公式：TFi-j=EFi-j-ESi-j-Di-j=LSi-j-ESi-j或者為： TFi-j=LFi-j-EFi-jb)工作自由時差FF。在不影響其緊后工作最早開始的前提下，工作所具有的機動時間。計算公式：FFi-j=ESj-k-ESi-j-Di-j 或： FFi-j= ESj-k- EFi-j 注意：關(guān)鍵路線上無機動時間，工作總時差為零

10、。最后一道工序的FF為總工期將該工序的最早結(jié)束時間。.OR3 22（3）工作時差OR3 . 例 計算上例工序時間參數(shù) 工序ijD(i,j)ESEFLSLFTFFFA4043730B6060600C641071333D761361300E561119241311F91322152420G71320132000H42226242822I82028202800OR3 23. 例 計算上例工序時間參數(shù) 工序ijD(i,j)ESEFL4 網(wǎng)絡優(yōu)化(1)工期優(yōu)化： 使用技術(shù)措施，縮短關(guān)鍵路線。 采取組織措施，合理調(diào)配人力，物力，資金等資源。(2)資源優(yōu)化： 優(yōu)先安排關(guān)鍵工作所需的資源； 利用非關(guān)鍵工作的總

11、時差，錯開各工作的開始時間。 的確受到資源約束時，考慮推遲工期12123網(wǎng)絡優(yōu)化在上述基礎(chǔ)上，尋求時間更短、資源更省、成本更低的方案。OR3 244 網(wǎng)絡優(yōu)化(1)工期優(yōu)化：12123網(wǎng)絡優(yōu)化在上述基礎(chǔ)上(3)時間費用優(yōu)化時間和費用雙目標優(yōu)化，一般來講二者是矛盾的。通過仔細分析，尋找既省時又省錢的方案，即最低成本日程。費用：直接費用和間接費用直接費用：建造工程本身所需材料、人工間接費用：工程所需管理費用、設(shè)備租賃費用等。ct間接費用總費用直接費用趕工：直接費用增加，間接費用減少。OR3 25(3)時間費用優(yōu)化ct間接費用總費用直接費用趕工：直接費用費用優(yōu)化的步驟(1)計算工作費用增加率；(2)

12、在網(wǎng)絡圖中找出費用率最低的一項關(guān)鍵工作或一組關(guān)鍵工作作為縮短持續(xù)時間的對象。(3)計算相應的增加的總費用，然后考慮由于工期的縮短間接費用的變化，在這個基礎(chǔ)上計算項目的總費用。重復上述步驟，直至獲得滿意的方案為止。趕工直接費用率費用差時間差OR3 26費用優(yōu)化的步驟(1)計算工作費用增加率；趕工直接費用率費用前面內(nèi)容總復習：第一章：緒論。（了解）第二章：線性規(guī)劃與單純形法1，掌握線性規(guī)劃的建模方法。2，掌握將非標準型LP模型轉(zhuǎn)變?yōu)闃藴市汀?，掌握LP問題的解法：圖解法，單純形解法。（圖解法：什么情況下會出現(xiàn)唯一最優(yōu)解，無窮多最優(yōu)解，無界解，無可行解。）（單純形法：會運用單純形法求解LP問題；會根

13、據(jù)單純形表中出現(xiàn)的特征判斷出該問題是否有唯一最優(yōu)解，無窮多最優(yōu)解，無界解以及無可行解P24。OR3 27前面內(nèi)容總復習：第一章：緒論。（了解）OR3 4，掌握大M法以及兩階段法。5，理解書P3637頁的表19，110，圖19。第三章：對偶理論與靈敏度分析1，掌握原問題與對偶問題數(shù)學模型的轉(zhuǎn)化。書P56，表24。2，對偶問題的基本性質(zhì)P57。特別是性質(zhì)3、5、6、73，理解影子價格，影子價格的應用。OR3 284，掌握大M法以及兩階段法。OR3 影子價格：對偶解yi* 的經(jīng)濟意義：其它條件不變的情況下，第i種資源改變一個單位所引起的目標函數(shù)最優(yōu)解的變化。 情況 某資源對偶解0，該資源有利可圖，可增加此種資源量；某資源對偶解為0，則不增加此種資源量。 情況 直接用影子價格與市場價格相比較，進行決策，決定是否買入該資源。 即：影子價格所含有的信息：1、資源緊缺狀況；2、確定資源轉(zhuǎn)讓基價；3、取得緊缺資源的代價。OR3 29影子價格：對偶解yi* 的經(jīng)濟意義：其它條件不變的情況下，第 CjC1 C2 CnCBXBbX1 X2 X3 X4 X5j 0 0 0X3X4X5360200300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1 904030j0 70 120 0 0 0 0 0 120X3X