最新運籌學(xué)案例項目報告

1、精品文檔工商管理中的運籌學(xué)問題一建模及求解項目報告摘 要：本項目報告主要研究內(nèi)容為工商管理中的一般線性規(guī)劃問題建模；運輸問題建模；目標規(guī)劃問題建模；整數(shù)規(guī)劃問題建模；網(wǎng)絡(luò)圖繪制，以及其管理運籌學(xué)軟件求解及分析。主要圍繞幾個不同類型的 實例來進行建模，并詳細分析其解題方法來深入研究這些運籌學(xué)問題。前言：本次項目報告的目的是為了幫助我們順利的完成對運籌學(xué)課程內(nèi)容的學(xué)習(xí)，能夠熟練地運用運籌學(xué)的知識對生活中遇到的問題進行建模以及求解。在全書范圍內(nèi)選取五個建模的主要問題：一般線性規(guī)劃問題建模；運輸問題建模；目標規(guī)劃問題 建模；整數(shù)規(guī)劃問題建模；網(wǎng)絡(luò)圖繪制來進行調(diào)查建模練習(xí)。在實驗中，我們首先自己 對于問

2、題進行建模處理，之后主要利用管理運籌學(xué)軟件進行問題求解并對結(jié)果進行分 析。通過完成這些實驗，我們達到了預(yù)期的結(jié)果，對于運籌學(xué)的建模過程及求解有了一 個更深刻的理解，既鞏固了之前學(xué)習(xí)的理論知識，又對于實際應(yīng)用有了一個全面的理解， 為以后的進一步學(xué)習(xí)和實際應(yīng)用打下了基礎(chǔ)。1 .工商管理中的一般線性規(guī)劃問題建模與管理運籌學(xué)軟件求解及分析研究內(nèi)容：在生產(chǎn)或經(jīng)營等管理工作中，需要經(jīng)常進行計劃或規(guī)劃。需要做到：在 現(xiàn)有各項資源條件的限制下，如何確定方案，使預(yù)期目標達到最優(yōu)：或為了達到預(yù)期目 標，確定使資源消耗為最少的方案。通過線性規(guī)劃問題的計算機軟件這一工具去求解線 性規(guī)劃問題及其靈敏度分析。現(xiàn)在我們來研

3、究線性規(guī)劃在工商管理中的應(yīng)用，解決工商 管理中的實際問題。1.1 項目過程1.1.1 一般線性規(guī)劃實際問題的描述：美佳工廠要用三種原料 1,2,3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲，乙，丙，已知產(chǎn)品的規(guī)格要求.產(chǎn)品的單價.每天能供應(yīng)的原材料數(shù)量及原材料單價，分別見表1-1和表1-2。該工廠該如何安排生產(chǎn)，使利潤收入為最大？表1-1產(chǎn)品名稱規(guī)格要求單位（元/千克）甲原材料1不少于50%原材料2不超過25%50乙原材料1不少于25%原材料2不超過50%35丙不限25原材料名稱每天最多供應(yīng)量單價（元/千克）110065210025360351.1.2實際問題求解數(shù)學(xué)模型:1.1.2.1 問題分析：我們的

4、目標是要使利潤最大，這類問題用數(shù)學(xué)語言表達，先根據(jù)問題要達到的目標選取適當(dāng)?shù)?變量，問題的目標通過用變量的函數(shù)形式表示，對問題的限制條件用有關(guān)變量的等式或者不等式表 達，當(dāng)變量連續(xù)取值且目標函數(shù)和約束條件均為線性時，建立線性規(guī)劃模型。1.1.2.2 建立模型：解：設(shè)Xij表示第i種產(chǎn)品中原材料j的含量（我們分別用產(chǎn)品1,2,3表示產(chǎn)品甲.乙.丙）。例如X23就表示乙產(chǎn)品中第 3種原材料的含量，我們的目標是要使利潤最大，利潤的計算公式如下：利潤£（銷售單價 該產(chǎn)品的數(shù)量）-t （每種原材料單價使用原料數(shù)量）。1.123目標i Sj 1函數(shù)：精品文檔精品文檔Max50 ( x 11+x

5、12+ x 13) +35 (x 21+ x22+ x 23) +25 (x 31 +x 32+x 33) -65 (x 11+x 21 + x 31) -25 ( x 12+x 22+x 32) -35 ( x 13+x 23+x 33) =-15 x 11+25x 12+15x 13-30 x 21 + 10x 22-40 x 31-10 x 33.從表 1-1 中有：x11>0.5(x11+x12+x13),x12<0.25(x11+x12+x13),x21>0.25(x21+x22+x23),x22<0.5(x21+x22+x23 ).從表 1-2 中，可知加入

