最优化理论-第一章课件.ppt

《最优化理论-第一章课件.ppt》由会员分享，可在线阅读，更多相关《最优化理论-第一章课件.ppt（52页珍藏版）》请在三一办公上搜索。

1、本课主要内容,最优化概述 最优化的数学基础 线性规划 整数规划 一维最优化方法 无约束多维非线性规划方法 约束问题的非线性规划方法 非线性规划中的一些其他方法,第一章 最优化的基本要素,1-1 绪论1-2 优化问题的示例1-3 优化问题的数学模型 1-4 优化问题的几何解释和基本解法,优化是从处理各种事物的一切可能的方案中，寻求最优的方案。优化的原理与方法，在科学的、工程的和社会的实际问题中的应用，便是优化问题。,1-1 绪论,1.优化的含义,（1）来源：优化一语来自英文Optimization，其本意是寻优的过程；（2）优化过程：是寻找约束空间下给定函数取极大值（以max表示)或极小(以mi

2、n表示)的过程。优化方法也称数学规划，是用科学方法和手段进行决策及确定最优解的数学。,2.优化的发展概况,历史上最早记载下来的最优化问题可追溯到古希腊的欧几里得（Euclid，公元前300年左右），他指出：在周长相同的一切矩形中，以正方形的面积为最大。十七、十八世纪微积分的建立给出了求函数极值的一些准则，对最优化的研究提供了某些理论基础。然而，在以后的两个世纪中，最优化技术的进展缓慢，主要考虑了有约束条件的最优化问题，发展了变分法。直到上世纪40年代初，由于军事上的需要产生了运筹学，并使优化技术首先应用于解决战争中的实际问题，例如轰炸机最佳俯冲轨迹的设计等。,近十几年来，最优化方法已陆续用到建

3、筑结构、化工、冶金、铁路、航天航空、造船、机床、汽车、自动控制系统、电力系统以及电机、电器等工程设计领域，并取得了显著效果。,50年代末数学规划方法被首次用于结构最优化，并成为优化设计中求优方法的理论基础。数学规划方法是在第二次世界大战期间发展起来的一个新的数学分支，线性规划与非线性规划是其主要内容。大型电子计算机的出现，使最优化方法及其理论蓬勃发展，成为应用数学中的一个重要分支，并在许多科学技术领域中得到应用。,第一阶段人类智能优化：与人类史同步，直接凭借人类的直觉或逻辑思维，如黄金分割法、穷举法和瞎子爬山法等。,第二阶段数学规划方法优化：从三百多年前牛顿发明微积分算起，电子计算机的出现推动

4、数学规划方法在近五十年来得到迅速发展。第三阶段工程优化：近二十余年来，计算机技术的发展给解决复杂工程优化问题提供了新的可能，非数学领域专家开发了一些工程优化方法，能解决不少传统数学规划方法不能胜任的工程优化问题。在处理多目标工程优化问题中，基于经验和直觉的方法得到了更多的应用。优化过程和方法学研究，尤其是建模策略研究引起重视，开辟了提高工程优化效率的新的途径。第四阶段现代优化方法：如遗传算法、模拟退火算法、蚁群算法、神经网络算法等，并采用专家系统技术实现寻优策略的自动选择和优化过程的自动控制，智能寻优策略迅速发展。,已知：制造一体积为100m3，长度不小于5m，不带上盖的箱盒，试确定箱盒的长x

5、1，宽x2，高x3，使箱盒用料最省。分析：（1）箱盒的表面积的表达式；（2）优化变量确定：长x1，宽x2，高x3；（3）优化约束条件：（a）体积要求；（b）长度要求；,箱盒的优化问题,1-2 优化问题示例,数学模型,优化变量：,目标函数：,约束条件：,某工厂生产A 和B 两种产品，A 产品单位价格为PA 万元，B 产品单位价格为PB 万元。每生产一个单位A 产品需消耗煤aC 吨，电aE 度，人工aL 个人日；每生产一个单位B 产品需消耗煤bC 吨，电bE 度，人工bL 个人日。现有可利用生产资源煤C 吨，电E 度，劳动力L 个人日，欲找出其最优分配方案，使产值最大。分析：（1）产值的表达式；（

