[最优化计算课件]概论.pptx

参考书 NumericalOptimization 1 JorgeNocedalandStephenJ Wright 教材 最优化计算方法 蒋金山等编 最优化方法 第二版施光燕等编 数值最优化 李董辉等编 min s t 0 E 0 I 最优化问题的三要素 决策变量目标函数约束条件 Mathematicallyspeaking optimizationistheminimizationormaximizationofafunctionsubjecttoconstraintsonitsvariables 最优化问题的分类 连续最优化 离散最优化单目标优化 多目标优化无约束优化 约束优化静态最优化 动态最优化 第一章线性规划的数学模型和基本性质 问题一 运输问题某公司有6个建筑工地要开工 每个工地的位置 用平面坐标x y表示 距离单位 km 及水泥日用量d t 由表1给出 目前有两个临时料场位于A 5 1 B 2 7 日储量各有20t 假设从料场到工地之间均有直线道路相连 试制定每天的供应计划 即从A B两个料场分别向各工地运送多少吨水泥 使总的吨公里数最小 表1工地的位置 x y 及水泥日用量d 问题归结为以 为决策变量的线性规划模型min 12 16 2 2 12 1 2 6 16 20 1 2 0 1 2 6 1 2 问题二 选课方案又到了新学期的选课时间 正在上大学三年级的小刚为选什么课拿不定主意 由于已经到了高年级 小刚在这个学期必须要选修的课程 必修课 只有一门 2个学分 但可以供他选修的限定选修课 限选课 有8门 任意选修课程 任选课 有10门 由于有些课程之间相互关联 所以可能在选修某门课程时必须同时选修其他某门课程 小刚已经搜集到了这18门课程的学分数和要求同时选修课程的相应信息见表2 表2 按照学校规定 学生每个学期选修的总学分数不能少于20学分 因此小刚必须在上述18门课程中至少选修18个学分 学校还规定学生每学期选修任选课的比例不能少于所修总学分数 包括2个必修学分 的1 6 也不能超过所修总学分数的1 3 问 为了达到学校的要求 小刚这学期最少应该选几门课 应该选哪几门课 试建立模型 用matlab求解模型 模型 min 118 1 5 1 5 2 4 3 4 4 3 5 3 6 3 7 2 8 2 3 9 3 10 3 11 2 12 2 13 2 14 15 16 17 18 1 2 2 20 6 2 3 2 1 5 2 7 8 9 6 10 4 11 5 12 7 13 6 14 0 1 问题三 压缩感知假设原始信号 图1 是长度为n 300的稀疏信号 0 其稀疏性是指向量中非零元素的个数 记为 0 0 这里 0 0 15 人们希望仅通过测量较少的观测数据y m 100 图2 就能从中恢复出原始信号 0来 这便是压缩感知的含义 假定观测数据y是这样获取的 令A 为从n维离散余弦变换矩阵 中随机抽取的m行 将 0用线性变化A编码得到压缩信号y A 0 数m被称为采样值 问 在已知A的前提下能否利用y A 0将稀疏信号 0恢复 图1原始信号 0图2观测数据y 数学模型 min 0 标准型线性规划minz s t 0 线性规划的数学模型 max min z c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 图解法用图解法求下列问题maxz 2x1 3x21x1 2x2 8 4x1 16 s t 4x2 12 x1 x2 0 解 1 建立x1 x2坐标 2 约束条件的几何表示 3 目标函数的几何表示 o 4 3 首先取z 0 然后 使z逐渐增大 直至找到最优解所对应的点 可见 在Q2点z取到最大值 因此 Q2点所对应的解为最优解 Q2点坐标为 4 2 即 x1 4 x2 2 由此求得最优解 x1 4x2 2最大值 maxz z 2x1 3x2 14 元 4 3 讨论 1 唯一最优解maxz z 时 解唯一 如上例 2 无穷多最优解对上例 若目标函数z 2x1 4x2 此时表示目标函数的直线与表示条件 的直线平行 最优点在线段Q3Q2上 即存在无穷多最优解 3 无界解maxz 2x1 3x24x1 16s t x1 x2 0则x2 z 即存在无界解 在实际问题中 可能是缺少约束条件 4 无可行解maxz 2x1 3x22x1 4x2 8s t x1 x2 1x1 x2 0无公共部分 无可行域 即无可行解 在实际问题中 可能是关系错 标准型的化法 1 mam min maxz min z min z maxz 令z z则minz 2 不等式 对于 情况 在 左边加上一个松弛变量 非负 变为等式 对于 情况 在 左边减去一个剩余变量 非负 变为等式 注意 松弛变量 剩余变量在目标函数中的价值系数为0 3 无约束变量令xk xk xk xk xk 0 代入即可 例 将下述问题化为标准型maxz x1 2x2 3x3x1 x2 x3 7 s t x1 x2 x3 2 3x1 x2 2x3 5 x1 x2 0 x3无约束 解 令x3 x3 x3 x3 x3 0 式加上一个松弛变量x4 式减去一个剩余变量x5 令z z minz x1 2x2 3 x3 x3 0 x4 0 x5x1 x2 x3 x3 x4 7s t x1 x2 x3 x3 x5 2 3x1 x2 2 x3 x3 5x1 x2 x3 x3 x4 x5 0 线性规划解的概念 A为m n矩阵 n m Rank A m A为行满秩矩阵 18 1 可行解 满足条件 的x 2 最优解 满足条件 的可行解 3 基 取B为A中的m m子矩阵 Rank B m 则称B为线性规划问题的一个基矩阵 取B A1 A2 Am 其中Aj a1j a2j amj T则称x1 x2 xm为基变量 其它为非基变量 4 基本解 取B A1 A2 Am a11 a1mx1a1m 1 a1nxm 1b1 am1 ammxmamm 1 amnxnbm 基基变量非基非基变量令xm 1 xn 0 非基变量为0 则BXB b 5 基本可行解满足 式要求的基本解 如右图所示 各边交点O Q1 Q2 Q3 Q4均为基可行解 而其延长线的交点Q5为基本解 但不是基本可行解 O 0 0 Q1 4 0 Q2 4 2 Q4 0 3 Q3 2 3 Q5 4 3 6 可行基基本可行解对应的B为可行基 线性规划问题的几何意义基本概念1 凸集 设K为Rn n维欧式空间 的一点集 X 1 K X 2 K 若 X 1 1 X 2 K 则称K为凸集 0 1 2 顶点 X K X 1 K X 2 K 任意两点 若X不能用 X 1 1 X 2 表示 则称X为K的一个顶点 0 1 注 顶点所对应的解是基可行解 3 凸组合 设X i Rn 若存在0 i 1 i 1 2 k 使 则称X为X i i 1 2 k 的凸组合 基本定理定理1若线性规划存在可行域 则 可行域D X Rn AX b X 0 为