华南农业大学期末考试试卷（A卷答案）
2004学年第1学期 考试科目：运筹学与最优化方法 评卷人： 1、 （25分）考虑函数 f(x)?100(x2?x12)2?(1?x1)2
（1） 求出f(x)的一阶导数（梯度）?f(x)和二阶导数（Hesse矩阵）?2f(x)。 （2） 用二阶导数（Hesse矩阵）?2f(x)的相关定理验证x*?(1,1)T为f(x)的一个极小点。 （3） 求出f(x)在点x(0)?(?1,1)T处的最速下降方向和牛顿方向。
??f解：（1）?f(x)=???x1?f?22T??400x(x?x)?2(1?x)200(x?x。。。。。5分 121121) 。??x2?T????2f??x22?f(x)=?21??f??x?x?21?2f???400x2?1200x12?2?400x1??x1?x2????。。。。。。。。。。。。。。。5分 ? 。2?f???400x1200?2??x2?200(x2?x12)2（2）?f(x)=?400x1(x2?x1)?2(1?x1)??Tx*?[0,0]T
??400x2?1200x12?2?400x1??f(x)=???400x1200??2*2*x*?802????400?400? 。。。。。。。。。。。。。。。。3分 200??2*802>0；?f(x)?0，故?f(x)正定，结论成立。 。。。。。。。。。。。。。。。。2分
（3）d???f(x)2x(0)?[2,0]T 。。。。。。。。。。。。。。。。5分
?1x(0) d??[?f(x)]?f(x)2、 （30分）考虑最优化问题
? 。。。。。。。。。。。。。。。。。。。5分
min{x2?x3}?x1?x2?x3?1
?222?x1?x2?x3?1（1） 给出其Kuhn—Tucker一阶最优性条件、拉格朗日函数、外点惩罚函数、增广格朗日函数。
（2） 验证x
1
(0)?(1,0,0)T满足Kuhn—Tucker一阶最优性条件，并求出相应的拉格朗日乘子。
（1） Kuhn—Tucker一阶最优性条件
???*??*2x1?0?1??*??*2x2?0? ? 。。。。。。。。。5分 **1????2x?03?**???(x1?x2?x3?1)?0,??0拉格朗日函数：
22L(x,?)?x2?x3??1(y2?(x1?x2?x3?1))??2(x12?x2?x3?1) 。。。。。。。5分
外点惩罚函数：
22F(x,?)?x2?x3??1max[{0,?(x1?x2?x3?1)}]2??2(x12?x2?x3?1)2 。。。。。。5分
增广格朗日函数：
22P(x,?,?)?x2?x3??1(y2?(x1?x2?x3?1))??2(x12?x2?x3?1)??1max[{0,?(x1?x2?x3?1)}]??2(x?x?x?1)（2）易验证：x(0)22122232 。。。。。。。。5分
?(1,0,0)T满足Kuhn—Tucker一阶最优性条件，且?*?1 。。。。。。。。10分
min{(x1?1)3?x2}3、 （10分）用内点法求解问题的K-T点。?x1?1?0
2??x2?02 解：定义障碍函数：G(x,rk)?(x1?1)?x2?rk(311?) 模型：minG(x,rk)。。。3分
x?intDx1?1x2?1??G2?3(x?1)?r()?01k???x1(x1?1)2*T ? 解得：xrk?(x1,x2)?(?1??G1??2x2?rk(2)?0??x2x2?rk?0rk3rkT,)。。。4分 32* x*?lim?xr。。。。。。。。。。。3分 ?(?1,0)，有条件x1?1?0，得K-T点为（1，0） 。k4、 （10分）求下列双目标规划
2minf(x)?(f1(x),f2(x))T 的有效解和弱有效解。
x?D其中 f1(x)?x?2x,f2(x)??x,D?{x?R0?x?2}
解：集合D为?0,2?，在f1Of2坐标面上画出象集合，方程为f1?f2?2f2。。。。。。。。。5分
2图形为：
2
由接触点定理知：
?f(D)的有效点和弱有效点集皆为：Epa?Ewp?AB 。。。。。。。。。。2分
?而AB的原象为[1，2]，于是：Rpa?Rwp?[1,2] 。。。。。。。。。。。。。。。。。。。。。。。。。3分 5、 （10分）设问题①为
max(f)?c1x1?c2x2?????cnxn?a11x1?a12x2?????a1nxn?b1?ax?ax?????ax?b2112222nn2 ? ?????????ax?ax?????ax?bm22mnnm?m11?x1,x2,x3,???xn?0?（1） 写出问题①的对偶问题②。
（2） 证明问题①有最优解的充分必要条件是问题②有最优解。 解：（1）问题①的对偶问题②为：
min(g)?b1y1?b2y2?????bmym?a11y1?a21y2?????am1ym?c1?ay?ay?????ay?c121222m2m2 ? 。。。。。。。。。。。。。。。。5分 ?????????ay?ay?????ay?cmn2mnmn?mn1?y1,y2,y3,???ym?0?（2）max(f)?CX?(AY)X?Y(AX)?Yb?(bY)?bY?min(g) 说明f(X)和g(Y)分别有上界和下界。
又可行域D是有界闭集，则最优解同时存在。 。。。。。。。。。。。。。。。。。5分
TTTTTTTTminz??2x1?3x2?x1?2x2?8?6、 （15分）用单纯形法求解：?4x1?16??4x2?12??x1,x2?0最优解x?(4,2) 。。。。。。。。。。。。12分
* 最优值max(z)?14 。。。。。。。。。。。。。。3分
3