數(shù)學(xué)模型 第六講 整數(shù)規(guī)劃模型與求解軟件2011

1、E-MAIL: 數(shù)學(xué)模型課程教學(xué)課件Copyright 2011 Dalian Jiaotong University. All rights reserved.2010-2011學(xué)年第二學(xué)期1第六講 整數(shù)規(guī)劃模型與0-1規(guī)劃 時間：2011年3月24日主講人：周大勇E-MAIL:整數(shù)規(guī)劃模型及其處理方法0-1規(guī)劃模型及其處理方法數(shù)學(xué)軟件求解上述模型分析2請各小組思考下列問題 數(shù)學(xué)規(guī)劃模型的一般形式是什么？E-mail: 常用的解決規(guī)劃模型的軟件有哪些？3規(guī)劃模型構(gòu)成及軟件處理實際問題中的優(yōu)化模型x決策變量f(x)目標(biāo)函數(shù)gi(x)0約束條件數(shù)學(xué)規(guī)劃線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃重點在模型的建立和

2、結(jié)果的分析E-mail:處理軟件LindoLingo MatlabMathematica 4設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1, x2, x3汽車廠生產(chǎn)計劃 模型建立 小型 中型 大型 現(xiàn)有量鋼材 1.5 3 5 600時間 280 250 400 60000利潤 2 3 4 線性規(guī)劃模型(LP)E-mail:5模型求解 3） 模型中增加條件：x1, x2, x3 均為整數(shù)，重新求解。 OBJECTIVE FUNCTION VALUE 1) 632.2581VARIABLE VALUE REDUCED COST X1 64.516129 0.000000 X2 167.741928 0

3、.000000 X3 0.000000 0.946237 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.731183 3) 0.000000 0.003226結(jié)果為小數(shù)，怎么辦？1）舍去小數(shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值z=629，與LP最優(yōu)值632.2581相差不大。2）試探：如取x1=65，x2=167；x1=64，x2=168等，計算函數(shù)值z，通過比較可能得到更優(yōu)的解。 但必須檢驗它們是否滿足約束條件。為什么？請寫出在Lindo軟件的源程序E-mail:6IP可用LINDO直接求解整數(shù)規(guī)劃(Integer Programmin

4、g,簡記IP)“gin 3”表示“前3個變量為整數(shù)”，等價于：gin x1gin x2gin x3 IP 的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z=632 max 2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin 3 OBJECTIVE FUNCTION VALUE 1) 632.0000VARIABLE VALUE REDUCED COST X1 64.000000 -2.000000 X2 168.000000 -3.000000 X3 0.000000 -4.000000 IP 結(jié)果輸出E-mail:7其

5、中3個子模型應(yīng)去掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：方法1：分解為8個LP子模型 汽車廠生產(chǎn)計劃-討論 若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃。x1,x2, x3=0 或 80 x1=80，x2= 150，x3=0，最優(yōu)值z=6108LINDO中對0-1變量的限定：int y1int y2int y3 方法2：引入0-1變量，化為整數(shù)規(guī)劃 M為大的正數(shù)，可取1000 OBJECTIVE FUNCTION VALUE 1) 610.0000VARIABLE VALUE REDUCED COST X1 80.000000 -2.000000 X2 150.000000

6、 -3.000000 X3 0.000000 -4.000000 Y1 1.000000 0.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000 若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃。x1=0 或 80 x2=0 或 80 x3=0 或 80最優(yōu)解同前 E-mail:9NLP雖然可用現(xiàn)成的數(shù)學(xué)軟件求解(如LINGO, MATLAB)，但是其結(jié)果常依賴于初值的選擇。 方法3：化為非線性規(guī)劃 非線性規(guī)劃（Non- Linear Programming，簡記NLP） 實踐表明，本例僅當(dāng)初值非常接近上面方法算出的最優(yōu)解時，才能得到正確的結(jié)果。 若生

