數(shù)學(xué)建模-非線性規(guī)劃省公開課一等獎(jiǎng)全國(guó)示范課微課金獎(jiǎng)?wù)n件

二、約束非線性規(guī)劃基本解法一、非線性規(guī)劃基本概念目錄

返回四、非線性規(guī)劃matlab求解三、無(wú)約束非線性規(guī)劃梯度解法1第1頁(yè)

定義

假如目標(biāo)函數(shù)或約束條件中最少有一個(gè)是非線性函數(shù)時(shí)最優(yōu)化問題就叫做非線性規(guī)劃問題．一非線性規(guī)劃基本概念

普通形式:

（1）其中，是定義在En上實(shí)值函數(shù)，簡(jiǎn)記:

其它情況:

求目標(biāo)函數(shù)最大值或約束條件為小于等于零情況，都可經(jīng)過取其相反數(shù)化為上述普通形式．2第2頁(yè)

定義1

把滿足問題（1）中條件解稱為可行解（或可行點(diǎn)），全部可行點(diǎn)集合稱為可行集（或可行域）．記為D．即問題(1)可簡(jiǎn)記為．定義2

對(duì)于問題(1)，設(shè)，若存在,使得對(duì)一切，且，都有，則稱X*是f(X)在D上局部極小值點(diǎn)（局部最優(yōu)解）．尤其地當(dāng)時(shí)，，則稱X*是則稱f(X)在D上嚴(yán)格局部極小值點(diǎn)（嚴(yán)格局部最優(yōu)解）．定義3對(duì)于問題(1),設(shè),對(duì)任意,都有則稱X*是f(X)在D上全局極小值點(diǎn)（全局最優(yōu)解）．尤其地當(dāng)時(shí)，若，則稱X*是f(X)在D上嚴(yán)格全局極小值點(diǎn)（嚴(yán)格全局最優(yōu)解）．

返回3第3頁(yè)二非線性規(guī)劃基本解法SUTM外點(diǎn)法SUTM內(nèi)點(diǎn)法（障礙罰函數(shù)法）1、罰函數(shù)法2、近似規(guī)劃法

返回4第4頁(yè)

罰函數(shù)法

罰函數(shù)法基本思想是經(jīng)過結(jié)構(gòu)罰函數(shù)把約束問題轉(zhuǎn)化為一系列無(wú)約束最優(yōu)化問題，進(jìn)而用無(wú)約束最優(yōu)化方法去求解．這類方法稱為序列無(wú)約束最小化方法（SequentialUnconstrainedMinimizationTechnique-SUMT）．簡(jiǎn)稱為SUMT法．其一為SUMT外點(diǎn)法，其二為SUMT內(nèi)點(diǎn)法．5第5頁(yè)其中T(X,M)稱為罰函數(shù)，M稱為罰因子，帶M項(xiàng)稱為罰項(xiàng)，這里罰函數(shù)只對(duì)不滿足約束條件點(diǎn)實(shí)施處罰：當(dāng)時(shí)，滿足各，故罰項(xiàng)=0，不受處罰．當(dāng)時(shí)，必有約束條件，故罰項(xiàng)>0，要受處罰．SUTM外點(diǎn)法6第6頁(yè)罰函數(shù)法缺點(diǎn)是：每個(gè)近似最優(yōu)解Xk往往不是允許解，而只能近似滿足約束，在實(shí)際問題中這種結(jié)果可能不能使用；在解一系列無(wú)約束問題中，計(jì)算量太大，尤其是伴隨Mk增大，可能造成錯(cuò)誤．1、任意給定初始點(diǎn)X0，取M1>1，給定允許誤差，令k=1；2、求無(wú)約束極值問題最優(yōu)解，設(shè)為Xk=X(Mk)，即；3、若存在，使，則取Mk>M()令k=k+1返回（2），不然，停頓迭代．得最優(yōu)解.計(jì)算時(shí)也可將收斂性判別準(zhǔn)則改為.

SUTM外點(diǎn)法(罰函數(shù)法)迭代步驟7第7頁(yè)SUTM內(nèi)點(diǎn)法（障礙函數(shù)法）8第8頁(yè)內(nèi)點(diǎn)法迭代步驟9第9頁(yè)內(nèi)點(diǎn)法特點(diǎn)：

1．初始點(diǎn)必須為嚴(yán)格內(nèi)點(diǎn)

2．不適于含有等式約束數(shù)學(xué)模型

3．迭代過程中各個(gè)點(diǎn)均為可行設(shè)計(jì)方案

4．普通收斂較慢

5．初始罰因子要選擇得當(dāng)

6．罰因子為遞減，遞減率c有0<c<1外點(diǎn)法特點(diǎn)：

