非線性規(guī)劃1(qh)

1、 非線性規(guī)劃的基本解法非線性規(guī)劃的基本解法SUTM外點(diǎn)法外點(diǎn)法SUTM內(nèi)點(diǎn)法（障礙罰函數(shù)法）內(nèi)點(diǎn)法（障礙罰函數(shù)法）1、罰函數(shù)法、罰函數(shù)法2、近似規(guī)劃法近似規(guī)劃法 返回返回 罰函數(shù)法罰函數(shù)法 罰函數(shù)法罰函數(shù)法基本思想是通過構(gòu)造罰函數(shù)把約束問題轉(zhuǎn)化為一系列無約束最優(yōu)化問題，進(jìn)而用無約束最優(yōu)化方法去求解這類方法稱為序列無約束最小化方法序列無約束最小化方法簡稱為SUMTSUMT法法 其一為SUMTSUMT外點(diǎn)法外點(diǎn)法，其二為SUMTSUMT內(nèi)點(diǎn)內(nèi)點(diǎn)法法 )2( , 0min,1212ljjmiiXhMXgMXfMXT可設(shè)：)3( ,min 1MXTnEX）轉(zhuǎn)化為無約束問題：將問題（ 其中T(X,M)稱

2、為罰函數(shù)罰函數(shù)，M稱為罰因子罰因子，帶M的項(xiàng)稱為罰項(xiàng)罰項(xiàng)，這里的罰函數(shù)只對不滿足約束條件的點(diǎn)實(shí)行懲罰：當(dāng) 時(shí)，滿足各 ，故罰項(xiàng)=0，不受懲罰當(dāng) 時(shí)，必有 的約束條件，故罰項(xiàng)0，要受懲罰DX 0, 0XhXgiiDX 00XhXgii或SUTMSUTM外點(diǎn)法外點(diǎn)法 ) 1 ( .,.,2 , 1 0 m;1,2,., 0. . min ljXhiXgtsXfji對一般的非線性規(guī)劃： 罰函數(shù)法的缺點(diǎn)缺點(diǎn)是：每個(gè)近似最優(yōu)解Xk往往不是容許解，而只能近似滿足約束，在實(shí)際問題中這種結(jié)果可能不能使用；在解一系列無約束問題中，計(jì)算量太大，特別是隨著Mk的增大，可能導(dǎo)致錯(cuò)誤1、任意給定初始點(diǎn)X0，取M11，給

3、定允許誤差 ，令k=1；2、求無約束極值問題 的最優(yōu)解，設(shè)為Xk=X(Mk)，即 ；3、若存在 ，使 ，則取MkM( )令k=k+1返回（2），否則，停止迭代得最優(yōu)解 .計(jì)算時(shí)也可將收斂性判別準(zhǔn)則 改為 . 0MXTnEX,min),(,minkkEXMXTMXTnmii1kiXg10, 1MMk 0, 0min12miiXgMkXX*kiXg SUTM SUTM外點(diǎn)法外點(diǎn)法(罰函數(shù)法)的迭代步驟迭代步驟) 1 (,.,2 , 10. .min i mXgtsXfi考慮問題： 所有嚴(yán)格內(nèi)點(diǎn)的集合。是可行域中，設(shè)集合00, 2 , 1, 0|DmiXgXDi 為障礙因子為障礙項(xiàng)，或其中稱或：構(gòu)造

4、障礙函數(shù)rXgrXgrXgrXfrXIXgrXfrXIrXImiimiimiimii11111 ln1)(),( ln, ）（得值問題：）就轉(zhuǎn)化為求一系列極這樣問題（kkkDXrXrXI ,min10SUTMSUTM內(nèi)點(diǎn)法（內(nèi)點(diǎn)法（障礙函數(shù)法） 內(nèi)點(diǎn)法的迭代步驟內(nèi)點(diǎn)法的迭代步驟(1) 給定允許誤差0，取10 , 01r；(2) 求出約束集合 D 的一個(gè)內(nèi)點(diǎn)00DX ，令1k；(3) 以01DXk為 初 始 點(diǎn)， 求 解kDXrXI,min0， 其 中0DX 的最優(yōu)解，設(shè)為 0DrXXkk；(4) 檢驗(yàn)是否滿足mikiXgr1ln或miikXgr11，滿足，停止迭代，kXX *；否則取kkrr

5、1，令1 kk，返回(3） 用MATLAB軟件求解,其輸入格式輸入格式如下: 1. x=quadprog(H,C,A,b); 2. x=quadprog(H,C,A,b,Aeq,beq); 3. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB); 4. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0); 5. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0,options); 6. x,fval=quaprog(.); 7. x,fval,exitflag=quaprog(.); 8. x,fval,exit

