數(shù)學(xué)建模(整數(shù)規(guī)劃)_圖文

1、 整數(shù)規(guī)劃模型 實際問題中x x x x f z Max Min Tn ",(,(1=或的優(yōu)化模型mi x g t s i ",2,1,0(.=x 決策變量f (x 目標(biāo)函數(shù)g i (x 0約束條件多元函數(shù)決策變量個數(shù)n 和數(shù)線性規(guī)劃條件極值約束條件個數(shù)m 較大最優(yōu)解在可行域?qū)W規(guī)非線性規(guī)劃解的邊界上取得劃整數(shù)規(guī)劃 Programming+Integer所有變量都取整數(shù),稱為純整數(shù)規(guī)劃;有一部分取整數(shù),稱為混合整數(shù)規(guī)劃;限制取0,1稱為01型整數(shù)規(guī)劃。型整數(shù)規(guī)劃 +整數(shù)線性規(guī)劃max(min nz c x =1j jj n=1s.t. (, 1,2,ij j i j a x

2、b i m="12 ,0 (n x x x "且為整數(shù)或部分為整數(shù) +例:假設(shè)有m 種不同的物品要裝入航天飛機,它們的重量和體積分別為價值為w j 和v j ,價值為c j ,航天飛機的載重量和體積限制分別為W 和V ,如何裝載使價值最大化?m11max j jj c y = 1 0j j y =被裝載 s.t. mj j v y V0j 沒被裝載1j m=1j j j w y W= 0 or 1 1,2,j y j m=" (Chicago大學(xué)的Linus Schrage教授于1980年美國芝加哥(ChiLi S h前后開發(fā), 后來成立LINDO系統(tǒng)公司(LIN

3、DO Systems Inc.,網(wǎng)址:I網(wǎng)址htt/li dLINDO: Interactive and Discrete Optimizer (V6.1 Linear(V61 LINGO: Linear Interactive General Optimizer (V8.0 LINDO解決線性規(guī)劃LPLinear Programming,整數(shù)規(guī)劃IPInteger Programming問題。LINGO解決線性規(guī)劃LPLinear Programming,非線性規(guī)劃NLPNonlinear Programming,整數(shù)規(guī)劃IPInteger Programmingg g整劃g g g 問題。

4、 1.“>”(或“<”號與“>=”(或“<=”功能相同2.甚至回車 但無運算變量與系數(shù)間可有空格(甚至車,但算符3.變量名以字母開頭,不能超過變量名字母開頭,不能超過8個字符 4.變量名不區(qū)分大小寫(包括LINDO 中的關(guān)鍵字 5.目標(biāo)函數(shù)所在行是第一行,第二行起為約束條件6.行號(行名自動產(chǎn)生或人為定義。行名以“”結(jié)束7.變量不能出現(xiàn)在一個約束條件的右端變量不能出現(xiàn)在個約束條件的右端8. 表達(dá)式中不接受括號“( ”和逗號“,”等任何符號, 例: 400(X1+X2需寫為400X1+400X2 9.表達(dá)式應(yīng)化簡,如2X1+3X24X1應(yīng)寫成2X1+3X22X13X210

5、.缺省假定所有變量非負(fù);可在模型的“END”語句后用“FREE name”將變量name的非負(fù)假定取消11.“END”后對01變量說明:INT n或INT name12.“END”后對整數(shù)變量說明:GIN n或GIN12后對整數(shù)變量說明name 汽車廠生產(chǎn)三種類型的汽車,已知各類型每輛車對鋼材、勞動時間的需求,利潤及工廠每月的現(xiàn)有量。材勞動時間的需求利潤及工廠每月的現(xiàn)有量。小型中型大型現(xiàn)有量鋼材(噸 1.5 3 5 600勞動時間(小時280 250 400 60000利潤(萬元2 3 4制訂月生產(chǎn)計劃,使工廠的利潤最大。制訂月生產(chǎn)計劃使工廠的利潤最大如果生產(chǎn)某一類型汽車,則至少要生產(chǎn)80輛,

6、那么最優(yōu)的生產(chǎn)計劃應(yīng)作何改變?汽車廠生產(chǎn)計劃汽車廠產(chǎn)計劃模型建立小型中型大型現(xiàn)有量設(shè)每月生產(chǎn)小、中、大型模建中鋼材 1.5 3 5 60060000汽車的數(shù)量分別為x 1,x 2,x 3時間280 250 400 利潤2 3 4321432x x x zMax +=線性600535.1.321+x x x t s 60000400250280+x x x 線規(guī)劃模型3210,321x x x (LP 模型OBJECTIVE FUNCTION VALUE 求解1632.2581VARIABLE VALUE REDUCED COST X164.5161290.000000X2167.7419280

7、.000000X30.0000000.946237結(jié)果為小數(shù),ROW SLACK OR SURPLUS DUAL PRICES20.0000000.73118330.0000000.003226怎么辦?1舍去小數(shù):取x 1=64,x 2=167,算出目標(biāo)函數(shù)值z =629,與LP 最優(yōu)值632.2581相差不大。2試探:如取x 1=65,x 2=167;x 1=64,x 2=168等,計算函數(shù)值z ,通過比較可能得到更優(yōu)的解。但必須檢驗它們是否滿足約束條件。3模型中增加條件:x 1,x 2,x 3均為整數(shù),重新求解。整數(shù)規(guī)劃(Integer Programming ,簡記IP IP 可用LIN

8、DO 直接求解max 321432x x x z Max +=模型求解2x1+3x2+4x3st600535.1.321+x x x t s 60000400250280321+x x x 1.5x1+3x2+5x3<600280x1+250x2+400x3<60000end為非負(fù)整數(shù)321,x x x “gin 3”表示“前3個變量為gin 3OBJECTIVE FUNCTION VALUE IP 結(jié)果輸出整數(shù)”,等價于:gin x1i 21632.0000VARIABLE VALUE REDUCED COST X164.0000002.000000gin x2gin x3 的最

9、解6680最值632X2168.0000003.000000X3 0.000000 4.000000IP 的最優(yōu)解x 1=64,x 2=168,x 3=0,最優(yōu)值z =632 汽車廠生產(chǎn)計劃汽車廠產(chǎn)計劃若生產(chǎn)某類汽車,則至少生產(chǎn)80輛,求生產(chǎn)計劃。M 80,0,0321=x x x 0,80,0321=x x x 321432x x x z Max +=600535.1.321+x x x t s 80,80,0321=x x x 60000400250280321+x x x x x x =0 80×0,0,80321=x x x 0,80,80321=x x x 方法1:分解為8

10、個LP 子模型1,2,3或其中3個子模型應(yīng)去掉,然后逐一求解比較目標(biāo)函數(shù)值80,0,80321=x x x 808080x x x ×逐求解,比較目標(biāo)函數(shù)值,再加上整數(shù)約束,得最優(yōu)解:,3210,321=x x x ×x 1=80,x 2= 150,x 3=0,最優(yōu)值z =610若生產(chǎn)某類汽車,則至少生產(chǎn)80輛,求生產(chǎn)計劃。方法2:引入01變量,化為整數(shù)規(guī)劃產(chǎn)車產(chǎn)產(chǎn)計M 為大的正數(shù),x 1=0 或8001,0,80,11111y y x My x 可取1000 x 2=0 或80x =0 或801,0,80,22222y y x My x 1,0,80,33333y y x

11、 My x LINDO 中對01OBJECTIVE FUNCTION VALUE 1610.00003變量的限定:int y1VARIABLE VALUE REDUCED COST X180.0000002.000000最優(yōu)解同前int y2int y3 X2150.000000 3.000000X30.0000004.000000Y1 1.0000000.00000010000000000000解同前Y2 1.0000000.000000Y3 0.000000 0.000000 售價4800元/噸汽油甲庫存500噸(A 50% 原油A汽油乙市場上可買到不超過售價5600元/噸庫存1000噸原

12、油B (A 60%1500噸的原油A :購買量不超過500噸時的單價為10000元/噸;購買量超過500噸但不超過1000噸時,超過500噸的8000元/噸;該公司應(yīng)如何安排原油的采購和加部分購買量超過1000噸時,超過1000噸的部分6000元/噸。該公司應(yīng)如何安排原油的采購和加工?問題利潤:銷售汽油的收入A 分析利潤銷售汽油的收購買原油的支出難點:原油A 的購價與購買量的關(guān)系較復(fù)雜決策原油A 的購買量,原油A, B 生產(chǎn)汽油甲,乙的數(shù)量變量甲(A 50% A購買x x 11x 12x 214.8千元/噸目標(biāo)B 乙(A 60% x 22 5.6千元/噸函數(shù)c (x 購買原油A 的支出利潤(千

13、元(6.5(8.422122111x c x x x x z Max +=c (x 如何表述?目標(biāo)x 500噸單價為10千元/噸;500噸x 1000噸,超過500噸的8千元/噸;噸超過噸函數(shù)1000噸x 1500噸,超過1000噸的6千元/噸。+=1000(500 1000 8500(0 10(x x x x x c 約束+5001(1000 30006x x 原油供應(yīng)條件x x x +5001211購買x Ax 11x 500噸10002221+x x B 12x 21x 庫存庫存1000噸1500x 22汽油含原油約束A 的比例限制條件x 115.011+x x x 2111x x 甲(

14、A 50% Ax 12x 21211112x B 乙(A 60%x 22數(shù)中是線數(shù)是線劃6.02212+x x 221232x x ¾目標(biāo)函數(shù)中c (x 不是線性函數(shù),是非線性規(guī)劃;¾,一般的非線性規(guī)劃軟對于用分段函數(shù)定義的c (x ,般的非線性規(guī)劃軟件也難以輸入和求解;想法將型簡用成的軟件求解¾想辦法將模型化簡,用現(xiàn)成的軟件求解。x x x 以價格10, 8, 6(A 模型求解1 ,2 ,3 價格,(千元/噸采購的噸數(shù)=+x +x c =+8+6目標(biāo)x x 1x 2x 3, (x 10x 18x 26x 3函數(shù)6810(6.5(8.432122122111x x

15、 x x x x x z Max += y 1, y 2 , y 3=1 以價格10, 8, 6(千元/噸采購A 增108加112500500y x y 223500500y x y x 1 , x 2 , x 3 以價格10, 8, 6(千元/噸采購A 的噸數(shù)y =0 x =0約束33500y x y 1,y 2,y 3 =0或1 x >0 y =1Max 4.8x11+4.8x21+5.6x12+5.6x2210x18x26x3stx11+x12x<500x21+x22<100005x1105x21>00.5x110.5x21>00.4x120.6x22>

16、;0x x1x2x3=0x1500y1<0x2500y2<0x3500y3<0500y2>0x1500y20x2500y3>0endint y1yint y2int y3 01線性規(guī)劃模型,可用LINDO求解OBJECTIVE FUNCTION VALUE15000.000VARIABLE VALUE REDUCED COSTY1 1.0000000.000000Y2 1.0000002200.000000Y3 1.0000001200.000000X110.0000000.80000000000000800000X210.0000000.800000X12150

17、0.0000000.000000X221000.0000000.000000X1500.0000000.000000X2500.0000000.000000X30.0000000.400000X 1000.0000000.00000010000000000000000購買1000噸原油A,與庫存的500噸原油A和1000噸原油B 一起,生產(chǎn)2500噸汽油乙,利潤為5,000千元。 分派問題若干項任務(wù)分給一些候選人來完成,每人的專長不同,完成每項任務(wù)取得的效益或需要的資源就不同,如何分派任務(wù)使獲得的總效益最大,或付出的總資源最少。選擇問題若干種策略供選擇,不同的策略得到的收益或付出的成本不同,各

18、個策略之間有相互制約關(guān)系,如何在滿成本不同各個策略之間有相互制約關(guān)系如何在滿足一定條件下作出決擇,使得收益最大或成本最小。 5名候選人的百米成績甲乙丙丁戊蝶泳106”857”2118”110”107”4仰泳115”6106”107”8114”2111”蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”4如何選拔隊員組成4×100米混合泳接力隊?丁的蛙泳成績退步到115”2;戊的自由泳成績進(jìn)步到57”5, 組成接力隊的方案是否應(yīng)該調(diào)整?窮舉法:組成接力隊的方案共有5!=120種。窮舉法組成接力隊的方案共有5!120種c ij (秒隊員i 第

19、j 種泳姿的百米成績 c ij i =1i =2i =3i =4i =51668572674j =166.857.2787067.4j =275.66667.874.271664846696838的比賽記j =38766.484.669.683.8j =458.65359.457.262.4目標(biāo)若選擇隊員i 參加泳姿j 的比賽,記x ij =1, 否則記x ij =045函數(shù)約束=11j i ijij x c Z Min條件每人最多入選泳姿之一每種泳姿有且只有1人45"5,1,11"=i x j ij 4,1,11=j xi ij模型求解輸求解輸入LINDOMIN 66.8

20、x11+75.6x12+87x13+58.6x14+57.2x21+66x22+66.4x23+53x24+78x31+67.8x32+84.6x33+59.4x34+70x41+74.2x42+69.6x43+57.2x44+67.4x51+71x52+83.8x53+62.4x54 SUBJECT TOx11+x12+x13+x14 <=1x21+x22+x23+x24 <=1x31+x32+x33+x34 <=1x41+x42+x43+x44 <=1x51x52x53x54 1x51+x52+x53+x54<=1x11+x21+x31+x41+x51 =1x

21、12+x22+x32+x42+x52 =1x13+x23+x33+x43+x53 1=1x14+x24+x34+x44+x54 =1ENDINT20 OBJECTIVE FUNCTION VALUE1 253.2000最優(yōu)解:VARIABLE VALUE REDUCED COSTX11 0.000000 66.800003X12 0.000000 75.599998最優(yōu)解x 14=x 21=x 32=x 43=1,X13 0.000000 87.000000X14 1.00000058.599998X21 1.00000057.200001000000066000000其它變量為0;X22 0

22、.000000 66.000000X23 0.000000 66.400002X24 0.000000 53.000000000000078000000成績?yōu)?53.2(秒=413”2X31 0.000000 78.000000X32 1.00000067.800003X33 0.000000 84.599998000000059400002甲 自由泳X34 0.000000 59.400002X41 0.000000 70.000000X42 0.000000 74.199997乙 蝶泳X43 1.000000 69.599998X44 0.000000 57.200001X51 0.000

23、000 67.400002X52 0.000000 71.000000丙 仰泳50000000000000X53 0.000000 83.800003X54 0.000000 62.400002丁 蛙泳 甲乙丙丁戊蝶泳106”857”2118”110”107”4仰泳115”6106”107”8114”2111”蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”4 丁蛙泳696752戊自由泳624討論c 43=69.675.2,戊自由泳c 54=62.4 57.5, 方案是否調(diào)整?敏感性分析?IP 規(guī)劃般沒有與規(guī)劃相類似的理論規(guī)劃一般沒有與LP 規(guī)劃

24、相類似的理論,LINDO 輸出的敏感性分析結(jié)果通常是沒有意義的。的新數(shù)據(jù)重新輸入模型用c 43, c 54的新數(shù)據(jù)重新輸入模型,用LINDO 求解 模型求解輸求解輸入LINDOMIN 66.8x11+75.6x12+87x13+58.6x14+57.2x21+66x22+66.4x23+53x24+78x31+67.8x32+84.6x33+59.4x34+70x41+74.2x42+75.2x43+57.2x44+67.4x51+71x52+83.8x53+57.5x54 SUBJECT TOx11+x12+x13+x14 <=1x21+x22+x23+x24 <=1x31+x3

25、2+x33+x34 <=1x41+x42+x43+x44 <=1x51x52x53x54 1x51+x52+x53+x54<=1x11+x21+x31+x41+x51 =1x12+x22+x32+x42+x52 =1x13+x23+x33+x43+x53 1=1x14+x24+x34+x44+x54 =1ENDINT20 最優(yōu)解:OBJECTIVE FUNCTION VALUE1 257.7000x =x =x =x =1VARIABLE VALUE REDUCED COSTX11 0.000000 66.800003X12 0.000000 75.5999980000000

26、8700000021324354成績?yōu)?17”7X13 0.000000 87.000000X14 0.000000 58.599998X21 1.000000 57.200001000000066000000X22 0.000000 66.000000X23 0.000000 66.400002X24 0.000000 53.000000000000078000000新方案乙 蝶泳原方案甲 自由泳X31 0.000000 78.000000X32 1.000000 67.800003X33 0.000000 84.599998丙 仰泳乙 蝶泳X34 0.000000 59.400002X41

27、 0.000000 70.000000X42 0.000000 74.199997X43 1.000000 75.199997丁 蛙泳丙 仰泳X44 0.000000 57.200001X51 0.000000 67.400002X52 0.000000 71.000000戊 自由泳丁 蛙泳.X53 0.000000 83.800003X54 1.000000 57.500000 甲乙丙丁戊蝶泳106”857”257”2118”110”107”4仰泳115”6106”107”8107”8114”2111”蛙泳127”106”4124”6109”6115”2123”81152自由泳58”653”

28、59”457”2102”457”5575 指派(Assignment問題:問題每項任務(wù)有且只有一人承擔(dān),每人只能承擔(dān)一項,益怎樣分派使總效益不同,怎樣分派使總效益最大. 課號課名學(xué)分所屬類別先修課要求1微積分5數(shù)學(xué)2線性代數(shù)4數(shù)學(xué)3最優(yōu)化方法4數(shù)學(xué);運籌學(xué)微積分;線性代數(shù)最優(yōu)方學(xué)籌學(xué)積分線代4數(shù)據(jù)結(jié)構(gòu)3數(shù)學(xué);計算機計算機編程5應(yīng)用統(tǒng)計4數(shù)學(xué);運籌學(xué)微積分;線性代數(shù)6計算機模擬3計算機;運籌學(xué)計算機編程7計算機編程2計算機應(yīng)用統(tǒng)計要求至少選兩門數(shù)學(xué)課三門運籌學(xué)課和兩門計算機課8預(yù)測理論2運籌學(xué)9數(shù)學(xué)實驗3運籌學(xué);計算機微積分;線性代數(shù)為了選修課程門數(shù)最少,應(yīng)學(xué)習(xí)哪些課程?要求至少選兩門數(shù)學(xué)課、三

29、門運籌學(xué)課和兩門計算機課選修課程最少,且學(xué)分盡量多,應(yīng)學(xué)習(xí)哪些課程?01規(guī)劃模型決策變量x i =1 選修課號i 的課號課名所屬類別1微積分?jǐn)?shù)學(xué)課程(x i =0 不選2線性代數(shù)數(shù)學(xué)3最優(yōu)化方法數(shù)學(xué);運籌學(xué)目標(biāo)函數(shù)選修課程總數(shù)最少最優(yōu)方法學(xué);籌學(xué)4數(shù)據(jù)結(jié)構(gòu)數(shù)學(xué);計算機5應(yīng)用統(tǒng)計數(shù)學(xué);運籌學(xué)=9x Z Min6計算機模擬計算機;運籌學(xué)7計算機編程計算機=1i i最少門數(shù)學(xué)2+x x x x x 8預(yù)測理論運籌學(xué)9數(shù)學(xué)實驗運籌學(xué);計算機約束條件2門數(shù)學(xué)課,3門運籌學(xué)課,54321398653+x x x x x 2門計算機課。29764+x x x x01規(guī)劃模型約束條件先修課程要求有課號課名先修

30、課要求微積分x 3=1必有x 1 = x 2 =11(52線性代數(shù)(43最優(yōu)化方法(4微積分;線性代數(shù)2x x x 2313,x x x x 最優(yōu)方法(微積分;線性代4數(shù)據(jù)結(jié)構(gòu)計算機編程5應(yīng)用統(tǒng)計微積分;線性代數(shù)74x x 213074x x 6計算機模擬(3計算機編程7計算機編程(2應(yīng)用統(tǒng)計02215x x x 模型求解(8預(yù)測理論9數(shù)學(xué)實驗(3微積分;線性代數(shù)76x x 058x x 最優(yōu)解:x 1 = x 2 = x 3 = x 6= x 7= x 9=1, LINDO 2219x x x 其它為0;6門課程,總學(xué)分21 FUNCTIONVALUEmin x1+x2+x3+x4+x5+x

31、6+x7+x8+x9stx1+x2+x3+x4+x5>2OBJECTIVE 1 6.000000x3+x5+x6+x8+x9>3x4+x6+x7+x9>22x3x1x2<0VARIABLE VALUE REDUCED COSTX1 1.000000 1.00000010000001000000x4x7<02x5x1x2<0x6x7<0X2 1.000000 1.000000X3 1.000000 1.000000X4 0.000000 1.000000x8x5<02x9x1x2<0end i t X5 0.000000 1.000000X6

32、 1.000000 1.000000X7 1.000000 1.000000X8 0.000000 1.000000int9X9 1.000000 1.000000 討論:選修課程最少,學(xué)分盡量多,應(yīng)學(xué)習(xí)哪些課程?學(xué)分最多修最課程最少5432143445x x x x x W Max +=9ix Z Min兩目標(biāo)(多目標(biāo)規(guī)劃98763223x x x x +,W Z Min =1i 多目標(biāo)優(yōu)化的處理方法:化成單目標(biāo)優(yōu)化。以課程最少為目標(biāo),不管學(xué)分多少。最優(yōu)解如上,6門課程,總學(xué)分21 。以學(xué)分最多為目標(biāo),最優(yōu)解顯然是選修所不管課程多少。有9門課程。多目標(biāo)規(guī)劃在課程最少的前提下增加約束,69=i

33、 x 以學(xué)分最多為目標(biāo)。以學(xué)分最多為目標(biāo)求解。1=i 最優(yōu)解:x 1 = x 2 = x 3 = x 5= x = x =1, 其它為0;總學(xué)課號課名學(xué)分1微積分579分由21增至22。意解唯2線性代數(shù)43最優(yōu)化方法44注意:最優(yōu)解不唯一!數(shù)據(jù)結(jié)構(gòu)35應(yīng)用統(tǒng)計46計算機模擬3=1=17計算機編程28預(yù)測理論2LINDO 無法告訴優(yōu)化可將x 91 易為x 619數(shù)學(xué)實驗3問題的解是否唯一。 max FUNCTIONVALUE5x1+4x2+4x3+3x4+4x5+3x6+2x7+2x8+3x9stx1+x2+x3+x4+x5>2x3+x5+x6+x8+x9>3OBJECTIVE 1 22.00000x3x5x6x8x9>3x4+x6+x7+x9>22x3x1x2<0x4x