最优化问题总论.ppt

济南大学控制科学与工程学院 最优化方法 最优化方法 济南大学控制科学与工程学院 授课教师：李实 cse_lis@ujn.edu.cn 1教1007室 课程结构 * 章节序号 章节名称 章节主要内容 第一章 最优化总论 最优化概念，图解法，下降迭代解法 第二章 数学基础 二次型、梯度、Hessian矩阵、泰勒展开、极值条件 第三章 线性规划 单纯形法、大M法、对偶单纯形法 第四章 无约束最优化方法 一维极值问题、最速下降法、牛顿法、拟牛顿法、共轭梯度法、信赖域法 第五章 约束最优化方法 可行方向法、惩罚函数法、序列二次规划法 第六章 遗传算法 教材与参考资料 教材： “最优化方法”，施光燕，钱伟懿，庞丽萍，高等教育出版社，第二版，2007-08 参考书目： “工程最优化设计”，李元科，清华大学出版社，第一版，2006-08 “最优化方法及其应用”，郭科，高等教育出版社，第一版，2007-07 “精通MATLAB最优化计算”，龚纯，王正林，电子工业出版社，2009-04. * 考核方式 17周考试 考试70%+平时30%（作业+点名） 课堂要求： 将课件下载打印，上课记好笔记，尤其是习题课。 遵守课堂纪律，聊天的同学请上台讲 * 第一章 最优化问题总论 1.1 引言 1.2 最优化设计举例 1.3 最优化问题的数学模型 1.4 最优化问题的图解法 1.5 最优化问题的下降迭代解法 1.6 最优化算法分类 1.7 MATLAB优化工具箱介绍 * 1.1 引言 最优化方法：从所有可能的方案中，选择出最合理的，达到最优目标的方案，搜寻最优方案的方法就是最优化方法。 工程设计：如何选择参数，使设计满足要求又能降低成本。 资源分配：满足各方面的基本要求，获得好的经济效益。 生产计划：提高产值，提高利润。 原料配比：选择何种成分比例，提高质量、降低成本。 城建规划：如何安排工厂、学校、医院、商店、住宅的合理布局。 最优化研究的是求解最优化问题的理论和方法，它是当前计算数学和运筹学领域中的一个十分活跃的分支。随着电子计算机的普及，最优化方法已广泛应用于化工、航空、机械、建筑、无线电技术等许多工程技术部门．另外，在生产组织、资源分配等管理科学方面，在现代军事指挥系统中，最优化方法也成为一种重要的决策手段．因此，最优化是一门应用广泛、实用性很强的交叉学科。 * 最优化的发展历程 早在十七世纪，费马，1638；牛顿，1670， 就已提出了函数的极值问题． 在1847年，法国数学家Cauchy对无约束最优化问题提出了最速下降法，而对约束极值的求解，则出现了Lagrange乘子法． 但是，在上世纪三十年代以前，这个古老的课题并未取得实质性的进展．由于近几十年来，生产和科学研究的迅猛发展以及电子计算机的广泛应用，不仅使求解最优化问题成为一种迫切需要，而且也有了求解这一问题的强有力的工具．因此，最优化的理论和方法得以迅速发展，并不断完善，逐步形成了一门系统的学科．迄今为止，在这个学科中已出现了线性规划、整数规划、非线性规划、几何规划、动态规划、不可微规划、网络流等许多分支. 本课程主要介绍线性规划和非线性规划（包括无约束和有约束）的基本方法，它是最优化理论的最基本部分． * 1.2最优化设计举例 [例1.1] 用一块边长为3米的正方形薄板，在四角各裁去一个大小相同的方块，做成一个无盖的箱子。试确定如何裁剪可以使做成的箱子具有最大的容积。 * 解：设裁去的边长为x，则做成的箱子容积为： 可将问题转化为求函数f(x)最大值的数学问题。X为变量，函数f(x)为目标函数。由于目标函数为非线性函数，无约束条件，此类问题称为非线性无约束最优化问题。 根据函数的极值条件，令 最优解： [例1.2] 某工厂生产甲、乙两种产品，生产每种产品所需的材料、工时、用电量和可以获得的利润，以及每天能够提供的材料、工时、用电量见表，试确定该厂两种产品每天的生产计划，以使得每天获得的利润最大。 这是一个简单的生产计划问题，可以归结为在满足各项生产条件下，合理安排每天的甲乙产品生产量，以使利润最大化的最优化设计问题。 * 产品 材料 kg 工时 h 用电量 kWh 利润 元 甲 9 3 4 60 乙 4 10 5 120 供应量 360 300 200 设每天生产甲x1件，乙x2件。每天获得的利润： * 产品 材料 kg 工时 h 用电量 kWh 利润 元 甲 9 3 4 60 乙 4 10 5 120 供应量 360 300 200 满足条件 材料约束 工时约束 电能约束 变量非负约束 目标函数 由于目标函数和约束函数都是线性的，所以该类问题成为线性最优化问题，也叫线性规划，无法用高等数学的极值条件直接求解。 [例1.3] 某单位拟建一排四间的停