整數(shù)線性規(guī)劃及0-1規(guī)劃.ppt

1、典型的整數(shù)線性規(guī)劃問題,一、背包問題 有一徒步旅行者要帶一背包，設對背包的總重量限制為b千克，今有n種物品可供選擇，已知第j種物品每件重量為aj千克，使用價值為cj，問旅行者應如何選取這些物品，使得總價值最大？,整數(shù)線性規(guī)劃及01規(guī)劃,令xj表示第j種物品的裝入件數(shù),模型建立,整數(shù)線性規(guī)劃模型(IP),典型的整數(shù)線性規(guī)劃問題,二、投資問題 今有一筆資金，設金額為b個單位，可以投資的發(fā)展項目有n個，要求對每個發(fā)展項目的的投資單位數(shù)必須是非負整數(shù)，且只考慮兩種決策：要么投資，要么不投資，若對第j個發(fā)展項目投資，所花資金為aj。已知對第j個發(fā)展項目每投資一單位可獲利cj個單位，問如何投資才能使總利潤

2、最大？,令xj表示對第j個發(fā)展項目的投資數(shù)量,模型建立,整數(shù)線性規(guī)劃01模型(IP),如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)80輛， 那么最優(yōu)的生產(chǎn)計劃應作何改變？,例1 汽車廠生產(chǎn)計劃,汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求，利潤及工廠每月的現(xiàn)有量。,制訂月生產(chǎn)計劃，使工廠的利潤最大。,整數(shù)線性規(guī)劃及01規(guī)劃,設每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1, x2, x3,汽車廠生產(chǎn)計劃,模型建立,線性規(guī)劃模型(LP),模型求解,3） 模型中增加條件：x1, x2, x3 均為整數(shù)，重新求解。,OBJECTIVE FUNCTION VALUE 1) 632.2581 VAR

3、IABLE VALUE REDUCED COST X1 64.516129 0.000000 X2 167.741928 0.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，算出目標函數(shù)值z=629，與LP最優(yōu)值632.2581相差不大。,2）試探：如取x1=65，x2=167；x1=64，x2=168等，計算函數(shù)值z，通過比較可能得到更優(yōu)的解。,但必須檢驗它們是否滿足約束條

4、件。為什么？,IP可用LINDO直接求解,整數(shù)規(guī)劃(Integer Programming,簡記IP),“gin 3”表示“前3個變量為整數(shù)”，等價于： gin x1 gin x2 gin x3,IP 的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z=632,max 2x1+3x2+4x3 st 1.5x1+3x2+5x3600 280 x1+250 x2+400 x360000 end gin 3,OBJECTIVE FUNCTION VALUE 1) 632.0000 VARIABLE VALUE REDUCED COST X1 64.000000 -2.000000 X2 168.0

5、00000 -3.000000 X3 0.000000 -4.000000,模型求解,IP 結(jié)果輸出,其中3個子模型應去掉，然后逐一求解，比較目標函數(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=610,LINDO中對0-1變量的限定： int y1 int y2 int y3,方法2：引入0-1變量，化為整數(shù)規(guī)劃,M為大的正數(shù)，可取1000,OBJECTIVE FUNCTION VALUE 1) 610.0000 VARIABLE

6、VALUE REDUCED COST X1 80.000000 -2.000000 X2 150.000000 -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,最優(yōu)解同前,NLP雖然可用現(xiàn)成的數(shù)學軟件求解(如LINGO, MATLAB)，但是其結(jié)果常依賴于初值的選擇。,方法3：化為非線性規(guī)劃,非線性規(guī)劃（Non- Linear Programming，簡記NLP）,實踐表明，本例僅當初值

7、非常接近上面方法算出的最優(yōu)解時，才能得到正確的結(jié)果。,若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃。,x1=0 或 80,丁的蛙泳成績退步到115”2；戊的自由泳成績進步到57”5, 組成接力隊的方案是否應該調(diào)整？,如何選拔隊員組成4100米混合泳接力隊?,例2 混合泳接力隊的選拔,5名候選人的百米成績,窮舉法：組成接力隊的方案共有5!=120種。,目標函數(shù),若選擇隊員i參加泳姿j 的比賽，記xij=1, 否則記xij=0,0-1規(guī)劃模型,cij(秒)隊員i 第j 種泳姿的百米成績,約束條件,每人最多入選泳姿之一,每種泳姿有且只有1人,模型求解,最優(yōu)解：x14 = x21 = x32 = x4

8、3 = 1, 其它變量為0; 成績?yōu)?53.2(秒)=413”2,MIN 66.8x11+75.6x12+87x13+58.6x14 + +67.4x51+71 x52+83.8x53+62.4x54 SUBJECT TO x11+x12+x13+x14 =1 x41+x42+x43+x44 =1 x11+x21+x31+x41+x51 =1 x14+x24+x34+x44+x54 =1 END INT 20,輸入LINDO求解,甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.,丁蛙泳c43 =69.675.2，戊自由泳c54=62.4 57.5, 方案是否調(diào)整？,敏感性分析？,乙 蝶泳、丙 仰泳、

9、丁 蛙泳、戊 自由泳,IP規(guī)劃一般沒有與LP規(guī)劃相類似的理論，LINDO輸出的敏感性分析結(jié)果通常是沒有意義的。,最優(yōu)解：x21 = x32 = x43 = x51 = 1, 成績?yōu)?17”7,c43, c54 的新數(shù)據(jù)重新輸入模型，用LINDO求解,指派(Assignment)問題：每項任務有且只有一人承擔，每人只能承擔一項，效益不同，怎樣分派使總效益最大.,討論,為了選修課程門數(shù)最少，應學習哪些課程 ？,例3 選課策略,要求至少選兩門數(shù)學課、三門運籌學課和兩門計算機課,選修課程最少，且學分盡量多，應學習哪些課程 ？,0-1規(guī)劃模型,決策變量,目標函數(shù),xi=1 選修課號i 的課程（xi=0

10、不選）,選修課程總數(shù)最少,約束條件,最少2門數(shù)學課，3門運籌學課， 2門計算機課。,先修課程要求,最優(yōu)解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它為0；6門課程，總學分21,0-1規(guī)劃模型,約束條件,x3=1必有x1 = x2 =1,模型求解（LINDO）,學分最多,多目標優(yōu)化的處理方法：化成單目標優(yōu)化。,兩目標(多目標)規(guī)劃,討論：選修課程最少，學分盡量多，應學習哪些課程？,課程最少,以學分最多為目標，不管課程多少。,以課程最少為目標，不管學分多少。,多目標規(guī)劃,在課程最少的前提下以學分最多為目標。,最優(yōu)解： x1 = x2 = x3 = x5 = x7 = x9 =1, 其它為0；總學分由21增至22。,注意：最優(yōu)解不唯一！,LINDO無法告訴優(yōu)化問題的解是否唯一