數(shù)學(xué)模型培訓(xùn)講稿3非線性規(guī)劃

1、非線性規(guī)劃 1*非線性規(guī)劃的基本解法非線性規(guī)劃的基本概念非線性規(guī)劃2 定義 如果目標(biāo)函數(shù)或約束條件中至少有一個是非線性函數(shù),則最優(yōu)化問題就叫做非線性規(guī)劃問題非線性規(guī)劃的基本概念 一般形式: （1） 其中 ， 是定義在 Rn 上的實(shí)值函數(shù)，簡記: 其它情況: 求目標(biāo)函數(shù)的最大值，或約束條件小于等于零兩種情況，都可通過取其相反數(shù)化為上述一般形式1nj1ni1nR:h,R:g,R:RRRf()nTnRxxxX=,21L()()=.,.,2,10m;1,2,.,0.ljXhiXgtsji3定義2 對于問題(1),設(shè) ,若存在 ,使得對一切 ,且 ,都有 ,則稱X*是f(X)在D上的局部極小值點(diǎn)（局部最

2、優(yōu)解）特別地,當(dāng) 時，若 ,則稱X*是f(X)在D上的嚴(yán)格局部極小值點(diǎn)（嚴(yán)格局部最優(yōu)解）定義3 對于問題(1),設(shè) ,若對任意的 ,都有則稱X*是f(X)在D上的全局極小值點(diǎn)（全局最優(yōu)解）特別地,當(dāng) 時，若 ,則稱X*是f(X)在D上的嚴(yán)格全局極小值點(diǎn)（嚴(yán)格全局最優(yōu)解） 定義1 把滿足問題（1）中條件的解 稱為可行解（或可行點(diǎn)），所有可行點(diǎn)的集合稱為可行集（或可行域）記為D即 問題(1)可簡記為 )(nRX()()njiRXXhXg XD=,0,0|()(),Xf Xf *4非線性規(guī)劃的基本解法SUTM外點(diǎn)法SUTM內(nèi)點(diǎn)法（障礙罰函數(shù)法）1 罰函數(shù)法2 近似規(guī)劃法5 罰函數(shù)法 罰函數(shù)法基本思想

3、是通過構(gòu)造罰函數(shù)把約束問題轉(zhuǎn)化為一系列無約束最優(yōu)化問題，進(jìn)而用無約束最優(yōu)化方法去求解這類方法稱為序列無約束最小化方法簡稱為SUMT法 其一為SUMT外點(diǎn)法，其二為SUMT內(nèi)點(diǎn)法6 其中T(X,M)稱為罰函數(shù)，M稱為罰因子，帶M的項(xiàng)稱為罰項(xiàng)，這里的罰函數(shù)只對不滿足約束條件的點(diǎn)實(shí)行懲罰:當(dāng) 時，滿足各 ，故罰項(xiàng)為0，不受懲罰當(dāng) 時,必有約束條件 ，故罰項(xiàng)大于0，要受懲罰SUTM外點(diǎn)法7 罰函數(shù)法的缺點(diǎn)：每個近似最優(yōu)解Xk往往不是容許解，而只能近似滿足約束，在實(shí)際問題中這種結(jié)果可能不能使用；在解一系列無約束問題中，計算量太大，特別是隨著Mk的增大，可能導(dǎo)致錯誤1任意給定初始點(diǎn) X0，取M11，給定允

4、許誤差 ，令k=1；2求無約束極值問題 的最優(yōu)解，設(shè)Xk=X(Mk)，即 ；3若存在 ，使 ,則取MkM( ),令k=k+1返回（2），否則，停止迭代得最優(yōu)解 計算時也可將收斂性判別準(zhǔn)則 改為 SUTM外點(diǎn)法(罰函數(shù)法)的迭代步驟8SUTM內(nèi)點(diǎn)法（障礙函數(shù)法）()()()()()()()為障礙因子.為障礙項(xiàng)，或其中稱或 ：構(gòu)造障礙函數(shù)rXgrXgrXgrXfrXIXgrXfrXIrXImiimiimiimii=+=+=11111ln1)(),(ln,SUTM內(nèi)點(diǎn)法適用范圍：只適用于不等式約束的最優(yōu)化問題9 內(nèi)點(diǎn)法的迭代步驟10 近似規(guī)劃法的基本思想：將問題(3)中的目標(biāo)函數(shù) 和約束條件 近似為

5、線性函數(shù)，并對變量的取值范圍加以限制，從而得到一個近似線性規(guī)劃問題，再用單純形法求解之，把其符合原始條件的最優(yōu)解作為(3)的解的近似近似規(guī)劃法每得到一個近似解，都從這點(diǎn)出發(fā)，重復(fù)以上步驟 這樣，通過求解一系列線性規(guī)劃問題，產(chǎn)生一個由線性規(guī)劃最優(yōu)解組成的序列，經(jīng)驗(yàn)表明，這樣的序列往往收斂于非線性規(guī)劃問題的解11 近似規(guī)劃法的算法步驟如下：1213 用MATLAB軟件求解,其輸入格式如下: 1x=quadprog(H,C,A,b); 2x=quadprog(H,C,A,b,Aeq,beq); 3x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB); 4x=quadprog(H,C

6、,A,b, Aeq,beq ,VLB,VUB,X0); 5x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0,options); 6x,fval=quaprog(); 7x,fval,exitflag=quaprog(); 8x,fval,exitflag,output=quaprog();1二次規(guī)劃用MATLAB優(yōu)化工具箱解非線性規(guī)劃14例1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x22 -x1+2x22 x10, x20 1寫成標(biāo)準(zhǔn)形式： 2輸入命令： H=1 -1; -1 2; c=-2 ;-6;A=1 1; -

