7非线性规划模型134

1、§2.7非线性规划模型在现实问题中，大量的问题是非线性的。因此，除线性规划外，使用更多的是非线性规划。本节简单介绍非线性规划的有关概念。一.引例例1.如图2-68,预建一猪舍，围墙和隔墙的总长不能超过40米，问长、宽各多少时，面积最大？设长、宽分别是Xi米、X?米时，问X1图2-68X1图2-68题即为下述优化问题：求maxx1x2st；2为+5X2兰40,Xi，x0易知，本问题的最优解是x1=10,x4.例2.某企业生产一种产品，其生产要素（可以是某种原材料，也可以是劳力、资本等）编号为1,2/,n.已知该产品的生产函数为g（xX2，xn）（第i种生产要素的投入量为xi时的产品产出

2、量）一般为非线性函数，设给定产品的总产量为a,第i种生产要素的单位生产费用为ci，问如何安排生产成本最低？数学模型为：minxcixistM（X1,X2，Xn）=a,x0例3.最优国民经济计划模型国民经济由n个部门所组成，编号为1,2/,n,各部门间直接消耗的系数矩阵为A=引二=,aj为第i个部门生产价值一个单位的产品直接消耗j部门产品的价值单位，j部门的生产函数为二fi（Li,Ki）其中xi为第i部门总产品的价值.Ki为投入i部门的资金数Li为投入i部门的劳力数问在总劳动力设yi表示第i部门最终产品的总价值，则数学模型为max'yiLLxi=aijxj+yiZst:送心兰K为=

3、63;（心丄）Lx-,yi,Li,K0例4.确定经验公式-非线性回归分析设（tyi）（i=1,2,，n）为实际问题中的一组数据,且y和1有关系y=abe",现求系数a,b,c使得y=abet和数据组最接近”化为数学问题，即求kmin'$-abef2i=1a,b,c0般地，称minf(x，Xn)s.t.gi(x，Xn)_0,i=1,mhj(x1,为规划问题（或称为条件极值问题特别1.当gi，hj为线性函数,特别1.当gi，hj为线性函数,f为二次函数，称上述问题为二次规划;2.当gi,hj,f均为线性函数，称上述问题为线性规划。gi-0,hj=0称为约束条件，f称为目标函数。二

4、.二变量非线性规划问题的图解法考虑规划问题minf(x1,x2)s.t.gi(Xi,X2)0hj(xX2)=0可以用图解法求出先给出若干概念1.约束集合首先我们知道，在平面上域。如：x2-y:0，表示y_22表示xy=1内部部分等.一个等式可确定一条曲线。将所有不等式、等式确定的区域的公共部分称为集合。2.等高线，一个不等式可确定，一个不等式可确定x2上方部分；x2-对于目标函数f(x1,X2),f(x1,X2)=z取定值时,确定平面上一条曲线，而zf(x1,x2)，z取不同值为平面上一条曲线。对应于该曲线上的点，其函数值相同，称这些曲线为等高线。22例5.Z=f(人，x2)=人x2的等高线为

5、一族以原点为圆心的同心圆，Z=C时，这些同心圆半径为.C。随着圆的半径增大，圆上的函数值增大(如图2-69)。1例6.Z二f(X1,X2)=二2的等高线x1+x2图2-7-6/-5>4-3-2-1y2V-6(见图图2-71也为一族以原点为圆心的同心圆，半径为随着圆的半径扩大，圆上的函数值变小。2-70)。3.几何意义及图解法例7.非线性规划问题22min(x12)(x22)stx2X红1的可行域（约束集合）如图2-71阴影部分，最优解为（0,0）.解“猪舍问题”（例1）maxx1x215x2乞40xi-0图2-72三.函数的梯度及最速下降法约束问题转化为无约束问题（如乘数法）后可用最速下

6、降法求Lagrange解。1.求解无约束极值-多元函数极值minf(x)二f(Xi,Xn)经典数学方法：令.=0,i=1,2,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当矩阵（fXj（X）nn正定时，f（X）在X0取极小；当矩阵（fXXj（X）nn负定时，f（X）在X0取极大。这种做法的困难是0要解方程

