13運(yùn)籌學(xué)安排與統(tǒng)籌學(xué)

課堂練

.此LP問題的解：x1=1,x2=0,x3=1.5,

Max

z=7。迭代次數(shù)基變量CBx1x2x3x4x5x6b比值1240002x4000.501-10.51x111-0.5001-0.51x34*03*/41*0*00.251.5zj12.54010.57*σj=cj-zj0-0.500-1-0.5練習(xí)二.求下圖中從v1到v7的最短路用標(biāo)號(hào)法求得下圖中從v1到v7的最短路081133P.279習(xí)題1：平均停留時(shí)間:一臺(tái)機(jī)器n個(gè)零件的排序問題。第j個(gè)加工的零件加工時(shí)間為Pj

,則ji

1

Pi它的總停留時(shí)間為：Tj平均停留時(shí)間:nn1jnP

(n

1)P2

...

PnnM

1

T

j1可見當(dāng):P1≤P2≤…≤Pn時(shí)M=minP.279習(xí)題2：加工順序、線條圖、總加工時(shí)間、鉆床停工時(shí)間和磨床停工時(shí)間.Johnson算法:零件7鉆床9.1磨床7.4最佳加工順序：2→3→7→5→1→6→4統(tǒng)籌方法國外

于上世紀(jì)50年代，60-70年代我國開始應(yīng)用和推廣。

、等都曾為此做了大量工作。的例子：有客來訪，要請(qǐng)他飲茶，于是要做幾件事：洗茶杯、洗杯蓋、燒開水、泡茶到端茶?？蛠砥悴璞締栴}的幾道“工序”有次序時(shí)間:洗杯蓋

2

端茶0.5燒水5

泡茶2洗杯1虛0網(wǎng)絡(luò)圖的畫法項(xiàng)目代號(hào)后續(xù)作業(yè)時(shí)間淘米AB、C2分洗切菜BD7分煮飯C結(jié)束20分炒菜D結(jié)束12分1

23427B20CD12項(xiàng)目代號(hào)后續(xù)作業(yè)時(shí)間淘米AB、C2min洗切菜BD7min蒸飯C20min炒菜D12min用帶箭頭的線段表示每項(xiàng)作業(yè)或任務(wù)，標(biāo)有數(shù)字的圓圈表示作業(yè)的開始和結(jié)束，把工期標(biāo)于箭頭上。A124A2B7C20D123由上圖可看出關(guān)鍵路徑為A－C或1－2－4，長度為22。但復(fù)雜的圖形就不易看出。A:淘米B:洗切菜C:煮飯D:炒菜客來沏茶最晚完成時(shí)間。端茶0.5燒水5

泡茶2洗杯101577.5虛05PERT解法：5

最早完成時(shí)間,5洗杯蓋2最佳次序：先燒開水，等待水開之時(shí)洗杯、蓋，水燒開后泡茶，端茶0577.57.5750關(guān)鍵路徑問題TQC(全面質(zhì)量管理)中的重要問題：有向圖：每條邊有方向(即邊v1v2與邊v2v1是區(qū)別的)的圖。工序之間的次序關(guān)系用有向圖表示叫PERT(計(jì)劃評(píng)審技術(shù))圖。避免窩工，掌握工程進(jìn)展中關(guān)鍵工序，提高工程速度的技術(shù)——關(guān)鍵路徑。一、網(wǎng)絡(luò)計(jì)劃方法的產(chǎn)生㈠ ：網(wǎng)絡(luò)計(jì)劃方法是項(xiàng)目計(jì)劃管理的重要方法。它于 。當(dāng)時(shí)，有兩種網(wǎng)絡(luò)計(jì)劃方法：關(guān)鍵路和計(jì)劃評(píng)審技術(shù)。1957年， 杜邦化學(xué)公司用關(guān)鍵路

(CriticalPath

Method)。當(dāng)年就節(jié)約100萬 ，為該公司用于該項(xiàng)目研究費(fèi)用的5倍以上。1958年， 在研制北極星 潛艇時(shí)，第一次采用了BuzzAllen

計(jì)劃評(píng)審技術(shù)(ProgramEvaluation

and

Review

Technique),主要承包商200多家，轉(zhuǎn)包商10000家。23個(gè)系統(tǒng)網(wǎng)絡(luò)，每兩周檢查一次，原定6年，提前兩年完成，節(jié)約經(jīng)費(fèi)10—15％。60年代耗時(shí)11年

登月計(jì)劃3000億$,42萬人,2萬家公司,120所大學(xué),600臺(tái)計(jì)算機(jī),700萬零件,終于在1969年7月，

11號(hào)船長 登上月球。節(jié)點(diǎn)v的后繼元素集Γ

(v)={x|x∈V且vx1、

∈E}2、節(jié)點(diǎn)v的先驅(qū)元素集Γ-(v)={x|x∈V且xv∈E}3、從發(fā)點(diǎn)起求最早完成時(shí)間(TE):是指活動(dòng)最早可能完成的時(shí)間TE(vi)=㈡關(guān)鍵路徑問題4、從收點(diǎn)起求最遲完成時(shí)間(TL):是指活動(dòng)最遲必須完成的時(shí)間TL(vi)=vj

