數(shù)學(xué)建模第二章非線性規(guī)劃

第三章非線性規(guī)劃3.1非線性規(guī)劃3.1.1非線性規(guī)劃的實(shí)例與定義

如果目標(biāo)函數(shù)或約束條件中包含非線性函數(shù)，就稱這種規(guī)劃問題為非線性規(guī)劃問題。，非線性規(guī)劃目前還沒有適于各種問題的一般算法，各個(gè)方法都有自己特定的適用范圍。下面通過實(shí)例歸納出非線性規(guī)劃數(shù)學(xué)模型的一般形式例1（投資決策問題）某企業(yè)有n個(gè)項(xiàng)目可供選擇投資，并且至少要對(duì)其中一個(gè)項(xiàng)目投資。已知該企業(yè)擁有總資金A元，投資于第i(i=1,….,n)個(gè)項(xiàng)目需花資金

ai元，并預(yù)計(jì)可收益

bi元。試選擇最佳投資方案。解設(shè)投資決策變量為則投資總額為，投資總收益為

因?yàn)樵摴局辽僖獙?duì)一個(gè)項(xiàng)目投資，并且總的投資金額不能超過總資金A，故有限制條件由于)xi(i=1,….,n

只取值0或1，所以還有

最佳投資方案應(yīng)是投資額最小而總收益最大的方案，所以這個(gè)最佳投資決策問題歸結(jié)為總資金以及決策變量（取0或1）的限制條件下，極大化總收益和總投資之比。因此，其數(shù)學(xué)模型為：

上面例題是在一組等式或不等式的約束下，求一個(gè)函數(shù)的最大值（或最小值）問題，其中至少有一個(gè)非線性函數(shù)，這類問題稱之為非線性規(guī)劃問題?？筛爬橐话阈问狡渲衳=[x1…..xn]T稱為模型的決策變量，f稱為目標(biāo)函數(shù)，gi(i=1,….P

)和)hj(j=1,…..q)稱為約束函數(shù)。另外，0)gi(x)=0(i=1,….P

)稱為等式約束，hj(x)≤0(j=1,…..q)稱為不等式的約束。線性規(guī)劃與非線性規(guī)劃的區(qū)別如果線性規(guī)劃的最優(yōu)解存在，其最優(yōu)解只能在其可行域的邊界上達(dá)到（特別是可行域的頂點(diǎn)上達(dá)到）；而非線性規(guī)劃的最優(yōu)解（如果最優(yōu)解存在）則可能在其可行域的任意一點(diǎn)達(dá)到。3.1.2非線性規(guī)劃的Matlab解法Matlab中非線性規(guī)劃的數(shù)學(xué)模型寫成以下形式其中f(x)

是標(biāo)量函數(shù)，Beq,Aeq,B,A是相應(yīng)維數(shù)的矩陣和向量，C(x),Ceq(x)是非線性向量函數(shù)。Matlab中的命令是X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)LB≤x≤UB

