7非線性規(guī)劃模型134

1、§2.7非線性規(guī)劃模型在現(xiàn)實(shí)問題中，大量的問題是非線性的。因此，除線性規(guī)劃外，使用更多的是非線性規(guī)劃。本節(jié)簡(jiǎn)單介紹非線性規(guī)劃的有關(guān)概念。一.引例例1.如圖2-68,預(yù)建一豬舍，圍墻和隔墻的總長(zhǎng)不能超過40米，問長(zhǎng)、寬各多少時(shí)，面積最大？設(shè)長(zhǎng)、寬分別是Xi米、X?米時(shí)，問X1圖2-68X1圖2-68題即為下述優(yōu)化問題：求maxx1x2st；2為+5X2蘭40,Xi，x0易知，本問題的最優(yōu)解是x1=10,x4.例2.某企業(yè)生產(chǎn)一種產(chǎn)品，其生產(chǎn)要素（可以是某種原材料，也可以是勞力、資本等）編號(hào)為1,2/,n.已知該產(chǎn)品的生產(chǎn)函數(shù)為g（xX2，xn）（第i種生產(chǎn)要素的投入量為xi時(shí)的產(chǎn)品產(chǎn)出

2、量）一般為非線性函數(shù)，設(shè)給定產(chǎn)品的總產(chǎn)量為a,第i種生產(chǎn)要素的單位生產(chǎn)費(fèi)用為ci，問如何安排生產(chǎn)成本最低？數(shù)學(xué)模型為：minxcixistM（X1,X2，Xn）=a,x0例3.最優(yōu)國(guó)民經(jīng)濟(jì)計(jì)劃模型國(guó)民經(jīng)濟(jì)由n個(gè)部門所組成，編號(hào)為1,2/,n,各部門間直接消耗的系數(shù)矩陣為A=引二=,aj為第i個(gè)部門生產(chǎn)價(jià)值一個(gè)單位的產(chǎn)品直接消耗j部門產(chǎn)品的價(jià)值單位，j部門的生產(chǎn)函數(shù)為二fi（Li,Ki）其中xi為第i部門總產(chǎn)品的價(jià)值.Ki為投入i部門的資金數(shù)Li為投入i部門的勞力數(shù)問在總勞動(dòng)力設(shè)yi表示第i部門最終產(chǎn)品的總價(jià)值，則數(shù)學(xué)模型為max'yiLLxi=aijxj+yiZst:送心蘭K為=

3、63;（心丄）Lx-,yi,Li,K0例4.確定經(jīng)驗(yàn)公式-非線性回歸分析設(shè)（tyi）（i=1,2,，n）為實(shí)際問題中的一組數(shù)據(jù),且y和1有關(guān)系y=abe",現(xiàn)求系數(shù)a,b,c使得y=abet和數(shù)據(jù)組最接近”化為數(shù)學(xué)問題，即求kmin'$-abef2i=1a,b,c0般地，稱minf(x，Xn)s.t.gi(x，Xn)_0,i=1,mhj(x1,為規(guī)劃問題（或稱為條件極值問題特別1.當(dāng)gi，hj為線性函數(shù),特別1.當(dāng)gi，hj為線性函數(shù),f為二次函數(shù)，稱上述問題為二次規(guī)劃;2.當(dāng)gi,hj,f均為線性函數(shù)，稱上述問題為線性規(guī)劃。gi-0,hj=0稱為約束條件，f稱為目標(biāo)函數(shù)。二

4、.二變量非線性規(guī)劃問題的圖解法考慮規(guī)劃問題minf(x1,x2)s.t.gi(Xi,X2)0hj(xX2)=0可以用圖解法求出先給出若干概念1.約束集合首先我們知道，在平面上域。如：x2-y:0，表示y_22表示xy=1內(nèi)部部分等.一個(gè)等式可確定一條曲線。將所有不等式、等式確定的區(qū)域的公共部分稱為集合。2.等高線，一個(gè)不等式可確定，一個(gè)不等式可確定x2上方部分；x2-對(duì)于目標(biāo)函數(shù)f(x1,X2),f(x1,X2)=z取定值時(shí),確定平面上一條曲線，而zf(x1,x2)，z取不同值為平面上一條曲線。對(duì)應(yīng)于該曲線上的點(diǎn)，其函數(shù)值相同，稱這些曲線為等高線。22例5.Z=f(人，x2)=人x2的等高線為

