常見優(yōu)化模型

1、編輯ppt常見優(yōu)化模型常見優(yōu)化模型東北大學(xué)東北大學(xué)應(yīng)用數(shù)學(xué)應(yīng)用數(shù)學(xué)王琪王琪編輯ppt常見優(yōu)化模型 線性規(guī)劃 整數(shù)規(guī)劃 非線性規(guī)劃編輯ppt 線性規(guī)劃 線性規(guī)劃的標(biāo)準(zhǔn)形式：可以采用的解決方法：編輯ppt問題一 加工費(fèi)用最低 問題一問題一 ： 任務(wù)分配問題：某車間有甲、乙兩臺(tái)機(jī)床，可用于加工三種工件。假定這兩臺(tái)車床的可用臺(tái)時(shí)數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺(tái)時(shí)數(shù)和加工費(fèi)用如下表。問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費(fèi)用最低？ 單位工件所需加工臺(tái)時(shí)數(shù) 單位工件的加工費(fèi)用 車床類 型 工件 1 工

2、件 2 工件 3 工件 1 工件 2 工件 3 可用臺(tái)時(shí)數(shù) 甲 0.4 1.1 1.0 13 9 10 800 乙 0.5 1.2 1.3 11 12 8 900 編輯ppt 解解 設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6。可建立以下線性規(guī)劃模型：編輯ppt用用MATLAB優(yōu)化工具箱解線性規(guī)劃優(yōu)化工具箱解線性規(guī)劃min z=cX bAXts. .1、模型：命令：x=linprog（c，A，b） 2、模型：min z=cX bAXts. .beqXAeq命令：x=linprog（c，A，b，Aeq, beq）注意：若沒有

3、不等式： 存在，則令A(yù)= ，b= .bAX 編輯ppt3、模型：min z=cX bAXts. .beqXAeqVLBXVUB命令：1 x=linprog（c，A，b，Aeq, beq, VLB，VUB） 2 x=linprog（c，A，b，Aeq, beq, VLB，VUB, X0） 注意：1 若沒有等式約束: , 則令A(yù)eq= , beq= . 2其中X0表示初始點(diǎn) beqXAeq4、命令：x,fval=linprog()返回最優(yōu)解及處的目標(biāo)函數(shù)值fval.編輯ppt解解 編寫編寫M文件文件xxgh1.m如下：如下：c=-0.4 -0.28 -0.32 -0.72 -0.64 -0.6;

4、A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08; b=850;700;100;900; Aeq=; beq=; vlb=0;0;0;0;0;0; vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub) 例例1 max 6543216 . 064. 072. 032. 028. 04 . 0 xxxxxxz 85003. 003. 003. 001. 001. 001. 0. .654321xxxxxxt s 70005. 002. 041xx

