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

习题二包括题目： P36页 5（1）（4）5（4） 习题三包括题目：P61页 1(1)(2); 3; 5; 6; 14；15(1)1(1)(2)的解如下 3题的解如下 5,6题14题解如下 14. 设, 求点在处的牛顿方向。解：已知 ，由题意得 15（1）解如下 15. 用DFP方法求下列问题的极小点（1）解：取 ，时，DFP法的第一步与最速下降法相同， ， 以下作第二次迭代， 其中， ， 所以 令 ， 利用 ，求得 所以 ， 以下作第三次迭代 ， ， 所以 令 ， 利用 ，求得 所以 ， 因为 ，于是停止即为最优解。习题四包括题目： P95页 3；4；8；9(1)；12选做；13选做3题解如下 3.考虑问题，其中（1）画出此问题的可行域和等值线的图形；（2）利用几何图形求出此问题的最优解及最优值；（3）分别对点指出哪些约束是紧约束和松约束。解：（1）如图所示，此问题的可行域是以O点为圆心，1为半径的圆的上半部分；等值线是平行于直线x2=2x1的一系列平行线，范围在如图所示的两条虚线内。（2）要求f的最小值，即求出这一系列平行线中与x2轴相交，所得截点纵坐标的最大值。显然当直线在虚线1的位置，能取得极值。如图求出切点，此点即为最优解，解得最优值PO 1x1x2x2=2x1xp11/2虚线1（3）对于区间集S可以简化为g1:g2:对于点，g1和g2均为该点处的紧约束；对于点，g1和g2均为该点处的松约束；对于点，g1为该点的松约束，g2为该点的紧约束；对于点，g1为该点的紧约束，g2为该点的松约束。4题解如下 4.试写出下列问题的K-T条件，并利用所得到的表达式求出它们的最优解：（1）s.t. （2）s.t. （1）解：非线性规划的K-T条件如下： （1） （2） （3）再加上约束条件 （4）为求出满足（1）（4）式的解，分情况考虑： 若（4）式等号不成立，即，那么由（2）式得，将代入（1）式解得，所得值不满足的条件，故舍去。若（4）式等号成立，由（1）式可以解得，代入（4）式有： 解得因为，所以，那么，满足以上所有条件。综上所述，所求非线性规划有唯一的K-T点为：(2)解：非线性规划的K-T条件如下： （1） （2） （3）再加上约束条件 （4）为求出满足（1）（4）式的解，分情况考虑： 若（4）式等号不成立，即，那么由（2）式得，将代入（1）式解得，所得值满足以上所有约束。若（4）式等号成立，由（1）式可以解得，代入（4）式有： 解得因为，所以所得值均舍去，该情况不成立。综上所述，所求非线性规划有唯一的K-T点为：8题解如下 8 考虑问题 Min x12+x1x2+2x22-6x1-2x2-12x3 S.t. X1+x2+x3=2 （1） -x1+2x23 （2） X1,x2,x30 （3）求出点（1,1,0）处的一个下降可行方向.解：首先检查在点（1,1,0）处哪些约束为有效约束。检查易知（1），X30为有效约束。设所求可行方向d=(d1,d2,d3)T。根据可行方向d的定义，应存在a0，使对t（0，a）能有 X+td=(1+td1,1+td2,0+td3)T也能满足所有有效约束： (1+td1)+(1+td2)+(0+td3)=2 td30 经整理即为 d1+d2+d3=0 d30 满足上述不等式组的d=(d1,d2,d3)T均为可行方向。现只求一个可行方向，所以任取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）因为 f（1,1,0）Td=-210表明d=（1,-2，1）T为原问题在x=（1,1,0）T处的一个下降可行方向 9题解如下 9 用lemke算法解下列问题：（1） min 2x12+2x22-2x1x2-4x1-6x2S.t. X1+x22 X1+5x25 X1,x20解： ，于是，与本题相应的线性互补问题为： W-MZ=q W0,Z0 WTZ=0写成表格为W11W22W33W44Z15Z26Z37Z48qdi01000001120100001550010-1-1-42-40001-1-52-4-6由于右端有负数，所以加一人工变量W0，表格改为W11W22W33W44Z15Z26Z37Z48W0 9qdi010000011-1201000015-150010-1-1-42-1-40001-1-52-4-1-6选择与max-qi=-q4=6相应的第4行第9列元素作主元进行旋转，得JBiW11W22W33W44Z15Z26Z37Z48W0 9qdi01100-115-15082010-115-190113001-104-66029000-115-2416由上表可看出仅w4，z4这一对变量全部不是基变量，因此从它们之中选一个进基，由于第一次碰到这一对变量，故选z4进基.在所选列中，有Min 8/5,11/9,2/6,6/4=2/6故选相应的第3行第8列元素作主元，再进行旋转，得JBi12345678 9di0110-5/6-1/6110/640038/6201-9/63/61-180088001/6-1/604/6-1102/6900-4/6-2/6114/620128/6由于W0仍在基变量中，故继续运算.由于这时仅有W3，Z3这一对变量全不在基中，故仍在它们之中选一变量进基，由于是第一次从这一对变量选取，故也选Z3进基，再由Min 38/6/4,8/8，28/6/2=8/8故选第二行第7列元素作主元，进行旋转，得JBi12345678 9di011-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再继续，得JBiy11y22V13V24u15u26X17X28W0 9di011-9/3149/62-1/31-4/31000-26/31-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）外点法min s.t. 解： 定义惩罚函数 F( = 当 当用解析法求解 min F(),有 当 当 令 ， 得到 TT易见，当时，T恰为所求费线性规划的最优解。13题解如下 13.（2）内点法解：定义障碍函数用解析法求解令 解得 （0,1）当（0,1），确为最优解。习题五包括题目：P108页 5；10 5题解如下 5. 试求的有效解集 解：用线性加权和法构造评价函数，令，；令，且，或则原问题转化为求对求导可得：由式可解得：即，又已知，或所以 有效解集为 或 10题解如下 10. 用线性加权和法求解：权系数取 解：构造函数，令，； 原求解问题转化成求解 构造拉格朗日函数L 求解 ，则如下，为拉格朗日乘子 对L函数求导得：由式分别得：代入式得：将代入式,可得：有效解为,把有效解代入，得，目标值为： 习题六包括题目：P130页 包括题目4；5；6；74,5题解如下 6,7题解如下 第六题答案1.与v1点相邻接的顶点有v2、v3两点，l2=1，l3=2，取Minl2、l3=1，于是连接v1、v2两点，令顶点集S=v1、v2；图示如下：V1V22.与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；图示如下：V1V2V33.与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；图示如下：V1V2V3V1V2V3V4V54.与S=v1、v2、v3、v4、v5相邻接的点有v6、v7两点，l6=Minl5+d56、l4+d46=6，l7=min l3+d37、l4+d47、l5+d57=7，取min= l6、l7=6，于是连接v4、v6两点，令顶点集S=v1、v2、v3、v4、v5、v6；图示如下：V1V2V3V4V5V65.与S=v1、v2、v3、v4、v5、v6相邻接的点有v7、v8两点，l7=min l3+d37、l4+d47、l5+d57、l6+d67=7，l8=l6+d68=11，min= l7、l8=7，于是连接v5、v7和v6、v7这两组点，令顶点集S=v1、v2、v3、v4、v5、v6、v7；图示如下V1V2V3V4V5V6V7V1V2V3V4V5V6V7V86.与S=v1、v2、v3、v4、v5、v6、v7相邻接的点有v8，l7= l5+d5