6、產(chǎn)品甲. 乙 . 丙的原材料不能超過原材料的供應(yīng)量的限額，所以有：(x11+x21+x31 ) < 100,(x12+x22+x32) & 100,(x13+x23+x33) < 60,1.1.1 .4. 模型約束條件：0.5x11-0.5x12-0.5x13>0,-0.25x11+0.75x12-0.25x13< 0,0.75x21-0.25x22-0.25x23> 0,-0.5x21+0.5x22-0.5x23& 0,X11+x21+x31<100,X12+x22+x32<100,X13+x23+x33<60,xiji=1,2

7、,3;j=1,2,3)此類問題的數(shù)學(xué)模型如下：目標函數(shù)：maxz=-15x11+25x12+15x13-30x21+10x22-40x31-10x33.約束條件；0.5x11-0.5x12-0.5x13>0,-0.25x11+0.75x12-0.25x13<0,0.75x21-0.25x22-0.25x23>0,-0.5x21+0.5x22-0.5x23& 0,X11+x21+x31<100,X12+x22+x32<100,X13+x23+x33<60,xij >0 (i=1,2,3;j=1,2,3)1.1.3 模型求解所列單純性表如圖所示:C

8、j-15 25 15 -30 10 0 -40 0 -10 0 0 0 0 0 0 0CB XB bX1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x160 x10 00.5 -0.5 -o.5 0 0 0 0 0 0 1 0 0 0 0 0 00 x11 0-0.25 0.75 -0.25 0 0 0 0 0 0 0 1 0 0 0 0 00 x12 00 0 0 -0.75 0.25 0.25 0 0 0 0 0 1 0 0 0 00 x13 00 0 0 -0.5 0.5 -0.5 0 0 0 0 0 0 1 0 0 00 x14 1

9、001 0 0 1 0 0 1 0 0 0 0 0 0 1 0 00 x15 1000 1 0 0 1 0 0 1 0 0 0 0 0 0 1 00 x16 600 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1制螳R：n驍口14囂1819EIDIII1121131 *KisiiiztSB二6-3010*100000瞬醐0 5-C.5Q0D00010000御電-0 260用-0.300000001Q0C械鞘3U00。毒口疆00000100 v運用線性規(guī)劃軟件輸入數(shù)據(jù)得解為 x11=100, x12=50,x13=50,其余的xij=0,也就是說每天只 生產(chǎn)甲產(chǎn)品200千克，分別需要

10、1原料100千克，2原料50千克，3原料50千克可使利潤收入為最 大。1.1.4 結(jié)果分析：線性規(guī)劃建模是運籌學(xué)中應(yīng)用最為廣泛的一個分支，也是進行后續(xù)學(xué)習(xí)的知識基礎(chǔ)，我們應(yīng)當(dāng)具備建模思想以及會進行基礎(chǔ)的計算運用。2.運輸問題建模與管理運籌學(xué)軟件求解及分析研究內(nèi)容：在社會生產(chǎn)和消費過程中，離不開人員、物資、資金和信息的合理組織和流動。 隨著社會經(jīng)濟的快速發(fā)展，運輸變得越來越復(fù)雜，運輸量有時非常巨大，科學(xué)組織運輸可有效降低 物流活動的成本，及時實現(xiàn)需要的物品空間位置的變動，以有效提升其空間價值。在實際運用過程 中，因為數(shù)據(jù)比較復(fù)雜，而且需要考慮的方面較多，單純形法運算太過復(fù)雜，故一般采用運輸問題