1．初始點(diǎn)能夠任選，但應(yīng)使各函數(shù)有定義

2．對(duì)等式約束和不等式約束均可適用

3．僅最優(yōu)解為可行設(shè)計(jì)方案

4．普通收斂較快

5．初始罰因子要選擇得當(dāng)

6．罰因子為遞增，遞增率c’有c’>110第10頁(yè)三.無(wú)約束最優(yōu)化問題解析方法：利用函數(shù)解析性質(zhì)結(jié)構(gòu)迭代公式使之收斂到最優(yōu)解。11第11頁(yè)梯度法（最速下降法）迭代公式：怎樣選擇下降最快方向？12第12頁(yè)梯度法（最速下降法）：梯度法算法步驟：13第13頁(yè)解：14第14頁(yè)收斂性性質(zhì).15第15頁(yè)16第16頁(yè)共軛梯度法1.共軛方向和共軛方向法共軛是正交推廣。17第17頁(yè)18第18頁(yè)幾何意義19第19頁(yè)20第20頁(yè)共軛方向法21第21頁(yè)2.共軛梯度法

怎樣選取一組共軛方向？以下分析算法詳細(xì)步驟。22第22頁(yè)23第23頁(yè)24第24頁(yè)25第25頁(yè)26第26頁(yè)27第27頁(yè)28第28頁(yè)3.用于普通函數(shù)共軛梯度法29第29頁(yè)30第30頁(yè)非線性規(guī)劃模型例子（處罰函數(shù)法）四非線性規(guī)劃模型matlab編程31第31頁(yè)globallamada%主程序main2.m,罰函數(shù)方法x0=[11];lamada=2;c=10;e=1e-5;k=1;whilelamada*fun2p(x0)>=e x0=fminsearch('fun2min',x0);lamada=c*lamada;k=k+1;enddisp(‘最優(yōu)解’),disp(x0)disp('k='),disp(k)

程序1：主程序main2.m32第32頁(yè)程序2：計(jì)算函數(shù)fun2p.mfunctionr=fun2p(x)%罰項(xiàng)函數(shù)r=((x(1)-1)^3-x(2)*x(2))^2;

33第33頁(yè)程序3：輔助函數(shù)程序fun2min.mfunctionr=fun2min(x)%輔助函數(shù)globallamadar=x(1)^2+x(2)^2+lamada*fun2p(x);34第34頁(yè)用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,exitflag,output]=quaprog(...);1、二次規(guī)劃非線性規(guī)劃matlab求解35第35頁(yè)例1

minf(x1,x2)=-2x1-6x2+x12-2x1x2+2x22s.t.x1+x2≤2-x1+2x2≤2x1≥0,x2≥0MATLAB（youh1）1、寫成標(biāo)準(zhǔn)形式：

2、輸入命令：

H=[1-1;-12];c=[-2;-6];A=[11;-12];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=0.66671.3333z=-8.2222s.t.36第36頁(yè)

1.首先建立M文件fun.m,定義目標(biāo)函數(shù)F（X）:functionf=fun(X);f=F(X);2、普通非線性規(guī)劃

其中X為n維變?cè)蛄?，G(X)與Ceq(X)均為非線性函數(shù)組成向量，其它變量含義與線性規(guī)劃、二次規(guī)劃中相同.用Matlab求解上述問題，基本步驟分三步：37第37頁(yè)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=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文件迭代初值參數(shù)說(shuō)明變量上下限38第38頁(yè)注意：[1]fmincon函數(shù)提供了大型優(yōu)化算法和中型優(yōu)化算法。默認(rèn)時(shí)，若在fun函數(shù)中提供了梯度（options參數(shù)GradObj設(shè)置為’on’），而且只有上下界存在或只有等式約束，fmincon函數(shù)將選擇大型算法。當(dāng)現(xiàn)有等式約束又有梯度約束時(shí)，使用中型算法。[2]fmincon函數(shù)中型算法使用是序列二次規(guī)劃法。在每一步迭代中求解二次規(guī)劃子問題，并用BFGS法更新拉格朗日Hessian矩陣。[3]fmincon函數(shù)可能會(huì)給出局部最優(yōu)解，這與初值X0選取相關(guān)。39第39頁(yè)1、寫成標(biāo)準(zhǔn)形式：

s.t.

2x1+3x26s.tx1+4x25x1,x20例240第40頁(yè)2、先建立M-文件fun3.m:

functionf=fun3(x);f=-x(1)-2*x(2)+(1/2)*x(1)^2+(1/2)*x(2)^2MATLAB(youh2)3、再建立主程序youh2.m：