6、2）优化变量确定：A 产品xA，B 产品xB；（3）优化约束条件：（a）生产资源煤约束；（b）生产资源电约束；（b）生产资源劳动力约束；,最大产值生产资源分配问题,数学模型,优化变量：,目标函数：,约束条件：,1-3 最优化的数学模型,1.优化变量 一个优化问题可以用一组基本参数的数值来表示，在优化过程中进行选择并最终必须确定的各项独立的基本参数，称作优化变量，又叫做决策变量。,最优化的数学模型是描述实际优化问题目标函数、变量关系、有关约束条件和意图的数学表达式，它反映了物理现象各主要因素的内在联系，是进行最优化的基础。,优化变量的全体实际上是一组变量，可用一个列向量表示。优化变量的数目称为优

7、化问题的维数，如n个优化变量，则称为n维优化问题。,按照优化变量的取值特点，可分为连续变量（例如轴径、轮廓尺寸等）和离散变量（例如各种标准规格等）。,图1-1 优化变量所组成的优化空间（a）二维问题（b）三维问题,只有两个优化变量的二维优化问题可用图（a）所示的平面直角坐标表示；有三个优化变量的三维问题可用图（b）所表示的空间直角坐标表示。,优化问题的维数表征优化的自由度，优化变量愈多，则问题的自由度愈大、可供选择的方案愈多，但难度亦愈大、求解亦愈复杂。小型优化问题：一般含有210个优化变量；中型优化问题：1050个优化变量；大型优化问题：50个以上的优化变量。,如何选定优化变量？任何一项产品

8、，是众多变量标志结构尺寸的综合体。变量越多，可以淋漓尽致地描述产品结构，但会增加建模的难度和造成优化规模过大。所以确定优化变量时应注意以下几点：（1）抓主要，舍次要。对产品性能和结构影响大的参数可取为优化变量，影响小的可先根据经验取为试探性的常量，有的甚至可以不考虑。（2）根据要解决问题的特殊性来选择优化变量。例如，圆柱螺旋拉压弹簧的优化变量有4个，即钢丝直径d，弹簧中径D，工作圈数n和自由高度H。在建模中，将材料的许用剪切应力 和剪切模量等作为优化常量。在给定径向空间内设计弹簧，则可把弹簧中径D作为优化常量。,2.约束条件,优化问题中有些是工程上所不能接受的，在优化中对优化变量取值有一些限制

9、条件，这些限制条件称作约束条件，简称约束。,约束又可按其数学表达形式分成等式约束和不等式约束两种类型：,(1)等式约束,(2)不等式约束,根据约束的性质可以把它们区分成：性能约束针对性能要求而提出的限制条件称作性能约束。例如，选择某些结构必须满足受力的强度、刚度或稳定性等要求；边界约束只是对设计变量的取值范围加以限制的约束称作边界约束。例如，允许机床主轴选择的尺寸范围，对轴段长度的限定范围就属于边界约束。,图1-2 优化问题中的约束面（或约束线）(a)二变量问题的约束线(b)三变量问题的约束面,如图1-3上画出了满足两项约束条件g1（X）=x12x2216 0和g2（X）2x20的二维设计问题

10、的可行域D，它位于x2=2的上面和圆 x12x22=16的圆弧ABC下面并包括线段AC和圆弧ABC在内。,图1-3 约束条件规定的可行域D,可行域:在优化问题中，满足所有约束条件的点所构成的集合。,满足 的约束为起作用约束,否则为不起作用的约束.(等式约束一定是起作用约束),一般情况下，可行域可表示为：,不可行域:可行点和不可行点 D内的点为可行点,否则为不可行点（外点）。边界点与内点约束边界上的可行点为边界点,其余可行点为内点。起作用的约束与不起作用的约束,3.目标函数,在优化过程中，通过优化变量的不断向f(X)值改善的方向自动调整，最后求得f(X)值最好或最满意的X值。在构造目标函数时，目

