MATLAB精品教程課件 第06講 非線性規(guī)劃

1、數學建模與數學實驗后勤工程學院數學教研室非線性規(guī)劃 1實驗目的實驗內容2、掌握用數學軟件求解優(yōu)化問題。1、直觀了解非線性規(guī)劃的基本內容。1、非線性規(guī)劃的基本理論。4、實驗作業(yè)。2、用數學軟件求解非線性規(guī)劃。3、鋼管訂購及運輸優(yōu)化模型2*非線性規(guī)劃的基本解法非線性規(guī)劃的基本概念非線性規(guī)劃 返回3 定義 如果目標函數或約束條件中至少有一個是非線性函數時的最優(yōu)化問題就叫做非線性規(guī)劃問題非現(xiàn)性規(guī)劃的基本概念 一般形式: （1） 其中 ， 是定義在 En 上的實值函數，簡記: 其它情況: 求目標函數的最大值或約束條件為小于等于零的情況，都可通過取其相反數化為上述一般形式4 定義1 把滿足問題（1）中條件

2、的解 稱為可行解（或可行點），所有可行點的集合稱為可行集（或可行域）記為D即 問題(1)可簡記為 定義2 對于問題(1)，設 ，若存在 ,使得對一切 ，且 ，都有 ，則稱X*是f(X)在D上的局部極小值點（局部最優(yōu)解）特別地當 時，若 ，則稱X*是f(X)在D上的嚴格局部極小值點（嚴格局部最優(yōu)解）定義3 對于問題(1),設 ,對任意的 ,都有 則稱X*是f(X)在D上的全局極小值點（全局最優(yōu)解）特別地當 時，若 ，則稱X*是f(X)在D上的嚴格全局極小值點（嚴格全局最優(yōu)解） 返回5非線性規(guī)劃的基本解法SUTM外點法SUTM內點法（障礙罰函數法）1、罰函數法2、近似規(guī)劃法 返回6 罰函數法 罰函

3、數法基本思想是通過構造罰函數把約束問題轉化為一系列無約束最優(yōu)化問題，進而用無約束最優(yōu)化方法去求解這類方法稱為序列無約束最小化方法簡稱為SUMT法 其一為SUMT外點法，其二為SUMT內點法7 其中T(X,M)稱為罰函數，M稱為罰因子，帶M的項稱為罰項，這里的罰函數只對不滿足約束條件的點實行懲罰：當 時，滿足各 ，故罰項=0，不受懲罰當 時，必有 的約束條件，故罰項0，要受懲罰SUTM外點法8 罰函數法的缺點是：每個近似最優(yōu)解Xk往往不是容許解，而只能近似滿足約束，在實際問題中這種結果可能不能使用；在解一系列無約束問題中，計算量太大，特別是隨著Mk的增大，可能導致錯誤1、任意給定初始點X0，取M

4、11，給定允許誤差 ，令k=1；2、求無約束極值問題 的最優(yōu)解，設為Xk=X(Mk)，即 ；3、若存在 ，使 ，則取MkM( )令k=k+1返回（2），否則，停止迭代得最優(yōu)解 .計算時也可將收斂性判別準則 改為 . SUTM外點法(罰函數法)的迭代步驟9SUTM內點法（障礙函數法）10 內點法的迭代步驟11 近似規(guī)劃法的基本思想：將問題(3)中的目標函數 和約束條件 近似為線性函數，并對變量的取值范圍加以限制，從而得到一個近似線性規(guī)劃問題，再用單純形法求解之，把其符合原始條件的最優(yōu)解作為(3)的解的近似近似規(guī)劃法每得到一個近似解后，都從這點出發(fā)，重復以上步驟 這樣，通過求解一系列線性規(guī)劃問題，

5、產生一個由線性規(guī)劃最優(yōu)解組成的序列，經驗表明，這樣的序列往往收斂于非線性規(guī)劃問題的解。12 近似規(guī)劃法的算法步驟如下13 返回14用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,

6、fval,exitflag=quaprog(.); 8.x,fval,exitflag,output=quaprog(.);1、二次規(guī)劃15例1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x22 -x1+2x22 x10, x20 MATLAB（youh1）1、寫成標準形式： 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,VUB)3、運算結果為： x =0.6667 1.333

7、3 z = -8.2222s.t.16 1. 首先建立M文件fun.m,定義目標函數F（X）:function f=fun(X);f=F(X);2、一般非線性規(guī)劃 其中X為n維變元向量，G(X)與Ceq(X)均為非線性函數組成的向量，其它變量的含義與線性規(guī)劃、二次規(guī)劃中相同.用Matlab求解上述問題，基本步驟分三步：173. 建立主程序.非線性規(guī)劃求解的函數是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,V