x0=[1;1];A=[23;14];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=0.76471.0588fval=-2.029441第41頁(yè)1．先建立M文件fun4.m,定義目標(biāo)函數(shù):

functionf=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=0s.t.1.5+x1x2-x1-x20-x1x2–10

0例32．再建立M文件mycon.m定義非線性約束：

function[g,ceq]=mycon(x)g=[1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10];ceq=[];42第42頁(yè)3．主程序youh3.m為:x0=[-1;1];A=[];b=[];Aeq=[11];beq=[0];vlb=[];vub=[];[x,fval]=fmincon('fun4',x0,A,b,Aeq,beq,vlb,vub,'mycon')MATLAB(youh3)3.運(yùn)算結(jié)果為：

x=-1.22501.2250fval=1.895143第43頁(yè)例4

1．先建立M-文件fun.m定義目標(biāo)函數(shù):functionf=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];

44第44頁(yè)3.主程序fxx.m為:x0=[3;2.5];VLB=[00];VUB=[510];[x,fval,exitflag,output]=fmincon('fun',x0,[],[],[],[],VLB,VUB,'mycon2')MATLAB(fxx(fun))45第45頁(yè)4.運(yùn)算結(jié)果為:x=4.00003.0000fval=-11.0000exitflag=1output=iterations:4funcCount:17stepsize:1algorithm:[1x44char]firstorderopt:[]cgiterations:[]

返回46第46頁(yè)應(yīng)用實(shí)例：供給與選址

某企業(yè)有6個(gè)建筑工地要開工，每個(gè)工地位置（用平面坐標(biāo)系a，b表示，距離單位：千米）及水泥日用量d(噸)由下表給出。當(dāng)前有兩個(gè)暫時(shí)料場(chǎng)位于A(5,1)，B(2,7)，日儲(chǔ)量各有20噸。假設(shè)從料場(chǎng)到工地之間都有直線道路相連。（1）試制訂天天供給計(jì)劃，即從A，B兩料場(chǎng)分別向各工地運(yùn)輸多少噸水泥，使總噸千米數(shù)最小。（2）為了深入降低噸千米數(shù)，打算舍棄兩個(gè)暫時(shí)料場(chǎng)，改建兩個(gè)新，日儲(chǔ)量各為20噸，問應(yīng)建在何處，節(jié)約噸千米數(shù)有多大？47第47頁(yè)（一）、建立模型

記工地位置為(ai，bi)，水泥日用量為di，i=1,…,6;料場(chǎng)位置為(xj，yj)，日儲(chǔ)量為ej，j=1,2；從料場(chǎng)j向工地i運(yùn)輸量為Xij。當(dāng)用暫時(shí)料場(chǎng)時(shí)決議變量為：Xij，當(dāng)不用暫時(shí)料場(chǎng)時(shí)決議變量為：Xij，xj，yj。48第48頁(yè)（二）使用暫時(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ī)劃模型為：設(shè)X11=X1,X21=X2,,X31=X3,X41=X4,X51=X5,,X61=X6X12=X7,X22=X8,,X32=X9,X42=X10,X52=X11,,X62=X12

編寫程序gying1.mMATLAB（gying1）49第49頁(yè)計(jì)算結(jié)果為：x=[3.00005.00000.00007.00000.00001.00000.00000.00004.00000.00006.000010.0000]’fval=136.227550第50頁(yè)（三）改建兩個(gè)新料場(chǎng)情形

改建兩個(gè)新料場(chǎng)，要同時(shí)確定料場(chǎng)位置(xj,yj)和運(yùn)輸量Xij，在一樣條件下使總噸千米數(shù)最小。這是非線性規(guī)劃問題。非線性規(guī)劃模型為：51第51頁(yè)設(shè)X11=X1,X21=X2,,X31=X3,X41=X4,X51=X5,,X61=X6X12=X7,X22=X8,,X32=X9,X42=X10,X52=X11,,X62=X12

x1=X13,y1=X14,x2=X15,y2=X16

（1）先編寫M文件liaoch.m定義目標(biāo)函數(shù)。MATLAB（liaoch）(2)取初值為線性規(guī)劃計(jì)算結(jié)果及暫時(shí)料場(chǎng)坐標(biāo):x0=[35070100406105127]';編寫主程序gying2.m.MATLAB（gying2）52第52頁(yè)(3)計(jì)算結(jié)果為：x=[3.00005.00000.07077.000000.9293003.929306.000010.07076.38754.39435.75117.1867]’fval=105.4626exitflag=153第53頁(yè)(4)若修改主程序gying2.m,取初值為上面計(jì)算結(jié)果:x0=[3.00005.00000.07077.000000.9293