排序與統(tǒng)籌方法MNEW

1、第十一章 排序與統(tǒng)籌方法統(tǒng)籌方法11 車間作業(yè)計(jì)劃模型車間作業(yè)計(jì)劃的基本概念計(jì)劃模型I計(jì)劃模型II21.基本概念車間作業(yè)計(jì)劃:指一個(gè)工廠生產(chǎn)工序的計(jì)劃和安排.停留時(shí)間:現(xiàn)有n個(gè)零件需要加工,加工時(shí)間分別為Pj ,安排在第j位加工的零件在車間里總的停留時(shí)間Tj : Tj =P1+P2+Pj31.基本概念平均停留時(shí)間:前n個(gè)零件的總時(shí)間為:T1+T2+T3+Tn,平均停留時(shí)間為(T1+T2+T3+Tn)/n42.模型I一臺(tái)機(jī)器,N個(gè)零件:零件加工時(shí)間(小時(shí))零件加工時(shí)間(小時(shí))11.840.922.051.330.561.5如何安排加工順序,才能使得這六個(gè)零件在車間里停留平均時(shí)間為最少?5零件加工

2、時(shí)間Pi 停留時(shí)間Tj零件加工時(shí)間Pi停留時(shí)間Tj11.81.840.95.222.03.851.36.530.54.361.58按1、2、3、4、5、6順序加工零件，各個(gè)零件平均停留時(shí)間為： (1.8+3.8+4.3+5.2+6.5+8)/6=4.93隨意排:1234566零件加工時(shí)間Pi 停留時(shí)間Tj零件加工時(shí)間Pi停留時(shí)間Tj30.50.551.33.4+1.3=4.722.02.561.56.240.9.25+0.9=3.411.88按1、2、3、4、5、6順序加工零件，各個(gè)零件平均停留時(shí)間為： (0.5+2.5+3.4+4.7+6.2+8)/6=4.22按324561的順序加工:7零

3、件加工時(shí)間Pi 停留時(shí)間Tj零件加工時(shí)間Pi停留時(shí)間TjN1Pn1Pn1N4Pn4T3+pn4N2Pn2pn1+pn2N5Pn5T4+Pn5n3pn3T2+Pn3N6Pn6T5+pn6按n1、n2、n3、n4、n5、n6順序加工零件，各個(gè)零件平均停留時(shí)間為：(T1+T2+T3+T4+T5+T6)/6=(p1+(p1+p2)+(p1+p2+p3)+(p1+p2+p3+p4)+(p1+p2+p3+p4+p5)+(p1+p2+p3+p4+p5+p6) )任意順序:n1,n2,n3,n4,n5,n6:8按n1、n2、n3、n4、n5、n6順序加工零件，各個(gè)零件平均停留時(shí)間為：(T1+T2+T3+T4+

4、T5+T6)/6=(p1+(p1+p2)+(p1+p2+p3)+(p1+p2+p3+p4)+(p1+p2+p3+p4+p5)+(p1+p2+p3+p4+p5+p6) )=(1p6+2P5+3P4+4P3+5P2+6P1) /6=(6p1+5P2+4P3+3P4+2P5+1P6) /6要使平均停留時(shí)間最少,只要系數(shù)大的時(shí)間短即可.即要對(duì)加工時(shí)間排序:短時(shí)間加優(yōu)先!任意順序:n1,n2,n3,n4,n5,n6:9本題加順序:3,4,5,6,1,2時(shí)間:0.5,0.9,1.3,1.5,1.8,2.0停留時(shí)間:0.5,1.4,2.7,4.2,6.0,8.0各個(gè)零件平均停留時(shí)間為:3.8103.模型II