11、标函数的最优值可能是最大值，也可能是最小值。在机械设计中，可作为参考目标函数的有：,体积最小、重量最轻、效率最高、承载能力最大、结构运动精度最高、振幅或噪声最小、成本最低、耗能最小、动负荷最小等等。,为了对优化进行定量评价，必须构造包含优化变量的评价函数，它是优化的目标，称为目标函数，以f(X)表示。,在优化问题中，可以只有一个目标函数，称为单目标函数。当在同一设计中要提出多个目标函数时，这种问题称为多目标函数的最优化问题。在一般的最优化问题中，多目标函数的情况较多。目标函数愈多，建模的综合效果愈好，但问题的求解亦愈复杂。,在实际工程问题中，常常会遇到在多目标函数的某些目标之间存在矛盾的情况，

12、这就要求建模者正确处理各目标函数之间的关系。,目标函数等值（线）面,目标函数是n维变量的函数，它的函数图像只能在n+1维空间中描述出来。为了在n维设计空间中反映目标函数的变化情况，常采用目标函数等值面的方法。目标函数的等值面（线）数学表达式为：,c为一系列常数，代表一族n维超曲面。如在二维优化问题中，f(x1,x2)=c 代表x1-x2平面上的一族曲线。对于具有相等目标函数值的自变量构成的平面曲线或曲面称为等值线或等值面。,图1-4 等值线,图1-4表示目标函数f（X）与两个优化变量x1，x2阶所构成的关系曲面上的等值线，它是由许多具有相等目标函数值的点所构成的平面曲线。当给目标函数以不同值时

13、，可得到一系列的等值线，它们构成目标函数的等值线族。在极值处目标函数的等值线聚成一点，并位于等值线族的中心。当目标函数值的变化范围一定时，等值线愈稀疏说明目标函数值的变化愈平缓。利用等值线的概念可用几何图象形象地表现出目标函数的变化规律。,从等值线上，可以清楚地看到函数值的变化情况。其中f=40的等值线就是使f(x1,x2)=40的各点x1,x2T所组成的连线。,如图函数 的等值线图。,图1-5 等值线,4.优化问题一般数学形式：,满足约束条件：,求优化变量向量,使目标函数,对于复杂的问题，要建立能反映客观工程实际的、完善的数学模型往往会遇到很多困难，有时甚至比求解更为复杂。这时要抓住关键因素

14、，适当忽略不重要的成分，使问题合理简化，以易于列出数学模型，这样不仅可节省时间，有时也会改善优化结果。,最优化问题的目标函数通常为求目标函数的最小值。若目标函数的最优点为可行域中的最大值时，则可看成是求-f（X）的最小值，因为min-f（X）与max f（X）是等价的。,5.建模实例,1）根据问题要求，应用专业范围内的现行理论和经验等，对优化对象进行分析。必要时，需要对传统问题中的公式进行改进，并尽可以反映该专业范围内的现代技术进步的成果。,2）对诸参数进行分析，以确定问题的原始参数、优化常数和优化变量。,3）根据问题要求，确定并构造目标函数和相应的约束条件，有时要构造多目标函数。,4）必要时

15、对数学模型进行规范化，以消除诸组成项间由于量纲不同等原因导致的数量悬殊的影响。,建立优化问题的数学模型一般步骤：,以最低成本确定满足动物所需营养的最优混合饲料。设每天需要混合饲料的批量为100磅，这份饲料必须含：至少0.8%而不超过1.2%的钙;至少22%的蛋白质;至多5%的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分为：,混合饲料配合,解:根据前面介绍的建模要素得出此问题的数学模型如下:设 是生产100磅混合饲料所须的石灰石、谷物、大豆粉的量（磅）。,6.优化设计的分类,对于最优化问题一般可作如下分类：,还有其它的一些划分方法：如按优化变量的性质分：连续变量、离散变量

16、、整数变量规划问题:二次规划、几何规划、随机规划等。,一、几何解释,1-4 优化问题的几何解释和基本解法,无约束优化问题就是在没有限制的条件下，对优化变量求目标函数的极小点。在优化空间内，目标函数是以等值面的形式反映出来的，则无约束优化问题的极小点即为等值面的中心。,约束优化问题是在可行域内对设计变量求目标函数的极小点，此极小点在可行域内或在可行域边界上。,等值线等高线,等值线等高线：它是由许多具有相同目标函数值的点所构成的平面曲线目标函数的等值线数学表达式为：,例1：如下二维非线性规划问题,例题,通过二维约束优化问题的几何求解来直观地描述优化问题的基本思想。,目标函数等值线是以点（2，0）为