它的返回值是向量x，其中FUN是用M文件定義的函數(shù)f(x)；X0是x的初始值；A,B,Aeq,Beq定義了線性約束A*X≤B,Aeq*X=Beq，如果沒有線性約束，則A=[],B=[],Aeq=[],Beq=[]；LB和UB是變量x的下界和上界，如果上界和下界沒有約束，則LB=[]，UB=[]，如果x無下界，則LB的各分量都為-inf，如果x無上界，則UB的各分量都為inf；NONLCON是用M文件定義的非線性向量函數(shù)C(x),Ceq(x)；OPTIONS定義了優(yōu)化參數(shù)，可以使用Matlab缺省的參數(shù)設(shè)置。例2求下列非線性規(guī)劃解（i）%編寫M文件fun1.m定義目標(biāo)函數(shù)functionf=fun1(x);f=sum(x.^2)+8;（ii）編寫M文件fun2.m定義非線性約束條件function[g,h]=fun2(x);G=-x(1)^2+x(2)-x(3)^2x(1)+x(2)^2+x(3)^3-20;%非線性不等式約束h=[-x(1)-x(2)^2+2x(2)+2*x(3)^2-3;%非線性等式約束（iii）編寫主程序文件example2.m如下：options=optimset('largescale','off');[x,y]=fmincon('fun1',rand(3,1),[],[],[],[],zeros(3,1),[],...'fun2',options)就可以求得當(dāng)x1=0.5522,x2=1.2033,x3=0.9478時(shí)，最小值y=10.6511。3.2Matlab求無約束極值問題3.2.2無約束極值問題的數(shù)值解在Matlab工具箱中，用于求解無約束極值問題的函數(shù)有fminunc和fminsearch，用法介紹如下。求函數(shù)的極小值其中x可以為標(biāo)量或向量。Matlab中fminunc的基本命令是[X,FVAL]=FMINUNC(FUN,X0,OPTIONS,P1,P2,...)其中的返回值X是所求得的極小點(diǎn)，F(xiàn)VAL是函數(shù)的極小值，其它返回值的含義參見相關(guān)的幫助。FUN是一個(gè)M文件，當(dāng)FUN只有一個(gè)返回值時(shí)，它的返回值是函數(shù)f(x)

；當(dāng)FUN有兩個(gè)返回值時(shí)，它的第二個(gè)返回值是f（x）的梯度向量；當(dāng)FUN有三個(gè)返回值時(shí)，它的第三個(gè)返回值是f(x)的二階導(dǎo)數(shù)陣（Hessian陣）。X0是向量x的初始值，OPTIONS是優(yōu)化參數(shù)，可以使用缺省參數(shù)。P1，P2是可以傳遞給FUN的一些參數(shù)。例3.5解：編寫M文件fun2.m如下：function[f,g]=fun2(x);f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;g=[-400*x(1)*(x(2)-x(1)^2)-2*(1-x(1));200*(x(2)-x(1)^2)];編寫主函數(shù)文件example6.m如下：options=optimset('GradObj','on');[x,y]=fminunc('fun2',rand(1,2),options)即可求得函數(shù)的極小值。方法2：在求極值時(shí)，也可以利用二階導(dǎo)數(shù)，編寫M文件fun3.m如下：function[f,df,d2f]=fun3(x);f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;df=[-400*x(1)*(x(2)-x(1)^2)-2*(1-x(1));200*(x(2)-x(1)^2)];d2f=[-400*x(2)+1200*x(1)^2+2,-400*x(1)-400*x(1),200];編寫主函數(shù)文件example62.m如下：options=optimset('GradObj','on','Hessian','on');[x,y]=fminunc('fun3',rand(1,2),options)即可求得函數(shù)的極小值。求多元函數(shù)的極值也可以使用Matlab的fminsearch命令，其使用格式為：[X,FVAL,EXITFLAG,OUTPUT]＝FMINSEARCH(FUN,X0,OPTIONS,P1,P2,...)例3.6求函數(shù)f(x)=sin(x)+3取最小值時(shí)的x值。解編寫f(x)的M文件fun4.m如下：functionf=fun4(x);f=sin(x)+3;編寫主函數(shù)文件example7.m如下：x0=2;[x,y]=fminsearch(@fun4,x0)運(yùn)行主函數(shù)文件即求得在初值2附近的極小點(diǎn)及極小值。3.3約束極值問題

帶有約束條件的極值問題稱為約束極值問題，也叫規(guī)劃問題。求解約束極值問題要比求解無約束極值問題困難得多。為了簡(jiǎn)化其優(yōu)化工作，可采用以下方法：將約束問題化為無約束問題；將非線性規(guī)劃問題化為線性規(guī)劃問題，以及能將復(fù)雜問題變換為較簡(jiǎn)單問題的其它方法。

庫恩—塔克條件是非線性規(guī)劃領(lǐng)域中最重要的理論成果之一，是確定某點(diǎn)為最優(yōu)點(diǎn)的必要條件，但一般說它并不是充分條件（對(duì)于凸規(guī)劃，它既是最優(yōu)點(diǎn)存在的必要條件，同時(shí)也是充分條件）。3.3.1二次規(guī)劃

若某非線性規(guī)劃的目標(biāo)函數(shù)為自變量x的二次函數(shù)，約束條件又全是線性的，就稱這種規(guī)劃為二次規(guī)劃。Matlab中二次規(guī)劃的數(shù)學(xué)模型可表述如下：Matlab中求解二次規(guī)劃的命令是[X,FVAL]=QUADPROG(H,f,A,b,Aeq,beq,LB,UB,X0,OPTIONS)返回值X是決策向量x的值，返回值FVAL是目標(biāo)函數(shù)在x處的值。其中，H為實(shí)對(duì)稱矩陣?yán)?.9求解二次規(guī)劃解編寫如下程序：h=[4,-4;-4,8];f=[-6;-3];a=[1,1;4,1];b=[3;9];[x,value]=quadprog(h,f,a,b,[],[],zeros(2,1))3.3.2罰函數(shù)法利用罰函數(shù)法，可將非線性規(guī)劃問題的求解，轉(zhuǎn)化為求解一系列無約束極值問題，因而也稱這種方法為序列無約束最小化技術(shù)，簡(jiǎn)記為SUMT(SequentialUnconstrainedMinizationTechnique)。

