第四章數(shù)學規(guī)劃ppt課件

1、第四章第四章 數(shù)學規(guī)劃數(shù)學規(guī)劃 (Lindo )(Lindo )優(yōu)化模型優(yōu)化模型 數(shù)學規(guī)劃數(shù)學規(guī)劃Lindo Matlab LingoLindo Matlab Lingo實踐問題中實踐問題中的優(yōu)化模型的優(yōu)化模型mixgtsxxxxfzMaxMiniTn, 2 , 1, 0)(. .),(),()(1或x決策變量決策變量f(x)目的函數(shù)目的函數(shù)gi(x)0約束條約束條件件數(shù)學規(guī)劃數(shù)學規(guī)劃線性規(guī)劃線性規(guī)劃(LP)二次規(guī)劃二次規(guī)劃(QP)非線性規(guī)劃非線性規(guī)劃(NLP)純整數(shù)規(guī)劃純整數(shù)規(guī)劃(PIP)混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃(MIP)整數(shù)規(guī)劃整數(shù)規(guī)劃(IP)0-1整數(shù)規(guī)劃整數(shù)規(guī)劃普通整數(shù)規(guī)劃普通整數(shù)規(guī)劃

2、延續(xù)規(guī)劃延續(xù)規(guī)劃LINDO LINDO 公司軟件產(chǎn)品簡要引見公司軟件產(chǎn)品簡要引見 美國芝加哥美國芝加哥(Chicago)大學的大學的Linus Schrage教授于教授于1980年前后開發(fā)年前后開發(fā), 后來成立后來成立 LINDO系統(tǒng)公司系統(tǒng)公司LINDO Systems Inc.， lindo LINDO: Linear INteractive and Discrete Optimizer (V6.1)LINGO: Linear INteractive General Optimizer (V8.0)LINDO API: LINDO Application Programming Inter

3、face (V2.0)Whats Best!: (SpreadSheet e.g. EXCEL) (V7.0)演示演示(試用試用)版、學生版、高級版、超級版、工業(yè)版、版、學生版、高級版、超級版、工業(yè)版、擴展版擴展版 求解問題規(guī)模和選件不同求解問題規(guī)模和選件不同LINDOLINDO和和LINGOLINGO軟件能求解的優(yōu)化模型軟件能求解的優(yōu)化模型 LINGO LINDO優(yōu)化模型優(yōu)化模型線性規(guī)劃線性規(guī)劃(LP)非線性規(guī)劃非線性規(guī)劃(NLP)二次規(guī)劃二次規(guī)劃(QP)延續(xù)優(yōu)化延續(xù)優(yōu)化整數(shù)規(guī)劃整數(shù)規(guī)劃(IP) LP QP NLP IP 全局優(yōu)化全局優(yōu)化(選選) ILP IQP INLP LINDO/LIN

4、GO軟件的求解過程 LINDO/LINGO預處置程序預處置程序線性優(yōu)化求解程序線性優(yōu)化求解程序非線性優(yōu)化求解程序非線性優(yōu)化求解程序分枝定界管理程序分枝定界管理程序1. 確定常數(shù)確定常數(shù)2. 識別類型識別類型1. 單純形算法單純形算法2. 內點算法內點算法(選選)1、順序線性規(guī)劃法、順序線性規(guī)劃法(SLP) 2、廣義既約梯度法、廣義既約梯度法(GRG) (選選) 3、多點搜索、多點搜索(Multistart) (選選) 建模時需求留意的幾個根本問題建模時需求留意的幾個根本問題 1、盡量運用實數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量、盡量運用實數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量2、盡量運用光滑優(yōu)化，減少非光滑約

5、束的個數(shù)、盡量運用光滑優(yōu)化，減少非光滑約束的個數(shù) 如：盡量少運用絕對值、符號函數(shù)、多個變量求如：盡量少運用絕對值、符號函數(shù)、多個變量求最大最大/最小值、四舍五入、取整函數(shù)等最小值、四舍五入、取整函數(shù)等3、盡量運用線性模型，減少非線性約束和非線性變、盡量運用線性模型，減少非線性約束和非線性變量的個數(shù)量的個數(shù) 如如x/y 5 改為改為x5y4、合理設定變量上下界，盡能夠給出變量初始值、合理設定變量上下界，盡能夠給出變量初始值 5、模型中運用的參數(shù)數(shù)量級要適當、模型中運用的參數(shù)數(shù)量級要適當 (如小于如小于103)需求掌握的幾個重要方面需求掌握的幾個重要方面1、LINDO: 正確閱讀求解報告尤其要掌握

6、敏感性分析正確閱讀求解報告尤其要掌握敏感性分析2、LINGO： 掌握集合掌握集合(SETS)的運用；的運用；正確閱讀求解報告；正確閱讀求解報告；正確了解求解形狀窗口；正確了解求解形狀窗口； 學會設置根本的求解選項學會設置根本的求解選項(OPTIONS) ； 掌握與外部文件的根本接口方法掌握與外部文件的根本接口方法企業(yè)消費方案企業(yè)消費方案4.1 奶制品的消費與銷售奶制品的消費與銷售 空間層次空間層次工廠級：根據(jù)外部需求和內部設備、人力、原料等工廠級：根據(jù)外部需求和內部設備、人力、原料等條件，以最大利潤為目的制定產(chǎn)品消費方案；條件，以最大利潤為目的制定產(chǎn)品消費方案；車間級：根據(jù)消費方案、工藝流程、

7、資源約束及費車間級：根據(jù)消費方案、工藝流程、資源約束及費用參數(shù)等，以最小本錢為目的制定消費批量方案。用參數(shù)等，以最小本錢為目的制定消費批量方案。時間層次時間層次假設短時間內外部需求和內部資源等不隨時間變化，假設短時間內外部需求和內部資源等不隨時間變化，可制定單階段消費方案，否那么應制定多階段消費方可制定單階段消費方案，否那么應制定多階段消費方案。案。本節(jié)課題本節(jié)課題例例1 加工奶制品的消費方案加工奶制品的消費方案1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶桶牛奶 時間時間480小時小時 至多加工至多加工100公斤公斤A1 制定消費方案，使

8、每天獲利最大制定消費方案，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？假設買，每天最多買多桶牛奶，買嗎？假設買，每天最多買多少少? 可聘用暫時工人，付出的工資最多是每小時幾元可聘用暫時工人，付出的工資最多是每小時幾元? A1的獲利添加到的獲利添加到 30元元/公斤，應否改動消費方案？公斤，應否改動消費方案？ 每天：每天：1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 x1桶牛奶消費桶牛奶消費A1 x2桶牛奶消費桶牛奶消費A2 獲利獲利 243x1 獲利獲利 164 x2 原料供應原料供應 5021 xx勞動時間勞動時間 48081221 xx加

9、工才干加工才干 10031x決策變量決策變量 目的函數(shù)目的函數(shù) 216472xxzMax每天獲利每天獲利約束條件約束條件非負約束非負約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)時間時間480小時小時 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天模型分析與假設模型分析與假設 比比例例性性 可可加加性性 延續(xù)性延續(xù)性 xi對目的函數(shù)的對目的函數(shù)的“奉獻與奉獻與xi取值取值成正比成正比 xi對約束條件的對約束條件的“奉獻與奉獻與xi取值取值成正比成正比 xi對目的函數(shù)的對目的函數(shù)的“奉獻與奉獻與xj取值取值無關無關 xi對約束條件的對約束條件的“奉獻與奉獻與xj取值取值無關無

