工程优化 第1章

1、工 程 优 化 方 法任课教师：卢楠联系方式：mathlunan最优化技术与数学模型是工程类研究生应掌握的数学基础课，是从事相应学科理论研究的前提。工程中许多实际问题都可以抽象为数学建模问题，数学模型其中包括最优化模型。了解最优化技术的基本原理、相关算法是分析问题、解决问题的一种技能，同时也是写出高水平学术论文的关键素材。最优化技术与数学模型所包括的知识点很多，选取了一些实用的方法。为什么要学习工程优化 从工程应用的角度出发，注重工程优化的基本思想和方法的阐述。 内容主要包括线性规划、非线性规划、约束优化、无约束优化等，并对如何建立数学模型、如何选择优化方法和提高优化效率作了适当的介绍。课程简

2、介 讲授工程优化的基本理论和方法，要求通过本课程的学习，具有应用工程优化方法解决实际问题的技能，并为以后的学习和工作打好基础。课程任务第一章 绪论第二章 基本概念和理论基础第三章 线性规划第四章 最优化搜索算法结构与一维搜索第五章 无约束最优化方法第六章 约束最优化方法具体内容最优化计算方法陈开周编，西电出版社最优化理论与方法袁亚湘等编，科学出版社最优化理论与算法陈宝林编，清华大学出版社数学规划讲义马仲蓄等编，人大出版社实用线性规划D.M希梅尔布劳著无约束最优化计算方法邓乃杨等编教材及主要参考书目本课程授课方式与考核学科总成绩平时成绩（20）课堂考勤（50）平时作业（50）期末成绩（80）讲授

3、为主，结合习题作业第一章 绪论什么是最优化最优化问题的数学模型与分类最优化问题举例1 什么是最优化 最优化是一个重要的数学分支，是一门应用广泛、实用性很强的学科。简单地说,最优化就是从所有可能的方案中选择最合理的一种以达到最优目标的学科。 达到最优目标的方案称为最优方案。 搜索最优方案的方法称为最优化方法。 这种方法的数学理论称为最优化理论。最优化问题的两大要素可能的方案追求的目标后者是前者的函数.如果第一要素与时间无关就称为静态最优化问题，否则称为动态最优化问题。本课程主要讨论静态最优化问题。最优化就是从所有可能的方案中选择最合理的一种以达到最优目标的学科公元前500年，古希腊在讨论建筑美学

4、中就已发现了长方形长与宽的最佳比例为1.618,称为黄金分割比。其倒数至今在优选法中仍得到广泛应用。在微积分出现以前，已有许多学者开始研究用数学方法解决最优化问题。阿基米德证明：给定周长，圆所包围的面积为最大。这就是欧洲古代城堡几乎都建成圆形的原因。但是最优化方法真正形成为科学方法则在17世纪以后。 历史与现状历史与现状17 世纪，Newton & Leibniz 提出了函数的极值问题；后来出现了Lagrange乘数法；1847年，Cauchy研究了函数值沿什么方向下降最快的问题，提出了最速下降法；1939年，苏联数学家提出解决下料问题和运输问题这两种线性规划问题的求解方法；1947年，Dan

5、tzig 提出解线性规划问题的单纯形法，被称为“20世纪最伟大的创作之一”；1948年，Fritz John 提出最优性条件；1951年，Kuhn和Tucher 提出最优性条件，完成了非线性规划的基础工作；近几十年来，最优化理论和算法发展十分迅速，应用也越来越广泛，已成为一个相当庞大的研究领域；狭义上主要指非线性规划问题的相关内容；广义上则涵盖：线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规划甚至还包括变分、最优控制等等。历史与现状 最优化的研究一般被分成两个方面：由实际生产或科技问题形成最优化的数学模型.对所形成的最优化数学模型进行数学加工和求解。对于第二方面的工作，

6、目前已有一些较系统成熟的资料第一方面工作即如何由实际问题抽象出数学模型，目前很少有系统的资料，而这一工作在应用最优化技术解决实际问题时是十分关键的。 因此，我们在学习本课程时要尽可能了解如何由实际问题形成最优化的数学模型。数学模型: 对现实事物或问题的数学抽象或描述。 过于简单的数学模型所得到的结果可能不符合实际情况；而过于详细复杂的模型又给分析计算带来困难。 具体建立怎样的数学模型需要丰富的经验和熟练的技巧。 2 最优化问题的数学模型与分类 建立数学模型时要尽可能简单，而且要能完整地描述所研究的系统。数学模型的建立 一般的模型简化工作包括以下几类： （1）将离散变量转化为连续变量。 （2）将

7、非线性函数线性化。 （3）删除一些非主要约束条件。 数学模型的建立 在建立了问题的数学模型之后，通常也必须对模型进行必要的数学简化以便于分析、计算。优化模型的一般形式其中： 为决策变量 为已知参数 为随机因素 为（一般或广义）函数在 的约束下求决策变量 ，使函数 达到极小min；若求极大max，相当于一个min（-f）。建立最优化问题数学模型的三要素： 决策变量和参数 决策变量是由数学模型的解确定的未知数。参数表示系统的控制变量，有确定性的也有随机性的。 约束或限制条件 由于现实系统的客观物质条件限制，模型必须包括把决策变量限制在它们可行值之内的约束条件，而这通常是用约束的数学函数形式来表示的