罰函數(shù)法求解非線性規(guī)劃問題的思想是，利用問題中的約束函數(shù)作出適當(dāng)?shù)牧P函數(shù)，由此構(gòu)造出帶參數(shù)的增廣目標(biāo)函數(shù)，把問題轉(zhuǎn)化為無約束非線性規(guī)劃問題。主要有兩種形式，一種叫外罰函數(shù)法，另一種叫內(nèi)罰函數(shù)法，下面介紹外罰函數(shù)法。取一個(gè)充分大的數(shù)M>0，構(gòu)造函數(shù)Matlab中可以直接利用max、min和sum函數(shù)。）則以增廣目標(biāo)函數(shù)P(x,M)為目標(biāo)函數(shù)的無約束極值問題對(duì)應(yīng)的最優(yōu)解x也是原問題的最優(yōu)解。例3.10求下列非線性規(guī)劃解(i)編寫M文件test.mfunctiong=test(x);M=50000;f=x(1)^2+x(2)^2+8;g=f-M*min(x(1),0)-M*min(x(2),0)-M*min(x(1)^2-x(2),0)+...M*abs(-x(1)-x(2)^2+2);或者是利用Matlab的求矩陣的極小值和極大值函數(shù)編寫test.m如下：functiong=test(x);M=50000;f=x(1)^2+x(2)^2+8;g=f-M*sum(min([x';zeros(1,2)]))-(ii)在Matlab命令窗口輸入[x,y]=fminunc('test',rand(2,1))即可求得問題的解。注意非線性問題很難求得全局最優(yōu)解，只能求得一個(gè)局部最優(yōu)解在Matlab優(yōu)化工具箱中，用于求解約束最優(yōu)化問題的函數(shù)有：fminbnd、fmincon、quadprog、fseminf、fminimax，上面已經(jīng)介紹了函數(shù)fmincon和quadprog。1fminbnd函數(shù)求單變量非線性函數(shù)在區(qū)間上的極小值Matlab的命令為[X,FVAL]=FMINBND(FUN,x1,x2,OPTIONS)它的返回值是極小點(diǎn)x和函數(shù)的極小值。這里fun是用M文件定義的函數(shù)或Matlab中的單變量數(shù)學(xué)函數(shù)。例3.11解(1)編寫M文件fun5.mfunctionf=fun5(x);f=(x-3)^2-1;(2)在Matlab的命令窗口輸入[x,y]=fminbnd('fun5',0,5)即可求得極小點(diǎn)和極小值。2fseminf函數(shù)上述問題的Matlab命令格式為X=FSEMINF(FUN,X0,NTHETA,SEMINFCON,A,B,Aeq,Beq)其中FUN用于定義目標(biāo)函數(shù)F(x)

；X0為x的初始值；NTHETA是半無窮約束PHI(x,w)的個(gè)數(shù)；函數(shù)SEMINFCON用于定義非線性不等式約束C(x)，非線性等式約束Ceq(x)和半無窮約束PHI(x,w)的每一個(gè)分量函數(shù)，函數(shù)SEMINFCON有兩個(gè)輸入?yún)⒘縓和S，S是推薦的取樣步長(zhǎng)解（1）編寫M文件fun6.m定義目標(biāo)函數(shù)如下：functionf=fun6(x,s);f=sum((x-0.5).^2);（2）編寫M文件fun7.m定義約束條件如下：function[c,ceq,k1,k2,s]=fun7(x,s);c=[];ceq=[];ifisnan(s(1,1))%s=[0.2,0;0.20];end%取樣值w1=1:s(1,1):100;w2=1:s(2,1):100;%半無窮約束k1=sin(w1*x(1)).*cos(w1*x(2))-1/1000*(w1-50).^2-sin(w1*x(3))-x(3)-1;k2=sin(w2*x(2)).*cos(w2*x(1))-1/1000*(w2-50).^2-sin(w2*x(3))-x(3)-1;%畫出半無窮約束的圖形,此處可以不用plot(w1,k1,'-',w2,k2,'+');（3）調(diào)用函數(shù)fseminf在Matlab的命令窗口輸入[x,y]=fseminf(@fun6,rand(3,1),2,@fun7)即可。3fminimax函數(shù)上述問題的Matlab命令為X=FMINIMAX(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON)例3.13解（1）編寫M文件fun8.m定義向量函數(shù)如下：functionf=fun8(x);f=[2*x(1)^2+x(2)^2-48*x(1)-40*x(2)+304-x(1)^2-3*x(2)^2x(1)+3*x(2)-18-x(1)-x(2)x(1)+x(2)-8];（2）調(diào)用函數(shù)fminimax[x,y]=fminimax(@fun8,rand(2,1))4利用梯度求解約束優(yōu)化問題