最优化计算方法课后习题答案----高等教育出版社施光燕

1、习题二包括题目：P36页5(1)(4)5(4)习题三包括题目：P61页1(1)(2);3;5;6;14;15(1)1(2)的解如下3题的解如下5,6题14题解如下14.设f(x)(6、2-、2_.TX1X2)(23x13x2X1X2),求点在(4,6)处的牛顿万向.解：x(4,6)丁,由题意得g1f(x)344562f(x)22(3x2)22(3x1)(3x2)2(23x1x1x2)22(3%)(3x1)2(23x13x2x®22(3x1)G(x)2f(x)1656564d(1)G(x(1)1g1141/100574/10015(1)解如下15.用DFP方法求以下问题的极小点22(1

2、)min3x1x25x1x2x13x2解：取x(0)(1,斤,H0I时,DFP法的第一步与最速下降法相同f(x)35x22x115x16x2(0)(1,1)T,f(x(0)1012(1)0.07801.3760,f(x)0.29361.1516以下作第二次迭代(1)(0)xx1.07801.2936f(x)f(x(0)8.624013.1516其中,1T126.3096,iTHo1iT1247.3380所以1.16211.39451.39451.67341TH074.3734113.4194113.4194172.9646(1)x1d,利用df(xdd)0,求得10.5727所以x(2)x(1

3、)0.5727d(1)0.77540.8535f(x)0.28330.244以下作第三次迭代(2)x(1)x0.85340.5599f(x)f(x)1.09270.9076所以1.4407,2THi1.99222d利用df(xd)-0,求得d所以d(2)由于f(x)0,于是停止(1,1)T即为最优解.习题四包括题目：3题解如下P95页3;4;8;9(1);12选做；13选做3.考虑问题minf(x)2x1函,%)sx2,其中(1)(2)画出此问题的可行域和等值线的图形；利用几何图形求出此问题的最优解及最优值;(3)分别对点x1T2T3T4T(1,0),x(1,1),x(0,0),x(0,1),

4、指出哪些约束是紧约束和松约束.解：(1)如下图,平行于直线x2=2x1此问题的可行域是以O点为圆心,1为半径的圆的上半局部；等值线是的一系列平行线,范围在如下图的两条虚线内.(2)要求f的最小值,即求出这一系列平行线中与x2轴相交,所得截点纵坐标的最大值.21显然当直线在虚线1的位置,能取得极值.如图求出切点P尸,一尸,此点即为最优解5.5x(4=,3)T,解得最优值f55,5(3)对于区间集S可以简化为gi：1x12x；0g2：x；0对于点x1(1,0)T,gi和g2均为该点处的紧约束;对于点x2(1,1)T,gi和g2均为该点处的松约束;对于点x3(0,0)T,g1为该点的松约束,g2为该

5、点的紧约束；对于点x4(0,1)T,g1为该点的紧约束,g2为该点的松约束.4题解如下4.试写出以下问题的K-T条件,并利用所得到的表达式求出它们的最优解:2/2(1) m1nxi2x21;221 Xx2022(2) m1nxi2x21;c22c9x1x20(1)解：非线性规划的K-T条件如下：2x142x1110(1)2x222x2(1x；x2)0(3)再加上约束条件1x2x20(4)为求出满足14式的解,分情况考虑:22假设4式等号不成立,即1XiX20,那么由2式得0,将0代入1式解得X12,x21,所得值不满足1Xi22X20的条件,故舍去.假设4式等号成立,由1式可以解得X12-1解

6、得14式有:由于0,所以1J5,那么X1-,X2,满足以上所有条件.综上所述,所求非线性规划有唯一的K-T点为:2解：非线性规划的K-T条件如下：2X142X12X222X20(1)22、(9X1X2)0(2)0再加上约束条件9X；X20(4)为求出满足14式的解,分情况考虑:22假设4式等号不成立,即9X1X20,那么由2式得0,将0代入1X2,代入(4)式有:11,X3>0为有效约束.设a>0,使对？tC0,a能有1式解得X12,X21,所得值满足以上所有约束.2假设4式等号成立,由1式可以解得X1,12221八一一;:9解得11由于0,所以所得值均舍去,该情况不成立.综上所述

7、,所求非线性规划有唯一的K-T点为：8题解如下8考虑问题Minx12+x1x2+2x22-6x1-2x2-12x3X1+x2+x3=21-x1+2x2W32X1,x2,x3>03求出点1,1,0处的一个下降可行方向.解：首先检查在点1,1,0处哪些约束为有效约束.检查易知所求可行方向d=d1,d2,d3T.根据可行方向d的定义,应存在X+td=(1+td1,1+td2,0+td3)T也能满足所有有效约束：(1+td1)+(1+td2)+(0+td3)=2td3>0经整理即为d1+d2+d3=0d3>0满足上述不等式组的d=(d1,d2,d3)T均为可行方向.现只求一个可行方向

8、,所以任取d3=1,求解d1+d2=-d3得d1+d2=-1,可任取d1=1,d2=-2得一可行方向d=(1,-2,1)T考虑下降性由题可知：将目标函数化为f(x)=1/2XTQX+bTX+C从而f=QX+b即f(1,1,0)=(-3,3,-12)由于Vf(1,1,0)Td=-21<0说明d=(1,-2,1)T为原问题在x=(1,1,0)T处的一个下降可行方向9题解如下9用lemke算法解以下问题：(1)min2x12+2x22-2x1x2-4x1-6x2.X1+x2<2X1+5x2&5X1,x2>0解：424112HcAb246155于是00112y1u100155

9、y2u2Mqwz11424v1x1156v2x2,与此题相应的线性互补问题为：W-MZ=qW>0,Z>0WTZ=0写成表格为W11W22W33W44Z15Z26Z37Z48qdi01000001120100001550010-1-1-42-40001-1-52-4-6由于右端有负数,所以加一人工变量W0,表格改为W11W22W33W44Z15Z26Z37Z48W09qdi010000011-1201000015-150010-1-1-42-1-40001-1-52-4-1-6选择与max-qi=-q4=6相应的第4行第9列元素作主元进行旋转,得JBiW11W22W33W44Z15Z

10、26Z37Z48W09qdi01100-115-15082010-115-190113001-104-66029000-115-2416由上表可看出仅w4,z4这一对变量全部不是基变量,因此从它们之中选一个进基,由于第一次碰到这一对变量,应选z4进基.在所选列中,有Min8/5,11/9,2/6,6/4=2/6应选相应的第3行第8列元素作主元,再进行旋转,得JBi123456789di0110-5/6-1/6110/640038/6201-9/63/61-180088001/6-1/604/6-1102/6900-4/6-2/6114/620128/6由于W0仍在基变量中,故继续运算.由于这时

11、仅有W3,Z3这一对变量全不在基中,故仍在它们之中选一变量进基,由于是第一次从这一对变量选取,故也选Z3进基,再由Min38/6/4,8/8,28/6/2=8/8应选第二行第7列元素作主元,进行旋转,得JBi123456789di011-1/2-1/12-5/121/213/60007/3701/8-3/161/161/8-1/81001801/8-1/48-5/481/813/240104/390-1/4-7/24-11/243/431/120018/3再继续,得JBiy11y22V13V24u15u26X17X28W09di011-9/3149/62-1/31-4/31000-26/31-

12、208/93707/62-59/2485/1245/310103/6235/318011/62-147/744-3/3729/124001-13/6224/3160-3/31-25/62-11/629/3110012/3132/31在上表中W0已被置换出基,即得到了相应线性互补问题的解,也就是所求二次规划的最优解：y1=-208/93,x1=35/31,x2=24/31,u2=32/31,y2=v2=v2=u1=0,即x*=(35/31,24/31)T12题解如下12.(1)外点法minf(x)2x12x2Xi解：定义惩罚函数F(x,22为x2max0,X12x1当X1用解析法求解2x12x2

13、x11当X1minF(x,有2x1当x1易见,当x2x1,x2时,2x1x1当x1x1,0x恰为所求费线性规划的最优解.13题解如下13.(2)内点法解：定义障碍函数用解析法求解minGx,rkxintD解得xgrkX,x2(0,1)xgkg(0,1),x确为最优解.习题五包括题目：P108页5;105题解如下5.试求min2X1X2,(X1221)(X21)T的有效解集和法构造评价函数令fi2X2,X2fl,f20,1Tf1f1原问题转化为求min对fX求导可得:由式(1)(2)可解得:X2即X1x22,又20,10,1所以有效解集为X1,X2X1X2,0X1X1,X2X2,0X110题解如

14、下10.用线性加权和法求解:权系数取u10.36,u20.64解：构造函数uTff1X2X322f2x12x2f1,f2原求解问题转化成求解min构造拉格朗日函数L求解minLK,X2,X3,X1X2为拉格朗日乘子对L函数求导得:由(1)(2)(3)式分别得:代入(4)式得:4.616将4.616代入(1)(2)(3)式,x12.67,可得：x21.84x31.48.有效解为(x,x2,x3)T(2.67,1.84,1.48)T,把有效解(2.67,1.84,1.48)T代入f1,f2得,222目标值为：minf12.6711.8421.4835.13习题六包括题目：P130页包括题目4;5;

15、6;74,5题解如下6,7题解如下第六题答案1.与V1点相邻接的顶点有V2、V3两点,12=1,13=2,取Minl2、l3)=1,于是连接V1、V2两点,令顶点集S=V1、V2；图示如下:2.与S=V1、V2相邻接的顶点有V3、V4、V5三点,l5=l2+d25=1+3=4,l4=l2+d24=1+3=4,Minl2+d23>l3=1,取Minl3、l4、l5=1,于是连接V1、V3两点,令顶点集S=V1、V2、V3;图示如下：V2V1V33.与S=V1、V2、V3相邻接的点有V4、V5、V7三点,l5=l2+d25=1+3=4,l4=l2+d24=1+3=4,l7=l3+d37=2+8=10,取Minl4、l5、l7=4,于是连接V2、V4、V5三点,令顶点集S=v1、V2、V3、V4、V5；图示如下：4.与S=v1、V2、V3、V4、V5相邻接的点有V6、V7V六,l6=Minl5+d56、l4+d46=6,l7=minl3+d37、l4+d47、l5+d57=7,取min=l6、l7=6,于是连接'V4、V6两点令顶点集S=v1、V2、V3、V4、V5、V6；图示如下:'V4,V55.与S=v1、V2、V3、V4、V5、V6V1邻接的点背2V7、V8两点,l7=minl3+d37、l4+d47、l5+d57、l6+d67=7,l