7、產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃。 x1=0 或 80 x2=0 或 80 x3=0 或 80E-mail:10分派問題 接力隊選拔和選課策略若干項任務(wù)分給一些候選人來完成，每人的專長不同，完成每項任務(wù)取得的效益或需要的資源就不同，如何分派任務(wù)使獲得的總效益最大，或付出的總資源最少。若干種策略供選擇，不同的策略得到的收益或付出的成本不同，各個策略之間有相互制約關(guān)系，如何在滿足一定條件下作出決擇，使得收益最大或成本最小。E-mail:11丁的蛙泳成績退步到115”2；戊的自由泳成績進步到57”5, 組成接力隊的方案是否應(yīng)該調(diào)整？如何選拔隊員組成4100米混合泳接力隊?混合泳接力隊的選拔

8、甲乙丙丁戊蝶泳106”857”2118”110”107”4仰泳115”6106”107”8114”2111”蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”45名候選人的百米成績窮舉法：組成接力隊的方案共有5!=120種。E-mail:12目標(biāo)函數(shù)若選擇隊員i參加泳姿j 的比賽，記xij=1, 否則記xij=0 0-1規(guī)劃模型 cij(秒)隊員i 第j 種泳姿的百米成績約束條件每人最多入選泳姿之一 ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683

9、.8j=458.65359.457.262.4每種泳姿有且只有1人 E-mail:13模型求解 最優(yōu)解：x14 = x21 = x32 = x43 = 1, 其它變量為0;成績?yōu)?53.2(秒)=413”2 MIN 66.8x11+75.6x12+87x13+58.6x14 + +67.4x51+71 x52+83.8x53+62.4x54SUBJECT TO x11+x12+x13+x14 =1 x41+x42+x43+x44 =1 x11+x21+x31+x41+x51 =1 x14+x24+x34+x44+x54 =1END INT 20 輸入LINDO求解 甲乙丙丁戊蝶泳106”857

10、”2118”110”107”4仰泳115”6106”107”8114”2111”蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”4甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.E-mail:14丁蛙泳c43 =69.675.2，戊自由泳c54=62.4 57.5, 方案是否調(diào)整？ 敏感性分析？乙 蝶泳、丙 仰泳、丁 蛙泳、戊 自由泳IP規(guī)劃一般沒有與LP規(guī)劃相類似的理論，LINDO輸出的敏感性分析結(jié)果通常是沒有意義的。最優(yōu)解：x21 = x32 = x43 = x54 = 1, 成績?yōu)?17”7 c43, c54 的新數(shù)據(jù)重新輸入模型，用LINDO求

11、解 指派(Assignment)問題：每項任務(wù)有且只有一人承擔(dān)，每人只能承擔(dān)一項，效益不同，怎樣分派使總效益最大. 討論甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.原方案E-mail:15為了選修課程門數(shù)最少，應(yīng)學(xué)習(xí)哪些課程 ？ 選課策略要求至少選兩門數(shù)學(xué)課、三門運籌學(xué)課和兩門計算機課 課號課名學(xué)分所屬類別先修課要求1微積分5數(shù)學(xué)2線性代數(shù)4數(shù)學(xué)3最優(yōu)化方法4數(shù)學(xué)；運籌學(xué)微積分；線性代數(shù)4數(shù)據(jù)結(jié)構(gòu)3數(shù)學(xué)；計算機計算機編程5應(yīng)用統(tǒng)計4數(shù)學(xué)；運籌學(xué)微積分；線性代數(shù)6計算機模擬3計算機；運籌學(xué)計算機編程7計算機編程2計算機8預(yù)測理論2運籌學(xué)應(yīng)用統(tǒng)計9數(shù)學(xué)實驗3運籌學(xué)；計算機微積分；線性代數(shù)選修課程最少

12、，且學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程 ？ E-mail:160-1規(guī)劃模型 決策變量 目標(biāo)函數(shù) xi=1 選修課號i 的課程（xi=0 不選） 選修課程總數(shù)最少 約束條件最少2門數(shù)學(xué)課，3門運籌學(xué)課，2門計算機課。 課號課名所屬類別1微積分數(shù)學(xué)2線性代數(shù)數(shù)學(xué)3最優(yōu)化方法數(shù)學(xué)；運籌學(xué)4數(shù)據(jù)結(jié)構(gòu)數(shù)學(xué)；計算機5應(yīng)用統(tǒng)計數(shù)學(xué)；運籌學(xué)6計算機模擬計算機；運籌學(xué)7計算機編程計算機8預(yù)測理論運籌學(xué)9數(shù)學(xué)實驗運籌學(xué)；計算機E-mail:17先修課程要求最優(yōu)解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它為0；6門課程，總學(xué)分21 0-1規(guī)劃模型 約束條件x3=1必有x1 = x2 =1模型