10、關 xi取值延續(xù)取值延續(xù) A1,A2每公斤的獲利是與各每公斤的獲利是與各自產(chǎn)量無關的常數(shù)自產(chǎn)量無關的常數(shù)每桶牛奶加工出每桶牛奶加工出A1,A2的數(shù)量的數(shù)量和時間是與各自產(chǎn)量無關的常和時間是與各自產(chǎn)量無關的常數(shù)數(shù)A1,A2每公斤的獲利是與相每公斤的獲利是與相互產(chǎn)量無關的常數(shù)互產(chǎn)量無關的常數(shù)每桶牛奶加工出每桶牛奶加工出A1,A2的數(shù)量的數(shù)量和時間是與相互產(chǎn)量無關的常和時間是與相互產(chǎn)量無關的常數(shù)數(shù)加工加工A1,A2的牛奶桶數(shù)是實的牛奶桶數(shù)是實數(shù)數(shù) 線性規(guī)劃模型線性規(guī)劃模型模型求解模型求解 圖解法圖解法 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx

11、約約束束條條件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472xxzMax目的目的函數(shù)函數(shù) Z=0Z=2400Z=3600z=c (常數(shù)常數(shù)) 等值線等值線c在在B(20,30)點得到最優(yōu)解點得到最優(yōu)解目的函數(shù)和約束條件是線性函數(shù)目的函數(shù)和約束條件是線性函數(shù) 可行域為直線段圍成的凸多邊形可行域為直線段圍成的凸多邊形 目的函數(shù)的等值線為直線目的函數(shù)的等值線為直線 最優(yōu)解一定在凸多邊最優(yōu)解一定在凸多邊形的某個頂點獲得。形的某個頂點獲得。 模型求解模型求解 軟件實現(xiàn)軟件實現(xiàn) LINDO 6.1 max 72x1+64x2st2x1+x250

