最优化计算方法课后习题答案高等教育出版社。施光燕
①若(4)式等号不成立,即9?x1?x2?0,那么由(2)式得??0,将??0代入(1)式解得
22x1?2,x2?1,所得值满足以上所有约束。
②若(4)式等号成立,由(1)式可以解得x1?2221,x2?,代入(4)式有: ??1??15?2??1????1? 解得 ??9????3???1????1?因为??0,所以所得?值均舍去,该情况不成立。
综上所述,所求非线性规划有唯一的K-T点为:
x??(2,1)T
8题解如下 8 考虑问题
Min x12+x1x2+2x22-6x1-2x2-12x3 S、t、 X1+x2+x3=2 (1) -x1+2x2≤3 (2) X1,x2,x3≥0 (3)
求出点(1,1,0)处的一个下降可行方向、
解:首先检查在点(1,1,0)处哪些约束为有效约束。检查易知(1),X3≥0为有效约束。设所求可行方向d=(d1,d2,d3)T。根据可行方向d的定义,应存在a>0,使对?t∈(0,a)能有 X+td=(1+td1,1+td2,0+td3)T 也能满足所有有效约束:
(1+td1)+(1+td2)+(0+td3)=2 td3≥0 经整理即为
d1+d2+d3=0 d3≥0
满足上述不等式组的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即
?2???1????0??x1???6???x2????2??f??1???4????0????????0???0????0????x3?????12??▽f(1,1,0)=(-3,3,-12)
因为 ▽f(1,1,0)Td=-21<0
表明d=(1,-2,1)T为原问题在x=(1,1,0)T处的一个下降可行方向
最优化计算方法课后习题答案高等教育出版社。施光燕
9题解如下
9 用lemke算法解下列问题: （1）min 2x12+2x22-2x1x2-4x1-6x2 S、t、 X1+x2≤2 X1+5x2≤5 X1,x2≥0 解:
?4???2??2???4??1?????1?H??b?c?A????????1?????5??2??4? ,?5? ??6?,??,
于就是
?0??0???1???1??2??y1??u1??0??0???1???5??5??y2??u2??q???w???z???M???1??1????4????2???4??v1??x1??????????1??5???????????,??6?,?v2?,?x2?
与本题相应的线性互补问题为:
W-MZ=q W≥0,Z≥0 WTZ=0 写成表格为 W1 1 1 0 0 0 W1 1 W2 2 0 1 0 0 W2 2 W3 3 0 0 1 0 W3 3 W4 4 0 0 0 1 W4 4 Z1 5 Z1 5 0 0 -1 -1 Z2 6 Z2 6 0 0 -1 -5 Z3 7 Z3 7 1 1 -4 2 Z4 8 Z4 8 1 5 2 -4 W0 9 q di0 2 5 -4 -6 q di0 由于右端有负数,所以加一人工变量W0,表格改为 1 0 0 0 JBi 0 1 0 0 W1 1 0 0 1 0 W2 2 0 0 0 1 W3 3 0 0 -1 -1 W4 4 Z1 5 0 0 -1 -5 Z2 6 1 1 -4 2 Z3 7 1 5 2 -4 Z4 8 -1 -1 -1 -1 W0 9 2 5 -4 -6 q di0 选择与max{-qi}=-q4=6相应的第4行第9列元素作主元进行旋转,得
1 2 3 1 0 0 0 1 0 0 0 1 -1 -1 -1 1 1 0 5 5 4 -1 -1 -6 5 9 6 0 0 0 8 11 2 最优化计算方法课后习题答案高等教育出版社。施光燕
9 0 0 0 -1 1 5 -2 4 1 6 由上表可瞧出仅w4,z4这一对变量全部不就是基变量,因此从它们之中选一个进基,由于第一次碰到这一对变量,故选z4进基、在所选列中,有 Min {8/5,11/9,2/6,6/4}=2/6
故选相应的第3行第8列元素作主元,再进行旋转,得 JBi 1 2 8 9 1 0 0 0 1 2 0 1 0 0 3 -5/6 -9/6 1/6 -4/6 4 -1/6 3/6 -1/6 -2/6 5 1 1 0 1 6 10/6 -1 4/6 14/6 7 4 8 -1 2 8 0 0 1 0 9 0 0 0 1 di0 38/6 8 2/6 28/6 由于W0仍在基变量中,故继续运算、由于这时仅有W3,Z3这一对变量全不在基中,故仍在它们之中选一变量进基,由于就是第一次从这一对变量选取,故也选Z3进基,再由
Min {38/6/4,8/8,28/6/2}=8/8
故选第二行第7列元素作主元,进行旋转,得 JBi 1 7 8 9 JBi y1 1 1 0 0 0 1 1 0 0 0 再继续,得 y2 2 -9/31 7/62 11/62 -3/31 V1 3 49/62 -59/248 -147/744 -25/62 V2 4 -1/31 5/124 -3/372 -11/62 u1 5 -4/31 5/31 9/124 9/31 u2 6 0 0 0 1 X1 7 0 1 0 0 X2 W0 8 9 0 0 1 0 -26/31 3/62 -13/62 12/31 di0 2 -1/2 1/8 1/8 -1/4 3 -1/12 -3/16 -1/48 -7/24 4 -5/12 1/16 -5/48 -11/24 5 1/2 1/8 1/8 3/4 6 13/6 -1/8 13/24 31/12 7 0 1 0 0 8 0 0 1 0 9 0 0 0 1 di0 7/3 1 4/3 8/3 1 7 8 6 -208/93 35/31 24/31 32/31 在上表中W0已被置换出基,即得到了相应线性互补问题的解,也就就是所求二次规划的
最优解:y1=-208/93,x1=35/31,x2=24/31,u2=32/31,y2=v2=v2=u1=0,即x*=(35/31,24/31)T 12题解如下
12、(1)外点法min f(x)?x1?x2 s、t、 x1?1 解: 定义惩罚函数 F( x,?22??x12?x22???max?0,??x1?1???2=
2x12?x2 当 x1?1
22 x1?x2???x1?1? 当x1?1
2用解析法求解 min F(x,?),有
最优化计算方法课后习题答案高等教育出版社。施光燕
?F? ?x1 2x1 当x1?1
2x1?2??x1?1? 当x1?1
?F?2x2 ?x2令
?F?F?0 ,?0 ?x1?x2?得到 x???x1,x2?T????,0?T
?1??????易见,当????时,x??x??1,0?T
x?恰为所求费线性规划的最优解。
13题解如下 13、(2)内点法
2minx12?x2s..2tx1?x2?2?0 ?x1?1?0解:定义障碍函数
?11?G?x,rk??x?x?rk????
2x?x?2?x?1?121?2122用解析法求解minG?x,rk?令
x?intD
2rkrk?F?2x1???0 22?x1?2x1?x2?2???x1?1?rk?F?2x2??0 2?x2?2x1?x2?2?grk
解得 x??x1,x2??(0,1)
gg当rk?0时，xrk?x?(0,1),x确为最优解。
g习题五
包括题目:P108页 5;10