5、 10005. 002. 052xx 90008. 003. 063xx 6, 2 , 10jxj編輯ppt解解: 編寫編寫M文件文件xxgh2.m如下：如下： c=6 3 4; A=0 1 0; b=50; Aeq=1 1 1; beq=120; vlb=30;0;20; x,fval=linprog(c,A,b,Aeq,beq,vlb)321)436(minxxxz5020030321xxx120111 s.t. 321xxx編輯ppt 投資的收益和風(fēng)險(xiǎn)投資的收益和風(fēng)險(xiǎn)編輯ppt二、基本假設(shè)和符號(hào)規(guī)定二、基本假設(shè)和符號(hào)規(guī)定符符號(hào)號(hào)規(guī)規(guī)定定：Si 第 i 種投資項(xiàng)目，如股票，債券ri,pi,

6、qi -分別為 Si的平均收益率,風(fēng)險(xiǎn)損失率，交易費(fèi)率ui -Si的交易定額 0r -同期銀行利率xi -投資項(xiàng)目 Si的資金 a -投資風(fēng)險(xiǎn)度Q -總體收益 Q -總體收益的增量編輯ppt三、模型的建立與分析三、模型的建立與分析1. 總體風(fēng)險(xiǎn)用所投資的Si中最大的一個(gè)風(fēng)險(xiǎn)來衡量,即max qixi|i=1，2,n2購買 Si所付交易費(fèi)是一個(gè)分段函數(shù),即 pixi xiui 交易費(fèi) = piui xiui而題目所給定的定值 ui(單位:元)相對(duì)總投資 M 很小, piui更小,可以忽略不計(jì),這樣購買 Si的凈收益為(ri-pi)xi 3要使凈收益盡可能大，總體風(fēng)險(xiǎn)盡可能小,這是一個(gè)多目標(biāo)規(guī)劃模

7、型: 目標(biāo)函數(shù) MAXniiiixpr0)( MINmax qixi 約束條件 niiixp0)1 (=M xi0 i=0,1,n4. 模型簡(jiǎn)化：編輯pptc投資者在權(quán)衡資產(chǎn)風(fēng)險(xiǎn)和預(yù)期收益兩方面時(shí)，希望選擇一個(gè)令自己滿意的投資組合。因此對(duì)風(fēng)險(xiǎn)、收益賦予權(quán)重 s（0s1)，s 稱為投資偏好系數(shù).模模型型 3 目標(biāo)函數(shù)：min smaxqixi -（1-s）niiiixpr0)( 約束條件 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

8、qixi 約束條件：niiiixpr0)(k， Mxpii)1 ( ， xi 0 i=0，1，na 在實(shí)際投資中，投資者承受風(fēng)險(xiǎn)的程度不一樣，若給定風(fēng)險(xiǎn)一個(gè)界限 a，使最大的一個(gè)風(fēng)險(xiǎn) qixi/Ma，可找到相應(yīng)的投資方案。這樣把多目標(biāo)規(guī)劃變成一個(gè)目標(biāo)的線性規(guī)劃。模模型型 1 1 固定風(fēng)險(xiǎn)水平，優(yōu)化收益 目標(biāo)函數(shù)： Q=MAX11)(niiiixpr 約束條件： Mxqiia Mxpii)1 (， xi 0 i=0，1，n編輯ppt四、模型四、模型1 1的求解的求解 模型1為: minf = (-0.05, -0.27, -0.19, -0.185, -0.185) (x0 x1 x2 x3 x

9、 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)度，到底怎樣給定沒有一個(gè)準(zhǔn)則，不同的投資者有不同的風(fēng)險(xiǎn)度。我們從a=0開始，以步長a=0.001進(jìn)行循環(huán)搜索，編制程序如下：編輯ppta=0;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.0

10、15 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)編輯ppta = 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

11、 = 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é)果：編輯ppt五、五、 結(jié)果分析結(jié)果分析4 4.在a=0.006附近有一個(gè)轉(zhuǎn)折點(diǎn)，在這一點(diǎn)左邊，風(fēng)險(xiǎn)增加很少時(shí)，利潤增長 很快。在這一點(diǎn)右邊，風(fēng)險(xiǎn)增加很大時(shí)，利潤增長很緩

12、慢，所以對(duì)于風(fēng)險(xiǎn)和 收益沒有特殊偏好的投資者來說，應(yīng)該選擇曲線的拐點(diǎn)作為最優(yōu)投資組合， 大約是a*=0.6%，Q*=20% ，所對(duì)應(yīng)投資方案為: 風(fēng)險(xiǎn)度 收益 x0 x1 x2 x3 x4 0.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212 3.3.曲線上的任一點(diǎn)都表示該風(fēng)險(xiǎn)水平的最大可能收益和該收益要求的最小風(fēng)險(xiǎn)。對(duì)于不同風(fēng)險(xiǎn)的承受能力，選擇該風(fēng)險(xiǎn)水平下的最優(yōu)投資組合。2 2.當(dāng)投資越分散時(shí)，投資者承擔(dān)的風(fēng)險(xiǎn)越小，這與題意一致。即: 冒險(xiǎn)的投資者會(huì)出現(xiàn)集中投資的情況，保守的投資者則盡量分散投資。1.1.風(fēng)險(xiǎn)大，收益也大。編輯ppt 定義定義 如果目標(biāo)函數(shù)或