11、獨特的運算方法：表上作業(yè)法來解決實際生活中的各種產(chǎn)銷平衡或產(chǎn)銷不平衡的運輸問題。2.1、 項目過程2.1.1、 運輸問題實際問題的描述有三個煤礦 A1、A2和 A3,它們需要供應(yīng)給 B1、B2、B3和B4四個地區(qū)，各煤礦運往四個地區(qū)的單 位運價、三個煤礦的產(chǎn)量情況以及四個地區(qū)的需求量見下表。問如何才能使總運價最低？B1BB3B4產(chǎn)量A1318211620< ai<80A1415181250A317121123a3>30需求量307050202.1.2、 實際問題求解2.1.2.1 、解題思路總思路：設(shè)法將其轉(zhuǎn)化為標準型解：由上表可知，四個地區(qū)總需求量為170萬噸，最低產(chǎn)量為1

12、10萬噸，最高產(chǎn)量無限制，但在產(chǎn)銷平衡的條件下，a3最高取120萬噸。這時最高產(chǎn)量為 230萬噸。它大于總需求量，而標準型為產(chǎn) 量=銷量。這時應(yīng)增設(shè)一個虛銷點B5,其需求量為60萬噸。但這個銷點只能儲存可有可無的最高產(chǎn)量部分，從而也應(yīng)將產(chǎn)量分為兩個部分，可以運往 B5的，和不可以運往 B5的。因為B5實際不存在，所以運往 B5的單位運價為0,另一部分不可以運往 B5,因而將這部分 煤礦運往B5的單位運價取為充分大的正數(shù)M基于上述分析，將表格轉(zhuǎn)換為下表。BiB3B5產(chǎn)量A13182116M2014151812M50A17121123M30求量3

13、0705020602302.1.2.2 、建立數(shù)學(xué)模型解：設(shè)xij為從第i個產(chǎn)地運往地第j個銷地的產(chǎn)品數(shù)量minz=13x11+18x12+21x13+16x14+100x15+13x21+18x22+21x23+16x24+14x31+15x32+18x33+12x34+100x35+17x41+12x42+11x43+23x44+100x45+17x51+12x52+11x53+23x54x11+x12+x13+x14+x15=20 fx21+x22+x23+x24+x25=60x31+x32+x33+x34+x35=50 Jx41+x42+x43+x44+x45=30x51+x52+x5

14、3+x54+x55=70s.t .x11+x21+x31+x41+x51=30x12+x22+x32+x42+x52=70x13+x23+x33+x43+x53=50x14+x24+x34+x44+x54=20x15+x25+x35+x45+x55=60x ij >0(i=1,2,3,4,5;j=1,2,3,4,5)2.1.2.3軟件求解噌回陋地 I I I ¥前4后 fflu 珀* 關(guān)于 電£產(chǎn)葩個熟fi'惻個匏5 二|目標函冢工 臉京鏟臉：工*也恚中feA “盧世3忍的m剪時:i ：MRIR?的同跖廣生AL1316fLB1DD2DA213IIE1D9口幅1

15、4W用12【叩5 3IlfIEUi】叩X 麗S7121£3i胭口口?0如1«物2.2 、過程分析2.2.1 、解讀題目：書上第二節(jié)所講的運輸問題的算法，是以產(chǎn)銷平衡為前提的。在本題中，明顯產(chǎn)銷不平衡，為了能使用表上作業(yè)法求解，首先要做的就是將其化為產(chǎn)銷平衡問題。2.2.2 建立模型：建模要建立在化為產(chǎn)銷平衡之后的表格的基礎(chǔ)上。2.2.3 、軟件求解：軟件求解時，輸入的是加入了虛銷地之后的數(shù)學(xué)模型，因此需要賦予M一個確定的值，但M取何值對于最終結(jié)果并無影響。2.2.4 、確定答案：根據(jù)軟件計算結(jié)果確定最佳運輸方案。3 .目標規(guī)劃問題建模與管理運籌學(xué)軟件求解及分析研究內(nèi)容：在實

16、際問題中，線性規(guī)劃與其他任何決策工具一樣，并不是完美無缺的。首先，一個計劃問題需要滿足多方面的要求，也就是說，這實際上是一個多目標問題，而線性規(guī)劃只適用于單目標問題；其次，線性規(guī)劃要求約束條件彼此相容，實際問題有時不能滿足這樣的要求；最后，有時決策者需要的并不是嚴格意義上的最優(yōu)解，而是可以幫助做出最優(yōu)計劃的參考性計劃甚至多個計劃。這是， 目標規(guī)劃的優(yōu)越性就顯現(xiàn)出來了，它既承認約束條件的沖突性，又能在最終決策時不強調(diào)絕對意義上的最優(yōu)性。3.1 項目過程3.1.1 目標規(guī)劃問題實際問題的描述某工廠生產(chǎn)兩種產(chǎn)品：桌子和椅子。經(jīng)測算，每生產(chǎn)一張桌子要在車間A加工1小時、在車間C加工3小時；每生產(chǎn)一把椅

