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

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