最优化方法及其应用课后答案(郭科 陈聆 魏友华)

最优化方法部分课后习题解答 习题一习题一 1.1.一直优化问题的数学模型为：一直优化问题的数学模型为： 22 12 112 212 31 42 min( )(3)(4) 5 ( )0 2 ( )50 . . ( )0 ( )0 f xxx g xxx gxxx st gxx gxx =+ = = + = = 试用图解法求出：试用图解法求出： （1 1）无约束最优点，并求出最优值。无约束最优点，并求出最优值。 （2 2）约束最优点，并求出其最优值。约束最优点，并求出其最优值。 （3 3）如果加一个等式约束如果加一个等式约束，其约束最优解是什么？，其约束最优解是什么？ 12 ( )0h xxx= 解：（1）在无约束条件下，的可行域在整个平面上，不难看出，当=（3，4）( )f x 12 0 xx * x 时，取最小值，即，最优点为=（3，4）：且最优值为：=0( )f x * x * ()f x （2）在约束条件下，的可行域为图中阴影部分所示，此时，求该问题的最优点就是( )f x 在约束集合即可行域中找一点，使其落在半径最小的同心圆上，显然，从图示中可 12 ( ,)x x 以看出，当时，所在的圆的半径最小。 * 15 5 (, ) 44 x=( )f x 其中：点为和的交点，令求解得到： 1( ) g x 2( ) gx 112 212 5 ( )0 2 ( )50 g xxx gxxx = = += 1 2 15 4 5 4 x x = = 即最优点为：最优值为：= * 15 5 (, ) 44 x= * ()f x 65 8 （3）.若增加一个等式约束，则由图可知，可行域为空集，即此时最优解不存在。 2.2.一个矩形无盖油箱的外部总面积限定为一个矩形无盖油箱的外部总面积限定为 S S， 怎样设计可使油箱的容量最大？试列出这个， 怎样设计可使油箱的容量最大？试列出这个优优 化问题的数学模型，并回答这属于几维的优化问题化问题的数学模型，并回答这属于几维的优化问题. . 解：列出这个优化问题的数学模型为： 该优化问题属于三维的优化问题。 123 122313 1 2 3 max( ) 22 0 . . 0 0 f xx x x x xx xx xS x st x x = + 3 2 31 /3,/3,/12 182 3 sss xsyszsv = 习题二习题二 3. 3. 3. 3.计算一般二次函数计算一般二次函数的梯度。的梯度。 1 ( ) 2 TT f xX AXb Xc=+ 解：设：则： 1212 (),( ,.) ,( ,.) TT ijn nnn Aabb bbXx xx = ，将它对变量球偏导数得： 111 1 ( ) 2 nnn ijijii iji f xa x xb xc = =+ (1,2,. ) i x in= = 1 2 3 ( ) ( ) ( ) ( ) f x x f x f x x f x x = 111 11 222 11 11 11 22 11 22 11 22 nn jjii ji nn jjii ji nn njjinin ji a xa xb a xa xb a xa xb = = = + + + 1 1 1 1 1 22 11 2 3 1 1 11 22 n n jj ii j i n n jjii ji n n ini njj i j a x a x b a xa x b b a xa x = = = = = + = 1 () 2 T AXA Xb+ 5. 5. 5. 5.求下列函数的梯度和求下列函数的梯度和 HesseHesseHesseHesse矩阵矩阵 （1）解： 222 12313 ( )234f xxxxx x=+ 2 2 0 -4 ( )0 4 0 4 0 6 f x = （2）解： 1 2 2 12 ( )3 x x f xx xe=+ 1 21 21 2 1 21 21 2 2 22122 2 21211 6+ ( ) 6+ 6 + x xx xx x x xx xx x x exex x e f x xex x exx e + = + 6. 6. 6. 6.判断下列函数是凸函数，凹函数，还是既不凸也不凹函数：判断下列函数是凸函数，凹函数，还是既不凸也不凹函数： （1） 22 121212 ( ,)23f x xxxx x= + 解：不是半正定，即非凸，然后判断-，经验证：不是半 2 ( )f x( )f x( )f x 2( ( )f x 正定，由此可知：非凸非凹。( )f x （2） 22 1211221 ( ,)24356f x xxx xxx=+ 解：半正定，故为凸函数。 2 ( )f x( )f x （3） 222 12312312 ( ,)234f x x xxxxx x=+ 解：不是半正定，即非凸，然后判断-，经验证：不是半 2 ( )f x( )f x( )f x 2( ( )f x 正定，由此可知：非凸非凹。( )f x 7. 7. 7. 7.设约束优化问题的数学模型为：设约束优化问题的数学模型为： 22 1122 112 22 21212 min( )4410 ( )20 . . ( )220 f xxxxx g xxx st gxxxxx =+ =+ = + 试用试用 K-TK-TK-TK-T 条件判别点条件判别点是否为最优点。是否为最优点。1,1 T x= 解：对于点，=0，点满足约束条件，故点是可行解。1,1 T x= 1( ) g x 2( ) 0gxX 且是起作用约束，,，由条件下的 1( ) g x 1I= 2 ( ) 2 f x = 1 1 ( ) 1 g x = ( )0 i g x K-T 条件得：，得到，点满足 K-T 条( )( )0,0 iii i I f xg x = 1 2=1,1 T x= 件。又因正定，故为严格凸函数，该最优化问题是凸规划问题，由 2 ( )f x( )f x 是 K-T 点，所以也是该问题的全局最优点。 * 1,1 T x= * 1,1 T x= 8. 8. 8. 8.设约束优化问题：设约束优化问题： 22 12 11 22 2 312 min( )(2) ( )0 . .( )0 ( )10 f xxx g xx stgxx gxxx =+ = = = + 它的当前迭代点为它的当前迭代点为，试用，试用 K-T 条件判定它是不是约束最优解。条件判定它是不是约束最优解。1,0 T k x= 解：对于点，点是可行点，1,0 T k x= 123 ()10,()0,()0 kkk g xgxgx= =1,0 T k x= 且起作用的约束条件是，,， 23 ( ),( )gx gx2,3I= k 2 () 0 f x = 2k 0 g () 1 x = ，由约束条件为时的 K-T 条件得，应有： 3k 2 g () 1 x = ( )0 i g x 解得：，所以为 K-T 点。( )( )0,0 iii i I f xg x += 2 3 1 1 = = 1,0 T k x= 现判断该问题是否为凸规划问题，因正定，故为凸函数，为 2 ( )f x( )f x 12 ( ),( )g x gx 线性函数，亦为凸函数，半正定，所以为凸函数，所以该优化问题为凸 2 3 g ( )x 3 g ( )x 规划问题，即点是该问题的约束最优解。1,0 T k x= 习题三习题三 1. 1. 1. 1.对于下列线性规划问题找出所有基解，指出哪些是基可行解，并确定出最优解。对于下列线性规划问题找出所有基解，指出哪些是基可行解，并确定出最优解。 （1 1 1 1） 123 1234 1235 16 max( )32 12369 84210 . . 30 0,(1,2.6) j f xxxx xxxx xxxx st xx xj =+ += += = = 解：令 123456 12 3 6 3 0 0 8 1 -4 0 2 0 ( ,) 3 0 0 0 0 -1 AP P P P P P = （1） 基解不是基可行解， 1 167 (0,0,0,0) 36 x= （2） 基解不是基可行解， 2 (0,10,0,7,0,0)x= （3） 基解是基可行解，且， 3 (0,3,0,0,3.5,0)x=( )3f x= （4） 基解不是基可行解， 4 721 ( , 4,0,0,0,) 44 x= （5） 基解不是基可行解， 5 5 (0,0,8,0,0) 2 x= （6） 基解是基可行解，且， 6 3 (0,0,0,16,0) 2 x=( )3f x= （7） 基解不是基可行解， 7 1 (1,0,0,0,3) 2 x= （8） 基解是基可行解，且， 8 (0,0,0,3,5,0)x=( )0f x= （9） 基解不是基可行解。 9 515 ( ,0,0, 2,0,) 44 x= （10） 基解是基可行解，且。 10 39 ( ,0,0,0,4, ) 44 x= 9 ( ) 4 f x= （11） 基解不是基可行解。 11 167 (0,0,0,0) 36 x= （12） 基解不是基可行解。 12 (0,10,0, 7,0,0)x= （13） 基解是基可行解，且。 13 7 (0,3,0,0,0) 2 x=( )3f x= （14） 基解不是基可行解。 14 5 (0,0,8,0,0) 2 x= （15） 基解是基可行解，且。 15 3 (0,0,0,8,0) 2 x=( )3f x= （16） 基解是基可行解，且。 16 (0,0,0,3,5,0)x=( )3f x= 2. 2. 2. 2.用单纯形法求解下列线性规划问题：用单纯形法求解下列线性规划问题： （1 1 1 1） 12 12 12 12 max( )105 349 . . 528 ,0 f xxx xx stxx x x =+ + + 解：将现行规划问题化为标准形式如下： 1234 123 124 1234 min( )10500 349 . . 528 ,0 f xxxxx xxx stxxx x x x x = + += += 作初始单纯形表，并按单纯形表步骤进行迭代，如下： 此时，均为正，目标函数已不能再减小，于是得到最优解为： j * 3 (1,0,0) 2 x= 目标函数值为： * ()17.5f x= 3. 3. 3. 3.分别用单纯形法中的大分别用单纯形法中的大 MMMM 法和两阶段法求解下列线性规划问题：法和两阶段法求解下列线性规划问题： B C B Xb-10 1 x -5 2 x 0 3 x 0 4 x i 0 3 x 934103 0 4 x 852011.6 0-10-500 0 3 x 4.202.81-0.61.5 -10 1 x 1.610.400.24 160-102 -5 2 x 1.501 5 14 3 14 -10 1 x 110 1 7 2 7 17.500 5 14 25 14 （1） 1234 1234 1234 1234 min( )5236 2347 . . 223 ,0 f xxxxx xxxx stxxxx x x x x =+ += += 解：（1 1 1 1）大大 MMMM 法法：把原问题化为标准形式，并加入人工变量如下： 123456 12345 12346 123456 min( )5236 2347 . . 223 ,0 f xxxxxMxMx xxxxx stxxxxx x x x x x x =+ += += 作初始单纯形表，并按单纯形表步骤进行迭代，如下： 因为 M 是一个很大的正数，此时均为正， j 所以，得到最优解：，最优值为 * (0,0,1,1,)Tx= * ()3f x= （2 2 2 2）两阶段法两阶段法 B C B Xb5 1 x -2 2 x 3 3 x -6 4 x -6 4 x -6 4 x i M 5 x 71234101.75 M 6 x 32112011.5 -10M5-3M-2-3M 3-4M -6-6M00 M 5 x 1-30101-21 -6 4 x 1.510.50.5100.53 9-M11+3M16-M003M+3 3 3 x 1-30101-2 -6 4 x 12.50.501-0.51.5 329100M-6 M+15 首先，构造一个仅含人工变量的新的线性规划如下： 123456 12345 12346 123456 min ( )0000 2347 . . 223 ,0 g xxxxxxx xxxxx stxxxxx x x x x x x =+ += += 按单纯形法迭代如下： 最优解为：，最优值： * (0,0,1,1,0,0)x=( )0g x= 因人工变量，则原问题的基可行解为:,进入第二阶段计算 56 0 xx= * (0,0,1,1,)Tx= 如下表所示： 由上表可知，检验数均大于等于 0，所以得到最优解： * (0,0,1,1,)Tx= 最优值为。 * ()3f x= 4. 4. 4. 4.某糖果厂用原料某糖果厂用原料 A A A A，B B B B，C C C C 加工成三中不同牌号的糖果，甲，乙，丙，已知各种牌号加工成三中不同牌号的糖果，甲，乙，丙，已知各种牌号糖糖 果中果中 A,B,CA,B,CA,B,CA,B,C 含量，原料成本，各种原料的每月限用量，三中牌号糖果的单位加工费及含量，原料成本，各种原料的每月限用量，三中牌号糖果的单位加工费及售售 B C B Xb0 1 x 0 2 x 0 3 x 0 4 x 1 4 x 1 4 x i 1 5 x71234101.75 1 6 x32112011.5 -10-3-3-4-600 1 5 x1-30101-21 0 4 x1.510.50.5100.53 -140-1003 0 3 x1-30101-2 0 4 x12.50.501-0.51.5 B C B Xb5 1 x -2 2 x 3 3 x -6 4 x 3 3 x1-3010 -6 4 x12.50.501 329100 价如下表所示，问该厂每月应生产这三种牌号糖果各多少千克，使该厂获利最大？试价如下表所示，问该厂每月应生产这三种牌号糖果各多少千克，使该厂获利最大？试建建 立这个问题的线性规划数学模型。立这个问题的线性规划数学模型。 解：设表示甲、乙、丙中分别含 A、B、C 的含量，构造此问题的,0,1,2,3 iii x y zi= 数学规划模型如下： 123123123 111 222 333 123 123 123 123 12 max( )0.91.41.90.450.951.450.50.450.95 2000 2500 1200 0.40.60.60 . . 0.850.150.150 0.20.20.80 0.60.60.40 0.50.5 f xxxxyyyzzz xyz xyz xyz xxx styyy xxx yyy zz =+ + + + + + + 3 0.50 ,0,1,2,3 iii z x y zi = 5. 5. 5. 5.求解下列线性规划问题的对偶问题求解下列线性规划问题的对偶问题 （1） 123 123 123 123 123 min( )224 2352 373 . . 465 ,0 f xxxx xxx xxx st xxx x x x =+ + + + （2） 123 123 123 123 123 max( )563 225 53 . . 4738 ,0,0 f xxxx xxx xxx st xxx xxx =+ += + + 无约束 甲乙丙 原料成本 （元/千克） 每月限用量 （千克） A 60 % 15 % 2.002000 B1.502500 C 20 % 60 % 50 % 1.001200 加工费0.500.400.30 售价3.402.852.25 解：（1）由表 3.7 可得该问题的对偶问题为： 123 123 123 123 123 max( )235 232 342 . . 5764 0,0 g yyyy yyy yyy st yyy yyy =+ + + + （2）该问题的对偶问题为： 123 123 123 123 123 min( )538 345 2576 . . 233 ,0,0 g yyyy yyy yyy st yyy yyy =+ += + + 无约束 6用对偶单纯形法求解下列线性规划问题： （1） 123 13 23 123 min( )41218 33 . . 225 ,0 f xxxx xx stxx x x x =+ + + 解：（1）首先，将“”约束条件两边反号，再加入松弛变量，得： 12345 134 235 12345 min( )412180 33 . .225 ,0 f xxxxxx xxx stxxx x x x x x =+ += += 建立初始单纯形表如下图所示，所有。0 j 则对应对偶问题解是可行的，则继续迭代： 计算，所以为换出变量，确定为换入变量。min3, 55= 5 xmin 6,96= 2 x 继续迭代，得到如下单纯形表： B C B Xb4 1 x 12 2 x 18 3 x 0 4 x 0 5 x 0 4 x-3-10-310 0 5 x-50-2-201 4121800 。 43 min33,min 4 22xx= =换出， 换入 此时，所有，故原问题的最优解为,最优值为：0 j * 3 0,1 2 T x= * ()36f x= 其对偶问题得到最优解为：，最优值为：。 * 2,6Tx= * ()36f x= 7. 7. 7. 7.已知线性规划问题已知线性规划问题 123 123 12 123 min( )2 6 . .24 ,0 f xxxx xxx stxx x x x =+ + + 先用单纯形法求出最优解，再分别就下列情况进行分析：先用单纯形法求出最优解，再分别就下列情况进行分析： （1 1 1 1） 目标函数中变量目标函数中变量的系数分别在什么范围内变化，问题的最优解不变；的系数分别在什么范围内变化，问题的最优解不变； 123 ,x x x （2 2 2 2） 两个约束条件的右端分别在什么范围内变化，问题的最优解不变。两个约束条件的右端分别在什么范围内变化，问题的最优解不变。 解：将该规划问题化为标准型，引入松弛变量 45 ,x x 12345 1234 125 12345 min( )200, 6 . .24 ,0 f xxxxxx xxxx stxxx x x x x x =+ += += B C B Xb4 1 x 12 2 x 18 3 x 0 4 x 0 5 x 0 4 x-3-10-310 0 2 x-2.50110-0.5 40600 B C B Xb4 1 x 12 2 x 18 3 x 0 4 x 0 5 x 0 3 x1 1 3 01 1 3 0 0 2 x1.5 1 3 10 1 3 -0.5 20026 用单纯形法求解，如下表： 由上表可知，所有的检验数均大于等于零，得最优解:,所以原问题的 * (0,2,0,4,0)Tx= 最优解为：，最优值 * (0,2,0,)Tx= * ()2f x= （1）。 123132 xxxxxx变量 ， ， 中， ， 为非基变量， 为基变量 3311 ,), 2222 1100,), ccccc ccccc = =+ = =+ 111111 333333 由，当时，所以，当此时最优解不变。 由，当时，所以，当此时最优解不变。 ，最优解不变。() 2 3,1c 综上， 1 ,) 4,00,), 2 ccc+ + 123 当，此时最优解不变。 （2）的变化范围 1 b 1111 1 410.5410 200.520000 bb B bBb +=+=+ 得到：，最优解保持不变。 1111 4042bbbb+ ，则 的变化范围是 11 2 22 00410.540.50 200.520.50 B bBb bb +=+=+ 得到：，最优解保持不变。 22 48bb ，则 的变化范围是0,12 习题四习题四 B C B Xb2 1 x -1 2 x 1 3 x 0 4 x 0 5 x i 0 4 x1111106 0 5 x1.5-120012 2-1100 0 4 x41.5011-0.5 -1 2 x2-0.51000.5 1.50100.5 3. 3. 3. 3.用用 Newton 法求解法求解 3 ( )21ttt=+ 用第用第 1 题求得的区间，按精度题求得的区间，按精度计算。计算。0.01= 解： 0100111010 ( )(0)1,1, ( )0,0,( )( )2ttthttthh=+=因为，则 2112212 1( )22,22, ( )( )K=20,=0b=3tthttt=+=，反向，因为所以， 则搜索区间为取：t0,3 2 ( )32,( )6,(0)20,(3)250ttt= ， 000 15 5 1,( )1,( )6,t110.01 66 6 ttt= =所以，继续迭代 0 5 =t 6 t= ， 0 000 0 ( )491149 ,0.01,0.8165 ( )606060 t tttttt t = 则令，则 。 * 0 0.00050.01,0.817,()0.088tt=继续迭代，因为 1122 1.832608, ( )0.306764,1.111392, ( )0.987592tttt= = = = ， ，因为，所以新的搜索区间为-1.832608，0.056： 12 ,tt继续迭代 12 ( )( )tt ， 1122 1.111292, ( )0.987592,0.665448, ( )0.888075tttt= = = = ， ，所以新的搜索区间为-1.832608，-0.665448 ： 12 ,tt继续 12 ( )( )tt ， 1122 1.386753, ( )0.854402,1.111392, ( )0.987592tttt= = = = ，因为，所以新的搜索区间为-1.386753，-0.665448 12 ,tt继续 12 ( )( )tt ， 2211 0.940987, ( )0.996518,1.111392, ( )0.987592tttt= = = = ， ，所以新的搜索区间为-1.111392，-0.665448 ： 12 ,tt继续 12 ( )( )tt因为 ， 1122 0.940987, ( )0.996518,0.835799, ( )0.973038tttt= = = = ， ，所以新的搜索区间为-1.111392，-0.835799 ： 12 ,tt继续 12 ( )( )tt因为 ， 2211 0.940987, ( )0.996518,1.006115, ( )0.999962tttt= = = = ， ，所以新的搜索区间为-1.111392，-0.940987 ： 12 ,tt继续 12 ( )( )tt因为 ， 1122 1.046295, ( )0.997857,1.006115, ( )0.999962tttt= = = = ， ，所以新的搜索区间为-1.046295，-0.940987 ： 12 ,tt继续 12 ( )( )tt因为 ， 2211 0.981215, ( )0.999647,1.006115, ( )0.999962tttt= = = = ， ，所以新的搜索区间为-1.046295，-0.981215 ： 12 ,tt继续 12 ( )( )tt因为 ， 1122 1.021434, ( )0.999540,1.006115, ( )0.999962tttt= = = = ， ，所以新的搜索区间为-1.021434，-0.981215 ： 12 ,tt继续 12 ( )( )tt因为 ， 2211 0.996579, ( )0.999987,1.006115, ( )0.999962tttt= = = = ，所以新的搜索区间为-1.006115，-0.981215 ： 12 ,tt继续 12 ( )( )tt因为 ， 1122 0.996579, ( )0.999987,0.990727, ( )0.999914tttt= = = = ， ，所以新的搜索区间为-1.006115，-0.990727 ： 12 ,tt继续 12 ( )( )tt继续 12 ( )( )tt继续 12 ( )( )tt因为 2211 0.998830, ( )0.999998505,1.000237, ( )1.00000016tttt= = = = ， ，新的搜索区间为-1.002472，-0.998830 12 ,tt继续 12 ( )( )tt因为 1122 1.001081, ( )0.999999075,1.000237, ( )1.00000016tttt= = = = ， 因为，停止迭代。所以： 12 tt， ，所以，新的搜索区间为0.5227，1， 0 ( )0.1588( )0.063tt= = = ， ，新的搜索区间为：0.6232，1， 0 ( )0.2032( )0.2029tt= = = 同理继续迭代，最后至，此时最优解， 2. 2. 2. 2.用用 NewtonNewtonNewtonNewton 法求解法求解 22 1212120 min( )60 10400.01. T f xxxxxx xx=+=-，初始点，0 ， 解： 1221 1 1 100 11 * ( )( ) 102, 42 21 21 33 ( )( ) 1212 33 21 010 33 ( )()8,6 0124 33 ( )0,0 ,( )00.01 8,6 ,()8 T T T T g xf xxxxx G xG x xxG xg x f xf x xf x = + + = = = = =最优解为 3. 3. 3. 3.用修正用修正 NewtonNewtonNewtonNewton 法求解法求解 22 12120 min( )412100.01. T f xxxxxx=+=（） （）+10，初始点，0 ， 解： 12 ( )( )89,43Tg xf xxx= =+ 0 1000 0 9 8 3 4 t xxt p t =+ = ， 1 1 0 80 8 ( )( ) 041 0 4 G xG x = = ， 0 ()93 T g x=， 则，令 1 00 1 0 99 3 8 ( )(), 318 4 0 4 T pG xg x = = 0 1000 0 9 8 3 4 t xxt p t =+ = 2 1 9999 ()161( ) 168 f xtttf x=+ = 时，最小 111 * 9 3 , ()0,0 ,()00.01 8 4 9 3157 , ,() 8 416 TT T xf xf x xf x = = = = ， 4. 4. 4. 4.用共轭梯度法求解用共轭梯度法求解 22 120 min410.01. T xxx+=（），取初始点，1 ， 解： 令， 22 1112 ( )4,( )2 ,8 T f xxxf xxx=+= 00 ()2,8 T pf x= = 1000000 12 12 ,1 8 18 T xxt pttt =+=+= 令， 22 00 min(12 )4(1 8 ) min ( )ttt+= 则 00 ( )5206800.130969 d ttt dt = 11 0.738062, 0.047752()1.476124, 0.382016 TT xf x=， 则 2 1 0 2 0 ()2.324878 0.034189 68 () f x f x = 1100 ()pf xp= +新搜索方向为 1.47612421.544502 0.034189 0.38201680.108504 =+= 211111 0.738062 1.544502 , 0.0477520.108504 T xxt ptt=+=+因此有 1111 ()00.477127 d f xt pt dt +=由 2111 0.7380621.544502 0.4771270.00,0.007 0.0477520.108504 T xxt p =+=+= 因而得下一迭代点 ， 2 ()00.01f x=停止迭代 * 0,0 ,()0 T xf x= 5. 5. 5. 5.用共轭梯度法求解用共轭梯度法求解 22 1212 min( )20.01.f xxxx x=+=-，自定初始点， 解：，取初始点， 1221 ( )4,2 T f xxxxx= 0 0,1 T x= 00 ()1, 2Tpf x= = 1000000 01 ,12 12 T xxt pttt =+=+= 令 22 0000 min2(12 )(1 2 )min ( )ttttt+= 则 00 ( )16500.125 d ttt dt = 11 0.3125, 0.375()0.875,0.4375 TT xf x=， 2 1 0 2 0 ()0.95703125 0.191406 5 () f x f x = 1100 ()pf xp= +新搜索方向为 0.87510.683594 0.191406 0.437520.82012 =+= = 2111 xxt p=+因而得下一迭代点 11 0.31250.683594 ,0.3750.820312 T tt ， 1111 ()00.456927 d f xt pt dt +=由 则停止迭代 222 0.000,0.000()0,0 ,()00.01 TT xf xf x=， 则=，综上所述，原问题的最优解，最优值为 * x 2 0,0Tx= * 0,0Tx= * ()0f x= 6. 6. 6. 6.用用 DFPDFPDFPDFP 法求解法求解 22 120 min( )45680.01. T f xxxx=+=（） （），初始点，9 ， 6、解：取 012 80 ,( )840,212 02 T HIAg xxx = 00 8,19,24,6 TT xg= 第一步迭代得： 11 4.86154,8.21538,1.10768,4.43076 TT xg= 用 DFP 法第二次迭代： 010 3.13846, 0.78462Tsxx= 010 25.10768, 1.56924Tygg= 则， 0 00000 10 00000 TT TT s sH y y H HH syy H y =+ 因： 00 80.03071, T sy= 00000 632.85811 TT y H yyy= ， 0 0 9.849932.46250 2.462500.61563 T s s = 0 0 9.849932.46250 2.462500.61563 T s s = 1 100.123080.030770.996110.062260.126970.03149 010.030770.007700.062260.003900.031491.0038 H =+= 则搜索方向 111 0.28017,4.48248TpH g= = 从出发沿进行直线搜索，即： 1 x 1 p 111 4.861540.28017 ,8.215384.48248 T xxtptt=+=+ 由，得 11 ()0 d f xtp dt +=0.48674t= 所以，由于，所以是极小 211 5.000,6.000Txxtp=+ 2 ()0,0Tg x= 2 5,6Tx= 点。 习题六习题六 1. 1. 1. 1.用外点罚函数法求解：用外点罚函数法求解： 12 2 112 21 min( ) ( )0 . . ( )0 f xxx g xxx st gxx =+ = + = 解：利用外点罚函数法构造增广目标函数，如下： 222 12121 12 ()() ( , ) () xxxxxxD F x xxxD + = + 对于的情况：xD 由得： 12 0,0 FF xx = 2 111 ( ), 2224(1) x = + 当时， +()( )0,0 x 即：，且()0,0 x=()0f x= 2. 2. 2. 2.用外点罚函数法求解：用外点罚函数法求解： 22 12 min( )f xxx=+ . .st 1 ( )10g xx= 解：构造增广目标函数： 222 121 22 12 (1)() ( , ) () xxxxD F x xxxD + = + 对于的情况：xD 由得： 12 0,0 FF xx = 11 2 22 (1)0 20 xx x = = 推出：( ),0 1 x = + 当时，。 +()( )1,0 x 即：且。()1,0 x=()1f x= 4. 4. 4. 4.用内点罚函数法求解：用内点罚函数法求解： 3 12 11 22 1 min( )(1) 3 ( )10 . . ( )0 f xxx g xx st gxx =+ = = 解：利用内点罚函数法构造如下增广目标函数： 3 12 12 111 ( ,)(1)() 31 kk F x rxxr xx =+ 由得： 1 2 0 0 F x F x = = *( )( 1,) kkk x xrr=+ 当时，0 k r + *( )(1,0) k x x =， * x(1,0) * 8 () 3 f x= 5. 5. 5. 5.用内点罚函数法求解：用内点罚函数法求解： 3 12 1 2 1 min(1) 3 10 . . 0 xx x st x + 解法同上。 习题七习题七 1. 1. 1. 1.用动态规划求解：用动态规划求解： 2 123 123 max 4 . . 0(1,2,3) i Ex x x xxx st xi = + = 解：将原问题表示为： 2 123 maxEu u u= 123 4 . . 0(1,2,3) i uuu st ui + = 由此，确定状态变量为：， 决策变量为： 123 ,x x x 123 ,u u u 状态转移方程：。 11; xu= 221; xux=+ 332 4xux=+ 用动态规划的思想顺推，如下： 第一步，1:k= 。 11 * 111111 () , max ux f xuxux = =且 第二步，2:k= 22 22 22 22211 0 2122 0 222 0 ()() () (). max max max ux ux ux fxuf x uf xu uxu = = = 2222222 22* 222222 1 () 2 111 ()max0, 0 442 uuxuuux fxxxux = = 令： ()=，由()=0，得： ，且 第三步，3:k= 33 33 33 2 33322 0 2 3233 0 22 333 0 ()() () 1 () . 4 max max max ux ux ux fxufx ufxu uxu = = = 22 3333333 44* 333333 4 333 11 () 42 111 ()max0, 0 64642 1 4()44 64 uuxuuux fxxxux xfx = = = 同理，令： ()=，由()=0，得： ，且 将代入上述表达式，逆序递推求出： 33 ()4fx= * 33 * 22 * 11 * * 42 21 11. (1,1,2)()4 (1,1,2)()4. xu xu xu uf u xf x = = = = = ,， ,， , 新问题的最优解为：，且 原问题的最优解为：，且 2. 2. 2. 2.设有设有 5 5 5 5 个城市，编号从个城市，编号从 1 1 1 1 到到 5 5 5 5，记第，记第 个城市与第个城市与第个城市的距离为个城市的距离为，记：，记：ij ij d ， 5 5 0652 2 60 0.5 5 7 ()5 0.5 0 1 5 251 0 3 2753 0 ij Dd = 试分别用函数迭代法和策略迭代法求出各城市到第试分别用函数迭代法和策略迭代法求出各城市到第 5 5 5 5 个城市的最短距离。个城市的最短距离。 解：法一，函数迭代法： 15 11111 21 05 21 21 2