8、UB) (4) x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon)(5)x=fmincon(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(.)輸出極值點M文件迭代的初值參數說明變量上下限18注意：1 fmincon函數提供了大型優(yōu)化算法和中型優(yōu)化算法。默認時，若在fun函數中提供了梯度（options參數的GradObj設置為on），并

9、且只有上下界存在或只有等式約束，fmincon函數將選擇大型算法。當既有等式約束又有梯度約束時，使用中型算法。2 fmincon函數的中型算法使用的是序列二次規(guī)劃法。在每一步迭代中求解二次規(guī)劃子問題，并用BFGS法更新拉格朗日Hessian矩陣。3 fmincon函數可能會給出局部最優(yōu)解，這與初值X0的選取有關。191、寫成標準形式： s.t. 2x1+3x2 6 s.t x1+4x2 5 x1,x2 0例2202、先建立M-文件 fun3.m: function f=fun3(x); f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)2MATLAB(youh2)3、再

10、建立主程序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、運算結果為： x = 0.7647 1.0588 fval = -2.0294211先建立M文件 fun4.m,定義目標函數: 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); x1+x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0例32再建立M文

11、件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;223主程序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. 運算結果為： x = -1.2250 1.2250 fval = 1.895123 例4 1先建立M-文件fun.m定義目標函數: function f=fun(x); f=-2*x

12、(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;243. 主程序fxx.m為: x0=3;2.5; VLB=0 0;VUB=5 10; x,fval,exitflag,output =fmincon(fun,x0,VLB,VUB,mycon2)MATLAB(fxx(fun)254. 運算結果為: x = 4.0000 3.0000fval =-11.0000exitflag = 1output = iterations: 4 funcCount: 17 stepsi

13、ze: 1 algorithm: 1x44 char firstorderopt: cgiterations: 返回26應用實例： 供應與選址 某公司有6個建筑工地要開工，每個工地的位置（用平面坐標系a，b表示，距離單位：千米 ）及水泥日用量d(噸)由下表給出。目前有兩個臨時料場位于A(5,1)，B(2,7)，日儲量各有20噸。假設從料場到工地之間均有直線道路相連。 （1）試制定每天的供應計劃，即從A，B兩料場分別向各工地運送多少噸水泥，使總的噸千米數最小。 （2）為了進一步減少噸千米數，打算舍棄兩個臨時料場，改建兩個新的，日儲量各為20噸，問應建在何處，節(jié)省的噸千米數有多大？27（一）、建立

14、模型 記工地的位置為(ai，bi)，水泥日用量為di，i=1,6;料場位置為(xj，yj)，日儲量為ej，j=1,2；從料場j向工地i的運送量為Xij。當用臨時料場時決策變量為：Xij，當不用臨時料場時決策變量為：Xij，xj，yj。28（二）使用臨時料場的情形 使用兩個臨時料場A(5,1)，B(2,7).求從料場j向工地i的運送量為Xij，在各工地用量必須滿足和各料場運送量不超過日儲量的條件下，使總的噸千米數最小，這是線性規(guī)劃問題. 線性規(guī)劃模型為：設X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6X12= X 7, X22=

15、X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12 編寫程序gying1.mMATLAB（gying1）29計算結果為：x = 3.0000 5.0000 0.0000 7.0000 0.0000 1.0000 0.0000 0.0000 4.0000 0.0000 6.0000 10.0000fval = 136.227530（三）改建兩個新料場的情形 改建兩個新料場，要同時確定料場的位置(xj,yj)和運送量Xij，在同樣條件下使總噸千米數最小。這是非線性規(guī)劃問題。非線性規(guī)劃模型為：31設 X11=X1, X21= X 2, X31= X 3, X

16、41= 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定義目標函數。MATLAB（liaoch）(2) 取初值為線性規(guī)劃的計算結果及臨時料場的坐標: x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;編寫主程序gying2.m.MATLAB（gying2）32(3) 計算結果為：x= 3.0000 5.0000 0.0707 7.0000 0 0.929

17、3 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867fval = 105.4626exitflag = 133(4) 若修改主程序gying2.m, 取初值為上面的計算結果:x0= 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.1867得結果為:x=3.0000 5.0000 0.3094 7.0000 0.0108 0.6798 0 0 3.6906 0 5.9892 10.3202 5.5369 4.

18、9194 5.8291 7.2852fval =103.4760exitflag = 1總的噸千米數比上面結果略優(yōu). (5) 若再取剛得出的結果為初值, 卻計算不出最優(yōu)解.MATLAB（gying2）MATLAB（gying2）34(6) 若取初值為: x0=3 5 4 7 1 0 0 0 0 0 5 11 5.6348 4.8687 7.2479 7.7499, 則計算結果為:x=3.0000 5.0000 4.0000 7.0000 1.0000 0 0 0 0 0 5.0000 11.0000 5.6959 4.9285 7.2500 7.7500fval =89.8835exitflag = 1總的噸千米數89.8835比上面結果更好. 通過此例可看出fmincon函數在選取初值上的重要性.MATLAB（gying2） 返回35鋼管訂購及運輸優(yōu)化模型2000年“網易杯”全國大學生數學建模競賽B題36符號說明：371、鋪設總費用：2、成本及運輸總