数学规划导论和预备知识.ppt

1 数学规划 MathematicalProgramming 主讲教师 孙冠颖办公地点 四教西204电话 88803690电子邮箱 sunguanying 教材 黄红选 韩继业编著 数学规划 清华大学出版社参考书目 1 陈宝林 最优化理论与算法 第2版 清华大学出版社2 袁亚湘 最优化理论与方法 科学出版社3 何坚勇 最优化方法 清华大学出版社4 OperationsResearch MathematicalProgramming ThirdEdition WAYNEL WINSTON 清华大学出版社 2 平时成绩 30 期末成绩 70 考试形式 开卷 3 主要内容 绪论和预备知识 第1章 第2章 线性规划 第3章 第7章 一般线性规划整数规划非线性规划 第4章 第5章 无约束非线性规划约束非线性规划 4 绪论和预备知识 最优化的发展史最优化例子相关数学概念和理论 什么是最优化 生产计划安排中选择怎样的方案才能获得最高的利润 有限的资源如何分配使得既能满足各方面要求并获得最好的经济效益 工程设计中如何选择参数使得既能满足要求又能降低成本 对抗赛时实施更有效的策略 田忌赛马 等等 需解决两方面的问题 什么样的方案最优 如何找出最优方案 数学规划 最优化 正是为解决这些问题提供理论基础和求解方法 它是应用广泛 实用性很强的学科 数学规划的发展史 二战之前 自然科学中的最优化Fermat 1637 Newton 1670 Euler 1755 Lagrange 1797Cauchy 1847最速下降法 Fermat 1637 Newton 1670Euler 1755Lagrange 1797Cauchy 1847最速下降法 二战以后 原苏联数学家康托洛维奇 下料问题和运输问题1939 生产组织与管理中的数学方法 1960 最佳资源利用的经济计算 1975诺贝尔经济学奖美国Dantzig 线性规划1947单纯型算法Kuhn和Tucker 非线性规划1950Kuhn Tucker条件 例1 运输问题 目标 变量 subjectto 受限制于 约束条件是 例2 生产问题 某厂生产两种产品 需要三种资源 已知各产品的利润 各资源的限量和各产品的资源消耗系数如下表 问题 如何安排生产计划 使得获利最多 Model 例3 方程组的求解 解非线性方程组是相当困难的一类问题 由于最优化方法的发展 对解非线性方程组提供了一种有力的手段 解非线性方程组 在方程组有解的情况下 等价于求下列函数的极小值点 非线性最小二乘问题 类似地 对于线性方程组Ax b的求解也可转化为一个最优问题 即求解 线性最小二乘问题 一些成功的事例 最优化人员安排使美国航空公司每年节约2000万美元 优化货运路线让YellowFreight每年的节约超过1730万美元 ReynoldsMetal公司通过改进卡车调度 提高了即时交付率 每年节约货运成本700万美元 GTE本地能力扩张每年节约3000万美元 Proctor Gamble 保洁公司 通过北美运营重构 削减了20 的厂房 每年节约2亿美元 DigitalEquipment通过优化全球供应链节约了3亿美元 优化水热生成器安排让南部公司每年节约1 4亿美元 数学规划的分类 根据问题的不同特点分类无约束极小化问题等式约束极小化问题不等式约束极小化问题一般约束极小化问题根据函数类型的分类线性规划非线性规划二次规划整数规划根据解法的分类解析方法直接方法 无约束最优化问题 最优化术语 可行点 可行解 在数学规划中 满足所有约束条件的点 可行域 可行集 所有可行点组成的集合 最优解 全局极小点 使得目标函数取得最小值的可行解局部最优解 局部极小点 任意全局极小点必为局部极小点 但反过来不成立 然而 对于凸规划而言 局部极小点就是全局极小点 预备知识 多元函数分析 梯度Hesse矩阵Taylor公式极值的判别条件 必要条件 充分条件 方向导数 梯度 几种特殊类型函数的梯度公式 Hesse矩阵 Taylor公式 极值的判别条件 一元函数 设f x 的定义域为区间D x0为內点 f x 在点x0可微 若x0为极值点 则 必要条件 二元函数 设f x y 的定义域为区域D x0 y0 为內点 f x y 在点 x0 y0 可微 若 x0 y0 为极值点 则 多元函数 充分条件 一元函数 设f x 的定义域为区间D x0为內点 f x 在点x0二次可微 1 若 则x0为极小点 2 若 则x0为极大点 若 则 x0 y0 是极值点 当时 x0 y0 是极小点 当时 x0 y0 是极大点 二元函数 设f x y 的定义域为区域D x0 y0 为內点 f x y 在点 x0 y0 二次可微 多元函数 1 x0为D的一个內点 2 f x 在点x0二次可微 3 4 H x0 0 H x0 0 则x0是极小点 极大点 方向导数 偏导数导数 设有单位向量h h1 h2 hn T 表示n维空间中的一个方向 则可微函数f x 在点x沿h的方向导数为 1 函数沿各个方向的变化率2 从各个方向中求出f x 变化最快的方向 亦即变化率最大的方向 对于方向导数 有以下结论 若 则h为f x 在点x的上升方向 若 则h为f x 在点x的下降方向 若