5、兩臺(tái)機(jī)器,n個(gè)零件:先削后磨,如何安排加工順序,才能使得完成這五個(gè)零件的總的加工時(shí)間為最少?11先車削,后車磨0.50.251.52.01.01.250.751.752.51.25按FCFS：先來(lái)先服務(wù)。1234512先車削,后車磨1.250.250.751.02.01.51.251.750.52.5按5321413如何確定加工順序,才能總加工時(shí)間最少?事實(shí)上總費(fèi)時(shí)多的原因是第二臺(tái)機(jī)器需要等待,要延時(shí)多,而第一臺(tái)并不需要延時(shí)。因此，要減少盡少磨車床中零件的加工等待時(shí)間。一方面要把短時(shí)間的車削加工往提前排，另一方面，要把磨床上加工時(shí)間短的越晚加工，把磨床上加工時(shí)間長(zhǎng)的往后延。14加工順序零件號(hào)5

6、34120.25,0.5,0.75,1.0,1.25,1.5,2.0,2.515兩臺(tái)機(jī)器,n個(gè)零件的排序問(wèn)題1.在加工時(shí)間表上選出最短加工時(shí)間tij,其中i為工序,j為零件號(hào),當(dāng)為i=1時(shí),將零件J的加工順序盡量靠前,若i=2時(shí),將零件j的加工順序盡量靠后;2.在表上劃去零件j的所在行，回到步驟16練習(xí)題：，New:p279. 1,217網(wǎng)絡(luò)圖1435cdbea262232182 統(tǒng)籌方法一、計(jì)劃網(wǎng)絡(luò)圖二、網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線三、完成工序所需時(shí)間不確定時(shí) 的網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線四、網(wǎng)絡(luò)優(yōu)化19一、計(jì)劃網(wǎng)絡(luò)圖網(wǎng)絡(luò)計(jì)劃技術(shù)的基本概念網(wǎng)絡(luò)圖的繪制20一、計(jì)劃網(wǎng)絡(luò)圖基本概念：工程：一項(xiàng)施工任務(wù)、科研試制項(xiàng)

7、目、生產(chǎn)以及較復(fù)雜的工作任務(wù)，統(tǒng)稱為工程。工序：為了完成某項(xiàng)工程，在工藝技術(shù)和組織管理上相對(duì)獨(dú)立的活動(dòng)稱為工序。如：車床削、磨，兩個(gè)工序，用a,b表示。21一、計(jì)劃網(wǎng)絡(luò)圖基本概念：事件：表示一個(gè)工序的開(kāi)始或結(jié)束，它是相鄰工序在時(shí)間上的分界點(diǎn)，用編號(hào)表示。網(wǎng)絡(luò)圖：由工序、事件及標(biāo)有完成各道工序所需時(shí)間等參數(shù)所構(gòu)成的有向圖，就是網(wǎng)絡(luò)圖。22例1：某公司研制新產(chǎn)品的部分工序與所需時(shí)間以及它們之間的相互關(guān)系如下表：試畫(huà)出其統(tǒng)籌方法網(wǎng)絡(luò)圖。工序代號(hào)工序內(nèi)容所需時(shí)間緊前工序A產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì)60-B外購(gòu)配套零件15AC外購(gòu)生產(chǎn)原料13Ad自制主件38Ce主配件可靠性試驗(yàn)8B,d23二、網(wǎng)絡(luò)圖的繪制網(wǎng)絡(luò)圖

8、的構(gòu)成作業(yè)（工作、工序、活動(dòng)），箭頭表示，箭頭之上表示工作名稱，之下表示工作時(shí)間。可有虛工作。事項(xiàng)，節(jié)點(diǎn)表示，表示某個(gè)工作的結(jié)束和另一工作的開(kāi)始。工作名稱時(shí)間12A60ij24一個(gè)科研項(xiàng)目網(wǎng)絡(luò)圖12345a60c13e8b15d3825例2：某公司研制新產(chǎn)品的部分工序與所需時(shí)間以及它們之間的相互關(guān)系如下表：試畫(huà)出其統(tǒng)籌方法網(wǎng)絡(luò)圖。26一個(gè)科研項(xiàng)目網(wǎng)絡(luò)圖12356a60c13e8b15d384f1027一個(gè)科研項(xiàng)目網(wǎng)絡(luò)圖12356a60c13e8b15d384f107h5g1628一個(gè)科研項(xiàng)目網(wǎng)絡(luò)圖12357a60c13e8b15d384f108h5g16629二、網(wǎng)絡(luò)圖的繪制從開(kāi)始節(jié)點(diǎn)到結(jié)束節(jié)