13、求解（LINDO） 課號課名先修課要求1微積分2線性代數(shù)3最優(yōu)化方法微積分；線性代數(shù)4數(shù)據(jù)結(jié)構(gòu)計算機編程5應(yīng)用統(tǒng)計微積分；線性代數(shù)6計算機模擬計算機編程7計算機編程8預(yù)測理論應(yīng)用統(tǒng)計9數(shù)學(xué)實驗微積分；線性代數(shù)E-mail:18學(xué)分最多多目標(biāo)優(yōu)化的處理方法：化成單目標(biāo)優(yōu)化。兩目標(biāo)(多目標(biāo))規(guī)劃 討論：選修課程最少，學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程？ 課程最少 以學(xué)分最多為目標(biāo)，不管課程多少。 以課程最少為目標(biāo)，不管學(xué)分多少。最優(yōu)解如上，6門課程，總學(xué)分21 。最優(yōu)解顯然是選修所有9門課程 。E-mail:19多目標(biāo)規(guī)劃 在課程最少的前提下以學(xué)分最多為目標(biāo)。最優(yōu)解： x1 = x2 = x3 = x5

14、= x7 = x9 =1, 其它為0；總學(xué)分由21增至22。注意：最優(yōu)解不唯一！課號課名學(xué)分1微積分52線性代數(shù)43最優(yōu)化方法44數(shù)據(jù)結(jié)構(gòu)35應(yīng)用統(tǒng)計46計算機模擬37計算機編程28預(yù)測理論29數(shù)學(xué)實驗3 LINDO無法告訴優(yōu)化問題的解是否唯一?？蓪9 =1 易為x6 =1增加約束 ，以學(xué)分最多為目標(biāo)求解。E-mail:20多目標(biāo)規(guī)劃 對學(xué)分數(shù)和課程數(shù)加權(quán)形成一個目標(biāo)，如三七開。 最優(yōu)解： x1 = x2 = x3 = x4 = x5 = x6 = x7 = x9 =1，其它為0；總學(xué)分28。課號課名學(xué)分1微積分52線性代數(shù)43最優(yōu)化方法44數(shù)據(jù)結(jié)構(gòu)35應(yīng)用統(tǒng)計46計算機模擬37計算機編程2

15、8預(yù)測理論29數(shù)學(xué)實驗3 E-mail:21討論與思考最優(yōu)解與1=0，2=1的結(jié)果相同學(xué)分最多多目標(biāo)規(guī)劃 最優(yōu)解與1=1，2=0的結(jié)果相同課程最少E-mail:22“課程論文二”發(fā)布時間，請安靜！ 論文上交時間：2011年 9月 27 日E-mail:注意 （1）封面必須是打印版，格式已下發(fā) （2）從摘要開始全部為手寫稿。23課程論文評分標(biāo)準(zhǔn) 方法新穎巧妙，格式非常好 20分模型建立，求解合理，格式很好 18-19分 模型建立，求解合理，格式規(guī)范 16-17分模型建立，求解基本合理，格式一般 14-15分模型建立，求解有問題，格式一般 12-13分模型建立不正確，格式糟糕，態(tài)度有問題 0-6分E-mail:24E-mail:A題：營養(yǎng)配餐問題每種蔬菜含有的營養(yǎng)素成份是不同的，從醫(yī)學(xué)上知道，每人每周對每種營養(yǎng)成分的最低需求量。某醫(yī)院營養(yǎng)室在制定下一周菜單時，需要確定表A-1中所列六種蔬菜的供應(yīng)量，以便使費用最小而又能滿足營養(yǎng)素等其它方面的要求。規(guī)定白菜的供應(yīng)一周內(nèi)不多于20 kg，其它蔬菜的供應(yīng)在一周內(nèi)不多于40kg，每周共需供應(yīng)140kg蔬菜，為了使費用最小又滿足營養(yǎng)素等其它方面的要求，試建立數(shù)學(xué)模型，說明在下一周內(nèi)應(yīng)當(dāng)供應(yīng)每種蔬菜各多少kg？25表A-1E-mail:26B題:廣告競