5、一族以原點(diǎn)為圓心的同心圓，Z=C時(shí)，這些同心圓半徑為.C。隨著圓的半徑增大，圓上的函數(shù)值增大(如圖2-69)。1例6.Z二f(X1,X2)=二2的等高線x1+x2圖2-7-6/-5>4-3-2-1y2V-6(見圖圖2-71也為一族以原點(diǎn)為圓心的同心圓，半徑為隨著圓的半徑擴(kuò)大，圓上的函數(shù)值變小。2-70)。3.幾何意義及圖解法例7.非線性規(guī)劃問題22min(x12)(x22)stx2X紅1的可行域（約束集合）如圖2-71陰影部分，最優(yōu)解為（0,0）.解“豬舍問題”（例1）maxx1x215x2乞40xi-0圖2-72三.函數(shù)的梯度及最速下降法約束問題轉(zhuǎn)化為無約束問題（如乘數(shù)法）后可用最速下

6、降法求Lagrange解。1.求解無約束極值-多元函數(shù)極值minf(x)二f(Xi,Xn)經(jīng)典數(shù)學(xué)方法：令.=0,i=1,2,n，解得駐點(diǎn)，是否極值點(diǎn)？看矩陣（f；Xj）的正定性即可，從xn)fx。CXnxn)fx。CXnf=f(X0，,X0)-(X1-X0)-(Xncx10住0住2(X1-X10)(Xn-X0)2f：X1:XnXi0、X120('AXi)00000二f(Xi,Xn)(XiXi，XnXn)(fxiXj(X)nnXn''0當(dāng)矩陣（fXj（X）nn正定時(shí)，f（X）在X0取極小；當(dāng)矩陣（fXXj（X）nn負(fù)定時(shí)，f（X）在X0取極大。這種做法的困難是0要解方程

7、組；（2判定正定性。2.規(guī)劃方法首先回顧梯度的性質(zhì)：2f（X）在給定點(diǎn)X0的負(fù)梯度即fX（x0）=（fX；,fX；,，f；）（x0）是函數(shù)f（X）在x°點(diǎn)下降最快的方向；2n=；時(shí)，梯度方向?yàn)榍€f（x；,x；）=f（X；0,X；）在X10的法向。（X；丿最速下降法：我們假設(shè)穩(wěn)定點(diǎn)又是最優(yōu)點(diǎn)。給定初始點(diǎn)X0二（X；0,，x0）T，若fx（X0）=0，則X0即為最優(yōu)點(diǎn)；否則，fx（Xi0）=O,則按梯度意義，-fx（x0）為f下降最快的方向，沿z0=_fx（x0）方向，求丸0，使mnf（X。+Xz0）=f（X0+%z0）（其中f（x0+z0）是的一元函數(shù)）。令X1=x0'0z0

8、，則f（x；）：f（X0）LgK0,f（x0+A0Z0）蘭f（x0+&Z0），特別取九=0,有f（x；）£f（X0）從X1依次迭代即可得到最優(yōu)解。步驟：1.取初始點(diǎn)X0,；0；2. 若fx(Xk)=jfxi(Xk)2+fx2(Xk)2+fxn(Xk)2蘭E，止；3. 計(jì)算一fX(xk)>g,求極值minf(xk+hzk)=f(xk+Zkzk)；4. 令xk41=xk+*zk,k:=k+1，轉(zhuǎn)2。例9.求無約束問題22min區(qū)-1)4(x2-1)。解：1.取x°=(1,0)T名=10工f(x°)=4；2. fx|=2(X11),8(X2叭=(0,8)|

9、；I3. fx=8A&；024. minf(x(0.8)=min(f(1,8)=4(8-1),=1/8；-fxd1)=0<名。-fxd1)=0<名。15.5.x1=x°-(0,8)T二(1,1)T8*T故fmin=0,x=(1,1)°四.罰函數(shù)法考慮非線性規(guī)劃問題minf(x)9i(x)0st*hj(x)=0圖2-73引入函數(shù)(t)=(minb,t)2J-)220,20<_2J2,t£0心0,"0r1®=丿=2min<0,t>2t,t“用(t)構(gòu)造函數(shù)mlT(x,M)=f(x)+M臣(gi(x)+Zi二j壬