13、約束條件中至少有一個(gè)是非線性函數(shù)時(shí)的最優(yōu)化問題就叫做非線性規(guī)劃問題非線性規(guī)劃問題非線性規(guī)劃的基本概念非線性規(guī)劃的基本概念 一般形式一般形式: （1） 其中 ， 是定義在 En 上的實(shí)值函數(shù)，簡(jiǎn)記: Xfmin .,.,2 , 1 0 m;1,2,., 0. . ljXhiXgtsjinTnExxxX,21jihgf,1nj1ni1nE :h ,E :g ,E :EEEf 其它情況其它情況: 求目標(biāo)函數(shù)的最大值或約束條件為小于等于零的情況，都可通過取其相反數(shù)化為上述一般形式 Matlab函數(shù)：fmincon()編輯ppt應(yīng)用實(shí)例：應(yīng)用實(shí)例： 供應(yīng)與選址供應(yīng)與選址 某公司有6個(gè)建筑工地要開工，每個(gè)

14、工地的位置（用平面坐標(biāo)系a，b表示，距離單位：千米 ）及水泥日用量d(噸)由下表給出。目前有兩個(gè)臨時(shí)料場(chǎng)位于A(5,1)，B(2,7)，日儲(chǔ)量各有20噸。假設(shè)從料場(chǎng)到工地之間均有直線道路相連。 （1）試制定每天的供應(yīng)計(jì)劃，即從A，B兩料場(chǎng)分別向各工地運(yùn)送多少噸水泥，使總的噸千米數(shù)最小。 （2）為了進(jìn)一步減少噸千米數(shù)，打算舍棄兩個(gè)臨時(shí)料場(chǎng)，改建兩個(gè)新的，日儲(chǔ)量各為20噸，問應(yīng)建在何處，節(jié)省的噸千米數(shù)有多大？工地位置（a，b）及水泥日用量 d 1 2 3 4 5 6 a 1.25 8.75 0.5 5.75 3 7.25 b 1.25 0.75 4.75 5 6.5 7.25 d 3 5 4 7

15、6 11 編輯ppt（一）、建立模型（一）、建立模型 記工地的位置為記工地的位置為(ai，bi)，水泥日用量為，水泥日用量為di，i=1,6;料場(chǎng)位置為料場(chǎng)位置為(xj，yj)，日儲(chǔ)量為，日儲(chǔ)量為ej，j=1,2；從料場(chǎng)；從料場(chǎng)j向工地向工地i的運(yùn)送量為的運(yùn)送量為Xij。目標(biāo)函數(shù)為：216122)()(minjiijijijbyaxXf 約束條件為：2 , 1 ,6 , 2 , 1 ,6121jeXidXjiijijij 當(dāng)用臨時(shí)料場(chǎng)時(shí)決策變量為：Xij，當(dāng)不用臨時(shí)料場(chǎng)時(shí)決策變量為：Xij，xj，yj。編輯ppt（二）使用臨時(shí)料場(chǎng)的情形（二）使用臨時(shí)料場(chǎng)的情形 使用兩個(gè)臨時(shí)料場(chǎng)A(5,1)，B(2,7).求從料場(chǎng)j向工地i的運(yùn)送量為Xij，在各工地用量必須滿足和各料場(chǎng)運(yùn)送量不超過日儲(chǔ)量的條件下，使總的噸千米數(shù)最小，這是線性規(guī)劃問題. 線性規(guī)劃模型為：2161),(minjiijXjiaaf2 , 1 , 6 , 2 , 1 , s.t.6121jeXidXjiijijij其中 22)()(),(ijijbyaxjiaa，i=1,2,6,j=1,2,為常數(shù)。 設(shè)X11=X1, X21= X 2, X31= X 3, X41= X 4,