12、312x1+8x248043x1100end OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2DO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶消費桶牛奶消費A1, 30

13、桶消費桶消費A2，利潤，利潤3360元。元。 結果解釋結果解釋 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2原料無剩余原料無剩余時間無剩余時間無剩余加工才干剩余加工才干剩余40max 72x1+6

14、4x2st2x1+x250312x1+8x248043x1100end三三種種資資源源“資源資源 剩余為零的約束為緊約束有效約束剩余為零的約束為緊約束有效約束 模型求解模型求解 reduced cost值表值表示當該非基變量示當該非基變量添加一個單位時添加一個單位時其他非基變量其他非基變量堅持不變目的堅持不變目的函數(shù)減少的量函數(shù)減少的量(對對max型問題型問題) OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLAC

15、K OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2也可了解為：也可了解為：為了使該非基變?yōu)榱耸乖摲腔兞孔兂苫兞?，量變成基變量，目的函?shù)中對應目的函數(shù)中對應系數(shù)應添加的量系數(shù)應添加的量結果解釋結果解釋 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLA

16、CK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2最優(yōu)解下最優(yōu)解下“資源添加資源添加1單位時單位時“效益的增量效益的增量 原料添加原料添加1單位單位, 利潤增長利潤增長48 時間添加時間添加1單位單位, 利潤增長利潤增長2 加工才干增長不影響利潤加工才干增長不影響利潤影子價錢影子價錢 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？35 或或“=或或“=功能一樣功能一樣變量與系數(shù)間可有空格變量與系數(shù)間可有空格(甚至回車甚至回

17、車), 但無運算符但無運算符變量名以字母開頭，不能超越變量名以字母開頭，不能超越8個字符個字符變量名不區(qū)分大小寫包括變量名不區(qū)分大小寫包括LINDO中的關鍵字中的關鍵字目的函數(shù)所在行是第一行，第二行起為約束條件目的函數(shù)所在行是第一行，第二行起為約束條件行號行號(行名行名)自動產(chǎn)生或人為定義。行名以自動產(chǎn)生或人為定義。行名以“終終了了行中注有行中注有“!符號的后面部分為注釋。如符號的后面部分為注釋。如: ! Its Comment.在模型的任何地方都可以用在模型的任何地方都可以用“TITLE 對模型命名對模型命名最多最多72個字符，如：個字符，如： TITLE This Model is onl

18、y an Example變量不能出如今一個約束條件的右端變量不能出如今一個約束條件的右端表達式中不接受括號表達式中不接受括號“( )和逗號和逗號“,等任何符號等任何符號, 例例: 400(X1+X2)需寫為需寫為400X1+400X2表達式應化簡，如表達式應化簡，如2X1+3X2- 4X1應寫成應寫成 -2X1+3X2缺省假定一切變量非負；可在模型的缺省假定一切變量非負；可在模型的“END語句語句后用后用“FREE name將變量將變量name的非負假定取消的非負假定取消可在可在 “END后用后用“SUB 或或“SLB 設定變量上設定變量上下界下界 例如：例如： “sub x1 10的作用等價