10、二f(x)M'min(O,gi(x)'(hj(x)2/其中M是一個(gè)很大的數(shù)。由申的定義，及約束條件的集合為R=&gi(x)X0,hj(x)=0,故T(x,M)T(x,M)f(x),>f(x),由于xR時(shí)，22*min(0,gi(x)亠二(hj(x)0及M為很大的正數(shù)，故MA也是一個(gè)很大的正數(shù)。于是，當(dāng)xfR時(shí)，T(x,M)二f(x)M厶也是很大的數(shù)。我們稱函數(shù)T(x,M)為罰函數(shù)，二稱為罰款項(xiàng)，M稱為罰因子。對(duì)于固定的M,T(x,M)為x的函數(shù)。下面求無條件約束問題的最優(yōu)解。(可用最速下降法)設(shè)其最優(yōu)解為0由于T(x,M)為很大的數(shù)，故無約束問題minT(x,M)

11、的最優(yōu)解?應(yīng)滿足條件?:R?？梢宰C明：minT(x,M)的最優(yōu)解?為規(guī)劃問題minf(x)/gi(x0stj(x)=0的最優(yōu)解。這里M取多大合適，我們事先不知道。但從上述結(jié)論，若對(duì)M=M1，minT(x,M1)的最優(yōu)解x>R，則x為原規(guī)劃問題的最優(yōu)解。否則，xR,則說明Mj不夠大。從而取M=M2rIOMj,再求解minT(x,M2)。kk依次下去，若求得minT(x,Mk)的最優(yōu)解xR，則x為原問題的最優(yōu)解。kk或X和R足夠接近，如：gi(x)E,hj(Xk)蘭S迭代停止。否則，令M=Mk1OMk，繼續(xù)上述步驟。這個(gè)方法稱為罰函數(shù)方法。罰函數(shù)方法的實(shí)際意義：考慮我們購(gòu)買1,2，n中貨物，

12、對(duì)每種貨物的采購(gòu)量分別為為，,xn,則我們把目標(biāo)函數(shù)f(x)=f(Xi廠，Xn)看成采購(gòu)量分別為Xi,，Xn時(shí)，所需總錢數(shù)。約束集合，理解為某種“規(guī)定”。因此，非線性規(guī)劃問題minf(x)6(x)2。stD(x)=O的經(jīng)濟(jì)意義為：在“規(guī)定”的范圍內(nèi)購(gòu)物，使花錢最少。對(duì)于罰函數(shù)，T(x,Mk)的意義是：相對(duì)“規(guī)定”制定一種“罰款”政策。若符合規(guī)定(即R)，則罰款為0。若違反規(guī)定，則需交納一筆正罰款(即罰款項(xiàng))m2l2Mmin(0,gi(x)M/(hj(x)kij¥于是，罰函數(shù)T(x,Mk)即為采購(gòu)的總代價(jià)。不難理解，當(dāng)Mk很大時(shí)，相當(dāng)于對(duì)違反“規(guī)定”的采購(gòu)規(guī)定了苛刻的罰款，這當(dāng)然不合算。于是迫使我們?cè)诳紤]總代價(jià)為最小時(shí)，要符合規(guī)定。在數(shù)學(xué)上表現(xiàn)為：當(dāng)Mk很大時(shí)，無約束極值問題的最優(yōu)解即xk.R。例10.利用罰函數(shù)法求解minxst：x_0解：T(x,M)=xM(min(0,x)2)Tx(X,Mk)='1,J+2Mkxx_0x_0若x為極值，則Tx(x,Mk)=0。故無約束問題的最優(yōu)解滿足12MkX=0，即1x二2Mk當(dāng)k時(shí)，得x=lim當(dāng)k時(shí)，得x=lim12Mk0。例11.解非線性規(guī)劃問題minx12x222X3st*x2x3-1=02222解:解:T(x,Mkx1x2x3M(x1x2