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

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,工 程 优 化 方 法,任课教师：杨国平 数学与统计(tngj)学院联系方式：466298072,第一页，共42页。,最优化技术与数学模型是工程类研究生应掌握的数学基础课，是从事相应学科理论研究的前提。,工程中许多实际问题都可以抽象为数学建模问题，数学模型包括最优化模型。,了解(lioji)最优化技术的基本原理、相关算法是分析问题、解决问题的一种技能，同时也是写出高水平学术论文的关键素材。,最优化技术与数学模型所包括的知识点很多，选取了一些实用的方法。,为什么要学习(xux)工程优化,第二页，共42页。,从工程应用的角度(jiod)出发，注重工程优化的基本思想和方法的阐述。,内容主要包括:,线性规划、非线性规划、约束优化、无约束优化等，,并对如何建立数学模型、如何选择优化方法和提高优化效率作了适当的介绍。,课程(kchng)简介,讲授工程优化的基本理论和方法，要求通过本课程的学习，具有(jyu)应用工程优化方法解决实际问题的技能，并为以后的学习和工作打好基础。,课程任务,第三页，共42页。,第一章 绪论(xln),第二章 基本概念和理论基础,第三章 线性规划,第四章 最优化搜索算法结构与一维搜索,第五章 无约束最优化方法,第六章 约束最优化方法,具体内容,第四页，共42页。,最优化计算方法(fngf)陈开周编，西电出版社,最优化理论与方法(fngf)袁亚湘等编，科学出版社,最优化理论与算法陈宝林编，清华大学出版社,数学规划讲义马仲蓄等编，人大出版社,实用线性规划希梅尔布劳著,无约束最优化计算方法(fngf)邓乃杨等编,教材(jioci)及主要参考书目,第五页，共42页。,学科总成绩,平时成绩,（,=80,）,讲授(jingshu)为主，结合习题作业,本课程授课方式(fngsh)与考核,作业以章为单位，本章结束后交作业，部分作业会在课堂(ktng)上讲评,第六页，共42页。,什么(shn me)是最优化,最优化问题的数学模型与分类,最优化问题举例,第1章 绪论(xln),第七页，共42页。,最优化是一个重要的数学分支，是一门应用广泛、实用性很强的学科。简单地说,最优化就是从所有可能的方案中选择最合理的一种以达到最优目标(mbio)的学科。,达到最优目标(mbio)的方案称为最优方案。,搜索最优方案的方法称为最优化方法。,这种方法的数学理论称为最优化理论。,什么(shn me)是最优化,第八页，共42页。,可能的方案,追求的目标,后者是前者的函数.,如果第一(dy)要素与时间无关就称为静态最优化问题，否则,称为动态最优化问题。,本课程主要讨论静态最优化问题。,最优化就是从所有(suyu)可能的方案中选择最合理的一种以达到最优目标的学科,最优化问题(wnt)的两大要素,第九页，共42页。,公元前500年，古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为1.618,称为黄金分割比。其倒数(do sh)至今在优选法中仍得到广泛应用。,在微积分出现以前，已有许多学者开始研究用数学方法解决最优化问题。阿基米德证明：给定周长，圆所包围的面积为最大。这就是欧洲古代城堡几乎都建成圆形的原因。但是最优化方法真正形成为科学方法则在17世纪以后。,历史(lsh)与现状,第十页，共42页。,历史(lsh)与现状,17 世纪，Newton&Leibniz 提出了函数的极值问题；后来出现了Lagrange乘数法；,1847年，Cauchy研究了函数值沿什么方向下降最快的问题，提出了最速下降法；,1939年，苏联数学家提出解决下料问题和运输问题这两种线性规划问题的求解方法(fngf)；,1947年，Dantzig 提出解线性规划问题的单纯形法，被称为“20世纪最伟大的创作之一”；,第十一页，共42页。,1948年，Fritz John 提出最优性条件；,1951年，Kuhn和Tucher 提出最优性条件，完成了非线性规划的基础工作；,近几十年来，最优化理论和算法发展十分迅速，应用也越来越广泛，已成为一个相当庞大的研究领域(ln y)；,狭义上主要指非线性规划问题的相关内容；,广义上则涵盖：线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规划甚至还包括变分、最优控制等等。,历史(lsh)与现状,第十二页，共42页。,最优化的研究一般被分成两个方面：,由实际生产或科技问题形成最优化的数学模型.,对所形成的最优化数学模型进行数学加工和求解。,对于第二方面的工作，目前已有一些较系统成熟的资料,第一方面工作即如何由实际问题抽象出数学模型，目前很少有系统的资料，而这一工作在应用最优化技术解决(jiju)实际问题时是十分关键的。,第十三页，共42页。,因此，我们在学习本课程时要尽可能了解如何(rh),由实际问题形成最优化的数学模型。,数学(shxu)模型:对现实事物或问题的数学(shxu)抽象或描述。,第十四页，共42页。,过于简单的数学模型所得到的结果可能不符合实际情况；而过于详细复杂的模型又给分析计算(j sun)带来困难。,具体建立怎样的数学模型需要丰富的经验和熟练的技巧。,最优化问题(wnt)的数学模型与分类,建立数学模型时要尽可能简单，而且要能完整地描述所研究(ynji)的系统。,数学模型的建立,第十五页，共42页。,一般的模型简化工作包括以下几类：,（1）将离散变量(binling)转化为连续变量(binling)。,（2）将非线性函数线性化。,（3）删除一些非主要约束条件。,在建立(jinl)了问题的数学模型之后，通常也必须对模型进行必要的数学简化以便于分析、计算。,最优化问题(wnt)的数学模型与分类,数学模型的建立,第十六页，共42页。,其中：为决策变量,为已知参数(cnsh),为随机因素,为（一般或广义）函数,在 的约束下求决策变量(binling)x，使函数 达到极小min；若求极大max，相当于一个min（-f）。,优化模型的一般(ybn)形式,第十七页，共42页。,决策变量和参数(cnsh),决策变量是由数学模型的解确定的未知数。参数(cnsh)表示系统的控制变量，有确定性的也有随机性的。,约束或限制条件,由于现实系统的客观物质条件限制，模型必须包括把决策变量限制在它们可行值之内的约束条件，而这通常是用约束的数学函数形式来表示的。,目标函数,其作为系统决策变量的一个数学函数来衡量系统的效率，即系统追求的目标。,建立(jinl)优化模型的三要素,第十八页，共42页。,无约束(yush)最优化问题,约束(yush)最优化问题,等式约束(yush)优化问题,不等式约束(yush)优化问题,优化模型(mxng)的分类,根据问题的不同特点(tdin)分类,第十九页，共42页。,标准(biozhn)形式,1）,2）,优化模型(mxng)的分类,根据(gnj)问题的不同特点分类,一般的约束优化问题,第二十页，共42页。,线性规划(xin xn u hu)：目标函数、约束条件都是线性的,非线性规划(xin xn u hu)：目标函数、约束条件中的函数不全是线性,的。,二次规划：目标函数为二次函数，约束条件中的函数为线,性的。,根据函数性质分类,动态与静态,随机与确定,单目标与多目标,优化模型(mxng)的分类,根据函数类型(lixng)分类,第二十一页，共42页。,解析方法:利用函数的分析性质去构造迭代公式，使之收敛,到极值(j zh)点。,直接方法：按一定的数学原理，用尽量少的计算量，直接比,较函数值的大小。,优化模型(mxng)的分类,解法(ji f)的分类,第二十二页，共42页。,1)提出问题：目标、约束、决策变量、参数,2)建立模型：变量、参数、目标之间的关系表示,3)模型求解：数学方法及其他方法,4)解的检验：制定检验准则、讨论与现实的一致性,5)灵敏性分析：参数扰动对解的影响情况(qngkung),6)解的实施：回到实践中,7)后评估：考察问题是否得到完满解决,最优化方法(fngf)解决问题的工作步骤,第二十三页，共42页。,最优化问题(wnt)举例,最优化在物质运输、自动控制、机械设计、采矿冶金、经济管理等科学技术各领域中有广泛应用。下面举几个(j)简单的实例。,例1：把半径为1的实心金属球熔化后，铸成一个实心圆柱体，问圆柱体取什么尺寸才能使它的表面积最小？,解：决定圆柱体表面积大小有两个决策变量：圆柱体底面半径r、高h。,问题的约束条件是所铸圆柱体重量与球重相等。即,第二十四页，共42页。,即：,问题追求的目标是圆柱体表面积最小，即,min,则得原问题的数学模型：,利用在高等数学中所学的Lagrange乘子法可求解本问题,分别(fnbi)对r,h,求偏导数,并令其等于零.有:,最优化问题(wnt)举例,第二十五页，共42页。,所以(suy)，圆柱体的表面积为：,最优化问题(wnt)举例,第二十六页，共42页。,例2:多参数曲线拟合问题,已知两个物理量x和y之间的依赖关系为:,其中 为待定参数,为确定这些(zhxi)参数,对x,y,测得m个实验点:,试将确定参数的问题表示成最优化问题。,最优化问题(wnt)举例,第二十七页，共42页。,解:很显然对参数 任意给定的一组数值,就由上式确定了 y关于(guny)x的一个函数关系式,在几何上它对应一条曲线,这条曲线不一定通过那m个测量点,而要产生“偏差”.,显然偏差S越小,曲线就拟合得越好,说明参数值就选择(xunz)得越好，从而我们的问题就转化为5维无约束最优化问题。即：,将测量点沿垂线方向到曲线的距离(jl)的,平方和作为这种“偏差”的度量.即,最优化问题举例,第二十八页，共42页。,最优化问题(wnt)举例,第二十九页，共42页。,例3：有一旅行团从 出发要遍游城市(chngsh)，已知从 到 的旅费为 ，问应如何安排行程使总费用最小？,模型(mxng)：,变量(binling)是否从i第个城市到第j个城市,约束每个城市只能到达一次、离开一次,最优化问题举例,第三十页，共42页。,目标(mbio)总费用最小,线性函数(hnsh)又称一次函数(hnsh)，一般表达式为y=cTx+b,x=0或1等价与x(x-1)=0,显然不是(b shi)线性函数,最优化问题举例,第三十一页，共42页。,例4：靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为200万m3的支流。两化工厂每天排放(pi fn)某种有害物质的工业污水分别为2万m3和万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的费用最小.,工厂,1,工厂,2,200,万,m,3,500,万,m,3,最优化问题(wnt)举例,第三十二页，共42页。,变量：x1、x2-分别代表工厂(gngchng)1和工厂(gngchng)2处理污水的数量(万m3),则目标(mbio)函数：min z=1000 x1+800 x2,约束条件：,化简有：,第一段河流(hli)（工厂1-工厂2之间）：,(2-,x,1,)/500 0.2%,第二段河流：,0.8(2-,x,1,x,2,)/7000.2%,此外有：,x,1,2,；,x,2,min,z,=1000,x,1,+800,x,2,s.t.x,1,1,x,1,+,x,2,x,1,2,x,2,x