姜啟源-數(shù)學模型第五版-第4章ppt課件

1、實際問題中 的優(yōu)化模型,x決策變量,f(x)目標函數(shù),gi(x)0約束條件,多元函數(shù)條件極值,決策變量個數(shù)n和 約束條件個數(shù)m較大,最優(yōu)解在可行域 的邊界上取得,數(shù)學規(guī)劃,線性規(guī)劃 非線性規(guī)劃 整數(shù)規(guī)劃,重點在模型的建立和結果的分析,第四章 數(shù)學規(guī)劃模型,第四章 數(shù)學規(guī)劃模型,4.1 奶制品的生產(chǎn)與銷售 4.2 自來水輸送與貨機裝運 4.3 汽車生產(chǎn)與原油采購 4.4 接力隊選拔和選課策略 4.5 飲料廠的生產(chǎn)與檢修 4.6 鋼管和易拉罐下料 4.7 廣告投入與升級調(diào)薪 4.8 投資的風險與收益,企業(yè)生產(chǎn)計劃,4.1 奶制品的生產(chǎn)與銷售,空間層次,工廠級：根據(jù)外部需求和內(nèi)部設備、人力、原料等條

2、件，以最大利潤為目標制訂產(chǎn)品生產(chǎn)計劃,車間級：根據(jù)生產(chǎn)計劃、工藝流程、資源約束及費用參數(shù)等，以最小成本為目標制訂生產(chǎn)批量計劃,時間層次,若短時間內(nèi)外部需求和內(nèi)部資源等不隨時間變化，可制訂單階段生產(chǎn)計劃，否則應制訂多階段生產(chǎn)計劃,例1 加工奶制品的生產(chǎn)計劃,50桶牛奶,時間480h,至多加工100kgA1,制訂生產(chǎn)計劃，使每天獲利最大,35元可買到1桶牛奶，買嗎？若買，每天最多買多少,可聘用臨時工人，付出的工資最多是每小時幾元,A1的獲利增加到 30元/kg，應否改變生產(chǎn)計劃,每天,問題,x1桶牛奶生產(chǎn)A1,x2桶牛奶生產(chǎn)A2,獲利 243x1,獲利 164 x2,原料供應,勞動時間,加工能力,

