最优化方法及其应用课后答案.docx

资源描述

《最优化方法及其应用课后答案.docx》由会员分享，可在线阅读，更多相关《最优化方法及其应用课后答案.docx（25页珍藏版）》请在三一办公上搜索。

1、最优化方法部分课后习题解答习题一1. 一直优化问题的数学模型为:min f(x) =(x -3)2 +(x -4)2f 1 5 2g (x) =x -x - U0I 112 2st|g (x) =-x -x +5 20g3(x) =X 20g (x) =x 2042试用图解法求出：(1) 无约束最优点，并求出最优值。(2) 约束最优点，并求出其最优值。(3) 如果加一个等式约束hX =x -x =0，其约束最优解是什么？12解：(1)在无约束条件下，f(x)的可行域在整个x0x平面上，不难看出，当x =*3, 4)12时，f M取最小值，即，最优点为带=(3， 4):且最优值为：f(x*) =

2、0 (2)在约束条件下，f(x)的可行域为图中阴影部分所示，此时，求该问题的最优点就是在约束集合即可行域中找一点* %)，使其落在半径最小的同心圆上，显然，从图示中可以看出，当X* = (? , 5)时，f(x)所在的圆的半径最小。其中：点为gi和g2(x)的交点，令，、5八g (x) =X -X - =0-1 122g (x) =-x -x +5 =0I 15 4 求解得到：I 0该优化问题属于三维的优化问题。s: 1x 02 cx 03x= -Js/ 3,y = s/ 3,z = 寸s/12(3s =18 =习题二3.计算一般二次函数f(X) =1 X以X +bTX +的梯度。解：设：A

3、 =(a ),b =(b,b ,.b)T,X =(xx，x )t则：i nxn1 2 n12 nf(x) = 1 _ n n a xx2 H 户 ji jn bx +c,将它对变量x (i =1, 2,.n)球偏导数得:f)=ldf(x)1 I位 |11df(x)1 ,Z_a x +j=11 l|2 a x +j=1 ax +b |=a x +b |=n a1 x | j=n a x2j j学111 =I a2 xb J|+b| f(x) 1dx J31j=x+nj j|2:|21 Mlax +b I =ax |nj jj=1|l j=1=|n i I2| bJ3=1 1=2(AX +A X)