(vi

)j

jimax{TE(v

)

w

}minj

iv

(v

)j

ij{TL(v

)

w

}5、ES(vi)=TL(vi)-TE(vi)叫緩沖時(shí)間。緩沖時(shí)間是0的節(jié)點(diǎn)組成關(guān)鍵路徑。某機(jī)械廠管理信息系統(tǒng)開發(fā)活動(dòng)活動(dòng)描述緊后活動(dòng)活動(dòng)時(shí)間(周)A系統(tǒng)分析和總體設(shè)計(jì)B,C3B輸入和輸出設(shè)計(jì)D4C模塊1詳細(xì)設(shè)計(jì)E,F6D輸入和輸出程序設(shè)計(jì)G,I8E模塊1程序設(shè)計(jì)G,I8F模塊2詳細(xì)設(shè)計(jì)H5G輸入和輸出及模塊1測(cè)試J3H模塊2程序設(shè)計(jì)I,K6I模塊1測(cè)試J3J系統(tǒng)總調(diào)試L5K文檔編寫無8L系統(tǒng)測(cè)試無3㈢繪制方法活動(dòng)作業(yè)時(shí)間ET(i)LT(j)ES(i,j)EF(i,j)LS(i,j)LF(i,j)①②③④⑤=③⑥=⑤+②⑦=④-②⑧=④1

—

240404042

—

384124124122

—

42411469113

—

5512—

631228121525284

—

566176121117例題12346109857A3B

4C6D8E8F5H6G3J5L3K8I

3例題03371291417

2020232831009914142020232328283131②的先驅(qū)元素是

①④的先驅(qū)元素是

②⑤的先驅(qū)元素是

④⑨的后繼元素是

⑩⑧的后繼元素是

⑨發(fā)點(diǎn)收點(diǎn)幾個(gè)概念最早完成時(shí)間(TE)；最晚完成時(shí)間(TL)；緩沖時(shí)間(ES)；各頂點(diǎn)的緩沖時(shí)間為0的(由發(fā)點(diǎn)到收點(diǎn)的)通路叫關(guān)鍵路徑。習(xí)題(P.280):

4,5關(guān)鍵路徑問題(P.264)例5：2675jd20g30i25a60f18c10b4515603708010011035135170135

1708110120

h11780460010e401→2→4→6→7→8作業(yè)名稱作業(yè)代號(hào)后續(xù)作業(yè)作業(yè)長度研究方案AB、I5制定比賽程序表BC、E、G10印刷比賽程序表CD10分發(fā)比賽程序表D結(jié)束1預(yù)定獎(jiǎng)品EF3驗(yàn)收獎(jiǎng)品F結(jié)束1制作比賽用具GH7搬運(yùn)用具HJ1聯(lián)系運(yùn)動(dòng)場(chǎng)IJ1布景運(yùn)動(dòng)場(chǎng)J結(jié)束1學(xué)校準(zhǔn)備開一個(gè)運(yùn)動(dòng)會(huì),作業(yè)明細(xì)表如下,請(qǐng)畫出網(wǎng)絡(luò)圖3452687B10I11C10E3G7H1J1D1

F

1A5作業(yè)名稱作業(yè)代號(hào)后續(xù)作業(yè)作業(yè)長度研究方案AB、I5制定比賽程序表BC、E、G10印刷比賽程序表CD10分發(fā)比賽程序表D結(jié)束1預(yù)定獎(jiǎng)品EF3驗(yàn)收獎(jiǎng)品F結(jié)束1制作比賽用具GH7搬運(yùn)用具HJ1聯(lián)系運(yùn)動(dòng)場(chǎng)IJ1布景運(yùn)動(dòng)場(chǎng)J結(jié)束1運(yùn)動(dòng)會(huì)*表示所有點(diǎn)，(i,j)表示一項(xiàng)作業(yè)，n表示最大結(jié)點(diǎn) 即終點(diǎn)。TEF(i,j)=TES(i,j)+tijTLF(*,n)=max{TEF(*,n)}TLF(i,j)=min{TLF(j,*)-tj*}TLS(i,j)=TLF(i,j)-tij124B7C20D12結(jié)點(diǎn)作業(yè)作業(yè)長度最早開工時(shí)刻最遲開工時(shí)刻最早完工時(shí)刻最遲完工時(shí)刻時(shí)差關(guān)鍵作業(yè)ijtijTESTLSTEFTLFS12A200220A23B723910124C202222220C34D129102122102222TES(1,*)=0,TES（i,j）=max{TES(*,i)+t*i}0

A

22

23109103

92222221黑色表示作業(yè)長度tij，紅色表示ES和EF，藍(lán)色表示LS和LF17DE20F9G10H8I400020C3333818

2629334343435

352643

34352

817283939

6

3929302030

3A8B10

2017819933