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

最优化方法部分课后习题解答1.一直优化问题的数学模型为：习题一12min f (x) = (x 3)2 + (x 4)2g (x) = x x 5 0 1122试用图解法求出：s.t. g2 (x) = x1 x2 + 5 0g (x) = x 0 31g4 (x) = x2 0（1） 无约束最优点，并求出最优值。（2） 约束最优点，并求出其最优值。（3） 如果加一个等式约束 h(x) = x1 x2 = 0 ，其约束最优解是什么？*解 ：（1）在无约束条件下， f(x) 的可行域在整个 x1 0x2 平面上，不难看出，当 x =（3，4）时， f(x) 取最小值，即，最优点为 x* =（3，4）：且最优值为： f (x* ) =0（2）在约束条件下， f(x) 的可行域为图中阴影部分所示，此时，求该问题的最优点就是在约束集合即可行域中找一点 (x1 , x2 ) ，使其落在半径最小的同心圆上，显然，从图示中可以看出，当 x* =(15 , 5 ) 时， f(x) 所在的圆的半径最小。4 4g (x) = x x 5 = 015x1 =其中：点为 g1 (x) 和 g2 (x) 的交点，令 1122求解得到： 45即最优点为 x* =g2 (x) = x1 x2 + 5 = 0(15 , 5 ) ：最优值为： f (x* ) = 65x = 244 48（3）.若增加一个等式约束，则由图可知，可行域为空集，即此时最优解不存在。2.一个矩形无盖油箱的外部总面积限定为 S，怎样设计可使油箱的容量最大？试列出这个优 化问题的数学模型，并回答这属于几维的优化问题.解：列出这个优化问题的数学模型为：max f (x) = x1x2 x3x1x2 + 2x2 x3 + 2x1x3 Ss.t. x1 0x2 0x3 0该优化问题属于三维的优化问题。x =s/ 3, y =s/ 3, z =s/ 12v = s33s = =1 =s2 182 3 习题二3.计算一般二次函数 f(x) = 1 XT AX + bT X + c的梯度。2ij nn12n12n解：设： A= (a ),b= (b,b ,.b )T , X = (x , x ,.x )T 则：f(x) = 1n nna xx +bx + c，将它对变量 x (i = 1, 2,.n) 球偏导数得： ij i j i ii2 i=1j=1i=1 1 n1 n n n f (x) a1 jxj +ai1xi + b1 a1 jxj ai1xi 2 j=12 i=1 j=1 i=1 x1 1 n1 n n nb f (x) a2 jxj +ai2 xi + b2 a jxj ai2 xi f(x) = = 2 j=112 i=11 2 = + 1+ b j=1 i=1 2 x2 2 2 b f (x) 3 1 n1 n nn x3 anjxj +ainxi + bn anjxj ainxi 2 j=11T2 i=1 j=1 i=1=(AX + A X) + b25.求下列函数的梯度和 Hesse 矩阵（1） f(x) = x2 + 2x 2 + 3x 2 4xx 2 0 -4 解： 2 f (x) = 0 4 0 1231 3 x 2ex1x2 4 0 6 6x + ex1x2 +xx ex1x2（2） f(x) = 3xx 2 + ex1x2解： 2 f (x) =221 21 21 21 2 1 26x + ex x +xx ex x6x +x2ex x21 2116.判断下列函数是凸函数，凹函数，还是既不凸也不凹函数：12121 2（1） f(x , x ) = x2 + 2x 2 + 3xx解： 2 f (x) 不是半正定，即 f(x) 非凸，然后判断- f(x) ，经验证： 2 ( f(x) 不是半正定，由此可知： f(x) 非凸非凹。1211 221（2） f(x , x ) = 2x2 4xx + 3x 2 5x 6解： 2 f (x) 半正定，故 f(x) 为凸函数。（3）222f(x1 , x2 , x3 ) = x1+ 2x2 3x3 4x1x2解： 2 f (x) 不是半正定，即 f(x) 非凸，然后判断- f(x) ，经验证： 2 ( f(x) 不是半正定，由此可知： f(x) 非凸非凹。7.设约束优化问题的数学模型为：1122min f(x) = x2 + 4x + x 2 4x +10g1 (x) = x1 x2 + 2 0s.t. 21212g (x) = x2 x 2 2x + 2x 0试用 K-T 条件判别点 x = 1,1T 是否为最优点。解：对于点 x = 1,1T ， g (x) =0， g (x) 0 ，点满足约束条件，故点 X 是可行解。12 2 1 且 g1 (x) 是起作用约束，I = 1 , f(x) = , g1 (x) = ，由 gi (x) 0 条件下的 2 1TK-T 条件得： f(x) igi(x) = 0, i 0 ，得到 1 = 2 ，点 x = 1,1iI满足 K-T 条件。又因 2 f (x) 正定，故 f(x) 为严格凸函数，该最优化问题是凸规划问题，由x* = 1,1T 是 K-T 点，所以 x* = 1,1T 也是该问题的全局最优点。8.设约束优化问题：12min f(x) = (x 2)2 + x 2g1 (x) = x1 0 22s.t. g (x) = x 0g (x) = 1 + x2 + x 0 312k它的当前迭代点为 x = 1, 0T ，试用 K-T 条件判定它是不是约束最优解。解：对于点 x = 1, 0T g (x ) = 1 0, g (x ) = 0, g (x ) = 0 ，点 x = 1, 0T 是 可 行 点 ，k1k2k3kk 2 0 且起作用的约束条件是， g2 (x), g3 (x) ， I = 2, 3 , f(xk ) = ， g2 (xk ) = 0 1 2 1g3 (xk ) = ，由约束条件为 gi(x) 0 时的 K-T 条件得，应有： 2 = 1Tf(x) + igi (x) = 0,i 0解得：，所以 x = 1, 0 = 1k为 K-T 点。iI 312现判断该问题是否为凸规划问题，因 2 f (x) 正定，故 f(x) 为凸函数， g (x), g (x) 为 线性函数，亦为凸函数， 2g (x) 半正定，所以 g (x) 为凸函数，所以该优化问题为凸33k规划问题，即点 x = 1, 0T 是该问题的约束最优解。习题三1. 对于下列线性规划问题找出所有基解，指出哪些是基可行解，并确定出最优解。max f (x) = 3x1 + x2 + 2x312x1 + 3x2 + 6x3 + x4 = 9（1）8x1 + x2 4x3 + 2x5 = 10s.t. 3x1 x6 = 0xj 0, ( j = 1, 2.6)12 3 6 3 0 0 解：令 A= 81 -4 0 2 0 = (P1 , P2 , P3 , P4 , P5 , P6 ) 30 0 0 0 -1 （1） 基解 x = (0, 16 , 7 , 0, 0, 0) 不是基可行解，136（2） 基解 x2 = (0,10, 0, 7, 0, 0) 不是基可行解，（3） 基解 x3 = (0, 3, 0, 0, 3.5, 0) 是基可行解，且 f(x) = 3 ，721（4） 基解 x4 = ( , 4, 0, 0, 0,45) 不是基可行解，4（5） 基解 x5 = (0, 0, , 8, 0, 0) 不是基可行解，2（6） 基解 x = (0, 0, 3 , 0,16, 0) 是基可行解，且 f(x) = 3 ，62（7） 基解 x = (1, 0, 1 , 0, 0, 3) 不是基可行解，72（8） 基解 x8 = (0, 0, 0, 3, 5, 0) 是基可行解，且 f(x) = 0 ，（9） 基解 x = ( 5 , 0, 0, 2, 0, 15) 不是基可行解。944399（10） 基解 x10 = ( 4 , 0, 0, 0, 4, 4) 是基可行解，且 f(x) = 4 。167（11） 基解 x11 = (0, 3 , 6 , 0, 0, 0) 不是基可行解。（12） 基解 x12 = (0,10, 0, 7, 0, 0) 不是基可行解。7（13） 基解 x13 = (0, 3, 0, 0, 2 , 0) 是基可行解，且 f(x) = 3 。（14） 基解 x = (0, 0, 5 , 8, 0, 0) 不是基可行解。142（15） 基解 x = (0, 0, 3 , 0, 8, 0) 是基可行解，且 f(x) = 3 。152（16） 基解 x16 = (0, 0, 0, 3, 5, 0) 是基可行解，且 f(x) = 3 。2. 用单纯形法求解下列线性规划问题：max f (x) = 10x1 + 5x2（1）3x1 + 4x2 95 12s.t. x + 2x 8x1 , x2 0解：将现行规划问题化为标准形式如下：min( f (x) = 10x1 5x2 + 0x3 + 0x43x1 + 4x2 + x3 = 95 124s.t. x + 2x + x = 8x1 , x2 , x3 , x4 0作初始单纯形表，并按单纯形表步骤进行迭代，如下：CBXBb-10x1-5x20x30x4i0x39341030x4852011.60-10-5000x34.202.81-0.61.5-10x11.610.400.24160-102-5x21.501514 314-10x1110 172717.5005142514此时， 均为正，目标函数已不能再减小，于是得到最优解为： x* = (1, 3 , 0, 0)j2目标函数值为： f(x* ) = 17.53. 分别用单纯形法中的大 M 法和两阶段法求解下列线性规划问题：min f (x) = 5x1 2x2 + 3x3 6x4x + 2x + 3x + 4x = 7（1）1234s.t. 2x1 + x2 + x3 + 2x4 = 3x1 , x2 , x3 , x4 0解：（1）大 M 法：把原问题化为标准形式，并加入人工变量如下：min f (x) = 5x1 2x2 + 3x3 6x4 + Mx5 + Mx6x1 + 2x2 + 3x3 + 4x4 + x5 = 712346s.t. 2x + x + x + 2x + x = 3x1 , x2 , x3 , x4 , x5 , x6 0CBXBb5x1-2x23x3-6x4-6x4-6x4iMx71234101.75Mx32112011.5-10M5-3M-2-3M3-4M-6-6M00Mx1-30101-21-6x1.510.50.5100.539-M11+3M16-M003M+33x1-30101-2-6x12.50.501-0.51.5329100M-6M+15作初始单纯形表，并按单纯形表步骤进行迭代，如下：565434因为 M 是一个很大的正数，此时j 均为正，所以，得到最优解： x* = (0, 0,1,1, )T ，最优值为 f(x* ) = 3（2）两阶段法首先，构造一个仅含人工变量的新的线性规划如下：按单纯形法迭代如下：min g(x) = 0x1 + 0x2 + 0x3 + 0x4 + x5 + x6x1 + 2x2 + 3x3 + 4x4 + x5 = 712346s.t. 2x + x + x + 2x + x = 3x1 , x2 , x3 , x4 , x5 , x6 0CBXBb0x10x20x30x41x41x4i1x571234101.751x632112011.5-10-3-3-4-6001x51-30101-210x41.510.50.5100.53-140-10030x31-30101-20x412.50.501-0.51.5最优解为： x* = (0, 0,1,1, 0, 0) ，最优值： g(x) = 0*T因人工变量 x5 = x6 = 0 ，则原问题的基可行解为:如下表所示：x = (0, 0,1,1, ),进入第二阶段计算CBXBb5x1-2x23x3-6x43x31-3010-6x412.50.501329100由上表可知，检验数均大于等于 0，所以得到最优解： x* = (0, 0,1,1, )T最优值为 f(x* ) = 3 。4.某糖果厂用原料 A，B，C 加工成三中不同牌号的糖果，甲，乙，丙，已知各种牌号糖果中 A,B,C 含量，原料成本，各种原料的每月限用量，三中牌号糖果的单位加工费及售价如下表所示，问该厂每月应生产这三种牌号糖果各多少千克，使该厂获利最大？试建 立这个问题的线性规划数学模型。甲乙丙原料成本（元/千克）每月限用量（千克）A 60% 15%2.002000B1.502500C 20% 60% 50%1.001200加工费0.500.400.30售价3.402.852.25解：设 xi, yi, zi 0,i = 1, 2, 3 表示甲、乙、丙中分别含 A、B、C 的含量，构造此问题的 数学规划模型如下：max f (x) = 0.9x1 + 1.4x2 + 1.9x3 + 0.45y1 + 0.95y2 + 1.45y3 0.5z1 + 0.45z2 + 0.95z3x1 + y1 + z1 2000x2 + y2 + z2 2500x3 + y3 + z3 12000.4x1 0.6x2 0.6x3 0123s.t. 0.85y 0.15y 0.15y 00.2x + 0.2x 0.8x 01230.6y1 0.6 y2 + 0.4 y3 00.5z1 + 0.5z2 0.5z3 0xi, yi, zi 0,i = 1, 2, 35.求解下列线性规划问题的对偶问题min f(x) = 2x1 + 2x2 + 4x32x1 + 3x2 + 5x3 2s.t. 3 123（1） x + x + 7x 3x1 + 4x2 + 6x3 5x1 , x2 , x3 0max f (x) = 5x1 + 6x2 + 3x3x1 + 2x2 + 2x3 = 5（2）x1 + 5x2 x3 3s.t. 4x1 + 7x2 + 3x3 8 123x 无约束, x 0, x 0解：（1）由表 3.7 可得该问题的对偶问题为：max g( y) = 2y1 + 3y2 + 5y32y1 + 3y2 + y3 2s.t. 3y123+ y + 4 y 25y1 + 7 y2 + 6 y3 4y1 0, y2 , y3 0（2）该问题的对偶问题为：min g( y) = 5y1 + 3y2 + 8y3y1 3y2 + 4 y3 = 52y1 + 5y2 + 7 y3 6s.t. 2y1 y2 + 3y3 3 123y 无约束, y 0, y 06用对偶单纯形法求解下列线性规划问题：min f(x) = 4x1 +12x2 +18x3x + 3x 3（1） 13s.t. 2x2 + 2x3 5x1 , x2 , x3 0解：（1）首先，将“ ”约束条件两边反号，再加入松弛变量，得：min f (x) = 4x1 +12x2 +18x3 + 0x4 + x5x1 3x3 + x4 = 3235s.t. 2x 2x + x = 5x1 , x2 , x3 , x4 , x5 0CBXBb4x112x218x30x40x50x4-3-10-3100x5-50-2-2014121800建立初始单纯形表如下图所示，所有j 0 。 则对应对偶问题解是可行的，则继续迭代：计算 min 3, 5 = 5 ，所以 x5 为换出变量， = min 6, 9 = 6 ，确定 x2 为换入变量。 继续迭代，得到如下单纯形表：CBXBb4x112x218x30x40x50x4-3-10-3100x2-2.50110-0.540600min 3 = 3, x4换出，min 4，2 = 2，x3换入 。CBXBb4x112x218x30x40x50x31101100x21.51101-0.520026*3T*此时，所有j 0 ，故原问题的最优解为 x = 0,12,最优值为： f(x ) = 36其对偶问题得到最优解为： x* = 2, 6T ，最优值为： f(x* ) = 36 。7.已知线性规划问题min f (x) = 2x1 x2 + x3x1 + x2 + x3 612s.t. x + 2x 4x1 , x2 , x3 0先用单纯形法求出最优解，再分别就下列情况进行分析：（1） 目标函数中变量 x1 , x2 , x3 的系数分别在什么范围内变化，问题的最优解不变；（2） 两个约束条件的右端分别在什么范围内变化，问题的最优解不变。解：将该规划问题化为标准型，引入松弛变量 x4 , x5min f (x) = 2x1 x2 + x3 + 0x4 + 0x5 ,x1 + x2 + x3 + x4 = 6s.t. x + 2x + x = 4125x1 , x2 , x3 , x4 , x5 0用单纯形法求解，如下表：CBXBb2x1-1x21x30x40x5i0x411111060x51.5-1200122-11000x441.5011-0.5-1x22-0.51000.51.50100.5由上表可知，所有的检验数均大于等于零，得最优解:x* = (0, 2, 0, 4, 0)T ,所以原问题的最优解为： x* = (0, 2, 0, )T ，最优值 f(x* ) = 2（1） 变量x1，x2，x3中，x1，x3为非基变量，x2为基变量 。由 = 3 ，当c 3 时，c = c + c 1 ，所以，当c 1 , +), 此时最优解不变。12 12 1112 12由3 = 1，当c3 1时，c3 = c3 + c3 0，所以，当c3 0, +), 此时最优解不变。c2 (3,1) ，最优解不变。综上，当c 1 , +)，c 4, 0，c 0, +), 此时最优解不变。1223（2） b1 的变化范围B1b+ B1 b1 = 4 + 1 0.5 b1 = 4 + 1 b 00200.5 02010 得到： 4 + b1 0 b1 4，则b1的变化范围是b1 2 ，最优解保持不变。B1b+ B1 041=+ 0.5 040.50=+b 2 b2 200.5 b2 20.50得到： 4 b2 8，则b2的变化范围是0,12，最优解保持不变。习题四3.用 Newton 法求解(t) = t3 2t+1用第 1 题求得的区间，按精度 = 0.01 计算。解：(t0 ) = (0) = 1,t1 = t0 + h0 = 1,(t1 ) = 0,1 = 0,因为(t1 ) (t0 )，则h1 = h0 = 2t2 = t1 + 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,(t ) = 1,(t ) = 6, 所以t = 1 1 = 5 5 1 0.01，继续迭代 t =t = 5000，66 606t = t (t0 ) = 49 , 则 t t= 11 0.01, 令t= 49 ，则t 0.8165 ，00(t )60060060t t0= 0.0005 0.01, 所以t*= 0.817,*= (t* ) 0.088 。4.用黄金分割法求解min(t) = t(t+ 2)已知初始单谷区间a，b=-3，5，按精度 = 0.001 计算。解：t1 = 3 + 0.382 8 = 0.056,t2 = 3 + 5 0.056 = 1.944 ，(t1 ) = 0.115136,(t2 ) = 7.667136 ，因为(t1 ) , 继续迭代，因为(t1 ) (t2 ) ，则新的搜索区间为-3，0.056：t1 = 1.832608,(t1 ) = 0.306764,t2 = 1.111392,(t2 ) = 0.987592，t1 t2 , 继续迭代 ，因为(t1 ) (t2 ) ，所以新的搜索区间为-1.832608，0.056：t1 = 1.111292,(t1 ) = 0.987592, t2 = 0.665448,(t2 ) = 0.888075，t1 t2 , 继续 ，(t1 ) (t2 ) ，所以新的搜索区间为-1.832608，-0.665448 ：t1 = 1.386753,(t1 ) = 0.854402,t2 = 1.111392,(t2 ) = 0.987592 ，t1 t2 , 继续 ，因为(t1 ) (t2 ) ，所以新的搜索区间为-1.386753，-0.665448t2 = 0.940987,(t2 ) = 0.996518,t1 = 1.111392,(t1 ) = 0.987592，t1 t2 , 继续 ，因为(t1 ) (t2 ) ，所以新的搜索区间为-1.111392，-0.665448 ：t1 = 0.940987,(t1 ) = 0.996518,t2 = 0.835799,(t2 ) = 0.973038，t1 t2 , 继续 ，因为(t1 ) (t2 ) ，所以新的搜索区间为-1.111392，-0.835799 ：t2 = 0.940987,(t2 ) = 0.996518,t1 = 1.006115,(t1 ) = 0.999962，t1 t2 , 继续 ，因为(t1 ) (t2 ) ，所以新的搜索区间为-1.111392，-0.940987 ：t1 = 1.046295,(t1 ) = 0.997857,t2 = 1.006115,(t2 ) = 0.999962，t1 t2 , 继续 ，因为(t1 ) (t2 ) ，所以新的搜索区间为-1.046295，-0.940987 ：t2 = 0.981215,(t2 ) = 0.999647,t1 = 1.006115,(t1 ) = 0.999962，t1 t2 , 继续 ，因为(t1 ) (t2 ) ，所以新的搜索区间为-1.046295，-0.981215 ：t1 = 1.021434,(t1 ) = 0.999540, t2 = 1.006115,(t2 ) = 0.999962，t1 t2 , 继续 ，因为(t1 ) (t2 ) ，所以新的搜索区间为-1.021434，-0.981215 ：t2 = 0.996579,(t2 ) = 0.999987,t1 = 1.006115,(t1 ) = 0.999962 ，t1 t2 , 继续 ，因为(t1 ) (t2 ) ，所以新的搜索区间为-1.006115，-0.981215 ：t1 = 0.996579,(t1 ) = 0.999987, t2 = 0.990727,(t2 ) = 0.999914，t1 t2 , 继续 ，因为(t1 ) , 继续 ，因为(t1 ) , 继续 ，因为(t1 ) (t2 ) ，所以新的搜索区间为-1.002472，-0.996579 ：t2 = 0.998830,(t2 ) = 0.999998505,t1 = 1.000237,(t1 ) = 1.00000016，t1 t2 , 继续 ，因为(t1 ) (t2 ) ，新的搜索区间为-1.002472，-0.998830t1 = 1.001081,(t1 ) = 0.999999075,t2 = 1.000237,(t2 ) = 1.00000016，因为 t1 t2 , t t0 ,(t ) = 0.063 , 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 (t0 ) = 0.2032新的搜索区间为0.6260，1，t1 = 0.6260,t2 = 1,t0 0.6284，t 0.6276,t0 t gTg1.919883.89760.07348x = x 1 1 g = 0.48089 = 1 12 1 gT Ag 1 0.003 0.15 0.06913f (x2 ) = 0.124872g2 T00同理继续迭代，最后至x = ，此时最优解x = 00，f (x) = 02.用 Newton 法求解22Tmin f (x) = 60 10x1 4x2 + x1解：+ x2-x1x2，初始点x0 = 0，0 ， = 0.01.1 2 2 1g(x) = f (x) = 10 + 2x x , 4 + 2x x T 2 1 2G(x) =13 3 G(x)1 =12 =1=2 3 3 2 1 x = x G(x)1 g(x ) = 0 3 3 10 = 8, 6T1 0 001 2 4 3 3 Tf(x1 ) = 0, 0 ,f(x1 )= 0 0.01最优解为x* = 8, 6T ,f (x* ) = 83.用修正 Newton 法求解22Tmin f (x) = （4 x1 +1）+ （2 x2 1）+ x1 + x2 +10，初始点x0 = 0，0 ， = 0.01.t 980 T解： g(x) = f (x) = 8x1 + 9, 4x2 3x1 = x0 + t0 p0 = 3 0t 410 G(x) = 80，G(x)1 = 8，g(x ) = 9， 3T004 0=1 4 10 9 t 8则 p = G(x)1 g(x ) = 9 9 3= , T ，令 8 0 00 0 1 38 44 x1 = x0 + t0 p0 =