運籌學(xué)實驗指導(dǎo)書.doc

實驗一、線性規(guī)劃綜合性實驗一、實驗?zāi)康呐c要求：使學(xué)生掌握線性規(guī)劃建模的方法以及至少掌握一種線性規(guī)劃軟件的使用，提高學(xué)生應(yīng)用線性規(guī)劃方法解決實際問題的實踐動手能力。通過實驗，使學(xué)生更深入、直觀地理解和掌握線性規(guī)劃的基本概念及基本理論和方法。要求學(xué)生能對一般的線性規(guī)劃問題建立正確的線性規(guī)劃數(shù)學(xué)模型，掌握運籌學(xué)軟件包線性規(guī)劃模塊的操作方法與步驟，能對求解結(jié)果進(jìn)行簡單的應(yīng)用分析。二、實驗內(nèi)容與步驟：1.選擇合適的線性規(guī)劃問題學(xué)生可根據(jù)自己的建模能力，從本實驗指導(dǎo)書提供的參考選題中或從其它途徑選擇合適的線性規(guī)劃問題。2.建立線性規(guī)劃數(shù)學(xué)模型學(xué)生針對所選的線性規(guī)劃問題，運用線性規(guī)劃建模的方法，建立恰當(dāng)?shù)木€性規(guī)劃數(shù)學(xué)模型。3.用運籌學(xué)軟件求解線性規(guī)劃數(shù)學(xué)模型學(xué)生應(yīng)用運籌學(xué)軟件包線性規(guī)劃模塊對已建好的線性規(guī)劃數(shù)學(xué)模型進(jìn)行求解。4.對求解結(jié)果進(jìn)行應(yīng)用分析學(xué)生對求解結(jié)果進(jìn)行簡單的應(yīng)用分析。三、實驗例題：(一)線性規(guī)劃問題某集團(tuán)摩托車公司產(chǎn)品年度生產(chǎn)計劃的優(yōu)化研究1)問題的提出某集團(tuán)摩托車公司是生產(chǎn)各種類型摩托車的專業(yè)廠家，有30多年從事摩托車生產(chǎn)的豐富經(jīng)驗。近年來，隨著國內(nèi)摩托車行業(yè)的發(fā)展，市場競爭日趨激烈，該集團(tuán)原有的優(yōu)勢逐漸喪失，摩托車公司的生存和發(fā)展面臨嚴(yán)峻的挑戰(zhàn)。為此公司決策層決心順應(yīng)市場，狠抓管理，挖潛創(chuàng)新，從市場調(diào)查入手，緊密結(jié)合公司實際，運用科學(xué)方法對其進(jìn)行優(yōu)化組合，制定出1999年度總體經(jīng)濟(jì)效益最優(yōu)的生產(chǎn)計劃方案。2)市場調(diào)查與生產(chǎn)狀況分析1998年，受東南亞金融風(fēng)暴的影響，國內(nèi)摩托車市場出現(xiàn)疲軟，供給遠(yuǎn)大于需求，該集團(tuán)的摩托車生產(chǎn)經(jīng)營也出現(xiàn)開工不足、庫存增加和資金周轉(zhuǎn)困難等問題。該集團(tuán)共有三個專業(yè)廠，分別生產(chǎn)輕便摩托車、普通兩輪車和三輪摩托車三大系列產(chǎn)品。在市場調(diào)查的基礎(chǔ)上，從企業(yè)實際出發(fā)普遍下調(diào)整車出廠價和目標(biāo)利潤率，有關(guān)數(shù)據(jù)如下表1產(chǎn)品系列輕便摩托車普通兩輪車三輪摩托車型號M1M2M3M4M5M6M7M8M9出廠價1800元2100元2300元3800元4800元6500元8200元8800元9200元目標(biāo)利潤率6%7%10%5%6%8%6%6%6%最大生產(chǎn)能力50000輛60000輛10000輛1999年該集團(tuán)可供摩托車生產(chǎn)的流動資金總量為4000萬元，年周轉(zhuǎn)次數(shù)為5次，生產(chǎn)各種型號摩托車資金占用情況如下表2型號M1M2M3M4M5M6M7M8M9占用資金(元/輛)152017001850320041005400600074508600由于發(fā)動機(jī)改型生產(chǎn)的限制，改型車M3和M6兩種車1999年的生產(chǎn)量預(yù)測數(shù)分別為20000輛和22000輛。經(jīng)預(yù)測三種系列摩托車1999年產(chǎn)銷率及倉儲面積占用情況如下表3產(chǎn)品系列輕便摩托車普通兩輪車三輪摩托車產(chǎn)銷率97%97%92%單車占用面積1個倉儲單位1.5個倉儲單位3個倉儲單位公司1999年可提供的最大倉儲能力為3000個倉儲單位，庫存產(chǎn)品最大允許占用生產(chǎn)資金為1600萬元。根據(jù)以上情況，該公司應(yīng)如何制定1999年度總體經(jīng)濟(jì)效益最優(yōu)的生產(chǎn)計劃方案？(二)線性規(guī)劃建模設(shè)Xj表示生產(chǎn)Mj型摩托車的數(shù)量(j=1,2,9),則總利潤最大的摩托車產(chǎn)品生產(chǎn)計劃數(shù)學(xué)模型為：MaxZ=0.180.06X1+0.210.07X2+0.230.1X3+0.380.05X4+0.480.06X5+0.650.08X6+0.820.06X7+0.880.06X8+0.920.06X9 =0.0108X1+0.0147X2+0.023X3+0.019X4+0.0288X5+0.052X6+0.0492X7+0.0528X8+0.0552X9滿足 X1+X2+X350000 (1) X4+X5+X660000 (2) X7+X8+X910000 (3) 0.152X1+0.17X2+0.185X3+0.32X4+0.41X5+0.54X6+0.6X7+0.745X8+0.86X940005 (4) X320000 (5) X622000 (6) 0.03(X1+X2+X3)+0.031.5(X4+X5+X6)+0.083(X7+X8+X9)3000 (7) 0.00456X1+0.0051X2+0.00555X3+0.0096X4+0.0123X5+0.0162X6+0.048X7+0.0596X8+0.0688X91600 (8) Xj0(j=1,2,3,49)模型說明：約束(1)、(2)、(3)分別表示三種系列摩托車的最大生產(chǎn)能力限制；約束(4)表示摩托車的生產(chǎn)受流動資金的限制；約束(5)和(6)表示M3和M6兩種車產(chǎn)量受發(fā)動機(jī)供應(yīng)量限制；約束 (7)表示未銷售的產(chǎn)量受庫存能力的限制；約束(8)表示未銷售產(chǎn)品占用資金的限制。(三)模型求解由管理運籌學(xué)軟件包中可知最優(yōu)解為X=(0，26000，20000，0，0，22000，0，0，0)T,最優(yōu)值Z=1986.2萬元。說明一下，摩托車生產(chǎn)數(shù)量是整數(shù)，應(yīng)該用整數(shù)規(guī)劃來求解，但由于摩托車生產(chǎn)數(shù)量較大，故采用線性規(guī)劃求解，四舍五入取整，誤差很小。(四)結(jié)果分析1)根據(jù)計算結(jié)果，能夠使年利潤達(dá)到最大化的產(chǎn)品生產(chǎn)計劃是：M2型車生產(chǎn)26000輛，M3型車生產(chǎn)20000輛，M6型車生產(chǎn)22000輛，共計68000輛。目標(biāo)利潤為1986.2萬元。2)由以上求解結(jié)果可知，三種系列的摩托車生產(chǎn)能力均有富余，尤其是三輪摩托車未安排生產(chǎn)，生產(chǎn)能力完全剩余；摩托車生產(chǎn)的流動資金完全用完，M3和M6兩種車型的發(fā)動機(jī)也完全用完；庫存容量和庫存車占用的生產(chǎn)資金額度也有富余。由影子價格也可看出，流動資金、M3和M6兩種車型的發(fā)動機(jī)是希缺的，若增加這三種資源，可提高總利潤，并且增加流動資金可使總利潤提高最快。因此上述產(chǎn)品生產(chǎn)計劃在實踐中應(yīng)作出適當(dāng)調(diào)整。(五)方案調(diào)整分析1)增加流動資金一是流動資金總量不變，加速資金周轉(zhuǎn)，比如年周轉(zhuǎn)次數(shù)由5次增至6次，其它條件不變，求解二是在資金周轉(zhuǎn)加速的基礎(chǔ)上，增加流動資金總量，比如增加1000萬元，由流動資金的影子價格可看出，總利潤有更大提高，求解2)增加M3和M6兩種車型的發(fā)動機(jī)若M3和M6兩種車型的發(fā)動機(jī)各增加5000臺，在上述條件基礎(chǔ)上，求解3)合理安排生產(chǎn)品種為保持公司各種系列摩托車有一定的市場占有率，需對上述結(jié)果作出修改，要保證三輪摩托車達(dá)到一個最低生產(chǎn)量。比如M9型車生產(chǎn)不少于2000輛，即增加約束X92000，求解4)適當(dāng)增加庫存能力為保證三輪摩托車生產(chǎn)線的開動，公司整個摩托車的產(chǎn)量和目標(biāo)利潤受到較大影響，由于三輪摩托車占用的庫存量較大，庫存容量資源影子價格很高，可適當(dāng)增加庫存容量，以提高目標(biāo)利潤。比如增加庫存容量500個單位，求解四、實驗參考選題：1.某工廠生產(chǎn)A、B兩種產(chǎn)品，均需經(jīng)過兩道工序，每生產(chǎn)一噸產(chǎn)品A需要經(jīng)第一道工序加工2小時，第二道工序加工3小時；每生產(chǎn)一噸產(chǎn)品B需要經(jīng)第一道工序加工3小時，第二道工序加工4小時。可供利用的第一道工序為12小時，第二道工序為24小時。 生產(chǎn)產(chǎn)品B的同時產(chǎn)出副產(chǎn)品C，每生產(chǎn)一噸產(chǎn)品B，可同時得到2噸產(chǎn)品C而毋需外加任何費用；副產(chǎn)品C一部分可以盈利，剩下的只能報廢。出售產(chǎn)品A每噸能盈利400元、產(chǎn)品B每噸能盈利1000元，每銷售一噸副產(chǎn)品C能盈利300元，而剩余要報廢的則每噸損失200元。經(jīng)市場預(yù)測，在計劃期內(nèi)產(chǎn)品C最大銷量為5噸。根據(jù)以上資料該工廠應(yīng)如何制定生產(chǎn)方案，使工廠總的利潤最大。2.某公司在5年內(nèi)考慮下列投資，已知：項目A可從第一年至第四年的年初投資，并于次年末收回本利共115%；項目B在第三年的年初投資，到第五年的年末收回本利135%,但規(guī)定投資額不能超過4萬元；項目C在第二年的年初投資，到第五年的年末收回本利145%,但規(guī)定投資額不能超過3萬元；項目D每年年初購買債券，年底歸還，利息是0.06。公司現(xiàn)有資金10萬元，問如何投資，才能使第五年年末擁有的資金最多？3.某企業(yè)在今后三年內(nèi)有四種投資機(jī)會。第一種是在三年內(nèi)每年年初投資，年底可回收本利和120；第二種是在第一年年初投資，第二年年底可回收本利和150，但該項投資不得超過2萬元；第三種是在第二年年初投資，第三年年底回收本利和160，但該項投資不得超過1.5萬元；第四種是在第三年年初投資，該年年底可回收本利和140，該項投資不得超過1萬元。現(xiàn)在該企業(yè)準(zhǔn)備拿出3萬元資金，問如何制訂投資計劃，使到第三年年末本利和最大？4.某公司有鋼材、鋁材、銅材1200噸，800噸和650噸，擬調(diào)往物資緊張的地區(qū)甲、乙、丙。已知甲、乙、丙對上述物資的總需求為：900噸，800噸和1000噸，各種物資在各地銷售每噸的獲利如下表所示。問該公司應(yīng)如何安排調(diào)運計劃，才能獲利最大？ 物資獲利地區(qū)甲乙丙鋼材260210180鋁材300250400銅材400550350 5.某工廠生產(chǎn)A，B，C三種產(chǎn)品，現(xiàn)根據(jù)訂貨合同及生產(chǎn)狀況制定5月份的生產(chǎn)計劃。已知合同甲為：A產(chǎn)品1000件，單件價格為500元，違約金為100元/件；合同乙為：B產(chǎn)品500件，單件價格為400元，違約金為120元/件；合同丙為：B產(chǎn)品600件，單件價格為420元，違約金為130元/件；C產(chǎn)品600件，單件價格為400元，違約金為90元/件；有關(guān)各產(chǎn)品生產(chǎn)過程所需工時以及原材料的情況如下表，問該工廠如何安排生產(chǎn)計劃才能使利潤最大？工序1工序2工序3原材料1原材料其它成本/件產(chǎn)品A2323410產(chǎn)品B1132310產(chǎn)品C2124210總工時(原材料)460040006000100008000工時原材料單位成本(元)1510102040 實驗二、對偶理論和靈敏度分析實驗一、實驗?zāi)康呐c要求：進(jìn)一步熟悉對偶規(guī)劃及靈敏度分析的有關(guān)基本概念；掌握寫對偶線性規(guī)劃，靈敏度分析和參數(shù)分析的使用方法及操作步驟；理解其輸出結(jié)果。二、實驗內(nèi)容與步驟：1.選擇線性規(guī)劃模型從本實驗指導(dǎo)書提供的參考選題中或從其它途徑選擇合適的線性規(guī)劃模型。2.寫出對偶線性規(guī)劃模型3.理解靈敏度分析4.進(jìn)行參數(shù)分析三、實驗題：1已知線性規(guī)劃模型如下：MaxZ=X1+2X2+4X3+X4滿足 3X1+9X3+5X415 6X1+4X2+X3+7X430 4X1+3X3+4X420 5X1+3X2+8X3+3X440Xj0 (j=1,2,3,4)1)寫出對偶線性規(guī)劃，變量用Y表示；2)求原問題及對偶問題的最優(yōu)解；3)分別寫出價值系數(shù)Cj及右端常數(shù)bi的最大允許變化范圍；4)目標(biāo)函數(shù)系數(shù)改為C=(4，2，6，1)，同時常數(shù)改為=(20,40,20,40),求最優(yōu)解；5)刪除第四個約束同時刪除第三個變量，求最優(yōu)解；6)增加一個變量X5，系數(shù)為(C5,a15,a25,a35,a45)=(6,5,4,2,3)，求最優(yōu)解；7)目標(biāo)函數(shù)為MaxZ=(1+m)X1+(2+3m)X2+4X3+(1-m)X4,分析參數(shù)的變化區(qū)間及對應(yīng)解的關(guān)系，繪制參數(shù)與目標(biāo)值的關(guān)系圖。2. 已知線性規(guī)劃模型如下：MaxZ=4X1+2X2+3X3滿足 2X1+2X2+4X3100 3X1+X2+6X3100 3X1+X2+2X3120 Xj0 (j=1,2,3)1)寫出對偶線性規(guī)劃，變量用Y表示；2)求原問題及對偶問題的最優(yōu)解；3)分別寫出價值系數(shù)Cj及右端常數(shù)bi的最大允許變化范圍；4)目標(biāo)函數(shù)系數(shù)改為C=(5，3，6)，同時常數(shù)改為=(120,140,100),求最優(yōu)解；5)在原模型基礎(chǔ)上增加一個約束6X1+5X2+X3200，同時增加一個變量X4，系數(shù)為(C4,a14,a24,a34,a44)=(7,5,4,1,2)，求最優(yōu)解；6)在5)的模型中刪除第二個約束，求最優(yōu)解；7)原模型的右端常數(shù)改為b =(100+m，100+3m，120+m),分析參數(shù)的變化區(qū)間及對應(yīng)解的關(guān)系，繪制參數(shù)與目標(biāo)值的關(guān)系圖。3. 已知線性規(guī)劃模型如下：Max Z=X1+5X2+3X3+4X4滿足 2X1+3X2 +X3+2X4800 5X1+4X2+3X3+4X41200 3X1+4X2+5X3+3X41000 Xj0 (j=1,2,3,4)1)寫出對偶線性規(guī)劃，變量用y表示；2)求原問題及對偶問題的最優(yōu)解;3)分別寫出價值系數(shù)Cj及右端常數(shù)的最大變化范圍;4)目標(biāo)函數(shù)系數(shù)改為C=(5,4，4，5),同時右端常數(shù)改為b=(800,1200，850)，求最優(yōu)解；5) 在原模型基礎(chǔ)上增加一個約束條件4X1+4X2+2X3+2X4700,同時增加一個決策變量X5，其系數(shù)為(C5,a15,a25,a35,)=(5,2,5,3)，求最優(yōu)解；6) 在5)的模型中刪除第一個約束條件，求最優(yōu)解；7)原模型的右端常數(shù)改為b=(800+t,1200+3t,1000+t),分析參數(shù)的變化區(qū)間及對應(yīng)解的關(guān)系，繪制參數(shù)與目標(biāo)值的關(guān)系圖。實驗三、整數(shù)規(guī)劃實驗一、實驗?zāi)康呐c要求：進(jìn)一步熟悉整數(shù)線性規(guī)劃的有關(guān)基本概念；掌握運籌學(xué)軟件包求解整數(shù)線性規(guī)劃的使用方法和操作步驟；理解其輸出結(jié)果。二、實驗內(nèi)容與步驟：1.選擇整數(shù)規(guī)劃模型從本實驗指導(dǎo)書提供的參考選題中或從其它途徑選擇整數(shù)規(guī)劃模型。2.求解整數(shù)規(guī)劃模型3.理解其輸出結(jié)果三、實驗例題：1. 求解整數(shù)規(guī)劃 2. 求解整數(shù)規(guī)劃MaxZ=3X1+2X2-5X3-2X4+3X5 Max Z=X1+5X2+3X3+4X4滿足 X1+X2+X3+2X4+X54 滿足 2X1+3X2 +X3+2X4800 7X1 +3X3-4X4+3X58 5X1+4X2+3X3+4X41200 11X1-6X2+3X4-3X53 3X1+4X2+5X3+3X41000 Xj=0或1 (j=1，2，3，4，5) Xj0 (j=1,2,3,4)且為整數(shù)實驗四、分配問題和運輸問題實驗一、實驗?zāi)康呐c要求：進(jìn)一步熟悉指派問題和運輸問題的有關(guān)基本概念；掌握運籌學(xué)軟件求解指派問題和運輸問題的使用方法和操作步驟；理解其輸出結(jié)果。二、實驗內(nèi)容與步驟：1.選擇分配問題和運輸問題從本實驗指導(dǎo)書提供的參考選題中或從其它途徑選擇分配問題和運輸問題。2.求解分配問題和運輸問題3.理解其輸出結(jié)果三、實驗例題：1.分配問題某商業(yè)集團(tuán)計劃在市內(nèi)四個點投資四個專業(yè)超市，考慮的商品有電器、服裝、食品、家具及計算機(jī)5個類別。通過評估，家具超市不能放在第3個點，計算機(jī)超市不能放在第4個點，不同類別的商品投資到各點的年利潤(萬元)預(yù)測值見下表4.1。該商業(yè)集團(tuán)如何作出投資決策使年利潤最大。表4.1地點商品1234電器120300360400服裝80350420260食品150160380300家具90200180計算機(jī)2202602702.運輸問題某混凝土構(gòu)件公司有3個碎石生產(chǎn)廠，供應(yīng)4個攪拌站碎石。各碎石生產(chǎn)廠的產(chǎn)量和各攪拌站的碎石需求量以及每個碎石生產(chǎn)廠到各攪拌站的距離如下表所示，求使總運輸量最小的方案。 銷地產(chǎn)地B1B2B3B4產(chǎn)量A13276500A27523600A31546300銷量6004002002001400說明：若為產(chǎn)銷不平衡問題，事先不必化為平衡問題。3. 某公司擬將四種新產(chǎn)品配置到四個工廠生產(chǎn)，每種新產(chǎn)品只能配置到一個工廠，一個工廠只能配置一種新產(chǎn)品，四個工廠的單位產(chǎn)品成本(元/件)如下表所示，如何進(jìn)行配置才能使單件產(chǎn)品總成本最低？產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4工廠27550150230工廠36570170250工廠482552002804.人事部門欲安排四人到四個不同崗位工作，每個崗位一個人，每個人一個崗位。經(jīng)考核五人在不同崗位的成績(百分制)如下表所示，如何安排他們的工作使總成績最好，應(yīng)淘汰哪一位。工作人員人力資源物流管理市場營銷信息管理甲85927390乙95877895丙82837990丁86908088戊768592935 求下表極小化運輸問題的最優(yōu)解 銷地單位運費產(chǎn)地B1B2B3B4產(chǎn)量A1411359A2102695A3871610銷量48872427實驗五：目標(biāo)規(guī)劃問題實驗一、實驗?zāi)康呐c要求：進(jìn)一步熟悉目標(biāo)規(guī)劃問題的有關(guān)基本概念；掌握運籌學(xué)軟件求解目標(biāo)規(guī)劃問題的使用方法和操作步驟；理解其輸出結(jié)果。二、實驗內(nèi)容與步驟：1.選擇目標(biāo)規(guī)劃問題從本實驗指導(dǎo)書提供的參考選題中或從其它途徑選擇目標(biāo)規(guī)劃問題。2.求解目標(biāo)規(guī)劃問題3.理解其輸出結(jié)果三、實驗例題：1、某公司分廠用一條生產(chǎn)線生產(chǎn)兩種產(chǎn)品A和B ，每周生產(chǎn)線運行時間為60小時，生產(chǎn)一臺A產(chǎn)品需要4小時，生產(chǎn)一臺B產(chǎn)品需要6小時根據(jù)市場預(yù)測，A、B產(chǎn)品平均銷售量分別為每周9、8臺，它們銷售利潤分別為12、18萬元。在制定生產(chǎn)計劃時，經(jīng)理考慮下述4項目標(biāo)：首先，產(chǎn)量盡量不要超過市場預(yù)測的銷售量； 其次，工人加班時間盡量最少； 第三，希望總利潤盡量大； 最后，要盡可能滿足市場需求, 當(dāng)不能滿足時, 市場認(rèn)為B產(chǎn)品的重要性是A產(chǎn)品的2倍 試建立這個問題的數(shù)學(xué)模型并求解2、 電視機(jī)廠裝配25寸和21寸兩種彩電，每臺電視機(jī)需裝備時間1小時，每周裝配線計劃開動40小時，預(yù)計每周25寸彩電銷售24臺，每臺可獲利80元，每周21寸彩電銷售30臺，每臺可獲利40元。該廠目標(biāo)：1、充分利用裝配線，避免開工不足。2、允許裝配線加班，但盡量不超過10小時。3、盡量滿足市場需求。實驗六、網(wǎng)絡(luò)優(yōu)化問題實驗一、實驗?zāi)康呐c要求：進(jìn)一步熟悉最小樹和最短路，最大流問題的有關(guān)基本概念；掌握運籌學(xué)軟件求解最小樹和最短路，最大流問題的使用方法和操作步驟；理解其輸出結(jié)果。二、實驗內(nèi)容與步驟：1.選擇最小樹問題和最短路，最大流問題從本實驗指導(dǎo)書提供的參考選題中或從其它途徑選擇最小樹問題和最短路問題及最大流問題。2.求解最小樹問題和最短路，最大流問題。3.理解其輸出結(jié)果三、實驗例題：1.最小樹問題某鐵路部門擬用鐵路線將7個市鎮(zhèn)連接起來,已知修建各市鎮(zhèn)間鐵路的費用如下圖所示。這是一個賦權(quán)圖,圖中的頂點V1,V2,V3,V7表示7個市鎮(zhèn),每條邊表示可能要修建的鐵路,每個邊的權(quán)值為修建該條鐵路將要花的費用。現(xiàn)在鐵路部門需知道，應(yīng)修建哪幾條鐵路才能既可以將7個市鎮(zhèn)