蔡詩文魯林霞李強(qiáng)

1、第5章 圖論 8推出新型產(chǎn)品完成計(jì)劃的問題 論文摘要本文根據(jù)某公司推出新型產(chǎn)品的作業(yè)流程和各作業(yè)的計(jì)劃完成時(shí)間、最短完成時(shí)間、計(jì)劃完成時(shí)間縮短所用費(fèi)用，來確定新產(chǎn)品生產(chǎn)時(shí)間和產(chǎn)品上市所需費(fèi)用的最優(yōu)策略。對(duì)于問題一，畫出相應(yīng)的計(jì)劃網(wǎng)絡(luò)圖，可以清楚的看出作業(yè)流程情況；對(duì)于問題二，利用遞推關(guān)系模型計(jì)算最早開始時(shí)間、最遲開始時(shí)間和工序時(shí)差，關(guān)鍵路線。利用Lingo 11.0 求解得到關(guān)鍵路線：，完成新產(chǎn)品的最遲時(shí)間加上作業(yè)的完成時(shí)間周是周。作業(yè)的最早時(shí)間分別是；最遲開始的時(shí)間分別是。對(duì)于問題三，可以說是對(duì)問題二的優(yōu)化。通過建立遞推關(guān)系模型計(jì)算最早完工時(shí)間與計(jì)劃完成時(shí)間縮短時(shí)間的關(guān)系，利用Lingo 1

2、1.0求解在規(guī)定時(shí)間內(nèi)完成的最小費(fèi)用以及相應(yīng)的時(shí)間。關(guān)鍵詞：計(jì)劃網(wǎng)絡(luò)圖 計(jì)劃評(píng)審方法 關(guān)鍵路線法 期望 概率 問題重述某公司計(jì)劃推出一種新型產(chǎn)品，需要完成的作業(yè)由表1示。表1作業(yè)名稱計(jì)劃完成時(shí)間（周）緊前作業(yè)最短完成時(shí)間（周）縮短1周的費(fèi)用（元）A設(shè)計(jì)產(chǎn)品6-4800B市場(chǎng)調(diào)查5-3600C原材料訂貨3A1300D原材料收購2C1600E建立產(chǎn)品設(shè)計(jì)規(guī)范3A,D1400F產(chǎn)品廣告宣傳2B1300G建立產(chǎn)品生產(chǎn)基地4E2200H產(chǎn)品運(yùn)輸?shù)箮?G,F2200（1）畫出產(chǎn)品的計(jì)劃網(wǎng)絡(luò)圖；（2）求完成的最短時(shí)間，列出各項(xiàng)作業(yè)的最早開始時(shí)間、最遲開始時(shí)間和計(jì)劃網(wǎng)絡(luò)的關(guān)鍵路線；（3）假定公司計(jì)劃在17 周

3、內(nèi)推出該產(chǎn)品，各項(xiàng)作業(yè)的最短時(shí)間和縮短1 周的費(fèi)用如上表所示，求產(chǎn)品在17 周內(nèi)上市的最小費(fèi)用；（4）如果各項(xiàng)作業(yè)的完成時(shí)間并不能完全確定，而是根據(jù)以往的經(jīng)驗(yàn)估計(jì)出來的，估計(jì)值如表2所示。試計(jì)算出產(chǎn)品在21 周內(nèi)上市的概率和以95的概率完成新產(chǎn)品上市所需的周數(shù)。表2作業(yè)ABCDEFGH最樂觀的估計(jì)24211321最可能的估計(jì)65323442最悲觀的估計(jì)106435564 問題分析由題意可以看出，問題一、二主要考察了計(jì)劃網(wǎng)絡(luò)圖的繪制與計(jì)算以及計(jì)劃評(píng)審方法和關(guān)鍵路徑法等相關(guān)統(tǒng)籌法的運(yùn)用，利用計(jì)劃網(wǎng)絡(luò)圖表示的作業(yè)之間的關(guān)系，確定出每個(gè)作業(yè)的最早開始時(shí)間、完成作業(yè)的時(shí)間、作業(yè)的最遲開始時(shí)間，工序時(shí)差的

