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

最优化方法部分课后习题解答 1.一直优化问题的数学模型为： 习题一 12 min f (x) = (x 3)2 + (x 4)2 5 g (x) = x x 0 1 1 2 2 s.t. g2 (x) = x1 x2 + 5 0 试用图解法求出： 0 g (x) = x 3 1 g4 (x) = x2 0 （1） 无约束最优点，并求出最优值。 （2） 约束最优点，并求出其最优值。 （3） 如果加一个等式约束 h(x) = x 1 x2 = 0 ，其约束最优解是什么？ * 解 ：（1）在无约束条件下， f(x) 的可行域在整个 x 1 0x2 平面上，不难看出，当 x =（3，4） 时， f(x) 取最小值，即，最优点为 x * =（3，4）：且最优值为： f (x* ) =0 （2）在约束条件下， f(x) 的可行域为图中阴影部分所示，此时，求该问题的最优点就是 在约束集合即可行域中找一点 (x 1 , x2 ) ，使其落在半径最小的同心圆上，显然，从图示中可 以看出，当 x * = ( 15 , 5 ) 时， f(x) 所在的圆的半径最小。 4 4 g (x) = x x 1 1 2 5 = 0 15 x 1 = 求解得到： 4 其中：点为 g 1 (x) 和 g2 (x) 的交点，令 2 5 即最优点为 x * = g2 (x) = x1 x2 + 5 = 0 ( 15 , 5 ) ：最优值为： f (x * ) = 65 x = 2 4 4 4 8 （3）.若增加一个等式约束，则由图可知，可行域为空集，即此时最优解不存在。 2.一个矩形无盖油箱的外部总面积限定为 S， 怎样设计可使油箱的容量最大？试列出这个优 化问题的数学模型，并回答这属于几维的优化问题. 解：列出这个优化问题的数学模型为： max f (x) = x 1x2 x3 x2 + 2x2 x3 + 2x 1x3 S x 1 s.t. x1 0 x2 0 x3 0 该优化问题属于三维的优化问题。 ij nn1 2 12nn n 1 2 1 2 1 2 1 x = s/ 3, y = s/ 3, z = s/ 12 v = s 3 3s = =1 =s2 18 2 3 习题二 3.计算一般二次函数 f(x) = 1 XT A X + b T X + c的梯度。 2 解：设： A= (a ,b= (b )T , X = (x , x ,. T ： ) ,b ,.bx )则 f(x) = 1 n n n a xx + bx + c，将它对变量 x (i = 1, 2,.n) 球偏导数得： ij i j i i i 2 i=1 j=1 i=1 1 1 n a1 jxj + n a i1xi + b1 n n a1 jxj ai1xi f (x) 2 j=1 2 i=1 x1 j=1 i=1 f (x) 1 1 n a2 jxj + n ai2 xi + b2 n n b jxa j + 1 + b ai2 xi f(x) = = 2 j=1 2 i=1 1 2 = j=1 i=1 2 x2 2 2 b f (x) 1 1 3 x3 n a njxj + n a i nxi + bn n anjxj ai nxi 2 j=1 2 i=1 j=1 i=1 1 T = (AX + A X) + b 2 5.求下列函数的梯度和 Hesse 矩阵 （1） f(x) = x2 2x 2 3x 2 4xx + 1 2 3 1 3 2 0 -4 解： 2 f (x) = 4 0 0 x 2e x1x2 4 0 6 6x e x1x2 +xx ex1x2 + 2 2 1 2 （2） f(x) = 3xx 2 + ex1x 2 解： 2 f (x) = 1 2 1 2 1 2 1 2 6x + e x x +xx ex x 6x +x2e x x 2 1 2 1 1 6.判断下列函数是凸函数，凹函数，还是既不凸也不凹函数： （1） f(x , x ) = x2 + 2x 2 + 3xx 解： 2 f (x) 不是半正定，即 f(x) 非凸，然后判断 f(x) ，经验证： 2 ( f(x) 不是半 正定，由此可知： f(x) 非凸非凹。 1 2 1 1 2 21 （2） f(x , x ) = 2x2 4xx + 3x 2 5x 6 解： 2 f (x) 半正定，故 f(x) 为凸函数。 （3） 2 2 2 f(x 1 , x2 , x3 ) = x1 + 2x2 3x 3 4x 1x2 解： 2 f (x) 不是半正定，即 f(x) 非凸，然后判断 f(x) ，经验证： 2 ( f(x) 不是半 正定，由此可知： f(x) 非凸非凹。 7.设约束优化问题的数学模型为： 1122 min f(x) = x2 + 4x + x 2 4x + 10 s.t. g 1 (x) = x1 x2 + 2 0 2 1212g (x) = x 2 x 2 2x + 2x 0 试用 K-T 条件判别点 x = 1,1 T 是否为最优点。 解：对于点 x = 1,1 T ， g ( 足约束条件，故点 X 是可行解。 x) =0， g (x) 0 ，点满 1 2 2 1 且 g 1 (x) 是起作用约束，I = 1 , f(x) = , g 1 (x) = ，由 g i (x) 0 条件下的 2 1 K-T 条件得： f(x) igi(x) = 0, i 0 ，得到 1 = 2 ，点 x = 1,1 T i I 满足 K-T 条 件。又因 2 f (x) 正定，故 f(x) 为严格凸函数，该最优化问题是凸规划问题，由 x * = 1,1 T 是 K-T 点，所以 x* = 1,1 T 也是该问题的全局最优点。 8.设约束优化问题： 12 min f(x) = (x 2)2 + x 2 g 1 (x) = x1 0 2 2 s.t. g (x) = x 0 g = + + 3 1 2 (x) 1 x2 x 0 k 它的当前迭代点为 x = 1, 0 T ，试用 K-T 条件判定它是不是约束最优解。 解：对于点 x= 1, 0 T g (x ) 1 0, g (x ) =, g (x ) 0 T 是 可 行 点 ， = k 1 k 2 0= ，点 x = 1, 0 k 3 k k 2 0 且起作用的约束条件是， g2 (x), g3 (x) ， I = 2, 3 , f(x k ) = ， g2 (xk ) = 0 1 1 2 g3 (xk ) = ，由约束条件为 gi(x) 0 时的 K-T 条件得，应有： 2 = 1 T ，所以 x = 1, 0 f(x) + igi (x) = 0,i 0 解得： i I = 1 k 3 为 K-T 点。 1 2 现判断该问题是否为凸规划问题，因 2 f (x) 正定，故 f(x) 为凸函数， g (x), g (x) 为 线性 函数，亦为凸函数， 2g (x) 半正定，所以 g (x) 为凸函数，所以该优化问题为凸 3 3 k 规划问题，即点 x = 1, 0 T 是该问题的约束最优解。 习题三 1. 对于下列线性规划问题找出所有基解，指出哪些是基可行解，并确定出最优解。 max f (x) = 3x 1 + x2 + 2x3 2x1 + 3x2 + 6x3 + x4 = 9 1 8x 1 + x2 4x3 + 2x5 = 10 （1） s.t. 3x1 x6 = 0 xj 0, ( j = 1, 2.6) 12 3 6 3 0 0 解：令 A= 8 1 -4 0 2 0 3 0 0 0 0 -1 = (P 1 , P2 , P3 , P4 , P5 , P6 ) （1） 基解 x (0, 16 , 7 , 0, 0, 0) 不是基可行解， = 1 3 6 （2） 基解 x 2 = (0,10, 0, 7, 0, 0) 不是基可行解， （3） 基解 x 3 = (0, 3, 0, 0, 3.5, 0) 是基可行解，且 f(x) = 3 ， 7 （4） 基解 x 4 = ( , 4, 0, 0, 0, 21 4 5 ) 不是基可行解， 4 （5） 基解 x 5 = (0, 0, , 8, 0, 0) 不是基可行解， 2 （6） 基解 x= (0, 0, 3 , 0,16, 0) 是基可行解，且 f(x) = 3 ， 6 2 （7） 基解 x= (1, 0, 1 , 0, 0, 3) 不是基可行解， 7 2 （8） 基解 x 8 = (0, 0, 0, 3, 5, 0) 是基可行解，且 f(x) = 0 ， （9） 基解 x = ( 5 , 0, 0, 2, 0, 15) 不是基可行解。 9 4 4 3 9 9 （10） 基解 x 10 = ( 4 , 0, 0, 0, 4, 4) 是基可行解，且 f(x) = 4 。 16 7 （11） 基解 x 11 = (0, 3 , 6 , 0, 0, 0) 不是基可行解。 （12） 基解 x 12 = (0,10, 0, 7, 0, 0) 不是基可行解。 7 （13） 基解 x 13 = (0, 3, 0, 0, 2 , 0) 是基可行解，且 f(x) = 3 。 （14） 基解 x (0, 0, 5 , 8, 0, 0) 不是基可行解。 = 14 2 （15） 基解 x (0, 0, 3 , 0, 8, 0) 是基可行解，且 f(x) = 3 。 = 15 2 （16） 基解 x 16 = (0, 0, 0, 3, 5, 0) 是基可行解，且 f(x) = 3 。 2. 用单纯形法求解下列线性规划问题： max f (x) = 10x 1 + 5x2 （1） 5 1 2 3x1 + 4x2 9 s.t. x + 2x 8 x1 , x2 0 解：将现行规划问题化为标准形式如下： min( f (x) = 10x 1 5x2 + 0x3 + 0x4 3x1 + 4x2 + x3 = 9 5 1 24 s.t. x + 2x + x = 8 x1 , x2 , x3 , x4 0 作初始单纯形表，并按单纯形表步骤进行迭代，如下： CB XB b -10 x 1 -5 x 2 0 x 3 0 x 4 i 0 x 3 9 3 4 1 0 3 0 x 4 8 5 2 0 1 1.6 0 -10 -5 0 0 0 x 3 4.2 0 2.8 1 -0.6 1.5 -10 x 1 1.6 1 0.4 0 0.2 4 16 0 -1 0 2 -5 x 2 1.5 0 1 5 14 3 14 -10 x 1 1 1 0 1 7 2 7 17.5 0 0 5 14 25 14 此时， 为正，目标函数已不能再减小，于是得到最优解为： x * = (1, 3 , 0, 0) 均 j 2 目标函数值为： f(x * ) = 17.5 3. 分别用单纯形法中的大 M 法和两阶段法求解下列线性规划问题： min f (x) = 5x 1 2x2 + 3x3 6x4 7 x + 2x + 3x + 4x = 1 2 3 4 （1） s.t. 2x 1 + x2 + x3 + 2x4 = 3 x1 , x2 , x3 , x4 0 解：（1）大 M 法：把原问题化为标准形式，并加入人工变量如下： min f (x) = 5x 1 2x2 + 3x3 6x4 + M x5 + M x6 x1 + 2x2 + 3x3 + 4x4 + x5 = 7 1 2346 s.t. 2x + x + x + 2x + x = 3 x1 , x2 , x3 , x4 , x5 , x6 0 作初始单纯形表，并按单纯形表步骤进行迭代，如下： CB XB b 5 x 1 -2 x 2 3 x 3 -6 x 4 -6 x 4 -6 x 4 i M x 7 1 2 3 4 1 0 1.75 M x 3 2 1 1 2 0 1 1.5 -10M 5-3M -2-3M 3-4M -6-6M0 0 M x 1 -3 0 1 0 1 -2 1 -6 x 1.5 1 0.5 0.5 1 0 0.5 3 9-M 11+3M 1 6-M 0 0 3M+3 3 x 1 -3 0 1 0 1 -2 -6 x 1 2.5 0.5 0 1 -0.5 1.5 3 29 1 0 0 M-6 M+15 5 6 5 4 3 4 因为 M 是一个很大的正数，此时j 均为正， 所以，得到最优解： x * = (0, 0,1,1, )T ，最优值为 f(x* ) = 3 （2）两阶段法 首先，构造一个仅含人工变量的新的线性规划如下： 1 2346 按单纯形法迭代如下： min g(x) = 0x 1 + 0x2 + 0x3 + 0x4 + x5 + x6 x1 + 2x2 + 3x3 + 4x4 + x5 = 7 s.t. 2x + x + x + 2x + x = 3 x1 , x2 , x3 , x4 , x5 , x6 0 CB XB b 0 x 1 0 x 2 0 x 3 0 x 4 1 x 4 1 x 4 i 1 x 5 7 1 2 3 4 1 0 1.75 1 x 6 3 2 1 1 2 0 1 1.5 -10 -3 -3 -4 -6 0 0 1 x 5 1 -3 0 1 0 1 -2 1 0 x 4 1.5 1 0.5 0.5 1 0 0.5 3 -1 4 0 -1 0 0 3 0 x 3 1 -3 0 1 0 1 -2 0 x 4 1 2.5 0.5 0 1 -0.5 1.5 最优解为： x * = (0, 0,1,1, 0, 0) ，最优值： g(x) = 0 * x = (0, 0,1,1, ) T 因人工变量 x 5 = x6 = 0 ，则原问题的基可行解为: 如下表所示： ,进入第二阶段计算 CB XB b 5 x 1 -2 x 2 3 x 3 -6 x 4 3 x 3 1 -3 0 1 0 -6 x 4 1 2.5 0.5 0 1 3 29 1 0 0 由上表可知，检验数均大于等于 0，所以得到最优解： x * = (0, 0,1,1, )T 最优值为 f(x * ) = 3 。 4.某糖果厂用原料 A，B，C 加工成三中不同牌号的糖果，甲，乙，丙，已知各种牌号糖 果中 A,B,C 含量，原料成本，各种原料的每月限用量，三中牌号糖果的单位加工费及售 价如下表所示，问该厂每月应生产这三种牌号糖果各多少千克，使该厂获利最大？试建 立这个问题的线性规划数学模型。 甲 乙 丙 原料成本 （元/千克） 每月限用量 （千克） A 60 % 15 % 2.00 2000 B 1.50 2500 C 20 % 60 % 50 % 1.00 1200 加工费 0.50 0.40 0.30 售价 3.40 2.85 2.25 解：设 x i, yi, zi 0,i = 1, 2, 3 表示甲、乙、丙中分别含 A、B、C 的含量，构造此问题的 数 学规划模型如下： max f (x) = 0.9x 1 + 1.4x2 + 1.9x3 + 0.45y1 + 0.95y2 + 1.45y3 0.5z1 + 0.45z2 + 0.95z3 x + y 1 + z1 2000 1 x2 + y2 + z2 2500 x + y 3 + z3 1200 3 1 2 3 0.4x1 0.6x2 0.6x3 0 s.t. 0.85y 0.15y 0.15y 0 .2x 0.2x 0.8x 0 0+ 1 2 3 0.6y 1 0.6 y2 + 0.4 y3 0 0.5z1 + 0.5z2 0.5z3 0 xi, yi, zi 0,i = 1, 2, 3 5.求解下列线性规划问题的对偶问题 min f(x) = 2x 1 + 2x2 + 4x3 2x1 + 3x2 + 5x3 2 s.t. 3 1 2 3 （1） x + x + 7x 3 x1 + 4x2 + 6x3 5 x1 , x2 , x3 0 max f (x) = 5x 1 + 6x2 + 3x3 + 2x2 + 2x3 = 5 x 1 x 1 + 5x2 x3 3 （2） s.t. 1 2 3 4x1 + 7x2 + 3x3 8 x 无约束, x 0, x 0 解：（1）由表 3.7 可得该问题的对偶问题为： max g( y) = 2y 1 + 3y2 + 5y3 2y1 + 3y2 + y3 2 s.t.3y 1 2 3 + y + 4 y 2 5y1 + 7 y2 + 6 y3 4 y1 0, y2 , y3 0 （2）该问题的对偶问题为： min g( y) = 5y 1 + 3y2 + 8y3 y1 3y2 + 4 y3 = 5 2y 1 + 5y2 + 7 y3 6 s.t. 1 2 3 2y1 y2 + 3y3 3 y 无约束, y 0, y 0 6用对偶单纯形法求解下列线性规划问题： min f(x) = 4x 1 +12x2 +18x3 x x 3 + 3 （1） 1 3 s.t. 2x 2 + 2x3 5 x1 , x2 , x3 0 解：（1）首先，将“ ”约束条件两边反号，再加入松弛变量，得： min f (x) = 4x 1 +12x2 +18x3 + 0x4 + x5 x1 3x3 + x4 = 3 235 s.t. 2x 2x + x = 5 x1 , x2 , x3 , x4 , x5 0 建立初始单纯形表如下图所示，所有j 0 。 则对应对偶问题解是可行的，则继续迭代： CB XB b 4 x 1 12 x 2 18 x 3 0 x 4 0 x 5 0 x 4 -3 -1 0 -3 1 0 0 x 5 -5 0 -2 -2 0 1 4 12 18 0 0 计算 min 3, 5 = 5 ，所以 x 5 为换出变量， = min 6, 9 = 6 ，确定 x 2 为换入变量。 继 续迭代，得到如下单纯形表： CB XB b 4 x 1 12 x 2 18 x 3 0 x 4 0 x 5 0 x 4 -3 -1 0 -3 1 0 0 x 2 -2.5 0 1 1 0 -0.5 4 0 6 0 0 min 3 = 3, x 4换出， min 4， 2 = 2，x 3换入 。 CB XB b 4 x 1 12 x 2 18 x 3 0 x 4 0 x 5 0 x 3 1 1 0 1 1 0 0 x 2 1.5 1 1 0 1 -0.5 2 0 0 2 6 * 3 T 此时，所有j 0 ，故原问题的最优解为 x = 0, ,1 * ,最优值为： f(x ) = 36 2 其对偶问题得到最优解为： x * = 2, 6T ，最优值为： f(x* ) = 36 。 7.已知线性规划问题 min f (x) = 2x 1 x2 + x3 x1 + x2 + x3 6 12 s.t. x + 2x 4 x1 , x2 , x3 0 先用单纯形法求出最优解，再分别就下列情况进行分析： （1） 目标函数中变量 x 1 , x2 , x3 的系数分别在什么范围内变化，问题的最优解不变； （2） 两个约束条件的右端分别在什么范围内变化，问题的最优解不变。 解：将该规划问题化为标准型，引入松弛变量 x 4 , x5 min f (x) = 2x 1 x2 + x3 + 0x4 + 0x5 , x1 + x2 + x3 + x4 = 6 s.t. x 4 + 2x + x = 1 2 5 x1 , x2 , x3 , x4 , x5 0 用单纯形法求解，如下表： CB XB b 2 x 1 -1 x 2 1 x 3 0 x 4 0 x 5 i 0 x4 1 1 1 1 1 0 6 0 x 5 1.5 -1 2 0 0 1 2 2 -1 1 0 0 0 x 4 4 1.5 0 1 1 -0.5 -1 x2 2 -0.51 0 0 0.5 1.5 0 1 0 0.5 由上表可知，所有的检验数均大于等于零，得最优解: x * = (0, 2, 0, 4, 0)T ,所以原问题的 最优解为： x * = (0, 2, 0, )T ，最优值 f(x* ) = 2 （1） 变量x 1，x2，x3中，x1，x3为非基变量，x2为基变量 。 由= 3 ，当c 3 时，c c + c 1 ，所以，当c 1 , +), 此时最优解不变。 = 1 2 1 2 1 1 1 2 1 2 由3 = 1，当c 3 1时， c 3 = c3 + c3 0，所以，当c3 0, +), 此时最优解不变。 c2 (3,1) ，最优解不变。 综上，当c 1 , +)，c 4, 0，c 0, +), 此时最优解不变。 1 2 2 3 （2） b 1 的变化范围 B 1b+ B 1 b1 = 4 + 1 0.5 0.5 b 1 4 1 b 0 = + 1 02 0 0 2 00 得到： 4 + b 1 0 b1 4，则b1的变化范围是b1 2 ，最优解保持不变。 B 1b+ B 1 0 4 1 = + 0.5 0 4 0.5 0 = + b 2 0 0.5 b2 2 0.5 2 0 b2 得到： 4 b 2 8，则b2的变化范围是0,12，最优解保持不变。 习题四 3.用 Newton 法求解 (t) = t 3 2t+1 用第 1 题求得的区间，按精度 = 0.01 计算。 解：(t0 ) = (0) = 1,t 1 = t0 + h0 = 1,(t1 ) = 0,1 = 0,因为(t1 ) (t0 )，则 h1 = h0 = 2 t2 = t 1 + h1 = 1，(t2 ) = 22,2 = 22,(t1 ) (t2 )，反向，因为 K=2 0,所以=0，b=3 则搜索区间为 t 0,3 (t) = 3t2 2,(t) = 6,(0) = 2 0 取： ，t = 1 1 = 5 5 1 0.01，继续迭代 t =t 5 = 1,(t ) = 1, (t )= 6, 所以 t 0 0 0 = 6 6 6 0 6 ， t = t (t0 ) = 49 , 则 t t 0 0 (t ) 60 0 60 0 60 = 11 0.01, 令t = 49 ，则t 0.8165 ， t t0 = 0.0005 , 继续迭代，因为 (t 1 ) (t2 ) ，则新的搜索区间为-3，0.056： t 1 = 1.832608,(t1 ) = 0.306764,t2 = 1.111392,(t2 ) = 0.987592， t 1 t2 , 继续迭代 ，因为(t 1 ) (t2 ) ，所以新的搜索区间为-1.832608，0.056： t 1 = 1.111292,(t1 ) = 0.987592, t2 = 0.665448,(t2 ) = 0.888075， ， t 1 t2 , 继续 ，(t 1 ) (t2 ) ，所以新的搜索区间为-1.832608，-0.665448 ： t 1 = 1.386753,(t1 ) = 0.854402,t2 = 1.111392,(t2 ) = 0.987592 ， t 1 t2 , 继续 ，因为(t 1 ) (t2 ) ，所以新的搜索区间为-1.386753，-0.665448 t2 = 0.940987,(t2 ) = 0.996518,t 1 = 1.111392,(t1 ) = 0.987592， ， t 1 t2 , 继续 ，因为(t 1 ) (t2 ) ，所以新的搜索区间为-1.111392，-0.665448 ： t 1 = 0.940987,(t1 ) = 0.996518,t2 = 0.835799,(t2 ) = 0.973038， ， t 1 t2 , 继续 ，因为(t 1 ) (t2 ) ，所以新的搜索区间为-1.111392，-0.835799 ： t2 = 0.940987,(t2 ) = 0.996518,t 1 = 1.006115,(t1 ) = 0.999962， ， t 1 t2 , 继续 ，因为(t 1 ) (t2 ) ，所以新的搜索区间为-1.111392，-0.940987 ： t 1 = 1.046295,(t1 ) = 0.997857,t2 = 1.006115,(t2 ) = 0.999962， ， t 1 t2 , 继续 ，因为(t 1 ) (t2 ) ，所以新的搜索区间为-1.046295，-0.940987 ： t2 = 0.981215,(t2 ) = 0.999647,t 1 = 1.006115,(t1 ) = 0.999962， ， t 1 t2 , 继续 ，因为(t 1 ) (t2 ) ，所以新的搜索区间为-1.046295，-0.981215 ： t 1 = 1.021434,(t1 ) = 0.999540, t2 = 1.006115,(t2 ) = 0.999962， ， t 1 t2 , 继续 ，因为(t 1 ) (t2 ) ，所以新的搜索区间为-1.021434，-0.981215 ： t2 = 0.996579,(t2 ) = 0.999987,t 1 = 1.006115,(t1 ) = 0.999962 ， t 1 t2 , 继续 ，因为(t 1 ) (t2 ) ，所以新的搜索区间为-1.006115，-0.981215 ： t 1 = 0.996579,(t1 ) = 0.999987, t2 = 0.990727,(t2 ) = 0.999914， ， t 1 t2 , 继续 ，因为(t 1 ) , 继续 ，因为(t 1 ) , 继续 ，因为(t 1 ) (t2 ) ，所以新的搜索区间为-1.002472，-0.996579 ： t2 = 0.998830,(t2 ) = 0.999998505,t 1 = 1.000237,(t1 ) = 1.00000016， t 1 t2 , 继续 ，因为(t 1 ) , t , t t0 , (t ) = 0.1588 , t t0 ,(t ) = 0.2004 , t t0 ,(t ) = 0.2029 , t t0 , (t ) = 0.2032 , t t0 ,(t ) = 0.2034 g Tg 1.91988 3.8976 0.07348 x = x 1 1 g = 0.48089 = 0.003 0.15 0.06913 2 1 g T A g 1 f (x 2 ) = 0.124872 g2 00 同理继续迭代，最后至x = ，此时最优解x = 0 0 ，f (x) = 0 2.用 Newton 法求解 2 2 T -x 1x2，初始点x0 = 0，0 ， = 0.01. min f (x) = 60 10x 1 4x2 + x1 解： + x 2 g(x) = f (x) = 10 + 2x x , 4 + 2x x T 2 1 2 G(x) = 1 G(x) 1 = 1 2 = 1 = 2 3 3 2 1 x = x G(x) 1 g(x ) = 0 3 10 = 8, 6T 1 0 0 3 0 1 2 4 3 3 T f(x 1 ) = 0, 0 , f(x 1 ) = 0 0.01 最优解为x * = 8, 6T , f (x * ) = 8 3.用修正 Newton 法求解 2 2 T min f (x) = （4 x 1 +1）+ （ 2 x 2 1）+ x1 + x2 +10，初始点x0 = 0，0 ， = 0.01. t 8 9 0 T 解： g(x) = f (x) = 8x 1 + 9, 4x2 3 x 1 = x0 + t0 p0 = 0 3 t 4 1 0 G(x) = 8 0 G(x)1 = ， 8 ，) 0 g(x = 9， 3 T 0 4 0 = 8 1 20 0 1 1 2 2 0 1 4 1 0 9 9 3 9 t 8 0 则 p = G(x) 1 g(x ) = = , T ，令 0 0 0 1 3 8 4 4 x 1 = x0 + t0 p0 = 3 4 t0 f(x = 99 t2 99 t+16 t = 1时，f (x)最小 ) 1 16 8 x 9 , 3 T，f (x ) 0, 0T , = 1 8 4 1 1 f (x ) = 0 0.01 x * = 9 , 3 T , f (x* ) = 157 8 4 16 4.用共轭梯度法求解 min （x2 + 4x 2），取初始点x = 1，1T， = 0.01. 解： 令 f(x) = x 2 2 = 2x , 8x T + 4x , f (x) ， p= ) = 1 1 1 2 0 0 f(x 2, 8 T 12 T x 1 = x0 + t0 p0 = + t 0 = 1 2t 0 ,1 8t0 1 8 令 min(1 2t 0 ) 2 + 4(1 8t )2 = min(t) ， 则 d (t) = 520t 68 0 t 0.130969 = = dt 0 0 x = 0.738062, 0.047752T，f(x ) = 1.476124, 0.382016T 则 = f (x 1 ) = 2.324878 0.034189 f (x 0 ) 68 新搜索方向为p 1 = f(x1 ) + 0 p0 1.476124 2 1.544502 = + 0.034189 = 0.382016 8 0.108504 2 1 1 1 11 因此有x = x + t p = 0.738062 1.544502t , 0.047752 + 0.108504t T 由 d f (x + t p 0 t .477127 ) =0 dt 1 1 1 1 0.738062 1.544502 T 0, 0.007 因而得下一迭代点x 2 = x1 + t1 p1 = 0.047752 + 0.477127 0.108504 = 0.0 * T* = 0, 0 , f (x ) = 0 f(x 2 ) = 0 0.01停止迭代 ， x 121 2 5.用共轭梯度法求解 min f(x) = 2x2 + x 2 -xx，自定初始点， = 0.01. 解： f(x) = 4x 1 x2 , 2x2 x1 T T ，取初始点 x 0 = 0,1 00 ， p = f(x ) = 1, 2T 01 T x 1 = x0 + t0 p0 = + t = t 0 ,1 2t0 0 1 2 0 0 令 min2t2 + (1 2t )2 t 0 (1 2t0 ) = min(t ) 则 d (t) = 16t 5 0 t 0.125 = = dt 0 0 1 1 x = 0.3125, 0.375T，f(x ) = 0.875, 0.4375T 2 2 0 = f (x 1 ) = 0.95703125 0.191406 f(x 0 ) 5 新搜索方向为p 1 = f(x1 ) + 0 p0 0.875 1 0.683594 = + 0.191406 = 0.4375 2 0.82012 2 1 1 111 因而得下一迭代点x = x + t p = 0.3125 0.683594t , 0.375 0.820312t T 由 d f (x t p 0 t = .456927 ， + ) =0 dt 1 1 1 1 2 2 则 x = 0.000, 0.000T，f(x ) = 0, 0T , f(x 2 ) = 0 0.01 停止迭代 2 则 x * = x = 0, 0T ，综上所述，原问题的最优解 x * = 0, 0T ，最优值为 f(x* ) = 0 6.用 DFP 法求解 min f(x) = （ 4 120 x 5） 2 + （x 6） 2 ，初始点x = 8 ，9 T ， = 0.01. 6、解：取 H0 = I, 8 0 T A= , 0 2 g(x) =8x 1 40, 2x2 12 T x 0 = 8,19 T , g0 = 24, 6 T x 1 = 4.86154, 8.21538 T , g 1 = 1.10768, 4.43076 第一步迭代得： 0 10 用 DFP 法第二次迭代： s = x x = 3.13846, 0.78462T 0 10 y = g g = 25.10768, 1.56924T s y y H y s s H yy H 0 0 T T 则 H = H+ T 0 0 0 0 ， 1 0 T T 0 0 0 0 0 T TT y0 H0 y0 = y0 因： s 0 y0 = 80.03071, y0 = 632.85811 s T = 9.84993 2.46250 s 0 0 2.46250 0.61563 s s ， 0 0 T = 9.84993 2.46250 2.46250 0.61563 1 0 0.12308 0.03077 0.99611 0.06226 0.12697 0.03149 H1 = 1 + .03077 0.00770 .06226 0.00390 = 0.03149 1.0038 0 0 0 则搜索方向 p 1 = H1g1 = 0.28017, 4.48248 从 x 1 出发沿 p1 进行直线搜索，即： x 1 = x1 + t p1 = 4.86154 0.28017t, 8.21538 + 4.48248t T 由 d f (x 0 ，得 t = 0.48674 + t p ) = dt 1 1 2 1 1 所以 x = x + t p 5.000, 6.000T 2 ，由于 g(x ) = 0, 0T 2 ，所以 x = 5, 6T 是极小 点。 习题六 1.用外点罚函数法求解： min f(x) = x 1 + x2 s.t. g (x) x 2 x 0 = + 1 1 2 g2 (x) = x1 0 解：利用外点罚函数法构造增广目标函数，如下： x + x+ + x + x 1 2 1 2 1 (x 2 )2 2 (x D) F(x, ) = x1 + x2 (x D) 对于 x D的情况： 由 F = 0, F = 0 得： x () = 1 , 1 1 2 4(1 + ) 2 x 1 x 2 2 + 2 当 + 时， x () (0, 0) 即： x = (0, 0) ，且 f(x ) = 0 2.用外点罚函数法求解： 2 min f (x) = x 1 2 + x2 s.t. g(x) = 1 x 1 0 12 k k x 1 解：构造增广目标函数： F(x, ) = x 2 2 x ) 2 + x+ (1 1 2 1 (x D) x 2 + x2 (x D) 对于 x D的情况： 由 F = 0, F = 0 x1 2(1 x1 ) = 0 2 得： x 1 x2 2x2 = 0 推出： x () = , 0 1 + 当 + 时， x () (1, 0) 。 即： x = (1, 0) 且 f(x ) = 1。 4.用内点罚函数法求解： min f (x) = 1 (x +1)3 + x 3 1 2 s.t. g1 (x) = x 1 1 0 g2 (x) = x2 0 解：利用内点罚函数法构造如下增广目标函数： F(x, r ) 1 (x +1)3 x r ( 1 = + + k 3 1 2 + 1 ) x 1 1 x 2 F = 0 由 得： x * (x ) = ( 1 + r , r ) F = 0 x 2 k k k + 当 r k 0 时， x * (x ) (1, 0) x * = (1, 0) ， f(x* ) = 8 3 5.用内点罚函数法求解： min 1 (x 3 +1)+ x 3 1 2 s.t. 0 x 1 0 1 x2 解法同上。 习题七 1.用动态规划求解： 1 2 3 max E = xx x 2 s.t. xi x + x2 + x3 4 1 0 (i = 1, 2, 3) 1 2 3 解：将原问题表示为： max E = uu u2 s.t. ui u + u2 + u3 4 1 0 (i = 1, 2, 3) 由此，确定状态变量为： x 1 , x2 , x3 ， 决策变量为： u1 ,u2 ,u3 状态转移方程： x 1 = u1 ; x2 = u2 + x1 ; x3 = u3 + x2 4 。 用动态规划的思想顺推，如下： 第一步， k = 1 : 1 1 max 1 1 1 f (x ) = u = x , 且 u * u1 =x 1 = x 1 。 第二步， k = 2 : f2 (x 2 ) = maxu2 f1 (x1 ) 0u2 x 2 = maxu2 f 1 (x2 u2 ) 0u2 x 2 = maxu 2 (x2 u2 ). 0u2 x 2 令：(u )=u (x = 2 2 2 2 2 2 2 2 u )， 由 ( u )=0， 得u： 1 x fmax0 (x ) = 2 2 4 2 1 ， x 2 , 0 = 1 x2， 且* 1 u= x 4 2 2 2 2 第三步， k = 3 : f x = ( ) u 3 3 max 2 f (x ) 3 2 2 0u3 x 3 = 2 u max f (x u ) 3 2 3 3 0u3 x 3 = 2 1 (x 2 u max u ) . 3 4 3 3 0u3 x 3 同理，令：(u )=u2 1 (x u )2 ， 由 ( u )=0， 得u：= 1 x 3