9、點(diǎn)的一條路經(jīng)叫做路線一個(gè)網(wǎng)絡(luò)圖的有多條路線，每條路線有一個(gè)總時(shí)間總時(shí)間最長(zhǎng)的路線叫做關(guān)鍵路線，關(guān)鍵路線的總時(shí)間叫做工期看下面的例子30網(wǎng)絡(luò)圖的路線31當(dāng)某些工作的時(shí)間調(diào)整后，可能引起關(guān)鍵路線的變化和工期的變化。例如將工作E的時(shí)間縮短為4天，則工期縮短為13天，關(guān)鍵路線將變?yōu)?346BEG5651356BFH553以上網(wǎng)絡(luò)圖共有8條路線可以計(jì)算出這8條路線的總時(shí)間，最長(zhǎng)的是16天。關(guān)鍵路線是32網(wǎng)絡(luò)圖的畫(huà)法作業(yè)的串聯(lián)作業(yè)的并聯(lián)33網(wǎng)絡(luò)圖的畫(huà)法作業(yè)的交叉作業(yè)的合并3435繪制網(wǎng)絡(luò)圖的基本原則兩事件間只能有一項(xiàng)作業(yè)改為36繪制網(wǎng)絡(luò)圖的基本原則網(wǎng)絡(luò)圖應(yīng)從左向右延伸，編號(hào)應(yīng)從小到大，且不重復(fù)。箭頭事項(xiàng)編

10、號(hào)大于箭尾事項(xiàng)編號(hào)網(wǎng)絡(luò)圖只能一個(gè)開(kāi)始節(jié)點(diǎn)，一個(gè)終止節(jié)點(diǎn)不能出現(xiàn)循環(huán)路線不能出現(xiàn)缺口盡量少交叉，采用暗橋；有層次性。3738使用暗橋39網(wǎng)絡(luò)圖的繪制步驟確定目標(biāo)，做好準(zhǔn)備工作任務(wù)分解和分析繪制網(wǎng)絡(luò)圖40表4-1 調(diào)查項(xiàng)目的任務(wù)分解和分析41繪制作業(yè)圖的方法試探性繪制法計(jì)算機(jī)輔助繪制法流程圖過(guò)渡繪制法42試探性繪制法：試探43試探性繪制法：修改44流程圖過(guò)渡繪制法：流程圖45流程圖過(guò)渡繪制法：加事項(xiàng)46流程圖過(guò)渡繪制法：去方框47流程圖過(guò)渡繪制法：修改48二、網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線從網(wǎng)絡(luò)圖中求出：完成此工程項(xiàng)目所需的最少時(shí)間；每個(gè)工序的開(kāi)始時(shí)間與結(jié)束時(shí)間；關(guān)鍵路線及其相應(yīng)的關(guān)鍵工序；非關(guān)鍵工序在不影響

11、工程的完成時(shí)間的前提下，其開(kāi)始時(shí)間與結(jié)束推遲多久。49例5 某公司裝配一條新的生產(chǎn)線。工序代號(hào)工序內(nèi)容所需時(shí)間緊前工序A生產(chǎn)線設(shè)計(jì)60-B外購(gòu)零配件45AC下料、鍛件10AD工裝制造120AE木模40AF機(jī)械加工118CG工裝制造230DH機(jī)械加工215D,eI機(jī)械加工325Gj裝配調(diào)試35B,I,f,h5012457a60c10i25b45d206h158j35g303e40f1851尋找關(guān)鍵路線：（1）從網(wǎng)絡(luò)起點(diǎn)按順序計(jì)算出每個(gè)工序的最早開(kāi)始時(shí)間（ES）和最早結(jié)束時(shí)間（EF）1260A0,60對(duì)同一個(gè)工序：EF=Es+t;對(duì)相鄰工序：EF=ES（Max）+t521245760c10i25b

