以下为《北航数学规划基础答案最新》的无排版文字预览，完整内容请下载
数学规划基础 部分习题参考解答 刘某某 编 XX航空航天大学数学与系统*** 2018 年 7 月 前言 本习题解答自 2008 年春季开始编写，当时由硕士研究生阎某某提供部分习题解答， 经讨论和确认后，由作者首次录入排版. 后来陆续参加习题解答修订的硕士研究生包括王 浩、欧某某、朱某某、易某某、杨茜和杨某某，其中的数值结果由欧某某提供. 作者在此向 他们的辛勤劳动表示衷心的感谢. 本解答得到了？项目的资助，在此表示感谢. 由于这些参考解答尚未经过特别严格的校对，仅供参考. 任何意见、建议或其它反馈 都可以发送至liuhongying@buaa.edu.cn，在此深表感谢. 刘某某 2018.7 于某某 目录 第一章 引言 1 第二章 线性规划: 基本理论与方法 3 第三章 线性规划：应用及扩展 25 第四章 无约束优化：基础 29 第六章 无约束优化：线搜索法 33 第六章 无约束优化：信赖域法 39 第七章 约束优化：理论 43 第八章 约束优化：线性约束规划 57 第九章 约束优化：非线性约束规划 61 5 第一章 引言 1.2 (该练习的目的是提高你的建模技巧，同时熟悉利用计算机求解线性优化问题) 一个 原油精练场有 8 百万桶原油 A 和 5 百万桶原油 B 用以安排下个月的生产. 可用这些 资源来生产售价为 38 元/桶的汽油，或者生产售价为 33 元/桶的民用燃料油. 有三种 生产过程可供选择，各自的生产参数如下： 输入原油A 输入原油B 输出汽油 输出燃料油 成本(单位：元) 过程1 3 5 4 3 51 过程2 1 1 1 1 11 过程3 5 3 3 4 40 除成本外，所有的量均以桶为单位. 例如，对于第一个过程而言，利用 3 桶原油 A 和 5 桶原油 B 可以生产 4 桶汽油和 3 桶民用燃料油，成本为 51 元. 表格中的成本指总 的成本(即原油成本和生产过程的成本). 将此问题建模成线性规划，其能使管理者极 大化下个月的净利润. 请利用Lingo,Cplex或Matlab在计算机上求解此问题. 解: 设下个月利用第一个过程生产x次, 第二个过程生产y次, 第三个过程生产z次. 则 利润为 f (x, y, z) = (38 × 4 + 33 × 3 − 51)x + (38 + 33 − 11)y + (38 × 3 + 33 × 4 − 40)z = 200x + 60y + 206z 其数学模型为 maximize 200x + 60y + 206z subject to 3x + y + 5z ≤ *** 5x + y + 3z ≤ *** x, y, z ≥ 0, 且 x, y, z 是整数. 忽略掉整性要求后，调用 Matlab 中的 linprog.m 函数求解，得最优解 x = 0, y = 500000, z = ***，自动满足整性要求. 1.4 确定下列 n 元函数的梯度向某某和 Hessian 阵： (a) aT x: a 是常某某； (b) xT Ax: A 是非对称的常某某； (c) 1 2 xT Ax − bT x: A 是对称的常某某，b 是常某某； (d) r(x)T r(x): r(x) = (r1(x), · · · , rm(x))T 是依赖于 x 的 m 维向某某，记 ∇rT 为 AT ， 它一般不是常量. 解: (a) ∇f (x) = a, ∇2f (x) = 0n×n; (b) ∇f (x) = (A + AT )x, ∇2f (x) = A + AT ; 1 2 第一章 引言 (c) ∇f (x) = Ax − b, ∇2f (x) = A; (d) f (x) = ∑m i=1 ri2(x), ∇f (x) = 2 ∑m i=1 ri(x)∇ri(x) = 2A(x)T r(x), ∇2f (x) = = 2 2 ∑m ∑mi=1 i=1 ri(x)∇2ri(x) ri(x)∇2ri(x) + + 2 ∑n i=1 ∇ri (x)(∇ri (x))T 2A(x)T A(x). 1.6 考虑向某某值函数 f (x) : Rn → Rm ，设 f 的每个分量函数 fi(x) 在 x′ 都某某. 写出 f 在 x′ 的Taylor展式，请用 A(x)T 表示 ∇f (x)T (= [∇f1(x), · · · , ∇fm(x)]). 解: 为了具体，考虑 m = 2, n = 3 给出，再表示成一般形式. 此时 ( )( ) f (x) = f1(x) = f1(x1, x2, x3) . f2(x) f2(x1, x2, x3) 因为函数 f1(x) 和 f2(x) 可微，则由多元函数的Taylor展式，有 fi(x) = fi(x′) + ∇fi(x′)T (x − x′) + o(∥x − x′∥), i = 1, 2. 写成向某某形式，即 f (x) = f (x′) + A(x′)(x − x′) + o(∥x − x′∥), (1.1) 这里 o(∥x − x′∥) 表示 f (x) − f (x′) − A(x′)(x − x′) lim x→x′ ∥x − x′∥ = 0. 这里的式(1.1)即为 f 在 x′ 的Taylor展式，其中的矩阵 A(x) 称为雅可比(Jacob)矩阵， 它的第 i 行为 fi(x) 在 x 处的梯度向某某的转置. 1.7 假设在点 x′ 有 g′ 8= 0，证明在所有单位向某某 pT p = 1 中，函数沿方向向某某 p = g′/∥g′∥2 的斜率最大. 称该方向是函数的最速上升(steepest ascent)方向. 证：记 g′ = ∇f (x′) . 因为函数可微，由方向导数与梯度的关系知函数沿方向 p 的方 向导数，即斜率为 pT g′ . 设 θ 为方向向某某 p 与梯度向某某 g′ 的夹角，则由向某某夹角 的定义和 ∥p∥2 = 1 ，有 pT g′ = ∥pT ∥2∥g′∥2 cos θ ≤ ∥pT ∥2∥g′∥2 = ∥g′∥2, 其中等式成立当且仅当 θ = 0 ，即 p 与梯度向某某 g′ 同方向. 又因为 p 为单位向某某，所 以当 p = g′/∥g′∥2 时，函数沿该方向的斜率(也即方向导数)最大. 第二章 线性规划: 基本理论与方法 习题设计说明： 1. 化标准形练习：习题2.1-习题2.3，其中习题2.2和习题2.3是最优化中常用的两种重 新表述技巧，这两种技巧的应用和进一步说明分别见习题2.27和习题7.19. 2. 基本解、基本可行解、退化基本可行解的练习：习题2.4, 习题2.5，习题2.6，习题2.7， 教材第25页的例2.2.3. 3. 习题2.8, 习题2.9、习题2.12(b)是为了理解使用单纯形法时，如何根据单纯形表的 数据判断线性规划何时有惟一解，何时有多解. 如果有多解时，如何得到多个解. 结论是： 最优解不惟一时，某基本可行解的非基变量的相对费用系数非负，并且至少有一个非基 变量的相对费用系数是零. 此外，习题2.30 说明，当原始问题的最优解是对偶非退化的(即 非基变量的既约费用系数严格大于零)，对偶问题有惟一解；否则，对偶问题有多个极点 解，进而有无穷多个解(这些极点解的凸组合都是原始问题的解). 4. 单纯形法的练习：习题2.10，习题2.11，习题2.12，习题2.13，习题2.20(说明单纯形 法的效率的一般性例子中，自变量为三个时所得问题)，习题2.21(说明单纯形法采用最小 相对费用系数进基原则确定进基变量时，如果所求解问题是退化的，则单纯形法会出现 循环！)，习题2.31. 5. 两阶段法的练习：习题2.14-习题2.16；大 M 法的练习：习题2.18. 6. 修正单纯形法的练习：习题2.17，习题；单纯形法的矩阵表示：2.19. 7. 习题2.11，习题2.12(c)，2.32是关于灵敏度分析的练习，这也可以看成是单纯形法 的应用，是难点. 8. 关于对偶性的练习：习题2.22－习题2.36. 2.1 将下面的线性规划问题化成标准形，并求解第 3 个问题(c)： (c) minimize x1 + 4x2 + x3 subject to x1 − 2x2 + x3 = 4 x1 − x3 = 1 x2 ≥ 0, x3 ≥ 0. 解: (c) 由于变量 x1 无限制，可利用约束 x1 = x3 + 1 对其消去. 因此，得其标准形 minimize 4x2 + 2x3 subject to −2x2 + 2x3 = 3 x2 ≥ 0, x3 ≥ 0. 再把约束 2x3 = 3 + 2x2 代入目标函数，得6x2 + 4, 又因为 x2 ≥ 0 ，所以其最小值 为 4，最优解为 x1 = 2.5, x2 = 0, x3 = 1.5 . 3 4 第二章 线性规划: 基本理论与方法 2.2 将下面的问题化成线性规划 minimize |x| + |y| + |z| subject to x + y ≤ 1 2x + z = 3. 方法1: 令 x = u1 − v1, |x| = u1 + v1, u1 ≥ 0, v1 ≥ 0, 类似地表示 y 和 z ，则可将原问题 重新编述为 minimize u1 + u2 + u3 + v1 + v2 + v3 subject to u1 − v1 + u2 − v2 + s = 1, 2u1 − 2v1 + u3 − v3 = 3, ui, vi, s ≥ 0, i = 1, 2, 3. 方法2: 引入非负变量 t1, t2, t3 ，将原问题转化成等价问题 minimize t1 + t2 + t3 subject to x + y ≤ 1, 2x + z = 3, |x| = t1, |y| = t2, |z| = t3. 该问题的最优值与 minimize t1 + t2 + t3 subject to x + y ≤ 1, 2x + z = 3, |x| ≤ t1, |y| ≤ t2, |z| ≤ t3. 的最优值相同，将这个问题的最优解投影到 (x, y, z) 所在的空间可以得到原问题的解. 这个问题可以写成线性规划问题： minimize t1 + t2 + t3 subject to x + y ≤ 1, 2x + z = 3, −t1 ≤ x ≤ t1, −t2 ≤ y ≤ t2, −t3 ≤ z ≤ t3. 2.3 一类逐段线性函数f (x) = max{cT1 x + d1, cT2 x + d2, · · · , cTp x + dp}，其中ci ∈ Rn, di ∈ R, i = 1, · · · , p. 针对这样的函数，考虑问题 minimize f (x) x∈Rn subject to Ax = b x ≥ 0. 将此问题化成线性规划. 5 解: 引入变量 t ，所给问题等价于 minimize t subject to f (x) = t, Ax = b, x ≥ 0. 考虑问题 minimize t subject to f (x) ≤ t, Ax = b, x ≥ 0, 因为该问题关于 t 最小化，故将最优解代入第一个不等式，必有等号成立，即问题的 最优解和最优值与上一个问题的相同. 从而所给问题等价于线性规划问题 minimize t subject to cTi x + di ≤ t, Ax = b, x ≥ 0. i = 1, · · · , p, 2.5 考虑问题 minimize subject to c1x1 + c2x2 + c3x3 x1 + x2 + x3 ≤ 4 x1 ≤ 2 x3 ≤ 3 3x2 + x3 ≤ 6 x1, x2, x3 ≥ 0. 注意系数 c1, c2, c3 尚未确定. 表示成标准形 Ax = b, x ≥ 0 后, 其中 A = 1 1 0 0 1 0 0 3 1 0 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 , x = x1 x2 x3 x4 x5 x6 , b = 4 2 3 6 ; x7 记 A 的第 i 列为 ai . (a) 画出所给问题的可行域(三维空间中). (b) 点 (0, 1, 3, 0, 2, 0, 0)T 是基本可行解吗？ (c) 点 (0, 1, 3, 0, 2, 0, 0)T 是退化基本可行解吗？如果是的话，找出可能的与其对应的 基. 6 第二章 线性规划: 基本理论与方法 解: (a) 略. (b) 是基本可行解，因为满足约束条件，且非零元素对应列 a2, a3, a5 线性无关. (c) 是退化的基本可行解，因为非零元素个数是3，小于系数矩阵 A 的秩4；共有四个 基与该基本可行解对应，他们是 B = [a2 a3 a5 aj] ，其中 j = 1, 4, 6, 7 . 2.8 如果与每个非基变量 xj 对应的既约费用系数 rj > 0 ，证明与其对应的基本可行解是 唯一的最优解. 证明: 不妨设满足条件的基本可行解 x∗ 对应的基 B 为系数矩阵 A 的前 m 列，与其 对应的既约线性规划如下 minimize subject to (∑x1mj==1)cyj1y00j−+∑rmnj=+m1+x1my+11j + xj ··· ≥ + 0 rnxn ... (xm =)ym0 − ∑n j=m+1 ymj xj ≥ 0 (2.1) xm+1 ≥ 0, · · · , xn ≥ 0, 其中rj cT x∗ = > 0, j ∑m j=1 = cj m + 1, · · · , n, y10 ≥ 0, yj0，且x∗是最优解. · · · , ym0 ≥ 0. 由已知，x∗ = (y10, . . . , ym0, 0, . . . , 0)T , 设 x¯ 是另一个最优解，则必有 cT x¯ = cT x∗. 另一方面，将x¯代入(2.1)的目标函数 和约束条件，得 ∑ m ∑n cT x¯ = cjx∗j + rj x¯j (2.2) j=1 j=m+1 和 x¯i = x∗i − ∑n j=m+1 yijx¯j, i = 1, · · · ,m (2.3) 将cT x¯ = cT x∗代入(2.2)，得 ∑n rjx¯j = 0. j=m+1 由于诸 rj > 0 ，且 x¯j ≥ 0 ，由上式，得 x¯j = 0, j = m + 1, . . . , n. 将该事实代入(2.3)， 得x¯i = x∗i , i = 1, · · · , m . 所以x¯ = x∗. 综上，问题的任一最优解均和所给解 x∗ 相同，从而满足条件的基本可行解是问 题的惟一最优解. 2.9 举例说明退化基本可行解不用满足所有 rj ≥ 0 也可以是最优的. 解: 考虑问题 minimize −x1 − x2 x∈R3 subject to x1 + x2 + x3 = 0 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0. 显然可行解只有 x = (0, 0, 0)T ，这也是最优解。但若用单纯形法来求解，例如选取 x3 为基变量,则表格为 a1 a2 a3 b 1 1 10 rT −1 −1 0 0 7 此时非基变量所对应的相对费用系数都是负的，但可见这已经达到最优. 2.10 将下面的问题转化成标准形，用单纯形法求解，然后画出问题在 x1, x2 空间的可行 域，并标明单纯形法的迭代路径. (a) maximize −x1 + x2 subject to x1 − x2 ≤ 2 x1 + x2 ≤ 6 x1 ≥ 0, x2 ≥ 0. 解: (a)引入松驰变量 x3, x4 ，化为标准形 minimize x1 − x2 subject to x1 − x2 + x3 = 2, x1 + x2 + x4 = 6, xi ≥ 0, i = 1, 2, 3, 4. 写出初始表，其已是第一张单纯形表 x1 x2 x3 x4 xB x1 x2 x3 x4 xB x3 1 −1 1 0 2 → x3 2 0 1 1 8 x4 1 1 0 1 6 x2 1 1 0 1 6 cT (rT ) 1 −1 0 0 0 rT 2 0 0 1 6 因为 rj ≥ 0 , 所以最优解 x∗ = (0, 6)T , 最优值 f ∗ = −6 . 从而原问题最优值为6. 2.11 (a) 利用单纯形法求解 maximize 2x1 + 4x2 + x3 + x4 subject to x1 + 3x2 + x4 ≤ 4 2x1 + x2 ≤ 3 x2 + 4x3 + x4 ≤ 3 xi ≥ 0, i = 1, 2, 3, 4. 利用(a)中的求解结果回答以下问题： (b) 为使最优基保持不变，给出 b = (4, 3, 3)T 中第一个元素的可变范围(其它的保持 不变)； (c) 为使最优基保持不变，给出 c = (2, 4, 1, 1)T 中第一个元素的可变范围(其它的保持 不变)；第四个的？ (d) 对于 b 微小的改变，最优解将发生怎样的改变？ (e) 对于 c 微小的改变，最优值将发生怎样的改变？ 解: 将原问题化为标准形，得初始表，并依次演算，得 x1 x2 x3 x4 x5 x6 x7 xB x5 1 3 0 1 1 0 0 4 x6 2 1 0 0 0 1 0 3 x7 0 1 4 1 0 0 1 3 cT (rT ) −2 −4 −1 −1 0 0 0 0 8 第二章 线性规划: 基本理论与方法 x1 x2 x3 x4 x5 x6 x7 xB x5 0 5/2 0 1 1 −1/2 0 5/2 → x1 1 1/2 0 0 0 1/2 0 3/2 x7 0 1 4 1 0 0 1 3 rT 0 −3 −1 −1 0 1 0 3 x1 x2 x3 x4 x5 x6 x7 xB x2 0 1 0 2/5 2/5 −1/5 0 1 → x1 1 0 0 −1/5 −1/5 3/5 0 1 x7 0 0 4 3/5 −2/5 1/5 1 2 rT 0 0 −1 1/5 6/5 2/5 0 6 x1 x2 x3 x4 x5 x6 x7 xB x2 0 1 0 2/5 2/5 −1/5 0 1 → x1 1 0 0 −1/5 −1/5 3/5 0 1 x3 0 0 1 3/20 −1/10 1/20 1/4 1/2 rT 0 0 0 7/2 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 λ(0) = 0 , 则二次规划子问题(9.3)显然无界；从而 SQP 法失败. 这 是由初值选取不当造成的. (b) 若取 λ(0) = 1 , 解二次规划子问题(9.3)得解 s(0) = (−0.5, 0)T , 对应的 Lagrange 乘子 λ(1) = 1 . 于是 x(1) = x(0) + s(0) = (−0.5, 0)T . 第二次迭代有 c(1) = 0.25, a(1) = (−1, −1)T , g(1) = (1, 1)T , [] W (1) = 2 0 . 00 将上述向某某代入二次规划子问题(9.3)后，得 minimize s21 + s1 + s2 subject to 0.25 − s1 − s2 ≤ 0. 解这个二次规划子问题得解 s(1) = (0, 0.25)T , 对应的 Lagrange 乘子 λ(2) = 1 . 于 是 x(2) = x(1) + s(1) = (−0.5, 0.25)T . 即得到问题的解 x∗ 和 Lagrange 乘子 λ∗ . 故从该初始点出发，由基本 SQP 法迭代两次即可得到问题的解. [文章尾部最后500字内容到此结束,中间部分内容请查看底下的图片预览]请点击下方选择您需要的文档下载。
以上为《北航数学规划基础答案最新》的无排版文字预览，完整内容请下载
北航数学规划基础答案最新由用户“LSXSTC”分享发布，转载请注明出处