4、關(guān)系從而將問題解答。問題三可以說是問題二的優(yōu)化，將之前的模型，加上兩個(gè)因素：一是對(duì)任務(wù)加上更多的資源，如在作業(yè)中加上更多的人力、物力使得產(chǎn)品完成的更快，成為“縮短期”；二是使計(jì)劃網(wǎng)絡(luò)模型滿足到期完成，必須報(bào)入縮短期費(fèi)用，目標(biāo)是使縮短期的費(fèi)用最少。1 模型假設(shè)1、每項(xiàng)作業(yè)完成的時(shí)間都是固定的。2、每一項(xiàng)工作的完成期間不受到任何因素的影響。 符號(hào)說明：表示事件的開始時(shí)間（）；：表示事件的最遲開始時(shí)間（）；：是作業(yè)的計(jì)劃完成時(shí)間；：是作業(yè)的最短完成時(shí)間；：表示以為開始作業(yè)，以為完工作業(yè)的工序之差； ：是作業(yè)縮短一周的費(fèi)用；：是作業(yè)的縮短時(shí)間；：要求完成的周數(shù)VI模型建立問題一： 根據(jù)題意，建立產(chǎn)品的

5、計(jì)劃網(wǎng)絡(luò)圖如圖1所示。C3E3D2B5H2F22G3A 645678123A6 圖1問題二：（1）設(shè)為最初事件，為最終事件。希望求得完成的最短時(shí)間，即極小化，因此對(duì)于事件和有不等式：由此得到的相應(yīng)的數(shù)學(xué)規(guī)劃模型為：(其中是所有的事件集合，是所有的作業(yè)集合)。利用Lingo 11.0 編寫程序（程序見附件一），由運(yùn)行結(jié)果（運(yùn)行結(jié)果見附件二）可以得到所求結(jié)果。運(yùn)行結(jié)果給出了各個(gè)作業(yè)的開工時(shí)間，只要每個(gè)作業(yè)按規(guī)定的時(shí)間開工，整個(gè)項(xiàng)目完成的最短時(shí)間為20周。（2）1計(jì)算最早開始時(shí)間：用表示作業(yè)的最早開始時(shí)間，它等于到的最長單向鏈長，由圖性質(zhì)可得如下的遞推公式：C3E3D2B5H2F22G3A 6567

6、89234A610圖若用表示完工作業(yè)，則為作業(yè)完成所需要的時(shí)間。計(jì)算最遲完工時(shí)間：他應(yīng)該等于總工期減去該作業(yè)的完工作業(yè)到總完工作業(yè)最長單向鏈的長。用表示作業(yè)的最遲完工時(shí)間，則有以下遞推公式： 計(jì)算時(shí)差：一道工序的時(shí)差是指該工序的最遲完成時(shí)間與最早開始時(shí)間之差再減去它的工序長，凡時(shí)差為零的工序，它們的開始時(shí)間必須準(zhǔn)時(shí)，即關(guān)鍵作業(yè)：利用Lingo 11.0 編寫程序（程序見附件三），由運(yùn)行結(jié)果（運(yùn)行結(jié)果見附件四）可以得到所求結(jié)果。從結(jié)果中可以看出，關(guān)鍵路線：，完成新產(chǎn)品的最遲時(shí)間加上作業(yè)的完成時(shí)間周是周。作業(yè)的最早時(shí)間分別是；最遲開始的時(shí)間分別是。問題三：1、完成每個(gè)作業(yè)所用的各個(gè)時(shí)間的約束，即