6、flag,output=quaprog(.);1、二次規(guī)劃、二次規(guī)劃標(biāo)準(zhǔn)型為： Min Z= 21XTHX+cTX s.t. AX=b beqXAeq VLBXVUB 例例1 1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x22 -x1+2x22 x10, x20 MATLAB（youh1）1、寫成標(biāo)準(zhǔn)形式寫成標(biāo)準(zhǔn)形式： 2、 輸入命令輸入命令： H=1 -1; -1 2; c=-2 ;-6;A=1 1; -1 2;b=2;2; Aeq=;beq=; VLB=0;0;VUB=; x,z=quadprog(H,c,A,b,Aeq,beq,VLB,V

7、UB)3、運(yùn)算結(jié)果運(yùn)算結(jié)果為： x =0.6667 1.3333 z = -8.2222212121622 11- 1 ),(minxxxxxxzT212100222 11 1 xxxxs.t. 1. 首先建立M文件fun.m,定義目標(biāo)函數(shù)F（X）:function f=fun(X);f=F(X);2、一般非線性規(guī)劃、一般非線性規(guī)劃標(biāo)準(zhǔn)型為： min F(X) s.t AX=b beqXAeq G(X)0 Ceq(X)=0 VLBXVUB 其中X為n維變元向量，G(X)與Ceq(X)均為非線性函數(shù)組成的向量，其它變量的含義與線性規(guī)劃、二次規(guī)劃中相同.用Matlab求解上述問題，基本步驟分三步：

8、2. 若約束條件中有非線性約束:G(X)0或Ceq(X)=0,則建立M文件nonlcon.m定義函數(shù)G(X)與Ceq(X): function G,Ceq=nonlcon(X) G=. Ceq=. 3. 建立主程序.非線性規(guī)劃求解的函數(shù)是fmincon,命令的基本格式如下： (1) x=fmincon(fun,X0,A,b) (2) x=fmincon(fun,X0,A,b,Aeq,beq) (3) x=fmincon(fun,X0,A,b, Aeq,beq,VLB,VUB) (4) x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon)(5)x=fminc

9、on(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon,options) (6) x,fval= fmincon(.) (7) x,fval,exitflag= fmincon(.) (8)x,fval,exitflag,output= fmincon(.)輸出極值點(diǎn)M文件迭代的初值參數(shù)說明變量上下限注意：注意：1 fmincon函數(shù)提供了大型優(yōu)化算法和中型優(yōu)化算法。默認(rèn)時(shí)，若在fun函數(shù)中提供了梯度（options參數(shù)的GradObj設(shè)置為on），并且只有上下界存在或只有等式約束，fmincon函數(shù)將選擇大型算法。當(dāng)既有等式約束又有梯度約束時(shí)，使用中型算法。2 fminc

10、on函數(shù)的中型算法使用的是序列二次規(guī)劃法。在每一步迭代中求解二次規(guī)劃子問題，并用BFGS法更新拉格朗日Hessian矩陣。3 fmincon函數(shù)可能會給出局部最優(yōu)解，這與初值X0的選取有關(guān)。1、寫成標(biāo)準(zhǔn)形式寫成標(biāo)準(zhǔn)形式： s.t. 00546322121xxxx2100 xx22212121212minxxxxf22212121212minxxxxf 2x1+3x2 6 s.t x1+4x2 5 x1,x2 0例例22、先建立先建立M-文件文件 fun3.m: function f=fun3(x); f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)2MATLAB(yo

11、uh2)3、再建立主程序youh2.m： x0=1;1; A=2 3 ;1 4; b=6;5; Aeq=;beq=; VLB=0;0; VUB=; x,fval=fmincon(fun3,x0,A,b,Aeq,beq,VLB,VUB)4、運(yùn)算結(jié)果為：運(yùn)算結(jié)果為： x = 0.7647 1.0588 fval = -2.02941先建立先建立M文件文件 fun4.m,定義目標(biāo)函數(shù)定義目標(biāo)函數(shù): function f=fun4(x); f=exp(x(1) *(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);) 12424()(22122211xxxxxexfx x1+

12、x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0例例32再建立再建立M文件文件mycon.m定義非線性約束：定義非線性約束： function g,ceq=mycon(x) g=x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;3主程序主程序youh3.m為為:x0=-1;1;A=;b=;Aeq=1 1;beq=0;vlb=;vub=;x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb,vub,mycon)MATLAB(youh3)3. 運(yùn)算結(jié)果為運(yùn)算結(jié)果為： x = -1.2250 1.