17、圆心的一组同心圆。如不考虑约束，本例的无约束最优解是：,，,约束方程所围成的可行域是D。,图1-9,由图易见约束直线与等值线的切点是最优点，利用解析几何的方法得该切点为，对应的最优值为(见图）,例2：,解：先画出目标函数等值线，再画出约束曲线，本处约束曲线是一条直线，这条直线就是可行集。而最优点就是可行域上使等值线具有最小值的点。,解：先画出等式约束曲线 的图形。这是一条抛物线，如图,例3：,再画出不等式约束区域，如图（选定哪侧区域）最后画出目标函数等值线，特别注意可行集边界点，,以及等值线与可行集的切点，易见可行域为曲线段ABCD。当动点沿抛物曲线段ABCD由A点出发时，AB段目标函数值下降

18、。过点B后，在BC段目标函数值上升。过C点后，在CD段目标函数值再次下降。D点是使目标函数值最小的可行点，其坐标可通过解方程组：,得出：,由以上例子可见，对二维最优化问题。我们总可以用图解法求解，而对三维或高维问题，已不便在平面上作图，此法失效。在三维和三维以上的空间中，使目标函数取同一常数值的是 X|f(X)=C,C是常数称为目标函数的等值面。等值面具有以下性质：（1）不同值的等值面之间不相交，因为目标函数是单值函数；（2）等值面稠的地方，目标函数值变化得较快，而稀疏的地方变化得比较慢；（3）一般地，在极值点附近，等值面（线）近似地呈现为同心椭球面族（椭圆族）。,求解优化问题的基本解法有：,

19、二、优化问题的基本解法,解析法：即利用数学分析(微分、变分等）的方法，根据函数（泛函）极值的必要条件和充分条件求出其最优解析解的求解方法。在目标函数比较简单时，求解还可以。,局限性：工程优化问题的目标函数和约束条件往往比较复杂，有时甚至还无法用数学方程描述，在这种情况下应用数学分析方法就会带来麻烦。,最优化方法是与近代电子计算机的发展紧密相联系的，数值计算法比解析法更能适应电子计算机的工作特点，因为数值计算的迭代方法具有以下特点：1）是数值计算而不是数学分析方法；2）具有简单的逻辑结构并能进行反复的同样的算术计算；3）最后得出的是逼近精确解的近似解。这些特点正与计算机的工作特点相一致。,数值迭

20、代法的基本思路：是进行反复的数值计算，寻求目标函数值不断下降的可行计算点，直到最后获得足够精度的最优点。这种方法的求优过程大致可归纳为以下步骤：,1）首先初选一个尽可能靠近最小点的初始点X（0），从X（0）出发按照一定的原则寻找可行方向和初始步长，向前跨出一步达到X（1）点；2）得到新点X（1）后再选择一个新的使函数值迅速下降的方向及适当的步长，从X（1）点出发再跨出一步，达到X（2）点，并依此类推，一步一步地向前探索并重复数值计算，最终达到目标函数的最优点。,1.求解步骤,在中间过程中每一步的迭代形式为：,图1-8 迭代计算机逐步逼近最优点过程示意图,上式中：X（k）第k步迭代计算所得到的点，称第k步迭代点，亦为第k步设计方案；a（k）第k步迭代计算的步长；S（k）第k步迭代计算的探索方向。,用迭代法逐步逼近最优点的探索过程如图1-8所示。,运用迭代法，每次迭代所得新的点的目标函数都应满足函数值下降的要求：,（1）选择搜索方向（2）确定步长因子（3）给定收敛准则,迭代法要解决的问题：,柯西收敛准则,点列 收敛的必要和充要条件是：对于任意指定的实数，都存在一个只与 有关而与 无关的自然数 N，使得当两自然数m，p N时,满足 或 或,2.迭代终止准则,（1）点距准则,或,（2）函数值下降量 准则,或,