19、于的作用等價于“x1ui 交易費 = piui xiui而題目所給定的定值 ui(單位:元)相對總投資 M 很小, piui更小,可以忽略不計,這樣購買 Si的凈收益為(ri-pi)xi 3要使凈收益盡可能大，總體風險盡可能小,這是一個多目標規(guī)劃模型: 目標函數(shù) MAXniiiixpr0)( MINmax qixi 約束條件 niiixp0)1 (=M xi0 i=0,1,n4. 模型簡化：c投資者在權衡資產(chǎn)風險和預期收益兩方面時，希望選擇一個令自己滿意的投資組合。因此對風險、收益賦予權重 s（0s1)，s 稱為投資偏好系數(shù).模模型型 3 目標函數(shù)：min smaxqixi -（1-s）nii

20、iixpr0)( 約束條件 niiixp0)1 (=M， xi0 i=0,1,2,nb若投資者希望總盈利至少達到水平k 以上，在風險最小的情況下尋找相應的投資組合。模模型型2 固定盈利水平，極小化風險 目標函數(shù)： R= minmax qixi 約束條件：niiiixpr0)(k， Mxpii)1 ( ， xi 0 i=0，1，na 在實際投資中，投資者承受風險的程度不一樣，若給定風險一個界限 a，使最大的一個風險 qixi/Ma，可找到相應的投資方案。這樣把多目標規(guī)劃變成一個目標的線性規(guī)劃。模型模型 1 1 固定風險水平，優(yōu)化收益 目標函數(shù)： Q=MAX11)(niiiixpr 約束條件： M

21、xqiia Mxpii)1 (， xi 0 i=0，1，n四、模型四、模型1 1的求解的求解 模型1為: minf = (-0.05, -0.27, -0.19, -0.185, -0.185) (x0 x1 x2 x3 x 4 ) T x0 + 1.01x1 + 1.02x2 +1.045x3 +1.065x4 =1s.t. 0.025x1 a 0.015x2 a 0.055x3 a 0.026x4a xi 0 (i = 0,1,.4) 由于a是恣意給定的風險度，究竟怎樣給定沒有一個準那么，不同的投資者有不同的風險度。我們從a=0開場，以步長a=0.001進展循環(huán)搜索，編制程序如下：a=0;

22、while(1.1-a)1 c=-0.05 -0.27 -0.19 -0.185 -0.185; Aeq=1 1.01 1.02 1.045 1.065; beq=1; A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026; b=a;a;a;a; vlb=0,0,0,0,0;vub=; x,val=linprog(c,A,b,Aeq,beq,vlb,vub); a x=x Q=-val plot(a,Q,.)，axis(0 0.1 0 0.5)，hold on a=a+0.001;end xlabel(a),ylabel(Q)To

23、Matlabxxgh5a = 0.0030 x = 0.4949 0.1200 0.2000 0.0545 0.1154 Q = 0.1266a = 0.0060 x = 0 0.2400 0.4000 0.1091 0.2212 Q = 0.2019a = 0.0080 x = 0.0000 0.3200 0.5333 0.1271 0.0000 Q = 0.2112a = 0.0100 x = 0 0.4000 0.5843 0 0 Q =0.2190a = 0.0200 x = 0 0.8000 0.1882 0 0 Q =0.2518 a = 0.0400 x = 0.0000 0.9901 0.0000 0 0 Q =0.2673計算結果：計算結果：五、五、 結果分析結果分析返 回4.4.在在a=0.006a=0.006附近有一個轉機點，在這一點左邊，風險添加很少時，利潤增長附近有一個轉機點，在這一點左邊，風險添加很少時，利潤增長 很快。在這一點右邊，風險添加很大時，利潤增長很緩慢，