13、2250 fval = 1.8951 例4 100 , 50 07 025 . .2min 21222122221121xxxxXgxxXgtsxxXf1先建立先建立M-文件文件fun.m定義目標(biāo)函數(shù)定義目標(biāo)函數(shù): function f=fun(x); f=-2*x(1)-x(2);2再建立再建立M文件文件mycon2.m定義非線性約束：定義非線性約束： function g,ceq=mycon2(x) g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;3. 主程序主程序fxx.m為為: x0=3;2.5; VLB=0 0;VUB=5 10; x,fval,exitflag,out

14、put =fmincon(fun,x0,VLB,VUB,mycon2)MATLAB(fxx(fun)4. 運(yùn)算結(jié)果為運(yùn)算結(jié)果為: x = 4.0000 3.0000fval =-11.0000exitflag = 1output = iterations: 4 funcCount: 17 stepsize: 1 algorithm: 1x44 char firstorderopt: cgiterations: 返回返回應(yīng)用實(shí)例：應(yīng)用實(shí)例： 供應(yīng)與選址供應(yīng)與選址 某公司有6個(gè)建筑工地要開工，每個(gè)工地的位置（用平面坐標(biāo)系a，b表示，距離單位：千米 ）及水泥日用量d(噸)由下表給出。目前有兩個(gè)臨時(shí)料

15、場位于A(5,1)，B(2,7)，日儲量各有20噸。假設(shè)從料場到工地之間均有直線道路相連。 （1）試制定每天的供應(yīng)計(jì)劃，即從A，B兩料場分別向各工地運(yùn)送多少噸水泥，使總的噸千米數(shù)最小。 （2）為了進(jìn)一步減少噸千米數(shù)，打算舍棄兩個(gè)臨時(shí)料場，改建兩個(gè)新的，日儲量各為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 6 11 （一）、建立模型（一）、建立模型 記工地的位置為記工地的位置為(ai，bi)，水泥日用量為，

16、水泥日用量為di，i=1,6;料場位置為料場位置為(xj，yj)，日儲量為，日儲量為ej，j=1,2；從料場；從料場j向工地向工地i的運(yùn)送量為的運(yùn)送量為Xij。目標(biāo)函數(shù)為：216122)()(minjiijijijbyaxXf 約束條件為：2 , 1 ,6 , 2 , 1 ,6121jeXidXjiijijij 當(dāng)用臨時(shí)料場時(shí)決策變量為：Xij，當(dāng)不用臨時(shí)料場時(shí)決策變量為：Xij，xj，yj。（二）使用臨時(shí)料場的情形（二）使用臨時(shí)料場的情形 使用兩個(gè)臨時(shí)料場A(5,1)，B(2,7).求從料場j向工地i的運(yùn)送量為Xij，在各工地用量必須滿足和各料場運(yùn)送量不超過日儲量的條件下，使總的噸千米數(shù)最小

17、，這是線性規(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, X51= X 5, X61= X 6X12= X 7, X22= X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12 編寫程序gying1.mMATLAB（gying1）計(jì)算結(jié)果為：計(jì)算結(jié)果為：x = 3.0000 5.0000

18、0.0000 7.0000 0.0000 1.0000 0.0000 0.0000 4.0000 0.0000 6.0000 10.0000fval = 136.2275即由料場A、B向6 個(gè)工地運(yùn)料方案為： 1 2 3 4 5 6 料場A 3 5 0 7 0 1 料場B 0 0 4 0 6 10 總的噸千米數(shù)為136.2275。 （三）改建兩個(gè)新料場的情形（三）改建兩個(gè)新料場的情形 改建兩個(gè)新料場，要同時(shí)確定料場的位置(xj,yj)和運(yùn)送量Xij，在同樣條件下使總噸千米數(shù)最小。這是非線性規(guī)劃問題。非線性規(guī)劃模型為：216122)()(minjiijijijbyaxXf2 , 1 , 6 ,

19、2 , 1 , . .6121jeXidXtsjiijijij設(shè) X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6 X12= X 7, X22= X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12 x1=X13, y1=X14, x2=X15, y2=X16 （1）先編寫M文件liaoch.m定義目標(biāo)函數(shù)。MATLAB（liaoch）(2) 取初值為線性規(guī)劃的計(jì)算結(jié)果及臨時(shí)料場的坐標(biāo): x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;編寫主程序gying2.m.MATLAB（gying2）(3) 計(jì)算結(jié)果為：x= 3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867fval = 105.4626exitflag = 1即兩個(gè)新料場的坐標(biāo)分別為(6.3875, 4.3943),(5.7511, 7.1867),由料場 A、B 向 6 個(gè) 工地運(yùn)料方案為： 1 2 3 4 5 6 料場 A 3 5 0.0707