17、子要在車間 B和車間C各加工2小時。而車間 A每周可用于生產(chǎn)這兩種新產(chǎn)品的時間為40小時，車間B為120小時，車間C為120小時。每張桌子利潤為30 元，每把椅子利潤為50 元。目前， 工廠領(lǐng)導(dǎo)根據(jù)市場的具體情況，對下周的生產(chǎn)計劃的制定又提出了新的要求。P1 ：根據(jù)市場需求的變化情況，椅子的銷售量有明顯下降的趨勢，希望椅子的產(chǎn)量不要超過桌子產(chǎn)量的2 倍。P2 :由于車間C有新產(chǎn)品生產(chǎn)的臨時任務(wù)，因此希望該車間節(jié)省出40個小時工時用于新產(chǎn)品的生產(chǎn)。P3 ：在此情況下，應(yīng)盡可能達到并超過每周總利潤3000元。精品文檔精品文檔請制定新的最優(yōu)化生產(chǎn)方案。3.1.2實際問題求解3.1.2.1建立模型設(shè)：

18、生產(chǎn)桌子xi張，椅子X2把，目標函數(shù)如下:minPidi -,P2d2 +,P3d3 -約束條件如下:i<402X2< 120s.t 2xi-x2+di - d i=03xi+2x2+d2 -d 2二16030xi+50X2+d3-d 3 +=30003.1.2.2模型求解目ism忖開不于Z3決策度里力數(shù)目標豹束千茹保存解決3£優(yōu)先州救 端對約束葉敕優(yōu)物.他差食里斯-&-J3-43 +11-1aaaa£QU1TQ> 3Q0003重肺希人約束條件II 1-1231-31*d2*i3-精品文檔精品文檔Result解相差值*5ML作科*卓幻40,0000

19、.000點0 0001.000J1-0.0000.000出+60,0000.000J3-40. 000Q. 000J2+O.OODd. ooaJ3-180cL OOOD.CX招*Q.OOD. ODO目標醴值為："80.000目標跚值為：40. OOO變里跑卓才*津二汽*40.0000 000 Q.000 eo. ooa 40. ODO O.OOD 1800. OOO O.OOD倡差值0.000IB+1S0. ooao. 0000. DOO0. ODO 口.000. ODOstep3精品文檔目標跟I值為；LMO. 000變量相差值*京*XI40. ODDQ.QOO120. 000lE+

20、ie41-0 Q000 ooo4 +SO OOO0.000d2-40.0000.000涯+0. 0000 oood3-1600.0000. ooo忒3*O. 0000.000精品文檔精品文檔因此根據(jù)目標規(guī)劃軟件，滿意解為：x1=40x2=0因此，最優(yōu)生產(chǎn)方案為生產(chǎn)桌子40 張，不生產(chǎn)椅子。3.2 過程分析3.2.1 解讀題目 ：多個目標函數(shù)，且約束條件具有優(yōu)先級，因此該問題應(yīng)經(jīng)不是簡單的線性規(guī)劃問題，而是目標規(guī)劃問題。3.2.2 建模：3.2.2.1 確定變量：由于該題是目標規(guī)劃問題，因此此時應(yīng)引入偏差變量d+,d- 。3.2.2.2 確定目標函數(shù)：因為為目標規(guī)劃問題，所以目標函數(shù)只能極小化。

21、同時約束條件優(yōu)先級題目已經(jīng)給出，因此優(yōu)先因子P1 、 P2 、 P3 已確定。同時因為椅子產(chǎn)量不超過桌子兩倍，所以minP1d1-;因為車間C盡可能節(jié)省出4小時，因此minP2d2+;因 為利潤盡可能達到并超過3000 元，所以minP3d3- 。3.2.2.3 確定約束條件：車間A可用工時為4小時、車間B為120小時為絕對約束；而 椅子產(chǎn)量不超過桌子兩倍、車間 C盡可能節(jié)省出40小時即可用160小時、總利潤盡可 能達到 3000 元為目標約束。3.2.3 模型求解，主要借助軟件求解。3.2.4 根據(jù)軟件得出的結(jié)果確定滿意解。4 .整數(shù)規(guī)劃問題建模與管理運籌學(xué)軟件求解及分析4.1 研究內(nèi)容：整