7、1 2;b=2;2; Aeq=;beq=; VLB=0;0;VUB=; x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)3運(yùn)算結(jié)果為： x =06667 13333 z = -82222s.t.15 1 首先建立M文件fun.m,用來定義目標(biāo)函數(shù)F（X）:function f=fun(X);f=F(X);2一般非線性規(guī)劃 其中X為n維變元向量，G(X)與Ceq(X)均為非線性函數(shù)組成的向量，其他變量的含義與線性規(guī)劃、二次規(guī)劃中相同用MATLAB求解上述問題，基本步驟分三步：163 建立主程序.求解非線性規(guī)劃的函數(shù)是fmincon,命令的基本格式如下： (1) x=fm

8、incon(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=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()輸出極值點(diǎn)M文件迭代

9、的初值參數(shù)說明變量上下限17注意：1 fmincon函數(shù)提供了大型優(yōu)化算法和中型優(yōu)化算法默認(rèn)時: 若在fun函數(shù)中提供了梯度（options參數(shù)的GradObj設(shè)置為on），并且只有上下界存在或只有等式約束，fmincon函數(shù)將選擇大型算法當(dāng)既有等式約束又有梯度約束時，使用中型算法2 fmincon函數(shù)的中型算法使用的是序列二次規(guī)劃法在每一步迭代中求解二次規(guī)劃子問題，并用BFGS法更新拉格朗日Hesse矩陣3 fmincon函數(shù)可能會給出局部最優(yōu)解，這與初值X0的選取有關(guān)181寫成標(biāo)準(zhǔn)形式： s.t. 2x1+3x2 6 s.t. x1+4x2 5 x1,x2 0例2192先建立M-文件 fu

10、n3m: function f=fun3(x); f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)23再建立主程序youh2m： 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é)果為： x = 07647 10588 fval = -2029420應(yīng)用實(shí)例： 供應(yīng)與選址 某公司有6個建筑工地要開工，每個工地的位置（用平面坐標(biāo)系a，b表示，距離單位：km）及水泥日用量d(t)由下表給出目前有兩個臨時料場位于A(5,1)，

11、B(2,7)，日儲量各有20t假設(shè)從料場到工地之間均有直線道路相連 （1）試制定每天的供應(yīng)計劃，即從A，B兩料場分別向各工地運(yùn)送多少水泥，可使總的噸千米數(shù)最小 （2）為了進(jìn)一步減少噸千米數(shù)，打算舍棄兩個臨時料場，改建兩個新的，日儲量各為20t，問應(yīng)建在何處，節(jié)省的噸千米數(shù)有多大？21（一）建立模型 記工地的位置為(ai，bi)，水泥日用量為di，i=1,6;料場位置為(xj，yj)，日儲量為ej，j=1,2；料場j向工地i的運(yùn)送量為Xij當(dāng)用臨時料場時決策變量為：Xij，當(dāng)不用臨時料場時決策變量為：Xij，xj，yj22（二）使用臨時料場的情形 使用兩個臨時料場A(5,1)，B(2,7)求從料

12、場j向工地i的運(yùn)送量Xij . 在各工地用量必須滿足和各料場運(yùn)送量不超過日儲量的條件下，使總的噸千米數(shù)最小，這是線性規(guī)劃問題 線性規(guī)劃模型為：設(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 23計算結(jié)果為：x = 30000 50000 00000 70000 00000 10000 00000 00000 40000 00000 60000 100000fval = 136227524（三）改建兩個新料

13、場的情形 改建兩個新料場，要同時確定料場的位置(xj,yj)和運(yùn)送量Xij，在同樣條件下使總噸千米數(shù)最小這是非線性規(guī)劃問題非線性規(guī)劃模型為：25設(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文件liaochm定義目標(biāo)函數(shù)(2) 取初值為線性規(guī)劃的計算結(jié)果及臨時料場的坐標(biāo): x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;編寫主程序gying2m26(3) 計算結(jié)果為：x= 30000 50000 00707 70000 0 09293 0 0 39293 0 60000 100707 63875 43943 57511 71867fval = 1054626exitflag = 127鋼管訂購及運(yùn)輸優(yōu)化模型2000年“網(wǎng)易杯”全國大學(xué)生數(shù)學(xué)建模競賽B題28 某廠向用