最优化计算方法(工程优化)第1章

工程优化方法任课教师：杨国平数学与统计学院联系方式：[e-mail]•最优化技术与数学模型是工程类研究生应掌握的数学基础课，是从事相应学科理论研究的前提。•工程中许多实际问题都可以抽象为数学建模问题，数学模型包括最优化模型。了解最优化技术的基本原理、相关算法是分析问题、解决问题的一种技能，同时也是写出高水平学术论文的关键素材。•最优化技术与数学模型所包括的知识点很多，选取了一些实用的方法。为什么要学习工程优化从工程应用的角度出发，注重工程优化的基本思想和方法的阐述。内容主要包括:线性规划、非线性规划、约束优化、无约束优化等，并对如何建立数学模型、如何选择优化方法和提高优化效率作了适当的介绍。课程简介讲授工程优化的基本理论和方法，要求通过本课程的学习，具有应用工程优化方法解决实际问题的技能，并为以后的学习和工作打好基础。课程任务•第一章绪论•第二章基本概念和理论基础•第三章线性规划•第四章最优化搜索算法结构与一维搜索•第五章无约束最优化方法•第六章约束最优化方法具体内容《最优化计算方法》陈开周编，西电出版社《最优化理论与方法》袁亚湘等编，科学出版社《最优化理论与算法》陈宝林编，清华大学出版社《数学规划讲义》马仲蓄等编，人大出版社《实用线性规划》D.M希梅尔布劳著《无约束最优化计算方法》邓乃杨等编教材及主要参考书目学科总成绩平时成绩（=20％）课堂考勤（50％）平时作业（50％）期末成绩（=80％）讲授为主，结合习题作业本课程授课方式与考核作业以章为单位，本章结束后交作业，部分作业会在课堂上讲评•什么是最优化•最优化问题的数学模型与分类•最优化问题举例第1章绪论最优化是一个重要的数学分支，是一门应用广泛、实用性很强的学科。简单地说,最优化就是从所有可能的方案中选择最合理的一种以达到最优目标的学科。达到最优目标的方案称为最优方案。搜索最优方案的方法称为最优化方法。这种方法的数学理论称为最优化理论。什么是最优化可能的方案追求的目标后者是前者的函数.如果第一要素与时间无关就称为静态最优化问题，否则称为动态最优化问题。本课程主要讨论静态最优化问题。最优化就是从所有可能的方案中选择最合理的一种以达到最优目标的学科最优化问题的两大要素•公元前500年，古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为1.618,称为黄金分割比。其倒数至今在优选法中仍得到广泛应用。•在微积分出现以前，已有许多学者开始研究用数学方法解决最优化问题。阿基米德证明：给定周长，圆所包围的面积为最大。这就是欧洲古代城堡几乎都建成圆形的原因。但是最优化方法真正形成为科学方法则在17世纪以后。历史与现状历史与现状•17世纪，Newton&Leibniz提出了函数的极值问题；后来出现了Lagrange乘数法；•1847年，Cauchy研究了函数值沿什么方向下降最快的问题，提出了最速下降法；•1939年，苏联数学家提出解决下料问题和运输问题这两种线性规划问题的求解方法；•1947年，Dantzig提出解线性规划问题的单纯形法，被称为“20世纪最伟大的创作之一”；•1948年，FritzJohn提出最优性条件；•1951年，Kuhn和Tucher提出最优性条件，完成了非线性规划的基础工作；•近几十年来，最优化理论和算法发展十分迅速，应用也越来越广泛，已成为一个相当庞大的研究领域；•狭义上主要指非线性规划问题的相关内容；•广义上则涵盖：线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规划甚至还包括变分、最优控制等等。历史与现状最优化的研究一般被分成两个方面：由实际生产或科技问题形成最优化的数学模型.对所形成的最优化数学模型进行数学加工和求解。对于第二方面的工作，目前已有一些较系统成熟的资料第一方面工作即如何由实际问题抽象出数学模型，目前很少有系统的资料，而这一工作在应用最优化技术解决实际问题时是十分关键的。因此，我们在学习本课程时要尽可能了解如何由实际问题形成最优化的数学模型。数学模型:对现实事物或问题的数学抽象或描述。过于简单的数学模型所得到的结果可能不符合实际情况；而过于详细复杂的模型又给分析计算带来困难。具体建立怎样的数学模型需要丰富的经验和熟练的技巧。最优化问题的数学模型与分类建立数学模型时要尽可能简单，而且要能完整地描述所研究的系统。数学模型的建立一般的模型简化工作包括以下几类：（1）将离散变量转化为连续变量。（2）将非线性函数线性化。（3）删除一些非主要约束条件。在建立了问题的数学模型之后，通常也必须对模型进行必要的数学简化以便于分析、计算。最优化问题的数学模型与分类数学模型的建立其中：为决策变量为已知参数为随机因素为（一般或广义）函数min,,..,,(,)0,1,2,,ijklijkfxystgxylm在的约束下求决策变量x，使函数达到极小min；若求极大max，相当于一个min（-f）。优化模型的一般形式ixjyk,lfg,,(,)0lijkgxy,,ijkfxy决策变量和参数决策变量是由数学模型的解确定的未知数。参数表示系统的控制变量，有确定性的也有随机性的。约束或限制条件由于现实系统的客观物质条件限制，模型必须包括把决策变量限制在它们可行值之内的约束条件，而这通常是用约束的数学函数形式来表示的。目标函数其作为系统决策变量的一个数学函数来衡量系统的效率，即系统追求的目标。建立优化模型的三要素无约束最优化问题约束最优化问题•等式约束优化问题•不等式约束优化问题优化模型的分类minnxRfxmin..0nxRifxsthxmin..01,2,,nxRifxstgxim根据问题的不同特点分类标准形式1）2）-00iigxgx0-00iiihxhxhx优化模型的分类根据问题的不同特点分类一般的约束优化问题min..0,1,2,,nxRifxstgxim线性规划：目标函数、约束条件都是线性的非线性规划：目标函数、约束条件中的函数不全是线性的。二次规划：目标函数为二次函数，约束条件中的函数为线性的。根据函数性质分类动态与静态随机与确定单目标与多目标优化模型的分类根据函数类型分类解析方法:利用函数的分析性质去构造迭代公式，使之收敛到极值点。直接方法：按一定的数学原理，用尽量少的计算量，直接比较函数值的大小。优化模型的分类解法的分类1)提出问题：目标、约束、决策变量、参数2)建立模型：变量、参数、目标之间的关系表示3)模型求解：数学方法及其他方法4)解的检验：制定检验准则、讨论与现实的一致性5)灵敏性分析：参数扰动对解的影响情况6)解的实施：回到实践中7)后评估：考察问题是否得到完满解决最优化方法解决问题的工作步骤最优化问题举例最优化在物质运输、自动控制、机械设计、采矿冶金、经济管理等科学技术各领域中有广泛应用。下面举几个简单的实例。例1：把半径为1的实心金属球熔化后，铸成一个实心圆柱体，问圆柱体取什么尺寸才能使它的表面积最小？解：决定圆柱体表面积大小有两个决策变量：圆柱体底面半径r、高h。问题的约束条件是所铸圆柱体重量与球重相等。即2343rhR即：问题追求的目标是圆柱体表面积最小，即min则得原问题的数学模型：利用在高等数学中所学的Lagrange乘子法可求解本问题分别对r,h,λ求偏导数,并令其等于零.有:0342hr24,3rh222rhr22min224..03rhrstrh224,,223Lrhrhrrh最优化问题举例所以，圆柱体的表面积为：222420202403LhrrhrLrrhrhLrh32/3r322/3h23263S最优化问题举例例2:多参数曲线拟合问题已知两个物理量x和y之间的依赖关系为:其中为待定参数,为确定这些参数,对x,y测得m个实验点:试将确定参数的问题表示成最优化问题。214351ln1expayaxaaa12345,,,,aaaaa1,12,2,,,mmxyxyxy最优化问题举例解:很显然对参数任意给定的一组数值,就由上式确定了y关于x的一个函数关系式,在几何上它对应一条曲线,这条曲线不一定通过那m个测量点,而要产生“偏差”.xy12345,,,,aaaaa22114351ln1expmiiiaSyaxaaa显然偏差S越小,曲线就拟合得越好,说明参数值就选择得越好，从而我们的问题就转化为5维无约束最优化问题。即：将测量点沿垂线方向到曲线的距离的平方和作为这种“偏差”的度量.即最优化问题举例2211435min1ln1expmiiiayaxaaa最优化问题举例例3：有一旅行团从出发要遍游城市，已知从到的旅费为，问应如何安排行程使总费用最小？0v12,,...,nvvvjvivijc模型：变量—是否从i第个城市到第j个城市约束—每个城市只能到达一次、离开一次1,0;ijx001;0,1,...,1;0,1,...nnijijjixinxjn最优化问题举例目标—总费用最小00nnijijijcx0000min1;1,2,...,..1;1,2,...,1,0,1,2,...,,1,2,...,nnijijijnijjnijiijcxxinstxjnxinjn线性函数又称一次函数，一般表达式为y=cTx+bx=0或1等价与x(x-1)=0,显然不是线性函数最优化问题举例例4：靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为200万m3的支流。两化工厂每天排放某种有害物质的工业污水分别为2万m3和1.4万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的费用最小.工厂1工厂2200万m3500万m3最优化问题举例变量：x1、x2----分别代表工厂1和工厂2处理污水的数量(万m3)则目标函数：minz=1000x1+800x2约束条件：化简有：第一段河流（工厂1----工厂2之间）：(2-x1)/500≤0.2%第二段河流：[0.8(2-x1)+(1.4-x2)]/700≤0.2%此外有：x1≤2；x2≤1.4minz=1000x1+800x2s.t.x1≥10.8x1+x2≥1.6x1≤2x2≤1.4x1、x2≥0最优化问题举例配料每磅配料中的营养含量钙蛋白质纤维每磅成本（元）石灰石谷物大豆粉0.3800.000.000.0010.090.020.0020.500.080.01640.04630.1250例5：（混合饲料配合）以最低成本确定满足动物所需营养的最优混合饲料。设每天需要混合饲料的批量为100磅，这份饲料必须含：至少0.8%而不超过1.2%的钙;至少22%的蛋白质;至多5%的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分为：最优化问题举例解:根据前面介绍的建模要素得出此问题的数学模型如下:设是生产100磅混合饲料所须的石灰石、谷物、大豆粉的量（磅），123,,xxx1231231231232323123min0.01640.04630.1250..1000.3800.0010.0020.0121000.3800.0010.0020.0