运筹学与最优化方法试卷A

华南农业大学期末考试试卷(A卷答案)2004学年第1学期考试科目:运筹学与最优化方法评卷人：1、 (25分)考虑函数f(x)=100(X一X2)2+(1-x)2(1)求出f(x)的一阶导数(梯度)Vf(x)和二阶导数(Hesse矩阵)V2f(x)。(2)用二阶导数(Hesse矩阵)V2f(x)的相关定理验证x*=(1,1)T为f(x)的一个极小点。(3)求出f(x)在点x(0)=(-1,1)t处的最速下降方向和牛顿方向。解：(1)Vf(x)=解：(1)Vf(x)=V2f(x)=82fdx2182f8x8x

218f 8f8x 8x1282f8x8x1282f8x22=[400x(x-x2)-2(1-x)200(x-x2)T112 1-400x+1200x2+2-400x11-400x1200(2(2)Vf(x)=[400气(x2-x2)-2(1-x1)200(x2-x：)T|*=[0,0]txV2f(xV2f(x*)=-400x+1200x2+2-400x-400x1 20011802-400-400200。。。2(3)。。。2(3)d=-Vf(x)=[2,0]t。。。5x(0)802>0；V2f(x*)>0，故V2f(x*)正定，结论成立。d=-[V2f(x)]-1Vf(x)| =x(0)2、(30分)考虑最优化问题min{x+x}x+x+x>1x2+x2+x2=1(1)给出其Kuhn-Tucker一阶最优性条件、拉格朗日函数、外点惩罚函数、增广格朗日函数。(2) 验证x(0)=(1,0,0)t满足Kuhn—Tucker一阶最优性条件，并求出相应的拉格朗日乘子。

一人*一旦*2x=011-X*一旦*2x=0TOC\o"1-5"\h\z< 21-X*一旦*2x=0X*(x+x+x一1)=0,X*>0拉格朗日函数:L(x,X)=x+x-X(y2一(x+x+x一1))-X(x2+x2+x2一1)。。。。。。。5分2 3 1 1 2 3 2 1 2 3外点惩罚函数：F(x,。)=x+x+bmax[{0,—(x+x+x—1)}]2+。(x2+x2+x2—1)2。。。。。。5分2 3 1 1 2 3 2 1 2 3增广格朗日函数:P(x,X,b)=x+x—X(y2—(x+x+x—1))—X(x2+x2+x2—1)2 3 1 1 2 3 2 1 2 3 5分。。。。。。。。+bmax[{0,—(x+x+x—1)}]2+b(x2+x2+x2—1)21 1 2 3 2 1 2 3(2)易验证：x(0)=(1,0,0)了满足Kuhn—Tucker一阶最优性条件，且X*=1。。。。。。。。10分min{(x+1)3+x2}3、(10分)用内点法求解问题的K-T点。fx—1>0I'%>0解：定义障碍函数：G(x,r)=(x+1)3+x2+r(-^+—)模型：minG(x,r)。。。3k1 2kx1—1x2 xeintD k'8G51c， '8G51, 、,■r厂解得：x**k=(气,x}T, 、,■r厂解得：x**k=(气,x}T=(±}|1土’3，&3)。。。41k(x—1)28G仁，1，八-—=2x+r(——)=02 2x*=limx*=(±1,0)，有条件x—1>0，得K-T点为(1，0) 。。。。。。。。。。。。3分其中rk项+rk 1其中。。。。。。。。。。。。。。。。。。。。。。。。。3分而AB的原象为[1,2],于是：Rpa=Rwp。。。。。。。。。。。。。。。。。。。。。。。。。3分5、 （10分）设问题①为TOC\o"1-5"\h\zmax(f)=cx+cx-\ bcx11 22 nnax+ax+ +ax<b111 122 1nn 1ax+ax ax<b211 222 2nn 2ax+ax ax<bm11 m22 mnnmx,x,x，•…x>01 2 3n（1）写出问题①的对偶问题②。（2）证明问题①有最优解的充分必要条件是问题②有最优解。解：（1）问题①的对偶问题②为:min(g)=by+by byTOC\o"1-5"\h\z11 22 mmay+ay +ay>c1 212 m1m 1ay+ay+•••+ay>c1 222 m2m 2<! ……ay+ay +ay>cmn1mn2 mnmny,y,y,•••y>0123m(2)max(f)=CtX<(AtY)tX=Yt(AX)<Yrb=(brY)t=brY=min(g)说明f（X）和g（Y）分别有上界和下界。又可行域D是有界闭集，则最优解同时存在。 。。。。。。。。。。。。。。。。。5分minz=一2x一3xx+2x<86、 （15分）用单纯形法求解：4x1<16 最优解x*=（4,2） 。。。。。。。。。。。。12分'4^<122x,x>0最优值max(z)=14(1) Kuhn—Tucker一阶最优性条件4、(10分)求下列双目标规划minf(x)=(f1⑴,f2(x))T的有效解和弱有效解。xeD 1f(x)=x2—2x