12、45d206h158j35g303e40f18A0,60d60,80e60,100b60,105c60,70f70,88g80,110i110,135h100,115j135,17053尋找關(guān)鍵路線：（2）從網(wǎng)絡(luò)收點(diǎn)開(kāi)始計(jì)算出每個(gè)工序的最遲（晚）開(kāi)始時(shí)間（LS）和最遲（晚）結(jié)束時(shí)間（LF）對(duì)同一個(gè)工序：LS=LF-t;對(duì)相鄰工序：LS=LF-t541245760c10i25b45d206h158j35g303e40f18A0,60d60,80e60,100b60,105c60,70f70,88g80,110i110,135h100,115j135,17035135,17025110,13515

13、120,1354080,1203080,11018117,1354590,13510107,1172060,80600,6055尋找關(guān)鍵路線：（3）計(jì)算出每個(gè)工序的時(shí)間差TS TS=LS-ES=LF-EF,對(duì)工序B來(lái)說(shuō)，TS=90-60=30工序在60-90天之內(nèi)任何時(shí)間內(nèi)開(kāi)工，都不會(huì)影響工期。稱為非關(guān)鍵工序。對(duì)工序g來(lái)說(shuō)，TS=80-80=0不能提前，也不能推后，否則會(huì)影響總工期。稱為關(guān)鍵工序。56例5 某公司裝配一條新的生產(chǎn)線。571245760c10i25b45d206h158j35g303e40f18A0,60d60,80e60,100b60,105c60,70f70,88g80,11

14、0i110,135h100,115j135,17035135,17025110,13515120,1354080,1203080,11018117,1354590,13510107,1172060,80600,60得關(guān)鍵路線： Adgij58三、完成工序所需時(shí)間不確定時(shí)的網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線：如果完成工序所需時(shí)間不確定的情況下怎樣來(lái)求網(wǎng)絡(luò)時(shí)間和關(guān)鍵路線？59例6。某培訓(xùn)中心準(zhǔn)備對(duì)各部門(mén)領(lǐng)導(dǎo)干部進(jìn)行培訓(xùn)?；顒?dòng)工序活動(dòng)內(nèi)容緊前活動(dòng)A 制定培訓(xùn)計(jì)劃-B選聘培訓(xùn)教師AC列出可選培訓(xùn)點(diǎn)-D確定培訓(xùn)點(diǎn)CE確定培訓(xùn)的日程安排B,dF落實(shí)教學(xué)設(shè)備、資料EG發(fā)培訓(xùn)通知及確定學(xué)員名單b,dh訂旅館房間Gi處理最后的

15、一些事務(wù)F,h60 通過(guò)調(diào)查的時(shí)間估計(jì)：活動(dòng)工序樂(lè)觀時(shí)間最可能時(shí)間悲觀時(shí)間A1.52.02.5B2.02.56C123D1.522.5E0.511.5F123G33.57h345i1.522.561要求：繪出統(tǒng)籌方法的網(wǎng)絡(luò)圖，設(shè)法求出網(wǎng)絡(luò)時(shí)間和關(guān)鍵路線。6212345678iabcdegfh 統(tǒng)籌方法網(wǎng)絡(luò)圖一、先畫(huà)出網(wǎng)絡(luò)圖：63二、工序（活動(dòng)）時(shí)間：樂(lè)觀時(shí)間（全綠燈）：順利情況下，完成活動(dòng)所需時(shí)間-a 最可能時(shí)間（正常）：指正常情況下，完成活動(dòng)所需時(shí)間-m悲觀時(shí)間（很不順）：指在不順利情況下，完成工作所需時(shí)間-b。64作業(yè)時(shí)間的確定對(duì)具有標(biāo)準(zhǔn)的作業(yè)，采用單一時(shí)間估計(jì)法對(duì)一般性作業(yè)，采用三點(diǎn)時(shí)間

