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

1、第四章第四章 數(shù)學(xué)規(guī)劃數(shù)學(xué)規(guī)劃 (Lindo )(Lindo )優(yōu)化模型優(yōu)化模型 數(shù)學(xué)規(guī)劃數(shù)學(xué)規(guī)劃Lindo Matlab LingoLindo Matlab Lingo實(shí)踐問題中實(shí)踐問題中的優(yōu)化模型的優(yōu)化模型mixgtsxxxxfzMaxMiniTn, 2 , 1, 0)(. .),(),()(1或x決策變量決策變量f(x)目的函數(shù)目的函數(shù)gi(x)0約束條約束條件件數(shù)學(xué)規(guī)劃數(shù)學(xué)規(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)大學(xué)的大學(xué)的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)演示演示(試用試用)版、學(xué)生版、高級版、超級版、工業(yè)版、版、學(xué)生版、高級版、超級版、工業(yè)版、擴(kuò)展版擴(kuò)展版 求解問題規(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ù)處置程序預(yù)處置程序線性優(yōu)化求解程序線性優(yōu)化求解程序非線性優(yōu)化求解程序非線性優(yōu)化求解程序分枝定界管理程序分枝定界管理程序1. 確定常數(shù)確定常數(shù)2. 識別類型識別類型1. 單純形算法單純形算法2. 內(nèi)點(diǎn)算法內(nèi)點(diǎn)算法(選選)1、順序線性規(guī)劃法、順序線性規(guī)劃法(SLP) 2、廣義既約梯度法、廣義既約梯度法(GRG) (選選) 3、多點(diǎn)搜索、多點(diǎn)搜索(Multistart) (選選) 建模時需求留意的幾個根本問題建模時需求留意的幾個根本問題 1、盡量運(yùn)用實(shí)數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量、盡量運(yùn)用實(shí)數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量2、盡量運(yùn)用光滑優(yōu)化，減少非光滑約

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

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

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

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

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

10、關(guān) xi取值延續(xù)取值延續(xù) A1,A2每公斤的獲利是與各每公斤的獲利是與各自產(chǎn)量無關(guān)的常數(shù)自產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工出每桶牛奶加工出A1,A2的數(shù)量的數(shù)量和時間是與各自產(chǎn)量無關(guān)的常和時間是與各自產(chǎn)量無關(guān)的常數(shù)數(shù)A1,A2每公斤的獲利是與相每公斤的獲利是與相互產(chǎn)量無關(guān)的常數(shù)互產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工出每桶牛奶加工出A1,A2的數(shù)量的數(shù)量和時間是與相互產(chǎn)量無關(guān)的常和時間是與相互產(chǎn)量無關(guān)的常數(shù)數(shù)加工加工A1,A2的牛奶桶數(shù)是實(shí)的牛奶桶數(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)點(diǎn)得到最優(yōu)解點(diǎn)得到最優(yōu)解目的函數(shù)和約束條件是線性函數(shù)目的函數(shù)和約束條件是線性函數(shù) 可行域?yàn)橹本€段圍成的凸多邊形可行域?yàn)橹本€段圍成的凸多邊形 目的函數(shù)的等值線為直線目的函數(shù)的等值線為直線 最優(yōu)解一定在凸多邊最優(yōu)解一定在凸多邊形的某個頂點(diǎn)獲得。形的某個頂點(diǎn)獲得。 模型求解模型求解 軟件實(shí)現(xiàn)軟件實(shí)現(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桶牛奶消費(fèi)桶牛奶消費(fèi)A1, 30

13、桶消費(fèi)桶消費(fèi)A2，利潤，利潤3360元。元。 結(jié)果解釋結(jié)果解釋 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值表值表示當(dāng)該非基變量示當(dāng)該非基變量添加一個單位時添加一個單位時其他非基變量其他非基變量堅(jiān)持不變目的堅(jiān)持不變目的函數(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ù)中對應(yīng)目的函數(shù)中對應(yīng)系數(shù)應(yīng)添加的量系數(shù)應(yīng)添加的量結(jié)果解釋結(jié)果解釋 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、車), 但無運(yùn)算符但無運(yùn)算符變量名以字母開頭，不能超越變量名以字母開頭，不能超越8個字符個字符變量名不區(qū)分大小寫包括變量名不區(qū)分大小寫包括LINDO中的關(guān)鍵字中的關(guān)鍵字目的函數(shù)所在行是第一行，第二行起為約束條件目的函數(shù)所在行是第一行，第二行起為約束條件行號行號(行名行名)自動產(chǎn)生或人為定義。行名以自動產(chǎn)生或人為定義。行名以“終終了了行中注有行中注有“!符號的后面部分為注釋。如符號的后面部分為注釋。如: ! Its Comment.在模型的任何地方都可以用在模型的任何地方都可以用“TITLE 對模型命名對模型命名最多最多72個字符，如：個字符，如： TITLE This Model is onl

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

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

20、iixpr0)( 約束條件 niiixp0)1 (=M， xi0 i=0,1,2,nb若投資者希望總盈利至少達(dá)到水平k 以上，在風(fēng)險(xiǎn)最小的情況下尋找相應(yīng)的投資組合。模模型型2 固定盈利水平，極小化風(fēng)險(xiǎn) 目標(biāo)函數(shù)： R= minmax qixi 約束條件：niiiixpr0)(k， Mxpii)1 ( ， xi 0 i=0，1，na 在實(shí)際投資中，投資者承受風(fēng)險(xiǎn)的程度不一樣，若給定風(fēng)險(xiǎn)一個界限 a，使最大的一個風(fēng)險(xiǎn) qixi/Ma，可找到相應(yīng)的投資方案。這樣把多目標(biāo)規(guī)劃變成一個目標(biāo)的線性規(guī)劃。模型模型 1 1 固定風(fēng)險(xiǎn)水平，優(yōu)化收益 目標(biāo)函數(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是恣意給定的風(fēng)險(xiǎn)度，究竟怎樣給定沒有一個準(zhǔn)那么，不同的投資者有不同的風(fēng)險(xiǎn)度。我們從a=0開場，以步長a=0.001進(jìn)展循環(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計(jì)算結(jié)果：計(jì)算結(jié)果：五、五、 結(jié)果分析結(jié)果分析返 回4.4.在在a=0.006a=0.006附近有一個轉(zhuǎn)機(jī)點(diǎn)，在這一點(diǎn)左邊，風(fēng)險(xiǎn)添加很少時，利潤增長附近有一個轉(zhuǎn)機(jī)點(diǎn)，在這一點(diǎn)左邊，風(fēng)險(xiǎn)添加很少時，利潤增長 很快。在這一點(diǎn)右邊，風(fēng)險(xiǎn)添加很大時，利潤增長很緩慢，