蔡詩文魯林霞李強

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

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

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

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

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

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

7、2、完成任務(wù)所用的時間不超過要求完成的時間，即 3、要使產(chǎn)品額外增加的費用最少，即 即所建立的模型為 利用Lingo 11.0 編寫程序（程序見附件五），由運行結(jié)果（運行結(jié)果見附件六）可以得到所求結(jié)果。最小費用為零，都沒有縮短。問題四：VII參考文獻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ū)來進行分類。 問題分析我們要用數(shù)量化的方法描述事物之間的相似程度來對事物進行分類。在數(shù)據(jù)標準化之后，利用歐式距離計算27個樣本點兩兩之間的距離，利用最短距離法來測量類與類之間的距離。最后畫出聚類圖然后按照要求進行分類。 模型假設(shè)1、 每個省、自治區(qū)的規(guī)模不會變化。 符號說明 模型建立1、 數(shù)據(jù)標準化： ；2、 構(gòu)造距離矩陣來計算27個樣本點兩兩之間的距離，利用歐幾里得得距離：用最短距離法來測量類之間的距離：；3、 構(gòu)造27個類，每一類只包含一個樣本點，每一類平臺高度為零；4、 合并距離最近的兩類為一新類，并以這兩類距離值作為聚類圖的平臺高度；5、 若類的個數(shù)為1，進入步驟6，若類數(shù)不為1，則回到步驟4；6、 繪制聚類圖，根據(jù)需要決定類的個數(shù)和種類。 模型求解 模型評價與改進參考文獻編號 作者，書名，出版地：出版社，出版年。編號 作者，論文名，雜志名，卷期號：起止頁碼，出版年。編號 作者，資源標題，網(wǎng)址