16、估計(jì)法最樂(lè)觀時(shí)間：a最可能時(shí)間：m最悲觀時(shí)間：b計(jì)算時(shí)間期望值和方差65工序時(shí)間計(jì)算方法amb平均時(shí)間66按期完成計(jì)劃的概率每項(xiàng)作業(yè)的時(shí)間是一個(gè)隨機(jī)變量，近似服從 分布，均值和標(biāo)準(zhǔn)差為工期也是一個(gè)隨機(jī)變量，它的期望值為各關(guān)鍵作業(yè)時(shí)間期望之和。67按期完成計(jì)劃的概率當(dāng)作業(yè)數(shù)足夠多時(shí)，工期近似服從正態(tài)分布68按期完成計(jì)劃的概率其中按期完成的概率6912345678ia0，2bcdegfh 統(tǒng)籌方法網(wǎng)絡(luò)圖一、先畫(huà)出網(wǎng)絡(luò)圖：2b0，22a0，222421224a7012345678ia0，2bcdegfh 統(tǒng)籌方法網(wǎng)絡(luò)圖一、先畫(huà)出網(wǎng)絡(luò)圖：2b0，22e5，622421224ag5，9c0，2d2，4f

17、6，8h9，13i13，157112345678ia0，2bcdegfh 統(tǒng)籌方法網(wǎng)絡(luò)圖一、先畫(huà)出網(wǎng)絡(luò)圖：2b2，52e5，62421224ag5，9c0，2d2，4f6，8h9，13i13，15213，15211，1349，13110，1145，923，521，332，520，272例5 某公司裝配一條新的生產(chǎn)線。YesYesYesYesYes7312345678ia0，2bcdegfh關(guān)鍵路線：abghi:平均時(shí)間的總和：2+3+4+4+2=152b2，52e5，62421224ag5，9c0，2d2，4f6，8h9，13i13，15213，15211，1349，13110，1145，92

18、3，521，332，520，274由于完成培訓(xùn)工作所需時(shí)間是一個(gè)隨機(jī)事件，是可變的，它服從一定的概率分布，根據(jù)概率論知識(shí)，各工序的時(shí)間服從分布，那么完成整個(gè)任務(wù)的時(shí)間和近似服從正態(tài)分布，從而可以估計(jì)不同守工時(shí)間的概率。例如，E(T)=Ta+Tb+Tg+Th+Ti=15, 2 =各方差之和=1.05那么完成整個(gè)工作的時(shí)間服從N(E(T), 2) 的正態(tài)分布.因此,可以利用此分布來(lái)估計(jì)在一定時(shí)間內(nèi)完成整個(gè)工作的可能性.75培訓(xùn)工作的平均完成時(shí)間為E（T）（約15周），波動(dòng)變化反映在幅度方差為2，具體完成的時(shí)間是動(dòng)態(tài)變化不確定的。那么我們可以根據(jù)時(shí)間服從N(E(T), 2) 的正態(tài)分布來(lái)估算完成時(shí)間

19、的可能性（概率）即利用此分布來(lái)估計(jì)在一定時(shí)間內(nèi)完成整個(gè)工作的可能性.如：上述平均時(shí)間是15周， 2=1.05,那么,培訓(xùn)工作能在16周內(nèi)完成的可能性有多大?76如果要以99%的把握來(lái)保證培訓(xùn)工作如期完成,那么應(yīng)在幾周前開(kāi)始準(zhǔn)備?如果要以99%的把握來(lái)保證培訓(xùn)工作如期完成,那么應(yīng)在幾周前開(kāi)始準(zhǔn)備?77如果要以100%的把握來(lái)保證培訓(xùn)工作如期完成,那么應(yīng)在幾周前開(kāi)始準(zhǔn)備?78四、網(wǎng)絡(luò)優(yōu)化 得到初始的計(jì)劃方案，但通常要對(duì)初始方案進(jìn)行調(diào)整與完善。根據(jù)計(jì)劃目標(biāo)，綜合考慮資源和降低成本等目標(biāo)，進(jìn)行網(wǎng)絡(luò)優(yōu)化，確定最優(yōu)的計(jì)劃方案。工期限定，資源需要平衡資源有限，工期希望最短工期縮短，總費(fèi)用最小79四、網(wǎng)絡(luò)優(yōu)化

