非线性规划(管理运筹学,李军)

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 ( x23)0，可得： x1 3,x2 31m取 m 1,10,100,1000 可得如下结果：m1： x(3, 2)t ，