4、 +b5.求下列函数的梯度和Hesse矩阵(1) f(x) =x2 +2x 2 +3x 2 -4xx12解：V2f(x)0 I 4 00 6(2)f(x) =3xx2 +ex1解：V2f(x)=6x +x2+xx/ w2126x +exx +xxexx6x +x2ecx2 1 2116, 判断下列函数是凸函数，凹函数，还是既不凸也不凹函数：(1) f(x,x ) =-x2 +2x 2 +3xx12121 2解：V2f(x)不是半正定，即f(x)非凸，然后判断-f(x)，经验证：V2( -f( x)不是半正定，由此可知：f(x)非凸非凹。(2) f(x,x) =2x2 -4xx +3x2 -5x

5、 -61 211 221解：V2f(x)半正定，故f(x)为凸函数。(3) f(x, x, x) =x 2 +2 x 2 -3x 2 -4xx1 2 31231 2解：V2f(x)不是半正定，即f(x)非凸，然后判断-f(x)，经验证：V2(-f(x)不是半正定，由此可知：f(x)非凸非凹。7. 设约束优化问题的数学模型为:min f(X) =x2 +4x +x 2 -4x +10I r11220g (x) =-x2 -x2 -2x +2x 0 试用K-T条件判别点x =-1,1是否为最优点。解：对于点x=-1,1，且g( x)是起作用约束，g(x) =0，g (x) 0,/点满足约束条件,

6、故点X是可行解。 1I 如 f =1-1 p由Vg(x) 0条件下的t满足K-T条K-T 条件得： f -.Vg(x) =01 0 ,得到 =2,点 x =-1 日件。又因V2f(x)正定，故f(x)为严格凸函数，该最优化问题是凸规划问题，由 x* =-1,1是K-T点，所以x* 4-1,1也是该问题的全局最优点。8. 设约束优化问题:min f(x) =(x -2)2 +x 2|(g( x) =-x M02st. g (x) =-x V02 |2g (x) =-1 +x2 +x V03 12试用K-T条件判定它是不是约束最优解。，点x =1,0是可行点，、筒 /)E / 5 =i 目它的当前

7、迭代点为x =1,0, k解：对于点 xk =h,0 g (“)了 - 0g (x) =0gk(x ) =0且起作用的约束条件是，g (x),g (x), I =2,3, Vf(x) =123kVg (x ) =1 H 由约束条件为g(x) 0 i ii日3 k M /i解得： 2 =1，所以x =11,0 丁为K-T点。 =1k现判断该问题是否为凸规划问题，因V2f正定，故f(x为凸函数，g(叫g(x)为线性函数，亦为凸函数，V2g(x)半正定，所以g为凸函数，所以该优化问题为凸3 3规划问题，即点X =1,0是该问题的约束最优解。k习题三1. 对于下列线性规划问题找出所有基解，指出哪些是基

8、可行解，并确定出最优解。max f(x) =3x +x +2x12x +3x +6x +x =91234(1) st I8x +x -4x +2x =1012353. =0x 0(j=1,2.6)12 3 6 3 0 0 I解：令 A=|81 -4 0 2 0 =(P P, P, P, P, P)1/ 1 2 3 4 5 6勺 0 0 0 0 -1/1(1) 基解x =(。16,- (13) 基解x =(030,0, ,0)是基可行解，且f(x =3。，殳0，0)不是基可行解，I 36(2) 基解x =(0,1Q7,Q0)不是基可行解，2(3) 基解x =(0JQQ3.50)是基可行解，且f(

9、x)=3，3721(4) 基解x =( -, 4,0,0,0 )不是基可行解，444(5) 基解x =(0Q-|,8,0,0)不是基可行解，523(6) 基解x6 =(00, ,20,16,0)是基可行解，且 f(x =3，(7) 基解x =(10,-1,0,0,3)不是基可行解，72(8) 基解x =(0QQ3,5,0)是基可行解，且f(x) =0，8(9) 基解 =9矽,0, -2,0,15|不是基可行解。(10) 基解x =*,0,0, 4,#是基可行解，且f(x) = 。13210 44416 7(11) 基解x =(0,厂, -,0,0)不是基可行解。II 36(12) 基解x =(

10、0,1Q,-7,0,0)不是基可行解。12(14)(15)基解x 14=(01-5,8必,0)不是基可行解。 3八基解x =(00, ,0,8,0)是基可行解，且f(X =3。(16)152基解x =(0QQ35,0)是基可行解，且f(x) =3。 162, 用单纯形法求解下列线性规划问题：max f(x) =10x +5x(1)底 +4 x2 9st5 x +2x 8X, x 20解：将现行规划问题化为标准形式如下：min( -f(x) = -0x -5x +0x +0x234I |Bx +4x +x =9& 5 x +2x +x =8虹 x, x, x 201234作初始单纯形表，并按单纯

11、形表步骤进行迭代，如下:CBXBb-10x1-5x20x30x40i0x39341030x4852011.60-10-5000x34.202.81-0.61.5-10x11.610.400.24160-102-5x21.5015 百314-10x11101 72717.5005 百25 百3此时，。卢为正目标函数已不能再减小于是得到最优解为f =(1,罗,0)目标函数值为：f(W =17.53. 分别用单纯形法中的大M法和两阶段法求解下列线性规划问题:min f(x =5x -2x +3x -6x(1234x +2 尤 +3 尤 +4 x =7x +x +x +2x =311234X,x,x,

12、x 20 1234解：(1)大M法：把原问题化为标准形式，并加入人工变量如下:min f(x =5x -2x +3x -6x +Mx +Mx(123456I x +2x +3x +4x +x =7 12345st 2 x +x +x +2x +x =312346x,x,x,x,x,x 20123456作初始单纯形表，并按单纯形表步骤进行迭代，如下:CBXBb5X1-2X23X3-6X4-6X4-6X40iMX571234101.75MX632112011.5-10M5-3M-2-3M3-4M-6-6M00MX51-30101-21-6X41.510.50.5100.539-M11+3M16-M

13、003M+33X31-30101-2-6X412.50.501-0.51.5329100M-6M+15因为M是一个很大的正数，此时七均为正，所以，得到最优解：x* =(0Q1,)4，最优值为f(x*)=-(2)两阶段法首先，构造一个仅含人工变量的新的线性规划如下:min 欢 _x) =0 尤 +0x +0x +0x +x +x(123456I x +2x +3x +4x +x =7 60 %15 %2.002000B1.502500C20 %60%0/ =1,2,3表示甲、乙、丙中分别含A、B、C的含量，构造此问题的数学 i i i规划模型如下：max f（x） =0.9x +1.4x +1

14、.9x +0.45y +0.95y +1.45y -0.5z +0.45z +0.95z r123123123x +y普至000x +y +z 2500 222x +y +z 1200IJst 00.4X -0.6x -0.6x 0 1230.2x +0.2x -0.8x 0 1230.6y -0.6y +0.4y 00.5z +0.5z -0.5z 0 123x, y, z 0i=1,2,3 i i i5. 求解下列线性规划问题的对偶问题min f（x） =2 x +2x +4x1232x +3x +5x 2（1）t x +x +7 x 3st 123x +4x +6x 0max f（x）=

15、5x +6x +3xx +2x +2x =5（2）J I-x +5x -x 3|4x +7x +3x 0x 0 解：(1)由表3.7可得该问题的对偶问题为： max 欢 y) =2 y +3 y +5 y 0y +3y +y 2此1 1 + y 2+4y 2St. U. 23|5y +7 y +6 y 0,y,y 6 sE | 1 2 3I I2, -y +3 y 无约束,y户0, y 06. 用对偶单纯形法求解下列线性规划问题：min f(x) =4 x +12x +18x123lx +3 x 3(1)I 公c3 yst |2x +2x 5Il 2 3X,x,x 0123解：(1)首先，将“

16、”约束条件两边反号，再加入松弛变量，得:min f(x) =4x +12x +18x +0x +xI |l-x -3x +x =-3s. -2x -2 x +x =-5X, x, x, x, x 0 1 2 3 4 5建立初始单纯形表如下图所示，所有 0。则对应对偶问题解是可行的，则继续迭代：CBXBb4x12x 18x 20x0x M0x-31-10-341004x-50-2-201计算min 53,-5)=-5，所以x为丰们出变4量，0 =min %,9=(i，确定x -力换入变如继续迭代，得到如下单纯形表:CBXBb4x 112x 18x 20x40x0x-3-10-31004x -2.

17、50110-0.5240600min(-3)= -,x4换出，min(4,2=2, q换入。CBXBb412x18x000x101_100x1.5_1101-0.5220026. 一，八，一一一.e 3、此时，所有a湘，故原问题的最优解为x纣0, -,1r，最优值为：f(x) =36j2其对偶问题得到最优解为：笫=2,6r，最优值为：f(W =36。7. 已知线性规划问题min f(x) =2x -x +x 1 2 3I |x +x +x 旬st - x +2x V412X,x,x 20先用单纯形法求出最优解，再分别就下列情况进行分析:(1)目标函数中变量十,x2,x3的系数分别在什么范围内

18、变化，问题的最优解不变;(2)两个约束条件的右端分别在什么范围内变化，问题的最优解不变。解：将该规划问题化为标准型，引入松弛变量j*min f(x) =2x -x +x +0x +0x,I (x +x +x +x =6I 1 2 3 4旦-x +2x +x =4lx, x , x, x, x 201 2 3 4 5用单纯形法求解，如下表:CBXBb2x-1x Q1x0x0x R00xA111114060x1.5-12001252-11000xA41.5011-0.5-14x 2-0.51000.51.50100.5由上表可知，所有的检验数均大于等于零，得最优解尤=(02Q40)t，所以原问题的

19、最优解为：尤=(02Q)t，最优值f(x-) =-2(1)变量x，x，x中，x，x为非基变量，x为基变量。 1231323,3 .-11由o =，当Ac -时，c =c +Ac ，所以，当c e,毋；此时最优解不变。i 2 i 2 i i i 2i 2由。3 =1，当A -1时匕=与+八与0所以，当c3 e0, +阿,此时最优解不变。A eMD最优解不变。综上，当c Ej,俱，c界-4,0，c e0,俱,此时最优解不变。(2) Ab的变化范围 1Ab 1 41 15t = jl J 0-0.51Ab14 1LJ01 0.5甘 A0j 1 I0J1得到：4 +Ab 0 n Ab 4,11 41

20、1而。1o B-1b+B1则b的变化范围是b 2,最优解保持不变。 1-0.5101 410.5 Jlj1 2J1-0.5101h J Ab2 loj最优解保持不变。得到：-4Ab 8，则b的变化范围是0,i2，习题四3. 用Newton法求解侦力=t -2t+1用第1题求得的区间，按精度 =0.01计算。解：侦t) =0(0) =1, t =t +h =10(t) =0,0 =0,因为巾(t)切(t)，则 h =h =2 0100111010t =t +h=1,0(t)=22,02=22,0(f)0(n，反向，因为 K=2,0,所以a=0,b=3则搜索区间为 t 0,3 0(t) =3t -

21、2,0(t) =6,0(0) =-2 0 取：t =1,0(t) =1,0(t) =6所以 t =1 = =1? 0.01,继续迭代 t =t =,0006 6 606t =t -0!9,则 t-t=11 0.0令 t= 4，则=0.81650 0 (t)600 600 600t-t0 | =0.0005 0.0所以t*=0.817,* =0 (t*) = 0.088。4. 用黄金分割法求解min0(t) =t(t +2)已知初始单谷区间a, b=-3, 5,按精度 =0.001计算。解： = - +0.382 x8 =0.056,t2 = - +5 -0.056 =1.944 ,0(t) =

22、0.115136,0(t) =7.667136 ,因为 0(t) e,继续迭代，因为0(t) 0(t)，则新的搜索区间为-3, 0.056： =-.832608,0 (p = 0.306764, t = -.111392,0 (t) =-0.987592,t -t2 |e,继续迭代，因为0(p 0(t)，所以新的搜索区间为-1.832608，0.056： =-.111292,0(p =-0.987592,t =-0.665448,0(t) =-0.888075,t -t1 2,继续，0(t) 0(p，所以新的搜索区间为-1.832608, -0.665448: t = -.3867530 (

23、t) =-0.854402, t =-1.111392,0 (t) =-0.987592,- |,继续，因为0(t) 0(t)，所以新的搜索区间为-1.386753,-0.665448t =-0.940987,0 (t) =-0.996518,t =-1.111392,0 (t) =-0.987592,t - |,继续，因为0(t) 0(t)，所以新的搜索区间为-1.111392,-0.665448: t1 = 0.940987,0 (t) = 0.996518, t2 = 0.835799,0 (t) =-0.973038,t - |,继续，因为0(f) 0(t)，所以新的搜索区间为-1.1

24、11392,-0.835799: t = 0.940987,0 (t) = 0.996518,( = -.006115,0 (t) = 0.999962,t - |,继续，因为0(0(t)，所以新的搜索区间为-1.111392,-0.940987: t1 = -.046295,0 (p = 0.997857,七=-.006115,0 (p = 0.999962,t - |,继续，因为0(p 0(t)，所以新的搜索区间为-1.046295,-0.940987: t = -0.981215,0(?) = 0.999647,t = -.006115,0(t) = 0.999962,t - |,继续，

25、因为0(0(t)，所以新的搜索区间为-1.046295,-0.981215:t = -.021434,0 (t) =-0.999540, t =-1.006115,0 (t) =-0.999962,1122t - |,继续，因为0Op 0(t)，所以新的搜索区间为-1.021434,-0.981215: t =-0.996579,0(t) =-0.999987,t =-1.006115,0(t) =-0.999962 ,t - |,继续，因为0(p 0(t)，所以新的搜索区间为-1.006115,-0.981215:t = 0.996579,0 (t) =-0.999987,t =-0.990

26、727,0(t) =-0.999914,1122t - |&继续，因为0(p &继续，因为0(p &继续，因为0(0(t)，所以新的搜索区间为-1.002472,-0.996579:t =-0.998830,0(t) =-0.999998505,t =-1.000237,。(t) =-1.00000016,2211t -2 |,继续，因为 0(t),t t,0(t) =-0.063 , t t ,。（。=-0.1588 。（,） =-0.063，所以，新的搜索区间为0.5227，1， =0.5227,2 =1, =0.5704, t =0.6146, 0-t 一| & t t,0(t) =-0

27、.2004 ,t t ,0(t)= 0.2029 , t t,0(D = 0.2032 , t 寻,。(t) =-0.2034 。( =-0.2032 新的搜索区间为0.6260, 1, =0.6260, =1* =0.6284, t =0.6276, t - ,t是。(Z)在区间上的近似最优解，t =。0.6276 ,。* =。（户）=-0.2034。习题五1.用最速下降法求解 min f(x2 +25x2, 2X 0 纣-11|2 :,2t，C =0.01.解：fx =2%,50% 矩阵 a=i % g =Vf(x) =4,100 00/gX =X0g10 gTAg00f(x) =3.68

28、6551g =f(x) =3.83976 11% =% 一 i gTg = | %2 =X 1 1 本 gI11f(x) =0.12487221、0150T ,|q | =100.07997T214=|0.02003 | |=|L21L100J L -0.003J1.919881 =I-0.15, T llq I 乂1.9198813.89761 .0.073481.L -0.003 J1 她48089 J1 =IL0.06913JIllg辰，2 Jq1同理继续迭代，最后至x=|0j一. .01 T 一此时最优解x=| L0J，f(x)=0min f(X) =60-10x -4x +x121

29、G(X)=I-12 J|=2|33n % =% -G( %)-1 g( x)1001I30 F21L3j -101=8,6t 4J2.用Newton法求解2+气2-贫初始点% =0 S =0.01.解：g(X =f(X =-10 +2x -x , -4 +2x -x tf%) =0,0 , t|f%) I =0 0.01最优解为，=8,6t,f(%=) =83.用修正Newton法求解min f(%) =4(% +1) +2(q -1) +%2+普+10,初始点%0 =0, 0 , c =0.01.9 -t 80解：g(x) =fx =8x +9, 4x -32T x =x +t p =1I

31、=0.01.0P20 =-fx) = -2,8Tx x +t+t I2 I _|1 _2t 1 8t tx =x +t P it 1 2/ ,1 8t1 0 0 010-8 J00令min(1-2t) 2 +4(1-8t)2 =min0(/), 00则 d侦t) =520t -68 =0 ntdt0=0.1309690x =0.738062, -0.047752t,1fx) =1.476124, -0.382016tf 1)=2.324878 =0.034189件)if 68新搜索方向为p = -f(x) +X p1 10 0-1.476124=l 0.382016 _+0.0341891-2

32、1-1.5445021，-8J1 =l 0.108504 因此有 x =x +t p =0.738062 -1.544502t, -0.047752 +0.108504t211111由 df+P)=0=t =0.4771270.738062 11-1.5445021因而得下一迭代点 % = + p =l_0)47752+0J477127 I 0 08504 =0-00,0.007t|(x) | =0 0.0停止迭代x* =0,0 t,f(x)*=05.用共轭梯度法求解minf(x) =2x2 +x2-xx, 自定初始点T，取初始点x =。,1 T 0解：Vf (%) =4x -x, 2x -x 122101x =x +t p =| I +t I10 0 01J令 min2t2 +(1-2t )2-t (1-2t) =min巾(t)0则力侦)000=16t -5 =0 nt =00125x =0.3125, P.375T, f) =0.875,0.4375t11BL! =0.95703125 =0.19

展开阅读全文