20、 1.時(shí)間-資源優(yōu)化 做法： 1）優(yōu)先安排關(guān)鍵工序所需的資源。 2）利用非關(guān)鍵工序的時(shí)差，錯(cuò)開(kāi)各工序的開(kāi)始時(shí)間。 3）統(tǒng)籌兼顧工程進(jìn)度的要求和現(xiàn)有資源的限制，多次綜合平衡。 下面列舉一個(gè)拉平資源需要量最高峰的實(shí)例。在例5中，若加工工人為65人，并假定這些工人可完成這5個(gè)工序任一個(gè)，下面來(lái)尋求一個(gè)時(shí)間-資源最優(yōu)方案。如表12-16所示：80安排d-i各工序的總?cè)藬?shù)為65811245760c10i25b45d206h15天8j35g303e40f18d58人f22人g42人i26人h3982274635 f(22人）18h(39人)1558人64人80人81人42人26人65人60 80 100

21、120 130 d(58人） i(26人） g(42人）302025圖12-171083dd+fF+ggG+hH+ii607080901001101201305880人644281人6526人84607080901001101201305880人644281人6526人85安排d-i各工序的總?cè)藬?shù)為6586idF+ggH+i607080901001101201305864426526人 同時(shí)我們應(yīng)優(yōu)先安排關(guān)鍵工序所需的工人，再利用非關(guān)鍵工序的時(shí)差，錯(cuò)開(kāi)各工序的開(kāi)始時(shí)間，從而拉平工人需要量的高峰。經(jīng)過(guò)調(diào)整，我們讓非關(guān)鍵工序f從第80天開(kāi)始，工序h從第110天開(kāi)始。找到了時(shí)間-資源優(yōu)化的方案，如圖

22、12-18所示，在不增加工人的情況下保證了工程按期完成。872.時(shí)間-費(fèi)用優(yōu)化工期不變，就是關(guān)鍵工作時(shí)間不能調(diào)整資源不平衡將導(dǎo)致資源不足利用時(shí)差，調(diào)整非關(guān)鍵路線上工作的開(kāi)始時(shí)間，使資源實(shí)現(xiàn)平衡。882 統(tǒng)籌方法2.時(shí)間-費(fèi)用優(yōu)化 需要考慮時(shí)間與費(fèi)用的問(wèn)題：在既定的時(shí)間前工程完工的前提下，使得所需的費(fèi)用最少，或者在不超工程預(yù)算的條件下使工程最早完工。這些是時(shí)間-費(fèi)用優(yōu)化要研究和解決的問(wèn)題。 直接費(fèi)用：為了加快工程進(jìn)度，必須設(shè)法縮短關(guān)鍵工序的時(shí)間，這樣需要增加人力、設(shè)備和工作班次，從而需要增加一筆費(fèi)用，成為直接費(fèi)用。 間接費(fèi)用：由于工程早日完工，減少了管理人員的工資辦公費(fèi)等費(fèi)用稱為間接費(fèi)用。一般說(shuō)

23、工序越短，直接費(fèi)用越多，間接費(fèi)用越少。892 統(tǒng)籌方法 工序的最快完成時(shí)間：指完成時(shí)間的最高限度。 我們?cè)O(shè)完成工序j的正常所需時(shí)間為T(mén)j;直接費(fèi)用為cj;完成工序j的最快完成時(shí)間為T(mén)j,直接費(fèi)用為cj。這樣我們可以計(jì)算出縮短工序j的一天工期所增加的直接費(fèi)用，用kj表示，稱為直接費(fèi)用變動(dòng)率。有 時(shí)間-費(fèi)用優(yōu)化問(wèn)題可建立兩個(gè)線性規(guī)劃模型。 模型一，在既定的時(shí)間T完工的前提下，問(wèn)各工序的完成時(shí)間為多少才使因縮短工期而增加的直接費(fèi)用最少。 設(shè)工序（i ,j)的提前完工時(shí)間為Yij,我們用Tij,Tij分別表示正常完工時(shí)間與最快完工的時(shí)間，則有工序（i ,j)的實(shí)際完工時(shí)間為：Tij-Yij。我們用Ci

