1、 整數規劃模型 實際問題中x x x x f z Max Min Tn ",(,(1=或的優化模型mi x g t s i ",2,1,0(.=x 決策變量f (x 目標函數g i (x 0約束條件多元函數決策變量個數n 和數線性規劃條件極值約束條件個數m 較大最優解在可行域學規非線性規劃解的邊界上取得劃整數規劃 Programming+Integer所有變量都取整數,稱為純整數規劃;有一部分取整數,稱為混合整數規劃;限制取0,1稱為01型整數規劃。型整數規劃 +整數線性規劃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 "且為整數或部分為整數 +例:假設有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大學的Linus Schrage教授于1980年美國芝加哥(ChiLi S h前后開發, 后來成立LINDO系統公司(LIN

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

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

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

6、那么最優的生產計劃應作何改變?汽車廠生產計劃汽車廠產計劃模型建立小型中型大型現有量設每月生產小、中、大型模建中鋼材 1.5 3 5 60060000汽車的數量分別為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 線規劃模型3210,321x x x (LP 模型OBJECTIVE FUNCTION VALUE 求解1632.2581VARIABLE VALUE REDUCED COST X164.5161290.000000X2167.7419280

7、.000000X30.0000000.946237結果為小數,ROW SLACK OR SURPLUS DUAL PRICES20.0000000.73118330.0000000.003226怎么辦?1舍去小數:取x 1=64,x 2=167,算出目標函數值z =629,與LP 最優值632.2581相差不大。2試探:如取x 1=65,x 2=167;x 1=64,x 2=168等,計算函數值z ,通過比較可能得到更優的解。但必須檢驗它們是否滿足約束條件。3模型中增加條件:x 1,x 2,x 3均為整數,重新求解。整數規劃(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為非負整數321,x x x “gin 3”表示“前3個變量為gin 3OBJECTIVE FUNCTION VALUE IP 結果輸出整數”,等價于:gin x1i 21632.0000VARIABLE VALUE REDUCED COST X164.0000002.000000gin x2gin x3 的最

9、解6680最值632X2168.0000003.000000X3 0.000000 4.000000IP 的最優解x 1=64,x 2=168,x 3=0,最優值z =632 汽車廠生產計劃汽車廠產計劃若生產某類汽車,則至少生產80輛,求生產計劃。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個子模型應去掉,然后逐一求解比較目標函數值80,0,80321=x x x 808080x x x ×逐求解,比較目標函數值,再加上整數約束,得最優解:,3210,321=x x x ×x 1=80,x 2= 150,x 3=0,最優值z =610若生產某類汽車,則至少生產80輛,求生產計劃。方法2:引入01變量,化為整數規劃產車產產計M 為大的正數,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最優解同前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元/噸;該公司應如何安排原油的采購和加部分購買量超過1000噸時,超過1000噸的部分6000元/噸。該公司應如何安排原油的采購和加工?問題利潤:銷售汽油的收入A 分析利潤銷售汽油的收購買原油的支出難點:原油A 的購價與購買量的關系較復雜決策原油A 的購買量,原油A, B 生產汽油甲,乙的數量變量甲(A 50% A購買x x 11x 12x 214.8千元/噸目標B 乙(A 60% x 22 5.6千元/噸函數c (x 購買原油A 的支出利潤(千

13、元(6.5(8.422122111x c x x x x z Max +=c (x 如何表述?目標x 500噸單價為10千元/噸;500噸x 1000噸,超過500噸的8千元/噸;噸超過噸函數1000噸x 1500噸,超過1000噸的6千元/噸。+=1000(500 1000 8500(0 10(x x x x x c 約束+5001(1000 30006x x 原油供應條件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數中是線數是線劃6.02212+x x 221232x x ¾目標函數中c (x 不是線性函數,是非線性規劃;¾,一般的非線性規劃軟對于用分段函數定義的c (x ,般的非線性規劃軟件也難以輸入和求解;想法將型簡用成的軟件求解¾想辦法將模型化簡,用現成的軟件求解。x x x 以價格10, 8, 6(A 模型求解1 ,2 ,3 價格,(千元/噸采購的噸數=+x +x c =+8+6目標x x 1x 2x 3, (x 10x 18x 26x 3函數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 的噸數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線性規劃模型,可用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 一起,生產2500噸汽油乙,利潤為5,000千元。 分派問題若干項任務分給一些候選人來完成,每人的專長不同,完成每項任務取得的效益或需要的資源就不同,如何分派任務使獲得的總效益最大,或付出的總資源最少。選擇問題若干種策略供選擇,不同的策略得到的收益或付出的成本不同,各

18、個策略之間有相互制約關系,如何在滿成本不同各個策略之間有相互制約關系如何在滿足一定條件下作出決擇,使得收益最大或成本最小。 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;戊的自由泳成績進步到57”5, 組成接力隊的方案是否應該調整?窮舉法:組成接力隊的方案共有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目標若選擇隊員i 參加泳姿j 的比賽,記x ij =1, 否則記x ij =045函數約束=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最優解:VARIABLE VALUE REDUCED COSTX11 0.000000 66.800003X12 0.000000 75.599998最優解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成績為253.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, 方案是否調整?敏感性分析?IP 規劃般沒有與規劃相類似的理論規劃一般沒有與LP 規劃

24、相類似的理論,LINDO 輸出的敏感性分析結果通常是沒有意義的。的新數據重新輸入模型用c 43, c 54的新數據重新輸入模型,用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 最優解:OBJECTIVE FUNCTION VALUE1 257.7000x =x =x =x =1VARIABLE VALUE REDUCED COSTX11 0.000000 66.800003X12 0.000000 75.5999980000000

26、8700000021324354成績為417”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問題:問題每項任務有且只有一人承擔,每人只能承擔一項,益怎樣分派使總效益不同,怎樣分派使總效益最大. 課號課名學分所屬類別先修課要求1微積分5數學2線性代數4數學3最優化方法4數學;運籌學微積分;線性代數最優方學籌學積分線代4數據結構3數學;計算機計算機編程5應用統計4數學;運籌學微積分;線性代數6計算機模擬3計算機;運籌學計算機編程7計算機編程2計算機應用統計要求至少選兩門數學課三門運籌學課和兩門計算機課8預測理論2運籌學9數學實驗3運籌學;計算機微積分;線性代數為了選修課程門數最少,應學習哪些課程?要求至少選兩門數學課、三

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

30、課要求微積分x 3=1必有x 1 = x 2 =11(52線性代數(43最優化方法(4微積分;線性代數2x x x 2313,x x x x 最優方法(微積分;線性代4數據結構計算機編程5應用統計微積分;線性代數74x x 213074x x 6計算機模擬(3計算機編程7計算機編程(2應用統計02215x x x 模型求解(8預測理論9數學實驗(3微積分;線性代數76x x 058x x 最優解:x 1 = x 2 = x 3 = x 6= x 7= x 9=1, LINDO 2219x x x 其它為0;6門課程,總學分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 討論:選修課程最少,學分盡量多,應學習哪些課程?學分最多修最課程最少5432143445x x x x x W Max +=9ix Z Min兩目標(多目標規劃98763223x x x x +,W Z Min =1i 多目標優化的處理方法:化成單目標優化。以課程最少為目標,不管學分多少。最優解如上,6門課程,總學分21 。以學分最多為目標,最優解顯然是選修所不管課程多少。有9門課程。多目標規劃在課程最少的前提下增加約束,69=i

33、 x 以學分最多為目標。以學分最多為目標求解。1=i 最優解:x 1 = x 2 = x 3 = x 5= x = x =1, 其它為0;總學課號課名學分1微積分579分由21增至22。意解唯2線性代數43最優化方法44注意:最優解不唯一!數據結構35應用統計46計算機模擬3=1=17計算機編程28預測理論2LINDO 無法告訴優化可將x 91 易為x 619數學實驗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