3、決策變量,目標函數(shù),每天獲利,約束條件,非負約束,線性規(guī)劃模型(LP,時間480h,至多加工100kgA1,基本模型,模型分析與假設,比例性,可加性,連續(xù)性,xi對目標函數(shù)的“貢獻”與xi取值成正比,xi對約束條件的“貢獻”與xi取值成正比,xi對目標函數(shù)的“貢獻”與xj取值無關,xi對約束條件的“貢獻”與xj取值無關,xi取值連續(xù),A1,A2每千克的獲利是與各自產(chǎn)量無關的常數(shù),每桶牛奶加工A1,A2的數(shù)量, 時間是與各自產(chǎn)量無關的常數(shù),A1,A2每千克的獲利是與相互產(chǎn)量無關的常數(shù),每桶牛奶加工A1,A2的數(shù)量,時間是與相互產(chǎn)量無關的常數(shù),加工A1,A2的牛奶桶數(shù)是實數(shù),線性規(guī)劃模型,模型求解

4、,圖解法,約束條件,目標函數(shù),z=c (常數(shù)) 等值線,在B(20,30)點得到最優(yōu)解,目標函數(shù)和約束條件是線性函數(shù),可行域為直線段圍成的凸多邊形,目標函數(shù)的等值線為直線,最優(yōu)解一定在凸多邊形的某個頂點取得,模型求解,軟件實現(xiàn),LINGO,model: max = 72*x1+64*x2; milk x1 + x250; time 12*x1+8*x2480; cpct 3*x1100; end,Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value R

5、educed Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000,20桶牛奶生產(chǎn)A1, 30桶生產(chǎn)A2，利潤3360元,結果解釋,Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable

6、Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000,model: max = 72*x1+64*x2; milk x1 + x250; time 12*x1+8*x2480; cpct 3*x1100; end,三種資源,資源” 剩余為零的約束為緊約束（有效約束,結果解釋,Global

7、optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000,最優(yōu)解下“資源”增加1單位“效益”的增量,35元可買到1桶牛奶，

8、要買嗎,35 48, 應該買,聘用臨時工人付出的工資最多每小時幾元,2元,Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase

9、Decrease MILK 50.00000 10.00000 6.666667 TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 40.00000,最優(yōu)解不變時目標函數(shù)系數(shù)允許變化范圍,敏感性分析 (“LINGO|Ranges”,x1系數(shù)范圍(64,96,x2系數(shù)范圍(48,72,A1獲利增加到 30元/kg，應否改變生產(chǎn)計劃,x1系數(shù)由24 3=72增加為303=90，在允許范圍內(nèi),不變,約束條件不變,結果解釋,Ranges in which the basis is unchanged: Objective Coefficien

10、t Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease MILK 50.00000 10.00000 6.666667 TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 4

11、0.00000,影子價格有意義時約束右端的允許變化范圍,原料最多增加10,時間最多增加53,35元可買到1桶牛奶, 每天最多買多少,最多買10桶,目標函數(shù)不變,充分條件,例2 奶制品的生產(chǎn)銷售計劃,在例1基礎上深加工,制訂生產(chǎn)計劃，使每天凈利潤最大,30元可增加1桶牛奶，3元可增加1h時間，應否投資？現(xiàn) 投資150元，可賺回多少,50桶牛奶, 480h,至多100kgA1,B1，B2的獲利經(jīng)常有10%的波動，對計劃有無影響,每天銷售10kgA1的合同必須滿足，對利潤有什么影響,出售x1 kg A1, x2 kg A2,x3 kg B1, x4 kg B2,原料供應,勞動時間,加工能力,決策變量

12、,目標函數(shù),利潤,約束條件,非負約束,x5 kg A1加工B1， x6 kg A2加工B2,附加約束,基本模型,模型求解,軟件實現(xiàn),LINGO,Global optimal solution found. Objective value: 3460.800 Total solver iterations: 2 Variable Value Reduced Cost X1 0.000000 1.680000 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5 24.00000 0.000000 X6 0.000000

13、 1.520000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 MILK 0.000000 3.160000 TIME 0.000000 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.00000 6 0.000000 32.00000,Global optimal solution found. Objective value: 3460.800 Total solver iterations: 2 Variable Value Reduced Cost X1 0.000000 1.680

14、000 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5 24.00000 0.000000 X6 0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 MILK 0.000000 3.160000 TIME 0.000000 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.00000 6 0.000000 32.00000,結果解釋,每天銷售168 kgA2和19.2 kgB1， 利

15、潤3460.8（元,8桶牛奶加工成A1，42桶牛奶加工成A2， 將得到的24kgA1全部加工成B1,除加工能力外均為緊約束,結果解釋,Global optimal solution found. Objective value: 3460.800 Total solver iterations: 2 Variable Value Reduced Cost X1 0.000000 1.680000 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5 24.00000 0.000000 X6 0.000000 1.52

16、0000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 MILK 0.000000 3.160000 TIME 0.000000 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.00000 6 0.000000 32.00000,增加1桶牛奶使利潤增長3.1612=37.92,增加1h時間使利潤增長3.26,30元可增加1桶牛奶，3元可增加1h時間，應否投資？現(xiàn)投資150元，可賺回多少,投資150元增加5桶牛奶,可賺回189.6元(大于增加時間的利潤增長,結果解釋,B1,B2的獲利有10%的波

17、動，對計劃有無影響,Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 24.00000 1.68000 INFINITY X2 16.00000 8.15000 2.10000 X3 44.00000 19.75000 3.166667 X4 32.00000 2.026667 INFINITY X5 -3.00000 15.80000 2.533333 X6 -3.0

18、0000 1.52000 INFINITY,B1獲利下降10%，超出X3 系數(shù)允許范圍,B2獲利上升10%，超出X4 系數(shù)允許范圍,波動對計劃有影響,生產(chǎn)計劃應重新制訂：如將x3的系數(shù)改為39.6計算，會發(fā)現(xiàn)結果有很大變化,敏感性分析,結果解釋,x1從0開始增加一個單位時，最優(yōu)目標函數(shù)值將減少1.68,Reduced Cost是有意義、有條件的(LINGO沒有給出,每天銷售10kgA1的合同必須滿足， 對利潤有什么影響,公司利潤減少 1.6810=16.8（元,最優(yōu)利潤為 3460.8 16.8 = 3444,Global optimal solution found. Objective v

19、alue: 3460.800 Total solver iterations: 2 Variable Value Reduced Cost X1 0.000000 1.680000 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5 24.00000 0.000000 X6 0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 MILK 0.000000 3.160000 TIME 0.000000 3.260000 CPCT 7

20、6.00000 0.000000 5 0.000000 44.00000 6 0.000000 32.00000,小結與評注,由于產(chǎn)品利潤、加工時間等均為常數(shù)，可 建立線性規(guī)劃模型,線性規(guī)劃模型的三要素：決策變量、目標 函數(shù)、約束條件,用LINGO求解，輸出豐富，利用影子價格 和靈敏性分析可對結果做進一步研究,建模時盡可能利用原始的數(shù)據(jù)信息，把盡量 多的計算留給計算機去做（分析例2的建模,4.2 自來水輸送與貨機裝運,生產(chǎn)、生活物資從若干供應點運送到一些需求點，怎樣安排輸送方案使運費最小，或利潤最大,運輸問題,各種類型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少

21、,其他費用:450元/ 103t,應如何分配水庫供水量，公司才能獲利最多,若水庫供水量都提高一倍，公司利潤可增加到多少,例1 自來水輸送,收入：900元/103t,支出,總供水量：160,確定送水方案使利潤最大,問題分析,總需求量：120+180=300,總收入900160=144000(元,收入：900元/ 103t,其他費用:450元/ 103t,支出,引水管理費,其他支出450160=72000(元,供應限制,約束條件,需求限制,線性規(guī)劃模型(LP,目標函數(shù),水庫i 向j 區(qū)的日供水量為 xij（x34=0,決策變量,模型建立,確定3個水庫向4個小區(qū)的供水量,模型求解,部分結果： Obj

22、ective Value: 24400.00 Variable Value Reduced Cost X11 0.000000 30.000000 X12 50.000000 0.000000 X13 0.000000 50.000000 X14 0.000000 20.000000 X21 0.000000 10.000000 X22 50.000000 0.000000 X23 0.000000 20.000000 X24 10.000000 0.000000 X31 40.000000 0.000000 X32 0.000000 10.000000 X33 10.000000 0.000

23、000,利潤=總收入-其他費用-引水管理費=144000-72000-24400 = 47600（元,引水管理費 24400(元,目標函數(shù),總供水量(320) 總需求量(300,每個水庫最大供水量都提高一倍,利潤 = 收入(900) 其他費用(450) 引水管理費,供應限制,B, C 類似處理,問題討論,確定送水方案使利潤最大,需求約束可以不變,模型求解,部分結果： Objective Value: 88700.00 Variable Value Reduced Cost X11 0.000000 20.000000 X12 100.000000 0.000000 X13 0.000000 4

24、0.000000 X14 0.000000 20.000000 X21 30.000000 0.000000 X22 40.000000 0.000000 X23 0.000000 10.000000 X24 50.000000 0.000000 X31 50.000000 0.000000 X32 0.000000 20.000000 X33 30.000000 0.000000,運輸問題,總利潤 88700（元,供需平衡或不平衡,如何裝運，使本次飛行獲利最大,三個貨艙最大載重(t),最大容積(m3,例2 貨機裝運,三個貨艙中實際載重必須與其最大載重成比例,飛機平衡,模型假設,每種貨物可以分

25、割到任意小,每種貨物可以在一個或多個貨艙中任意分布,多種貨物可以混裝，并保證不留空隙,所給出的數(shù)據(jù)都是精確的，沒有誤差,第i種貨物的重量wi, 體積vi, 利潤pi (i=1,2,3,4,已知參數(shù),貨艙j的重量限制WETj , 體積限制VOLj, (j=1,2,3 分別代表前、中、后倉,貨艙容積,目標函數(shù)(利潤,約束條件,模型建立,貨艙重量,xij-第i 種貨物裝入第j 個貨艙的重量 i=1,2,3,4, j=1,2,3,決策變量,約束條件,平衡要求,貨物供應,模型建立,xij-第i 種貨物裝入第j 個貨艙的重量,j,k=1,2,3; jk,Global optimal solution fo

26、und. Objective value: 121515.8 Total solver iterations: 12 Variable Value Reduced Cost X( 1, 1) 0.000000 400.0000 X( 1, 2) 0.000000 57.89474 X( 1, 3) 0.000000 400.0000 X( 2, 1) 7.000000 0.000000 X( 2, 2) 0.000000 239.4737 X( 2, 3) 8.000000 0.000000 X( 3, 1) 3.000000 0.000000 X( 3, 2) 12.94737 0.0000

27、00 X( 3, 3) 0.000000 0.000000 X( 4, 1) 0.000000 650.0000 X( 4, 2) 3.052632 0.000000 X( 4, 3) 0.000000 650.0000,貨物2：前倉7,后倉8； 貨物3: 前倉3, 中倉13；貨物4: 中倉3,模型求解,最大利潤約121516元,貨物供應點 貨艙需求點,裝載平衡要求,如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)80輛， 那么最優(yōu)的生產(chǎn)計劃應作何改變,例1 汽車廠生產(chǎn)計劃,汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求，利潤及工廠每月的現(xiàn)有量,制訂月生產(chǎn)計劃，使工廠的利潤最大,4.3 汽

28、車生產(chǎn)與原油采購,設每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1, x2, x3,模型建立,線性規(guī)劃模型(LP,模型求解,3）模型中增加條件：x1, x2, x3 均為整數(shù)，重新求解,Objective Value: 632.2581 Variable Value Reduced Cost X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237 Row Slack or Surplus Dual Price 2 0.000000 0.731183 3 0.000000 0.003226,結果為小數(shù)，怎么辦,1）舍去小數(shù)：取

29、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)的解,但必須檢驗它們是否滿足約束條件. 為什么,IP可用LINGO直接求解,整數(shù)規(guī)劃(Integer Programming,簡記IP,IP 的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z=632,max=2*x1+3*x2+4*x3; 1.5*x1+3*x2+5*x3600; 280*x1+250*x2+400*x3 60000; gin(x1);gin(x2);gin(x3,Global o

30、ptimal solution found. Objective value: 632.0000 Extended solver steps: 0 Total solver iterations: 3 Variable Value Reduced Cost X1 64.00000 -2.000000 X2 168.0000 -3.000000 X3 0.000000 -4.000000,模型求解,IP 結果輸出,其中3個子模型應去掉，然后逐一求解，比較目標函數(shù)值，再加上整數(shù)約束，得最優(yōu)解,方法1：分解為8個LP子模型,若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃,x1,x2, x3=0 或 8

31、0,x1=80，x2= 150，x3=0，最優(yōu)值z=610,LINGO中對0-1變量的限定： bin(y1); bin(y2); bin(y3,方法2：引入0-1變量，化為整數(shù)規(guī)劃,M為大的正數(shù),本例可取1000,Objective Value: 610.0000 Variable 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)某類汽車

32、，則至少生產(chǎn)80輛，求生產(chǎn)計劃,x1=0 或 80,最優(yōu)解同前,max=2*x1+3*x2+4*x3; 1.5*x1+3*x2+5*x30; x2*(x2-80)0; x3*(x3-80)0; gin(x1);gin(x2);gin(x3,方法3：化為非線性規(guī)劃,非線性規(guī)劃（Non- Linear Programming，簡記NLP,若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃,x1=0 或 80,最優(yōu)解同前,一般地，整數(shù)規(guī)劃和非線性規(guī)劃的求解比線性規(guī)劃困難得多，特別是問題規(guī)模較大或者要求得到全局最優(yōu)解時,決策變量為整數(shù), 建立整數(shù)規(guī)劃模型,求解整數(shù)規(guī)劃和非線性規(guī)劃比線性規(guī)劃困難得多 (即便用

33、數(shù)學軟件),當整數(shù)變量取值很大時, 可作為連續(xù)變量處理, 問題簡化為線性規(guī)劃,對于類似于“x=0 或 80”這樣的條件，通常引入0-1變量處理，盡量不用非線性規(guī)劃（特別是引入的整數(shù)變量個數(shù)較少時,小結與評注,應如何安排原油的采購和加工 ,市場上可買到不超過1500t的原油A： 購買量不超過500t時的單價為10000元/t； 購買量超過500t但不超過1000t時，超過500t的 部分8000元/t； 購買量超過1000t時，超過1000t的部分6000元/t,例2 原油采購與加工,決策變量,目標函數(shù),問題分析,利潤：銷售汽油的收入購買原油A的支出. 難點：原油A的購價與購買量的關系較復雜,原

34、油A的購買量,原油A, B生產(chǎn)汽油甲,乙的數(shù)量,c(x) 購買原油A的支出,利潤(千元,c(x)如何表述,原油供應,約束條件,x 500，單價為10千元/t； 500 x 1000，超過500t的8千元/t； 1000 x 1500，超過1000t的6千元/t,目標函數(shù),汽油含原油A的比例限制,約束條件,目標函數(shù)中c(x)不是線性函數(shù)，是非線性規(guī)劃,對于用分段函數(shù)定義的c(x)，一般的非線性規(guī)劃 軟件也難以輸入和求解,想辦法將模型化簡，用現(xiàn)成的軟件求解,x1 , x2 , x3 以價格10, 8, 6(千元/t)采購A的噸數(shù),目標函數(shù),只有當以10千元/t的價格購買x1=500(t)時，才能以

35、8千元/t的價格購買x2,方法1,非線性規(guī)劃模型，可以用LINGO求解,模型求解,x= x1+x2+x3, c(x) = 10 x1+8x2+6x3,500 x 1000，超過500t的8千元/t,類似地有,方法1：LINGO求解,Local optimal solution found. Objective value: 4800.000 Total solver iterations: 14 Variable Value Reduced Cost X11 500.0000 0.000000 X21 500.0000 0.000000 X12 0.000000 0.2666667 X22 0

36、.000000 0.000000 X1 0.000000 0.4000000 X2 0.000000 0.000000 X3 0.000000 0.000000 X 0.000000 0.000000,LINGO得到的是局部最優(yōu)解,還能得到更好的解嗎,用庫存的500t原油A、500t原油B生產(chǎn)汽油甲，不購買新的原油A，利潤為4800千元,方法1：LINGO求解,計算全局最優(yōu)解 ： 選LINGO|Options菜單； 在彈出的選項卡中選擇“General Solver”； 然后找到選項“Use Global Solver”將其選中； 應用或保存；重新求解,Global optimal solut

37、ion found. Objective value: 5000.000 Extended solver steps: 1 Total solver iterations: 43 Variable Value Reduced Cost X11 0.000000 0.000000 X21 0.000000 0.900000 X12 1500.000 0.000000 X22 1000.000 0.000000 X1 500.0000 0.000000 X2 500.0000 0.000000 X3 0.000000 0.000000 X 1000.000 0.000000,還有其他建模和求解方法

38、嗎,購買1000t原油A，與庫存的500t原油A和1000t原油B一起，共生產(chǎn)2500t汽油乙，利潤為5000千元,y1, y2 , y3=1 以價格10, 8, 6(千元/t)采購A,增加約束,方法2,0-1線性規(guī)劃模型, 可用LINGO求解,y1,y2,y3 =0或1,購買1000t原油A，與庫存的500t原油A和1000t原油B一起，生產(chǎn)汽油乙，利潤為5000千元,x1 , x2 , x3 以價格10, 8, 6(千元/t)采購A的噸數(shù),與方法1（全局最優(yōu)解）的結果相同,引入0-1變量,模型求解,b1 b2 b3 b4,方法3,b1 xb2，x= z1b1+z2b2， z1+z2=1，z

39、1, z20, c(x)= z1c(b1)+z2c(b2,b2 x b3，x= z2b2+z3b3， z2+z3=1，z2, z3 0, c(x)= z2c(b2)+z3c(b3,b3 x b4，x= z3b3+z4b4， z3+z4=1，z3, z4 0, c(x)= z3c(b3)+z4c(b4,直接處理處理分段線性函數(shù)c(x,IP模型，LINGO求解，得到的結果與方法2相同,bkxbk+1yk=1,否則,yk=0,方法3,bkxbk+1 ,x= zkbk+z k+1 bk+1 zk+zk+1 =1，zk, zk+1 0, c(x)= zkc(bk)+zk+1 c(bk+1,對于k=1,2

40、,3,方法3: 直接處理分段線性函數(shù)，方法更具一般性,分段函數(shù)無法直接用非線性規(guī)劃方法或軟件求解,方法1: 增加約束化為非線性規(guī)劃,可以用LINGO 求解, 但可能得到的是局部最優(yōu)解,方法2: 引入0-1變量, 化為線性規(guī)劃模型, 可用 LINGO求解,小結與評注,分派問題,4.4 接力隊選拔和選課策略,若干項任務分給一些候選人來完成，每人的專長不同,完成每項任務取得的效益或需要的資源不同，如何分派任務使獲得的總效益最大，或付出的總資源最少,若干種策略供選擇，不同的策略得到的收益或付出的成本不同，各個策略之間有相互制約關系，如何在滿足一定條件下作出抉擇，使得收益最大或成本最小,如何選拔隊員組成

41、4100m混合泳接力隊,例1 混合泳接力隊的選拔,5名候選人4種泳姿的百米成績,窮舉法：組成接力隊的方案共有5!=120種,討論:丁的蛙泳成績退步到 ；戊的自由泳成績進步到 , 組成接力隊的方案是否應該調(diào)整,目標函數(shù),若選擇隊員i參加泳姿j 的比賽，記xij=1, 否則記xij=0,0-1規(guī)劃模型,cij隊員i第j 種泳姿的百米成績(s,約束條件,每人最多入選泳姿之一,每種泳姿有且只有1人,模型求解,最優(yōu)解：x14 = x21 = x32 = x43 = 1, 其他變量為0,LINGO求解,甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳,成績?yōu)?53.2(s),丁蛙泳c43 = 69.675.2 (

42、s)，戊自由泳c54= 62.4 57.5 (s), 方案是否調(diào)整,敏感性分析,新方案:乙 蝶泳、丙 仰泳、丁 蛙泳、戊 自由泳,IP一般沒有與LP相類似的理論，LINGO輸出的敏感性分析結果通常是沒有意義的,c43, c54 的新數(shù)據(jù)重新輸入模型，用LINGO求解,原分配方案: 甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳,討論,最優(yōu)解：x21 = x32 = x43 = x51 = 1, 成績?yōu)?混合泳接力隊的選拔,指派(Assignment)問題：有若干項任務, 每項任務必有且只能有一人承擔，每人只能承擔一項，不同人員承擔不同任務的效益(或成本)不同，怎樣分派各項任務使總效益最大(或總成本最

43、小),人員數(shù)量與任務數(shù)量相等,人員數(shù)量大于任務數(shù)量(本例,人員數(shù)量小于任務數(shù)量 ,建立0-1規(guī)劃模型是常用方法,為了選修課程門數(shù)最少，應學習哪些課程 ,要求至少選兩門數(shù)學課、三門運籌學課和兩門計算機課,選修課程最少，且學分盡量多，應學習哪些課程 ,例2 選課策略,0-1規(guī)劃模型,決策變量,目標函數(shù),xi=1 選修課號i 的課程（xi=0 不選,選修課程總數(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,

44、模型求解（LINGO,學分最多,多目標優(yōu)化的處理方法：化成單目標優(yōu)化,兩目標(多目標)規(guī)劃,討論：選修課程最少，學分盡量多，應學習哪些課程,課程最少,以學分最多為目標,不管課程多少,以課程最少為目標,不管學分多少,多目標規(guī)劃,在課程最少的前提下以學分最多為目標,最優(yōu)解： x1 = x2 = x3 = x5 = x7 = x9 =1, 其他為0；總學分由21增至22,注意：最優(yōu)解不唯一,LINGO不能告訴優(yōu)化問題的解是否唯一,可將x9 =1 易為x6 =1,多目標規(guī)劃,對學分數(shù)和課程數(shù)加權形成一個目標，如三七開,最優(yōu)解： x1 = x2 = x3 = x4 = x5 = x6 = x7 = x9

45、 =1， 其他為0；總學分28,討論與思考,最優(yōu)解與1=0，2=1的結果相同學分最多,多目標規(guī)劃,最優(yōu)解與1=1，2=0的結果相同課程最少,選 課 策 略,用0-1變量表示策略選擇是常用的方法,要選甲 (x1)必選乙 (x2)” 可用x1 x2描述,要選甲 (x1)必不選乙 (x2)” 怎樣描述,甲乙二人至多選一人” 怎樣描述,甲乙二人至少選一人” 怎樣描述,雙(多)目標規(guī)劃的處理方法,加權組合成一個新目標, 化為單目標規(guī)劃,一個目標作為約束, 解另一個目標的規(guī)劃,4.5 飲料廠的生產(chǎn)與檢修,單階段生產(chǎn)計劃,多階段生產(chǎn)計劃,生產(chǎn)批量問題,企業(yè)生產(chǎn)計劃,考慮與產(chǎn)量無關的固定費用,給優(yōu)化模型求解帶

46、來新的困難,安排生產(chǎn)計劃, 滿足每周的需求, 使4周總費用最小,存貯費:每周每千箱飲料 0.2 (千元,例1 飲料廠的生產(chǎn)與檢修計劃,4周內(nèi)安排一次設備檢修,占用當周15千箱生產(chǎn)能力, 能使檢修后每周增產(chǎn)5千箱,檢修應排在哪一周,某種飲料4周的需求量、生產(chǎn)能力和成本,問題分析,除第4周外每周的生產(chǎn)能力超過每周的需求； 生產(chǎn)成本逐周上升； 前幾周應多生產(chǎn)一些,飲料廠在第1周開始時沒有庫存； 從費用最小考慮, 第4周末不能有庫存； 周末有庫存時需支出一周的存貯費； 每周末的庫存量等于下周初的庫存量,模型假設,目標函數(shù),約束條件,產(chǎn)量、庫存與需求平衡,決策變量,能力限制,非負限制,模型建立,x1 x

47、4：第14周的生產(chǎn)量,y1 y3：第13周末庫存量,存貯費:0.2(千元/周千箱,模型求解,4周生產(chǎn)計劃的總費用為528 (千元,最優(yōu)解： x1 x4：15，40，25，20； y1 y3： 0，15，5,LINGO求解,討論,增加庫存量(y1 y3)為決策變量使模型清晰并便于檢查,檢修計劃,0-1變量wt ：wt=1 檢修安排在第t周(t=1,2,3,4,在4周內(nèi)安排一次設備檢修,占用當周15千箱生產(chǎn)能力,能使檢修后每周增產(chǎn)5千箱，檢修應排在哪一周,檢修安排在任一周均可,約束條件,能力限制,產(chǎn)量、庫存與需求平衡條件不變,增加約束條件：檢修1次,檢修計劃,目標函數(shù)不變,0-1變量 wt=1 檢

48、修安排在第t周,LINGO求解,總費用由528降為527(千元,檢修所導致的生產(chǎn)能力提高的作用, 需要更長的時間才能得到充分體現(xiàn),最優(yōu)解：w1=1, w2 , w3, w4=0; x1 x4：15,45,15,25； y1 y3：0,20,0,討論,引入0-1變量表示檢修,例2 飲料的生產(chǎn)批量問題,安排生產(chǎn)計劃, 滿足每周的需求, 使4周總費用最小,存貯費:每周每千箱飲料 0.2 (千元) (與例1同),飲料廠使用同一條生產(chǎn)線輪流生產(chǎn)多種飲料. 若某周開工生產(chǎn)某種飲料, 需支出生產(chǎn)準備費8千元,某種飲料4周的需求量、生產(chǎn)能力和成本(與例1同,ct 時段t 生產(chǎn)費用(元/件);ht 時段t (末

49、)存貯費(元/件) st 時段t 生產(chǎn)準備費(元)；dt 時段t 市場需求(件)； Mt 時段t 生產(chǎn)能力(件,假設初始庫存為0,制訂生產(chǎn)計劃, 滿足需求并使T個時段的總費用最小,決策變量,xt 時段t 生產(chǎn)量；yt 時段t (末)存貯量,問題分析,與例1的主要差別,需考慮與生產(chǎn)數(shù)量無關的費用生產(chǎn)準備費,模型建立,wt =1 時段t 開工生產(chǎn) (wt =0 不開工,混合0-1規(guī)劃模型,目標函數(shù),約束條件,模型建立,ct 生產(chǎn)費,ht 存貯費,st 準備費,dt 需求量, Mt 生產(chǎn)能力,xt 生產(chǎn)量,yt 存貯量,wt 開工生產(chǎn)0-1變量,滿足需求,既含可變費用(生產(chǎn)成本、存貯費)又含固定費用

50、(生產(chǎn)準備費)的多階段生產(chǎn)計劃問題,最優(yōu)解：x1 x4：15，40，45，0；總費用：554.0(千元,將所給參數(shù)代入模型，用LINGO求解,模型求解,與例1的最優(yōu)解： x1 x4：15,45,15,25 的區(qū)別,生產(chǎn)批量(lot-sizing)問題,關鍵是引入0-1變量wt表示時段t是否開工生產(chǎn),生產(chǎn)中通過切割、剪裁、沖壓等手段，將原材料加工成規(guī)定大小的成材,4.6 鋼管和易拉罐下料,原料下料問題,優(yōu)化問題: 按照工藝要求，確定下料方案，使所用材料最省，或利潤最大,問題1. 如何下料最節(jié)省 ,例1 鋼管下料,問題2. 客戶增加需求,節(jié)省的標準是什么,由于采用不同切割模式太多, 會增加生產(chǎn)和管

51、理成本,規(guī)定切割模式不能超過3種. 如何下料最節(jié)省,按照客戶需要在一根原料鋼管上安排切割的一種組合,如,切割模式,合理切割模式的余料應小于客戶需要鋼管的最小尺寸,鋼管下料,為滿足客戶需要，按照哪些種合理模式切割，每種模式切割多少根原料鋼管，最為節(jié)省,合理切割模式,2. 所用原料鋼管總根數(shù)最少,鋼管下料問題1,節(jié)省的 兩種標準,1. 原料鋼管剩余總余量最小,xi 按第i 種模式切割的原料鋼管根數(shù)(i=1,7,約束,滿足需求,決策變量,目標1（總余量,按模式2切割12根,按模式5切割15根,共27根,余料27m,最優(yōu)解：x2=12, x5=15, 其余為0； 最優(yōu)值：27,整數(shù)約束： xi 為整數(shù)

52、,目標2（總根數(shù),鋼管下料問題1,約束條件不變,最優(yōu)解：x2=15, x5=5, x7=5, 其余為0； 最優(yōu)值：25,xi 為整數(shù),按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35m,目標2切割減少了2根, 但余料增加8m, 為什么,與目標1的結果“共切割27根，余料27m” 相比,若余料沒有用處, 通常以總根數(shù)最少為目標,鋼管下料問題1,目標1(總余量) x2=12, x5=15, 共27根,余27m,目標2(總根數(shù)) x2=15, x5=5, x7=5, 共25根, 余35m,按照目標1比需求多生產(chǎn)1根4m、7根6m, 共46m, 正好等于2根原料(38m)再加

53、8m,原料鋼管:每根19m,若多生產(chǎn)的也視為余料, 則總余量最小等價于總根數(shù)最少,鋼管下料問題2,對大規(guī)模問題，用模型的約束條件界定合理模式,增加一種需求：10根5m ；切割模式不超過3種,現(xiàn)有4種需求：50根4m, 10根5m, 20根6m,15根8m，用枚舉法確定合理切割模式，過于復雜,決策變量,xi 按第i 種模式切割的原料鋼管根數(shù)(i=1,2,3,r1i, r2i, r3i, r4i 第i 種切割模式下，每根原料鋼管生產(chǎn)4m、5m、6m和8m長的鋼管的數(shù)量,滿足需求,模式合理：每根余料不超過3m,整數(shù)非線性規(guī)劃模型,鋼管下料問題2,目標函數(shù)（總根數(shù),約束條件,整數(shù)約束： xi ,r1i

54、, r2i, r3i, r4i (i=1,2,3)為整數(shù),增加約束，縮小可行域，便于求解,原料鋼管總根數(shù)下界,特殊生產(chǎn)計劃：對每根原料鋼管 模式1：切割成4根4m鋼管，需13根； 模式2：切割成1根5m和2根6m鋼管，需10根； 模式3：切割成2根8m鋼管，需8根. 原料鋼管總根數(shù)上界：13+10+8=31,模式排列順序可任定,鋼管下料問題2,需求：50根4m，10根5m，20根6m，15根8m,每根原料鋼管長19m,LINGO求解整數(shù)非線性規(guī)劃模型,Local optimal solution found. Objective value: 28.00000 Variable Value R

55、educed Cost X( 1) 10.00000 1.000000 X( 2) 10.00000 1.000000 X( 3) 8.000000 1.000000 R( 1, 1) 3.000000 0.000000 R( 1, 2) 2.000000 0.000000 R( 1, 3) 0.000000 0.000000 R( 2, 1) 0.000000 0.000000 R( 2, 2) 1.000000 0.000000 R( 2, 3) 0.000000 0.000000 R( 3, 1) 1.000000 0.000000 R( 3, 2) 1.000000 0.000000

56、R( 3, 3) 0.000000 0.000000 R( 4, 1) 0.000000 0.000000 R( 4, 2) 0.000000 0.000000 R( 4, 3) 2.000000 0.000000,也是全局最優(yōu)解 模式1：每根原料鋼管切割成 3根4m和1根6m鋼管, 共10根; 模式2：每根原料鋼管切割成 2根4m、1根5m和1根6m鋼管，共10根； 模式3：每根原料鋼管切割成 2根8m鋼管，共8根. 原料鋼管總根數(shù)為28根,板材規(guī)格2： 長方形， 3228cm， 2萬張,例2 易拉罐下料,每周工作40h，每只易拉罐利潤0.10元，原料余料損失0.001元 / cm2(不能裝

57、配的罐身、蓋、底也是余料,罐身高10cm，上蓋、下底直徑均5cm,板材規(guī)格1： 正方形，邊長24cm，5萬張,如何安排每周生產(chǎn),模式1: 正方形 邊長24cm,問題分析,計算各種模式下的余料損失,上、下底直徑d=5cm，罐身高h=10cm,模式1 余料損失: 242-10d2/4 - dh=222.6 cm2,問題分析,目標:易拉罐利潤扣除原料余料損失后的凈利潤最大,約束：每周工作時間不超過40h； 原料數(shù)量：規(guī)格1（模式1 3）5萬張， 規(guī)格2（模式4）2萬張； 罐身和底、蓋的配套組裝,注意：不能裝配的罐身、上下底也是余料,決策變量,xi 按照第i 種模式的生產(chǎn)張數(shù)(i=1,2,3,4)；

58、y1 一周生產(chǎn)的易拉罐個數(shù)； y2 不配套的罐身個數(shù)； y3 不配套的底、蓋個數(shù),模型建立,目標,約束條件,時間約束,原料約束,模型建立,y1 易拉罐個數(shù)；y2 不配套的罐身； y3 不配套的底、蓋,每只易拉罐利潤0.10元，余料損失0.001元 / cm2,罐身面積dh=157.1 cm2 底蓋面積d2/4=19.6 cm2,40h,約束條件,配套約束,y1 易拉罐個數(shù)；y2 不配套的罐身； y3 不配套的底、蓋,雖然xi和y1，y2，y3應是整數(shù)，但是因生產(chǎn)量很大，可以把它們看成實數(shù)，從而用線性規(guī)劃模型處理,將所有決策變量擴大10000倍（xi 萬張，yi 萬件,數(shù)據(jù)之間的數(shù)量級差別太大，

59、可以進行預處理，縮小數(shù)據(jù)之間的差別，便于減少計算誤差,模式2生產(chǎn)40125張， 模式3生產(chǎn)3750張， 模式4生產(chǎn)20000張， 共產(chǎn)易拉罐160250個 (罐身和底、蓋無剩余)， 凈利潤為4298元,模型求解,Objective value: 0.4298337 Variable Value Reduced Cost Y1 16.02500 0.000000 X1 0.000000 0.000050 X2 4.012500 0.000000 X3 0.3750000 0.000000 X4 2.000000 0.000000 Y2 0.000000 0.2233312 Y3 0.000000 0.0364844,下料問題的建模,確定下料模式,構造優(yōu)化模型,規(guī)格不太多，可枚舉下料模式，建立整數(shù)線性規(guī)劃模型，否則要構造整數(shù)非線性規(guī)劃模型，求解困難，可用縮小可行域的方法進行化簡，但要保證最優(yōu)解的存在,一維問題（如鋼管下料,二維問題（如