24、j,Cij表示用正常完工時(shí)間和最快完成時(shí)間完成工序所需要的費(fèi)用，Kij為工序（i ,j)的直接費(fèi)用變動(dòng)率。得到這個(gè)問(wèn)題的線性規(guī)劃模型如下： minf=（Kij*Yij) （i,j)S.t. Xj-Xi Tij-Yij,對(duì)一切?。╥, j) Yij Tij-Tij, 對(duì)一切?。╥, j) Xn-X1 T, Xi 0， Yij 0。902 統(tǒng)籌方法例7. 例5所提供的信息都作為本例的信息，另外還給出了在裝配過(guò)程中各道工序所需正常完工時(shí)間與最快完工時(shí)間，以及對(duì)應(yīng)正常完工時(shí)間與最快完工時(shí)間的所需的直接費(fèi)用和每縮短一天工期所需增加的直接費(fèi)用，如表12-17所示。 表12-17工序Tij正常完工Cij直接

25、費(fèi)用Tij最快完工Cij直接費(fèi)用直接費(fèi)用變動(dòng)率a60100006010000-b454500306300120c10280054300300d2070001011000400e40100003512500500f183600105440230g3090002012500350h153750105750400i256250159150290j35120003512000-912 統(tǒng)籌方法 該工程要求在150天內(nèi)完工，問(wèn)每個(gè)工序應(yīng)比正常完工時(shí)間提前多少天完成，才能使整個(gè)工程因縮短工期而增加的直接費(fèi)用為最少。如果工期要求在140天完工呢？12345678abfechgijd圖12-19922 統(tǒng)籌方

26、法解：繪出如圖12-19所示，根據(jù)此網(wǎng)絡(luò)圖建立數(shù)學(xué)模型。 設(shè)此網(wǎng)絡(luò)圖上第i點(diǎn)發(fā)生的時(shí)間為xi，工序提前完工的時(shí)間為yij。 目標(biāo)函數(shù)minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67.s.t. x2-x1 60-y12, x7- x2 45-y27 x3-x210-y23 x4-x220-y24 x5-x240-y25 x7-x318-y37 x6-x430-y46 x5-x40虛擬?。?，5） x7-x515-y57 x7-x625-y67932 統(tǒng)籌方法 x1 =0, y120, y2715, y23 5 y24 10

27、y25 5 y37 8 y46 10 y57 5 y78 0 x8 150 xi 0，yij 0.（對(duì)一切可能的ij)運(yùn)算得到結(jié)果：f=6400。942 統(tǒng)籌方法 模型二，我們知道直接費(fèi)用是隨著完成時(shí)間的縮短而增加，而間接費(fèi)用卻會(huì)隨著完成時(shí)間的縮短而減少，設(shè)單位時(shí)間的間接費(fèi)用為d,計(jì)劃期的間接費(fèi)用與總工期成正比，即為d(xn-x1),那么求使包括間接費(fèi)用與直接費(fèi)用在內(nèi)的總費(fèi)用最少的整個(gè)工程最優(yōu)完成時(shí)間T和各個(gè)工序最優(yōu)完成時(shí)間的模型為： 目標(biāo)函數(shù)min f=d(xn-x1)+ s.t. xj-xi Tij-yij，對(duì)一切?。╥ ,j) yijTij-Tij ，對(duì)一切弧（i ,j) xi 0， y

28、ij 0。952 統(tǒng)籌方法 例8 如果在例7中，每天的間接費(fèi)用為330元，求使包括間接費(fèi)用與直接費(fèi)用在內(nèi)的總費(fèi)用最少的整個(gè)工程最優(yōu)完成時(shí)間T和各個(gè)工序最優(yōu)完成時(shí)間。 解：決策變量的含義同例7。 此數(shù)學(xué)模型的目標(biāo)函數(shù)為： min f=330(x8-x1) +120y27+300 y23 +400y24+500y25+230y37+350y46+290y67 此模型的約束條件與例7的約束條件基本相同，只要在例子的約束條件中去掉x8 150就得到了例8模型的約束條件了。 計(jì)算得到以下結(jié)果： f=55700. x1=0, y12=0, y67 =10, x2=60, y27 =0, y78=0.962 統(tǒng)籌方法x3 =125, y23 =0, x4 =107, y24 =0, x5 =110, y2