工程优化方法及应用第一章(2学时).ppt

工程优化方法及应用 u最优化是一个重要的数学分支，它所研究的问题是：讨论在众多的方案中什么样 的方案最优，以及怎样找出最优方案。 l工程设计中怎样选择设计参数，使得设计方案既满足设计要求 又能降低成本； l资源分配中，怎样分配资源，使得分配方案既能满足各方面的 基本要求，又能获得好的经济效益； l城建规划中，怎样安排工厂、机关、学校、商店、医院、住户 和其他单位的合理布局，才能方便群众； l军事指挥中，怎样确定最佳作战方案，才能有效地消灭敌人， 保存自己，有利于战争的全局胜利等等。 u 最优化理论与方法具有重要的理论意义和应用价值。 课程简介课程简介 uu第一章第一章 绪论绪论(2(2学时学时) ) 最优化的发展历程、举例、模型 uu第二章第二章 预备知识预备知识(6(6学时学时) ) 代数基础、数学分析基础、凸分析基础 uu第三章第三章 常用的一维搜索方法常用的一维搜索方法(8(8学时学时) ) 精确和不精确一维搜索：进退法、黄金分割法、插值法、二分 法、牛顿法、不精确搜索 uu第四章第四章 无约束最优化方法无约束最优化方法(14(14学时学时) ) 最速下降法、牛顿法、共轭梯度法、变尺度法、最小二乘法 uu第五章第五章 线性规划线性规划(10(10学时学时) ) 图解法、单纯形法、对偶理论、对偶单纯形法 uu第六章第六章 约束最优化方法约束最优化方法(8(8学时学时) ) 最优性条件、内外罚函数法、乘子法、可行方向法 授课方式与考核 u讲授：多媒体为主、结合板书 u作业：以章为单位，活页方式，写清姓名、学号、院系专业 u考核：闭卷考试 成绩=平时成绩（20）+期末成绩(80) 基本要求与目标 n熟练掌握优化基本理论和方法，培养科研能力。 n熟练使用优化计算的数学软件（MATLAB优化工具箱， MAPLE，MATHEMARICA等），培养技能技能。 教材与参考书目 教 材：最优化计算方法陈开周编，西电出版社 参考：最优化理论与算法陈宝林编，清华大学出版 参考：最优化理论与方法袁亚湘等编，科学出版社 参考：最优化方法宋巨龙等编，西电出版社 第一章 绪 论 本章主要内容：本章主要内容： 1 最优化的发展历程 2 最优化问题举例 3 最优化问题的数学模型与分类 4 最优化问题的解相关概念 1 最优化的发展历程 u最优化(Optimization)，广义上称为 “运筹学” (Operational Research)，狭义上称为“数学规划” (Mathematical Programming) l最优化是个古老的课题。长期以来，人们对最优化问题进行着深 入的探讨和研究。早在17 世纪，英国数学家Newton l1939年，前苏联数学家提出解决下料问题和运输问题这两种线性 规划问题的求解方法； l1847年，法国数学家 Cauchy 研究了函数值沿什么方向下降最快 的问题，提出了最速下降法； l虽然最优化可以追朔到十分古老的极值问题，然而由于历史条件 的限制，直到20世纪30年代，它并未成为一门独立的学科。 l20世纪40年代以来，随着科学技术的日益发展，很多工程的核心 问题最终都归结为求解一个优化问题；特别是计算机的普及，使得 一些大规模的优化问题的求解可以在一台普通的计算机上实现，最 优化理论和方法迅速发展起来，形成一门独立的学科。 l1947年，Dantzig 提出解线性规划问题的单纯形法。单纯形法的提 出为线性规划的理论和算法奠定了基础，被称为“20世纪最伟大的 创作之一”； l1948年，Fritz John 提出最优性条件； l19501965年，匈牙利数学家Kuhn和Tucher 建立了线性规划的对 偶理论、提出最优性条件 l如今，大数据时代的到来，使得最优化方法得到了比以往任何时 候都更加广泛的应用，最优化方法已经成为工程技术人员所必须具 备的研究工具。 l更重要的是，压缩感知理论的诞生，把优化这一领域推向新的研 究高潮，稀疏优化成为目前研究的热点。 因此，无论继续深造还是工作，学好优化理论和方法具有重要的现 实意义。 l由于优化学科的迅猛发展，至今已经出现线性规划、整数规划、 非线性规划、几何规划、动态规划、随机规划、网络流、多目标规 划等许多分支，最优化的理论和算法正在发挥越来越大的作用。 2 2 最优化问题举例最优化问题举例 u最优化主要是研究在一定限制条件下，选取某种方案以使某目 标达到最优的一门学科，属于数学和运筹学的范畴。 最优方案：使目标达到最优的方案称为最优方案。 最优化方法：获取某种方案的方法称为最优化方法。 最优化理论：这种方法的数学理论称为最优化理论。 u建立最优化模型的三要素：目标函数、决策变量、约束条件。 给一个实际的优化问题，首先得建立优化模型，然后利用优化方 法去求解。 最优化在物质运输、自动控制、机械设计、采矿冶金、经济管 理等科学技术各领域中有广泛应用。下面举几个专业性不强的 实例。 例2.1 把半径为1的实心金属球熔化后，铸成一个实心圆柱体， 问圆柱体取什么尺寸才能使它的表面积最小？ 解：两个决策变量：圆柱体底面半径r、高h 问题的约束条件是所铸圆柱体质量与球质量相等。即 即 问题追求的目标是圆柱体表面积最小。即 则得原问题的数学模型： 利用在高等数学中所学的Lagrange乘子法可求解本问题 此时圆柱体的最小的表面积为: 分别对 r, h, 求偏导数,并令其等于零. 有: 例2.2(多参数曲线拟合问题) 已知两个物理量x和y之间的依赖 关系为: 其中a1，a2，a3，a4和a5为待定参数,为确定这些参数，对x、 y测得m个实验点(x1,y1),(x2,y2), (xm,ym).试将确定参数的问 题表示成最优化问题. 解: 决策变量是参数a1，a2，a3，a4，a5。 显然任意给定的一组数值a1，a2，a3，a4 和a5，就由上式确定了 y关于x的一个函数 关系式,在几何上它对应一条曲线。 曲线不一定通过那m个测量点，而要产生“偏差”，将测量点沿垂 线方向到曲线的距离的平方和作为这种“偏差”的度量. 即 显然偏差S越小,曲线拟合得越好,说明参数值就选择得越好，因此 目标函数是偏差，我们的问题就转化为5维无约束优化问题. 即 例2.3 现有一批某种型号的圆钢长8米，需要截取2.5米长的毛 坯100根，长1.3米的毛坯200根。问如何设计方案才能既满足 需要，又能使总的用料最少？ 解：为了找到一个省料的套裁方案，必须先设计出较好的几 个下料方案。其次要求这些方案的总体能裁下所有各种规格 的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目 的，为此可以设计出4种下料方案以供套裁用。 2.5m3210 1.3m0246 料头0.50.40.30.2 设按方案、下料的原材料根数分别为 xj (j=1,2,3,4), 可列出下面的数学模型： 例2.4 有一旅行团从v0出发要遍游城市 v1,v2,vn，已知从vi到vj的旅费为cij， 问应如何安排行程使总费用最小？ v0 v1 v2 l l 变量变量是否从i第个城市到第j个城市，xij=1,0 l l 约束约束每个城市只能到达一次、离开一次, l l 目标目标总费用最小 解： 例2.5.（混合饲料配合）以最低成本确定满足动物所需营养的 最优混合饲料。设每天需要混合饲料的批量为100磅，这份饲 料必须含：至少达到0.8%而不超过1.2%的钙;至少22%的蛋 白质;至多5%的粗纤维。假定主要配料包括石灰石、谷物、 大豆粉。这些配料的主要营养成分为： 配料每磅含钙每磅含蛋 白质 每磅含 纤维 每磅成本 石灰石0.3800.000.000.0164 谷物0.0010.090.020.0463 大豆粉0.0020.500.080.1250 解: 设 是生产100磅混合饲料所须的石灰石、谷物、大 豆粉的量（磅）。 3 最优化问题的数学模型与分类 l优化模型的共同特点：求满足一定条件（约束条件 ）的变量 （决策变量），使得某函数 （目标函数）取得最大值或最小值。 l分类方式有很多：(I)根据约束类型分类 (II)根据目标函数类型分类 (III)根据变量类型分类 根据约束类型的不同特点分类根据约束类型的不同特点分类 设Rn 为n维欧氏空间， 向量变量实值 函数 gi，hj 均为向量x 的实值函数. 无约束优化问题 以上均是优化模型的标准形式，不标准形式可以转化成标准形式 等式约束 优化问题 不等式约束 优化问题 混合约束优 化问题 如果是求极大值即 ，则可将目标函数乘以(-1)，化为 求极小值问题，即 目标函数的转换：极大变成极小 模型统一化模型统一化 不等式约束的转换：小于等于号变成大于等于号 等式约束的转换：等号变成大于等于号 通过上述模型转化技巧，以上模型均可以统一转化成如下两种通过上述模型转化技巧，以上模型均可以统一转化成如下两种 类型，类型，因此我们只研究这两种模型的解法。因此我们只研究这两种模型的解法。 uu无约束优化问题的标准形式无约束优化问题的标准形式 uu约束优化问题的标准形式约束优化问题的标准形式 线性规划线性规划：目标函数 f(x)和约束函数 gi(x) 皆为线性函数。 非线性规划非线性规划:目标函数 f(x) 和约束函数 gi(x) 不全是线性函数 ; 特别地，如果目标函数为二次函数，约束函数全为线性函数, 则称为二次规划二次规划。 根据目标函数及约束类型的不同特点分类根据目标函数及约束类型的不同特点分类 整数规划：整数规划：变量的各分量只取整数 根据变量的类型分类根据变量的类型分类 混合整数规划：混合整数规划：变量的部分分量只取整数 0-10-1规划：规划：变量的各个分量只取0或1 其他分类其他分类 对于最优化问题一般可作如下分类：对于最优化问题一般可作如下分类： 注意：我们只讲静态规划问题，并且只考虑标准形式。注意：我们只讲静态规划问题，并且只考虑标准形式。 4 最优化问题的解相关概念 可行集,最优值,最优解 定义1：称满足所有约束条件的向量x为容许解或可行解，容许 点的集合称为容许集或可行集。 定义2：在容许集中找一点 x* ，使目标函数 f(x) 在该点取最小值， 即满足： 的过程，即为最优化的求解过程。其 中x*称为问题的（全局）最优点，f(x*)称为最优值，（ x* , f(x*) ） 称为最优解。 考虑约束优化问题考虑约束优化问题 定理定理: : 若 f(x) 和gi(x) 均连续，则 （1）问题(P)的可行集D为闭集； （2）问题(P) 的最优解集合为闭集。 极小点 定义4.3 ：设