7、组；（2判定正定性。2.规划方法首先回顾梯度的性质：2f（X）在给定点X0的负梯度即fX（x0）=（fX；,fX；,，f；）（x0）是函数f（X）在x°点下降最快的方向；2n=；时，梯度方向为曲线f（x；,x；）=f（X；0,X；）在X10的法向。（X；丿最速下降法：我们假设稳定点又是最优点。给定初始点X0二（X；0,，x0）T，若fx（X0）=0，则X0即为最优点；否则，fx（Xi0）=O,则按梯度意义，-fx（x0）为f下降最快的方向，沿z0=_fx（x0）方向，求丸0，使mnf（X。+Xz0）=f（X0+%z0）（其中f（x0+z0）是的一元函数）。令X1=x0'0z0

8、，则f（x；）：f（X0）LgK0,f（x0+A0Z0）兰f（x0+&Z0），特别取九=0,有f（x；）£f（X0）从X1依次迭代即可得到最优解。步骤：1.取初始点X0,；0；2. 若fx(Xk)=jfxi(Xk)2+fx2(Xk)2+fxn(Xk)2兰E，止；3. 计算一fX(xk)>g,求极值minf(xk+hzk)=f(xk+Zkzk)；4. 令xk41=xk+*zk,k:=k+1，转2。例9.求无约束问题22min区-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)°四.罚函数法考虑非线性规划问题minf(x)9i(x)0st*hj(x)=0图2-73引入函数(t)=(minb,t)2J-)220,20<_2J2,t£0心0,"0r1®=丿=2min<0,t>2t,t“用(t)构造函数mlT(x,M)=f(x)+M臣(gi(x)+Zi二j壬

10、二f(x)M'min(O,gi(x)'(hj(x)2/其中M是一个很大的数。由申的定义，及约束条件的集合为R=&gi(x)X0,hj(x)=0,故T(x,M)T(x,M)f(x),>f(x),由于xR时，22*min(0,gi(x)亠二(hj(x)0及M为很大的正数，故MA也是一个很大的正数。于是，当xfR时，T(x,M)二f(x)M厶也是很大的数。我们称函数T(x,M)为罚函数，二称为罚款项，M称为罚因子。对于固定的M,T(x,M)为x的函数。下面求无条件约束问题的最优解。(可用最速下降法)设其最优解为0由于T(x,M)为很大的数，故无约束问题minT(x,M)

11、的最优解?应满足条件?:R。可以证明：minT(x,M)的最优解?为规划问题minf(x)/gi(x0stj(x)=0的最优解。这里M取多大合适，我们事先不知道。但从上述结论，若对M=M1，minT(x,M1)的最优解x>R，则x为原规划问题的最优解。否则，xR,则说明Mj不够大。从而取M=M2rIOMj,再求解minT(x,M2)。kk依次下去，若求得minT(x,Mk)的最优解xR，则x为原问题的最优解。kk或X和R足够接近，如：gi(x)E,hj(Xk)兰S迭代停止。否则，令M=Mk1OMk，继续上述步骤。这个方法称为罚函数方法。罚函数方法的实际意义：考虑我们购买1,2，n中货物，

12、对每种货物的采购量分别为为，,xn,则我们把目标函数f(x)=f(Xi厂，Xn)看成采购量分别为Xi,，Xn时，所需总钱数。约束集合，理解为某种“规定”。因此，非线性规划问题minf(x)6(x)2。stD(x)=O的经济意义为：在“规定”的范围内购物，使花钱最少。对于罚函数，T(x,Mk)的意义是：相对“规定”制定一种“罚款”政策。若符合规定(即R)，则罚款为0。若违反规定，则需交纳一笔正罚款(即罚款项)m2l2Mmin(0,gi(x)M/(hj(x)kij¥于是，罚函数T(x,Mk)即为采购的总代价。不难理解，当Mk很大时，相当于对违反“规定”的采购规定了苛刻的罚款，这当然不合算。于是迫使我们在考虑总代价为最小时，要符合规定。在数学上表现为：当Mk很大时，无约束极值问题的最优解即xk.R。例10.利用罚函数法求解minxst：x_0解：T(x,M)=xM(min(0,x)2)Tx(X,Mk)='1,J+2Mkxx_0x_0若x为极值，则Tx(x,Mk)=0。故无约束问题的最优解满足12MkX=0，即1x二2Mk当k时，得x=lim当k时，得x=lim12Mk0。例11.解非线性规划问题minx12x222X3st*x2x3-1=02222解:解:T(x,Mkx1x2x3M(x1x2