7、2、完成任務(wù)所用的時(shí)間不超過要求完成的時(shí)間，即 3、要使產(chǎn)品額外增加的費(fèi)用最少，即 即所建立的模型為 利用Lingo 11.0 編寫程序（程序見附件五），由運(yùn)行結(jié)果（運(yùn)行結(jié)果見附件六）可以得到所求結(jié)果。最小費(fèi)用為零，都沒有縮短。問題四：VII參考文獻(xiàn)1 附件一：model:sets:events/1.8/:x;operate(events,events)/1 2,1 3,1 5,2 4,3 7,4 5,5 6,6 7,7 8/:t;endsetsdata:t=6,5,0,3,2,2,3,4,2; enddatamin=x(8)-x(1);for(operate(i,j):x(j)>x(i

8、)+t(i,j);End附件二： Global optimal solution found. Objective value: 20.00000 Infeasibilities: 0.000000 Total solver iterations: 0 Variable Value Reduced Cost X( 1) 0.000000 0.000000 X( 2) 6.000000 0.000000 X( 3) 5.000000 0.000000 X( 4) 9.000000 0.000000 X( 5) 11.00000 0.000000 X( 6) 14.00000 0.000000 X

9、( 7) 18.00000 0.000000 X( 8) 20.00000 0.000000 T( 1, 2) 6.000000 0.000000 T( 1, 3) 5.000000 0.000000 T( 1, 5) 0.000000 0.000000 T( 2, 4) 3.000000 0.000000 T( 3, 7) 2.000000 0.000000 T( 4, 5) 2.000000 0.000000 T( 5, 6) 3.000000 0.000000 T( 6, 7) 4.000000 0.000000 T( 7, 8) 2.000000 0.000000 Row Slack

10、or Surplus Dual Price 1 20.00000 -1.000000 2 0.000000 -1.000000 3 0.000000 0.000000 4 11.00000 0.000000 5 0.000000 -1.000000 6 11.00000 0.000000 7 0.000000 -1.000000 8 0.000000 -1.000000 9 0.000000 -1.000000 10 0.000000 -1.000000附件三：model:sets:events/1.9/:t,x,y,s;operate(events,events)/1 2,2 3,2 4,2

11、 6,3 5,4 8,5 6,6 7,7 8,8 9/;endsetsdata:t=0,6,5,3,2,2,3,4,2;enddatax(1)=0;for(events(j)|j#gt#1:x(j)=max(operate(i,j):x(i)+t(i);levents=size(events);y(levents)=x(levents);s(levents)=0;for(events(i)|i#lt#levents:y(i)=min(operate(i,j):y(j)-t(i);s(i)=y(i)-x(i);End附件四：Feasible solution found. Total solve

12、r iterations: 0 Variable Value LEVENTS 9.000000 T( 1) 0.000000 T( 2) 6.000000 T( 3) 5.000000 T( 4) 3.000000 T( 5) 2.000000 T( 6) 2.000000 T( 7) 3.000000 T( 8) 4.000000 T( 9) 2.000000 X( 1) 0.000000 X( 2) 0.000000 X( 3) 6.000000 X( 4) 6.000000 X( 5) 11.00000 X( 6) 13.00000 X( 7) 15.00000 X( 8) 18.000

13、00 X( 9) 22.00000 Y( 1) 0.000000 Y( 2) 0.000000 Y( 3) 6.000000 Y( 4) 15.00000 Y( 5) 11.00000 Y( 6) 13.00000 Y( 7) 15.00000 Y( 8) 18.00000 Y( 9) 22.00000 S( 1) 0.000000 S( 2) 0.000000 S( 3) 0.000000 S( 4) 9.000000 S( 5) 0.000000 S( 6) 0.000000 S( 7) 0.000000 S( 8) 0.000000 S( 9) 0.000000 Row Slack or

14、 Surplus 1 0.000000 2 0.000000 3 0.000000 4 0.000000 5 0.000000 6 0.000000 7 0.000000 8 0.000000 9 0.000000 10 0.000000 11 0.000000 12 0.000000 13 0.000000 14 0.000000 15 0.000000 16 0.000000 17 0.000000 18 0.000000 19 0.000000 20 0.000000 21 0.000000 22 0.000000 23 0.000000 24 0.000000 25 0.000000

15、26 0.000000 27 0.000000 28 0.000000附件五：sets:events/1.8/:x;operate(events,events)/1 2,1 3,1 5,2 4,3 7,4 5,5 6,6 7,7 8/:t,ts,c,h;endsetsdata:t=6,5,0,3,2,2,3,4,2;ts=4,3,0,1,1,1,1,2,2;c=800,600,0,300,600,400,300,200,200;d=17;enddatamin=sum(operate:c*h);for(operate(i,j):x(j)-x(i)+ts(i,j)>=t(i,j);n=siz

16、e(events);x(n)-x(1)<=d;for(operate:bnd(0,h,t-ts);for(operate:h<=t-ts);end附件六：Global optimal solution found. Objective value: 0.000000 Infeasibilities: 0.000000 Total solver iterations: 0 Variable Value Reduced Cost D 17.00000 0.000000 N 8.000000 0.000000 X( 1) 0.000000 0.000000 X( 2) 2.000000

17、0.000000 X( 3) 2.000000 0.000000 X( 4) 4.000000 0.000000 X( 5) 5.000000 0.000000 X( 6) 7.000000 0.000000 X( 7) 17.00000 0.000000 X( 8) 17.00000 0.000000 T( 1, 2) 6.000000 0.000000 T( 1, 3) 5.000000 0.000000 T( 1, 5) 0.000000 0.000000 T( 2, 4) 3.000000 0.000000 T( 3, 7) 2.000000 0.000000 T( 4, 5) 2.0

18、00000 0.000000 T( 5, 6) 3.000000 0.000000 T( 6, 7) 4.000000 0.000000 T( 7, 8) 2.000000 0.000000 TS( 1, 2) 4.000000 0.000000 TS( 1, 3) 3.000000 0.000000 TS( 1, 5) 0.000000 0.000000 TS( 2, 4) 1.000000 0.000000 TS( 3, 7) 1.000000 0.000000 TS( 4, 5) 1.000000 0.000000 TS( 5, 6) 1.000000 0.000000 TS( 6, 7

19、) 2.000000 0.000000 TS( 7, 8) 2.000000 0.000000 C( 1, 2) 800.0000 0.000000 C( 1, 3) 600.0000 0.000000 C( 1, 5) 0.000000 0.000000 C( 2, 4) 300.0000 0.000000 C( 3, 7) 600.0000 0.000000 C( 4, 5) 400.0000 0.000000 C( 5, 6) 300.0000 0.000000 C( 6, 7) 200.0000 0.000000 C( 7, 8) 200.0000 0.000000 H( 1, 2)

20、0.000000 800.0000 H( 1, 3) 0.000000 600.0000 H( 1, 5) 0.000000 0.000000 H( 2, 4) 0.000000 300.0000 H( 3, 7) 0.000000 600.0000 H( 4, 5) 0.000000 400.0000 H( 5, 6) 0.000000 300.0000 H( 6, 7) 0.000000 200.0000 H( 7, 8) 0.000000 200.0000 Row Slack or Surplus Dual Price 1 0.000000 -1.000000 2 0.000000 0.

21、000000 3 0.000000 0.000000 4 5.000000 0.000000 5 0.000000 0.000000 6 14.00000 0.000000 7 0.000000 0.000000 8 0.000000 0.000000 9 8.000000 0.000000 10 0.000000 0.000000 11 0.000000 0.000000 12 2.000000 0.000000 13 2.000000 0.000000 14 0.000000 0.000000 15 2.000000 0.000000 16 1.000000 0.000000 17 1.0

22、00000 0.000000 18 2.000000 0.000000 19 2.000000 0.000000 20 0.000000 0.000000 21 0.000000 0.000000第二十六章 1 問題重述通過表49中1999年中國省、自治區(qū)的城市規(guī)模結(jié)構(gòu)特征的一些數(shù)據(jù)，利用聚類分析的方法將這些省、自治區(qū)來進(jìn)行分類。 問題分析我們要用數(shù)量化的方法描述事物之間的相似程度來對(duì)事物進(jìn)行分類。在數(shù)據(jù)標(biāo)準(zhǔn)化之后，利用歐式距離計(jì)算27個(gè)樣本點(diǎn)兩兩之間的距離，利用最短距離法來測(cè)量類與類之間的距離。最后畫出聚類圖然后按照要求進(jìn)行分類。 模型假設(shè)1、 每個(gè)省、自治區(qū)的規(guī)模不會(huì)變化。 符號(hào)說明 模型建立1、 數(shù)據(jù)標(biāo)準(zhǔn)化： ；2、 構(gòu)造距離矩陣來計(jì)算27個(gè)樣本點(diǎn)兩兩之間的距離，利用歐幾里得得距離：用最短距離法來測(cè)量類之間的距離：；3、 構(gòu)造27個(gè)類，每一類只包含一個(gè)樣本點(diǎn)，每一類平臺(tái)高度為零；4、 合并距離最近的兩類為一新類，并以這兩類距離值作為聚類圖的平臺(tái)高度；5、 若類的個(gè)數(shù)為1，進(jìn)入步驟6，若類數(shù)不為1，則回到步驟4；6、 繪制聚類圖，根據(jù)需要決定類的個(gè)數(shù)和種類。 模型求解 模型評(píng)價(jià)與改進(jìn)參考文獻(xiàn)編號(hào) 作者，書名，出版地：出版社，出版年。編號(hào) 作者，論文名，雜志名，卷期號(hào)：起止頁碼，出版年。編號(hào) 作者，資源標(biāo)題，網(wǎng)址