8、。 目标函数 其作为系统决策变量的一个数学函数来衡量系统的效率，即系统追求的目标。根据问题的不同特点分类无约束最优化问题约束最优化问题 等式约束优化问题不等式约束优化问题优化模型的分类标准形式1）2） 一般的约束优化问题优化模型的分类根据函数类型分类线性规划：目标函数、约束条件都是线性的二次规划：目标函数为二次函数，约束条件 中的函数为线性的。非线性规划：目标函数不是一次或者二次的， 或约束条件中的函数不全是线 性的。根据函数性质分类动态与静态随机与确定单目标与多目标优化模型的分类解法的分类解析方法:利用函数的分析性质去构造迭代 公式，使之收敛到极值点。直接方法：按一定的数学原理，用尽量少的

9、计算量，直接比较函数值的大小。优化模型的分类最优化方法解决问题的工作步骤1 ）提出问题：目标、约束、决策变量、参数2 ）建立模型：变量、参数、目标之间的关系表示3 ）模型求解：数学方法及其他方法4 ）解的检验：制定检验准则、讨论与现实的一致性5 ）灵敏性分析：参数扰动对解的影响情况6 ）解的实施：回到实践中7 ）后评估：考察问题是否得到完满解决3 最优化问题举例 最优化在物质运输、自动控制、机械设计、采矿冶金、经济管理等科学技术各领域中有广泛应用。下面举几个简单的实例。 例1. 把半径为1的实心金属球熔化后，铸成一个实心圆柱体，问圆柱体取什么尺寸才能使它的表面积最小？ 解：决定圆柱体表面积大小

10、有两个决策变量：圆柱体底面半径r、高h。 问题的约束条件是所铸圆柱体重量与球重相等。即 即：问题追求的目标是圆柱体表面积最小。即 min 则得原问题的数学模型： 利用在高等数学中所学的Lagrange乘子法可求解本问题分别对r, h,求偏导数,并令其等于零.有:所以，圆柱体的表面积为：例2:多参数曲线拟合问题 已知两个物理量x和y之间的依赖关系为: 其中 为待定参数,为确定这些参数, 对x.y测得m个实验点:试将确定参数的问题表示成最优化问题.解:很显然对参数 和 任意给定的一组数值,就由上式确定了 y关于x的一个函数关系式,在几何上它对应一条曲线,这条曲线不一定通过那m个测量点,而要产生“偏

11、差”.将测量点沿垂线方向到曲线的距离的平方和作为这种“偏差”的度量.即显然偏差S越小,曲线就拟合得越好,说明参数值就选择得越好，从而我们的问题就转化为5维无约束最优化问题。即：例3：有一旅行团从 出发要遍游城市 ，已知从 到 的旅费为 ，问应如何安排行程使总费用最小？模型：变量是否从i第个城市到第j个城市约束每个城市只能到达一次、离开一次 目标总费用最小线性函数又称一次函数，一般表达式为y=cTx+bx=0或1等价与x(x-1)=0,显然不是线性函数 例4：靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为200万m3的支流。两化工厂每天排放某种有害

12、物质的工业污水分别为2万m3和1.4万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的费用最小.工厂1工厂2200万m3500万m3变量：x1、x2分别代表工厂1和工厂2处理污水的数量(万m3)。则目标函数：min z=1000 x1+800 x2约束条件：第一段河流（工厂1工厂2之间）： (2x1)/500 0.2%第二段河流： 0.8(2x1) +(1.4x2)/700

13、0.2%此外有： x12； x21.4化简有： min z=1000 x1+800 x2 x1 1 0.8x1 + x2 1.6 x1 2 x2 1.4 x1、x2 0配料每磅配料中的营养含量钙蛋白质纤维每磅成本（元）石灰石谷物大豆粉0.380 0.00 0.000.001 0.09 0.020.002 0.50 0.08 0.0164 0.0463 0.1250例5：（混合饲料配合）以最低成本确定满足动物所需营养的最优混合饲料。设每天需要混合饲料的批量为100磅，这份饲料必须含：至少0.8%而不超过1.2%的钙;至少22%的蛋白质;至多5%的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分为： 解:根据前面介绍的建模要素得出此问题的数学模型如下:设 是生产100磅混合饲料所须的石灰石、谷物、大豆粉的量（磅）。 可行集：定义1: 若 使得 ，恒有 称 为问题（p）的最优解或者全局极小点。4 最优解与极值点 定义2:若 ，使得 ， 恒有 ，称 为问题（p）的严格全局 极小点。定义3:若 ， 使得 ，恒有 称 为问题（p）的局部极小点。定义4:若 ， ，恒有 称 为问题（p）的严格局部极小点。严格局部极小点严格全局极小点局部极小点 严格全局极小点 全局极小点 非严格全局极小点极小点 严格局部极小点 局部极小点 非严格