22、數(shù)規(guī)劃是生活中一種特殊的問題，他的全部或一部分決策變量只能取 整數(shù)熟練掌握整數(shù)規(guī)劃問題的各種不同形式，靈活的使用不同的方法進行建模求解非 常有必要。純整數(shù)規(guī)劃問題使用割平面法或分支定界法求解，0-1型整數(shù)規(guī)劃問題使用隱枚舉法求解，而其中特殊的指派問題使用匈牙利解法求解，非標準的指派問題需要化 成標準問題再求解。4.2 問題描述運籌學(xué)三級項目中，9B321宿舍六名同學(xué)有五個模塊需要進行建模處理，現(xiàn)準備每人選 做一套，每人做且只做一套，每人完成各套題目的困難指數(shù)如下表：（困難程度分為五 個檔次，其中1最低）一般性規(guī)劃問運輸問題目標規(guī)劃問題整數(shù)規(guī)劃問題網(wǎng)絡(luò)圖繪制同學(xué)A41325同學(xué)B31224同學(xué)C

23、42335同學(xué)D22413同學(xué)E31434同學(xué)F42234確定使總困難程度最低的指派方案，最低困難指數(shù)是多少？4.3 求解過程4.3.1 建立數(shù)學(xué)模型minz=4x11+x12+3x13+4x14+5x15+0x16+3x21+x22+2x23+2x24+4x25+0x26+4x31+2x32+ 3x33+3x34+5x35+0x36+2x41+2x42+4x43+x44+3x45+0x46+3x51+x52+4x53+3x54+4x55+ 0x56+4x61+2x62+2x63+3x64+4x65+0x66S6i=iXj=1(j=1,26)W6j=iXj=1(i=1,26)Xj =0 或 1

24、(i,j=1,26)精品文檔4.2.2將數(shù)據(jù)輸入運籌學(xué)解題軟件中得:4.2.3由運籌學(xué)解題軟件得出結(jié)果為:4.4 過程分析:4.4.1 解讀題目：本問題屬于指派問題中的特殊問題：指派問題，而且由于有六個人五個問題需要解決， 每人只能解決一件事情，所以是非標準的指派問題類型，首先虛擬的增加一件事情，它 的其他指數(shù)均為0,之后進行數(shù)學(xué)建模。4.4.2 確定目標函數(shù)以及決策變量，建立數(shù)學(xué)模型4.4.3 確定解題方法，根據(jù)課本知識，指派問題一般使用匈牙利解法進行解答4.4.4 求出結(jié)果，進行結(jié)果分析，看是否符合現(xiàn)實情況4.5 結(jié)果分析根據(jù)解題結(jié)果，最優(yōu)指派方案應(yīng)該是讓 A同學(xué)做運輸問題，B同學(xué)做網(wǎng)絡(luò)圖

25、繪制問題, D同學(xué)做整數(shù)規(guī)劃問題，E同學(xué)做一般性規(guī)劃問題，F(xiàn)同學(xué)做目標規(guī)劃問題。此時的最小困難指數(shù)為1+4+1+3+2=115、網(wǎng)絡(luò)圖繪制與管理運籌學(xué)軟件求解及分析研究內(nèi)容在許多龐大而復(fù)雜的科研和工程項目，這些項目常常需要運用大量的人力、物力和財力，因此如何 合理而有效地對這些項目進行組織，在有限資源下以最短的時間和最低的成本費用下完成整個項目 就成為一個突出的問題。5.1 問題分析周末，某家庭主婦將準備一個小型家庭宴會，宴會需要完成的活動有：制定菜單、原料采購、餐具 準備、甜點準備、原料清洗、烹飪、桌持布置、宴會開始。為使宴會能按時進行，宴會的主人至多 需要提前多少時間開始準備宴會流程。求出此宴會的關(guān)鍵路線，確保宴會進行。5.2 建立模型；求最晚完成時間，即求其關(guān)鍵路線，工作時間由問題資料可知，為確定型工作工作內(nèi)容緊前工作工時（分鐘）A菜單定制30B原料采購A60C餐具準備A45D甜點