《非线性规划(管理运筹学,李军).docx》由会员分享，可在线阅读，更多相关《非线性规划(管理运筹学,李军).docx（26页珍藏版）》请在三一文库上搜索。
1、6 非线性规划1、判断函数的凸凹性（1） f ( x)( 4x) 3 ， x 4（2） f ( X ) x122x1 x2 3x22（3） f ( X )x1 x2（ 1 ） 解 ： f (x)3(4 x)20 ， Q x=4, 故 f(x) 在 （ - ， 4 上 是 不 减 函 数 ，f (x) 6(4 x)0，故 f(x) 在（ -， 4上是凸函数。（2）解： f(x) 的海赛矩阵 H ( x)222，因 H（ x）正定，故 f （ x）为严格的凸函数。6（3）解：取任意两点 X (1)(a1, b1 ) 、 X ( 2 )(a2 , b2 ) ，从而f (X (1) )a1.b1 ，
2、f ( X (2) )a2.b2 ， f (X (1) )T(b1, a1 )看下式是否成立：f ( X (2)f ( X (1) )f ( X (1) ).( X (2)X (1) )a2 .b2a1 .b1 (b1, a1 )(a2 a1, b2b1 )T(a2a1 ).(b2b1)0Q a1, a2 , b1, b2 是任意点，并不能保证上式恒成立，故所以 f ( X )x1x2 既非凸函数，也非凹函数。2、分别用 斐波那契法和黄金分割法 求下述函数的极小值，初始的搜索区间为x 1,15 ，要求 | f ( xn )f ( xn 1 ) |0.5 。f ( X ) x 415 x372x
3、2135x解：斐波那契法已知= 0.5/(15-1)=1/28 、 a = 1、 b = 15，有 Fn128 ，即 n 8 。1a1bFF7(ba)15 3421 (151)6.35298b1aFF7(ba)13421 (151)9.64718f (a1 )168.876f (b1)592.4527故搜索区间可以从1,15 缩减为1,9.6471。已经存在一个已知的试点a16.3529 及其函数值 f (a1)168.876 ，将原试点a16.3529 改为 b16.3529 ， f (b1)168.876 。计算一个新试点a1 9.64711321 (9.64711)4.2941，f (a
4、1 )99.7703f (b1)168.876 ，故搜索区间缩减为4.2941,9.6471 。将原有点 a1 6.3529视为a1 ，新的试点 b14.2941138 (9.64714.2941)7.5883故搜索区间缩减为4.2941,7.5883 。继续选取对称点比较函数值，以使区间进一步缩短，直到区间长度不大于0.5，因此符6.35295 6.7647合精度要求的点为26.5588 ，近似极小值为-169.799。黄金分割法a 1， b15， a1a 0.382( ba)1 0.382(15 1) 6.348b1 a0.618(ba)00.618(151)9.652 ,f ( a16.
5、348)168.822f (b19.652)595.7061 ，故搜索区间缩减为 1,9.6527 。令 b1 =6.348，寻找新点a1 =4.3051，f (a14.348)100.096f (b16.348)168.822，故搜索区间缩减为4.3051,9.6527 。f (a1 5.5674)147.644 ， f (b17.6095)114.599f (6.0495)163.291 ， f (6.8294)166.403f (6.348)168.822 ， f (6.8294)166.403因 6.8295-6.348=0.48150.5 ，因此符合精度要求的近似极小点为6.8295
6、6.3486.58875 ，近似2极小值为 -169.7。23、试计算出下述函数的梯度和海赛矩阵（1） f ( X )x12x22x32（ 2）（3） f ( X )3x1 x224ex1x2（ 4）f ( X )ln( x12x1 x2 x22 )f ( X )x1x2ln( x1 x2 )200（1）解：f ( X ) (2 x1 , 2x2, 2x3 )T ， H ( X ) 020002（2）解：f ( X ) ( 22x1x22, 2x12x22 )Tx1x1 x2x2x1x1x2x2H ( X )12x122x1x2x2 2x124x1 x2x222x1 x2x22 ) 2x124
7、x1x2x2 2x1 22 x1 x22x2 2( x1（3）解：f ( X )(3x124 x2ex1x2 ,6 x1x24x1ex1x2 )TH ( X )4 x224 x2 ex1 x26 x24(1x1 x2 )ex1 x24(1x1 x 2 ) e x1 x26 x14 x12 ex1 x26 x2（4）解：f ( X )(x2 x1x211 , x1x2 ln x11 )Tx1x2x2 ( x21) x1 x2212x2 x1x 2 2 ln x1x1x 2 1H ( X )x1x21 lnx2 1x2 (ln x1 ) 21x2 x1x1x1x12x24、用梯度法（最速下降法）求
8、函数f ( X )4x14x22x12x1 x2x22 的极大点，初始点X (0)(1,1)T 。解：初始近似点 X (0)(1,1)T，f ( X )(4 4x1x2 , 4x12x2 )Tf ( X (0) ) (1,1)T ，f ( X (0) )2(1)2(1)2 2241f ( X (0) )Tf ( X (0)1又因为 H ( X )， 0 =f ( X (0) )T H ( X (0) )f ( X (0) )2123下一迭代点 X (1) = X (0 )10 f ( X ( 0) ) =112112， f ( X (1) )( 1, 3 )T13222f ( X (1) )T
9、f ( X (1) )1121 =f ( X (1) )T H ( X (1) ) f ( X(1) )24115X (2)= X (1)1 f ( X (1) ) =21234122X (3)(0.5625,1.6875) T，f ( X (3) )X (4)(0.5781,1.7031)T，f ( X (4)8f ( X(2)11T113，(, )， 2 =2888( 1 , 1)T ， 2 =2188(0.0625,0.0625)T1， 3 =4(5)T(5)(T1X(0.5703,1.7109)，f ( X0.01563,0.015625) ， 4= 2X (6)(0.5723,1.7
10、129) T，f ( X (6)(0.00781,0.00781) T ， 5 =14X (7)(0.5713,1.7139) T，f ( X (7)(0.00196,0.001952) T2因为f ( X (7) )0.002763 已经很小，所以过程可以结束。此时所得的近似极大点是X (7)(0.5713,1.7139) T。5、用牛顿法求解 max f ( X )x212 ，初始点 X(0 )(4,0)Tx2，分别用最佳步长和固定步长121.0进行计算。6、用变尺度法求解 minf ( X ) (x1 2) 3( x1 2x2 ) 2 ，初始点 X ( 0)(0,3)T ，要求近似极小点
11、梯度的模不大于0.5 。10， X (0)0解： H ( X ( 0 ) )1304f ( X )(3x1x22, x2x1 ) T于是f ( X (0) )(0, 24)TP(0)H ( X (0) ) f ( X (0) )1000012424利用一维搜索0： min f ( X (0 )P (0 ) ) ，可得081 ，于是：X (1)X (0)0 P(0)03180 (0,0) T24f (X (1) )(12,0)TX (0)X (1)X (0)(0,3)TG (0)f ( X (1) )f ( X (0) )(12, 24)T利用式（ 6-17）有：H ( X(1) H ( X(0
12、 )X ( 0 ) ( X ( 0 ) ) TH ( X ( 0) ) G (0 ) ( G( 0)T H ( X (0 ) )( G( 0) )T X ( 0 )( G ( 0 ) ) T H ( X (0 ) ) G ( 0 )1010001801132164016131720144 288288 576P(1)H ( X(1)f ( X(1)13216124016130485245再利用一维搜索1： min f ( X (1)P(1) ) ，可得1245 ，于是：X (2)X (1)1P(1)21f ( X (2) )(0,0)T于是 X (2)(2,1)T 即为极小点，函数f ( X
13、) 的极小为 0。57、写出下述非线性规划问题的K-T 条件（1） min f ( X )x1（ 2） min f ( X )( x1 3)2(x2 3) 2(1 x1 ) 3x204 x1x20x1 , x20x1 , x20（ 1 ）解 ：f ( X ) (1,0)T ， g1 ( X ) 3(1x1 ) 2, 1T，g2 ( X ) 1,0T ，g3 ( X )0,1T 。对三个约束条件分别引入拉格朗日乘子1 、2 和3 ，则有如下 K T条件：113(1x1* ) 22130001011 (1x1) 3x202 x103 x201 ，2 ， 30即：1 3 1 (1x1* )22013
14、01 (1x1) 3x202 x103 x201 ，2 ， 30（ 2 ） 解 ： f ( X ) (2 x1 6,2 x26)T ，g1( X ) 1,1T,g2 ( X ) 1,0 T ，g3 ( X ) 0,1T 。对三个约束条件分别引入拉格朗日乘子1 、2 和3 ，则有如下 K T条件：62x1*61100 ，即可分解为：2x2*61231012x1*61202x2*61301 (4x1x2 )02 x103 x201 ，2 ， 308、分析下述非线性规划在X (1)(0,0)T 、 X (2 )(4,0)T 、 X ( 3)(2,3)T 、 X ( 4 )(0,2)T和 X (5 )
15、( 1348 , 136) T 各点处的可行下降方向。解 ： f (X ) (2 x12x2 , 2x13)T，g1 ( X ) (2 x110, 1)T ，g2 ( X ) 1, 1T ，g3 ( X )1,0T ，g4 ( X )0,1 T 。当 X (1)(0,0) T 时，f ( X (1) )(0,3)T， g1 ( X (1) )( 10, 1)T因为第一、第二个约束条件为无效约束，故可有下列有效约束来确定向量D：0d1 3d20 ， d10, d2 0 ，即 D 的可行下降方向为：d10, d20 。当 X (2)(4,0) T时，f ( X (2) (8,5) T ，g1 (X
16、 (1)(2,1)T因为第一、第二、第三个约束条件为无效约束，故可有下列有效约束来确定向量D ：8d1 5d20 ， d20 ，即 D 的可行下降方向为：d0, d5 d。2182当 X (3)(2,3) T时，f ( X (3) (10,1)T ，g1 ( X(1) )(6,1)T可有下列有效约束来确定向量D ： 10d1d20，即 D 的可行下降方向为： d210d1 。当 X (4)(0, 2)T时，f ( X (4) (4, 3)T，g1 ( X (1) )( 10, 1)T可有下列有效约束来确定向量D ： 4d13d2 0， d10 。即 D 的可行下降方向为：7d24d1 ， d1
17、0 。3当 X (5)(48,6)T 时，f ( X (5) )(108,57)T ，g1 ( X (1) ) (34, 1)T1313131313可有下列有效约束来确定向量D ：48d160，即 D 的可行下降方向为： d11d2 。1313 d289、二次规划max f (X )4x1x128x2x22x1x22x1 , x20（ 1） 用 K-T 条件求解；（ 2） 写出等价的线性规划问题并求解。（ 1）解：标准化模型得：min f ( x)4x1x128x2 x22 ， g1 (x)2 x1x20 ，g2 ( x)x10 ， g3 ( x)x20 各函数的梯度分别为：f ( x) (
18、42x1,82x2 )T ，g1 (x) (1, 1)T ， g2 ( x)(1,0)T ，g3( x)(0,1)T 。对三个约束条件分别引入拉格朗日乘子1 、2 和 3 ，则有如下K T 条件：42x1*1100 ，即可分解为：82x2*12310142x1*1282x*213001 (2x1 x2) 02 x103 x201 ，2 ， 30求解得： x1*0, x2*2, r1*4, r2*0, r3*08（2）解：问题可以用矩阵形式表示为：x110x1max f ( X ) (4,8)(x1, x2 )1x2x20(1,1)x12x2x1, x20从而转化为：x1201100x24021
19、01018110001122s1即等价于线性规划问题为： max( x)R1R22x11r142x21r28x1x2s12x1 , x2 , 1 , r1 , r2 , s10引入人工变量R1 和 R2 得到第一阶段的初始单纯形表，得：cj000000-1-1bCBXBx1x2112s1R1R2-1R1201-100104-1R20210-100180s1100010021j222-1-1000第一次迭代：10，可以让 x1 入基，按最小比值确定R1 出基，见下表c000000-1-1jbCBXBx1x2112s1R1R20x1101/2-1/2001/202-1R20210-100180s0
20、1-1/21/201-1/2001j033/21/2-10-3/209第二次迭代：20 ，可以让x2 入基，按最小比值确定s1 出基，见下表：cj000000-1-1bCBXBxxsRR121121120x1101/2-1/2001/202-1R2002-1-1-21180x201-1/21/201-1/200j002-1-1-200第三次迭代： s10 ，可以让1 入基，按最小比值确定R2 出基，见下表：c000000-1-1jbCBXBxxsRR121121120x1100-1/41/41/21/4-1/4001001-1/2-1/2-11/21/240x20101/4-1/41/2-1/
21、41/42j000000-1-10上表给出了第一阶段的最优解，由于R1R20 ，所以此解对于原二次规划不仅是可行的而且是最优的，即最优解X(0, 2)T ，最优值f ( X )12 。10、试用可行方向法求解非线性规划，初始点X (0)(0,0.75)T。min f ( X )2x122x222x1x24x1 6x2x15x252x1x20x1 , x2011、分别用 内点法 和外点法 求解下述非线性规划问题（1）min f ( X )( x12)4( x12x2 ) 210x12x2 0（2）min f ( X )x126x1 2x2 9x13 ， x23 ，（1）解：外点法：构造惩罚函数P
22、( X , M )(x12) 4(x12x2 ) 2M min(0,(x12x2 ) 2P4(x132(x1 2x2 )2Mmin(0,(2x2)(2x1)x2)x11P4x1 (x12x2 )2M min(0,(2x2 )xx12对于不满足约束条件的点X(x1 , x2 )T ，可以有x12x20 或 x10 。PP0 ，有：令 x1x2P4(x132(x12x2)4Mx1(2x2 )0x12)x1P4x1( x12x2 ) 0x22x2 ) 2M ( x1解得：2(x1 2)3x12Mx13)2 x1Mx1222Mx14M用试算法迭代可得：KM kX (k 1)10.1（1.4539，0.
23、7608）21（1.1687，0.7407）310（0.9906，0.8425）4100（0.9507，0.8875）51000（0.9461，0.8934）当 M k 趋向无穷大时，X (M ) 趋于原问题的极小解 Xmin (1,1)T内点法：11（2）解：外点法：构造惩罚函数 P( X ,M )x126x12x29M min(0,( x1 3) 2M min(0,( x2 3) 2P2x1 62Mmin(0,x1 3)，P22M min(0, x23)x1x2对于一切的外点x13, x23 ，并令PP0 ，可得 MinP(X,M)的解为：xx122x16 2M ( x13)0,22M (
24、 x23)0，可得： x1 3,x2 31M取 M 1,10,100,1000 可得如下结果：M1： X(3, 2)T ， M10 ： X(3, 2.9)TM100 ： X(3, 2.99)T ， M1000 ： X(3, 2.9999)T从此结果可知X ( M ) 从 R 的外部逐步逼近R 的边界，当 M 趋于无穷时， X (M ) 趋于原问题的极小解 Xmin(3,3) T内点法：构造障碍函数 P( X ,r ) x126x12x2 9rrx13 x2 3P2 x16r0 ，得 (2 x16)( x13)2rx1( x13)2P2r0 ，得 x2( r )rx2(x23)232各步迭代结果
25、列于下表rkx1 (rk )x2 ( rk )k11.0003.79453.7071k20.5003.633.5k30.2503.53.3536k40.1003.3693.2236k50.00133.0224当 r 趋向 0 时，得最优解X min(3,3) T 。1212、试用 内点法 求解非线性规划问题min f ( x)( x1) 2x 0（ 1） 障碍项采用倒数函数；（ 2） 障碍项采用对数函数。解（ 1）障碍项采用倒数函数：构 造 障 碍 函 数P( X ,r ) (x 1)2r， 则d Pxdx2 x 2 ( x1)r 。各步迭代结果列于下表rkxk11.0000.566k20.5000.42k30.2500.309k40.1000.2k50.0010.02当 r 趋向 0时，得最优解 X min 0。（2）障碍项采用对数函数：构造障碍函数P( X ,r ) (x 1)2r lg x ，则d P2( xdx得 x ( x1)r。各步迭代结果列于下表2 In 10rkxk11.0000.184k20.5000.098k30.2500.052当 r 趋向 0 时，得最优解 X min0。r0 ， 得2( x 1)2x1)r0 ，xIn 10