運籌學實驗指導書.doc

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