最优化理论-第一章优秀PPT.ppt

《最优化理论-第一章优秀PPT.ppt》由会员分享，可在线阅读，更多相关《最优化理论-第一章优秀PPT.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、本课主要内容l l 最优化概述l l 最优化的数学基础l l 线性规划l l 整数规划l l 一维最优化方法l l 无约束多维非线性规划方法l l 约束问题的非线性规划方法l l 非线性规划中的一些其他方法第一章第一章 最优化的基本要素最优化的基本要素 1-1 1-1 1-1 1-1 绪论绪论绪论绪论1-2 1-2 1-2 1-2 优化问题的示例优化问题的示例优化问题的示例优化问题的示例1-3 1-3 1-3 1-3 优化问题的数学模型优化问题的数学模型优化问题的数学模型优化问题的数学模型 1-4 1-4 1-4 1-4 优化问题的几何说明和基本解法优化问题的几何说明和基本解法优化问题的几何说

2、明和基本解法优化问题的几何说明和基本解法 优化是从处理各种事物的一切可能的方案中，寻求优化是从处理各种事物的一切可能的方案中，寻求最优的方案。最优的方案。优化的原理与方法，在科学的、工程的和社会的实优化的原理与方法，在科学的、工程的和社会的实际问题中的应用，便是优化问题。际问题中的应用，便是优化问题。1-1 1-1 绪论绪论1.1.1.1.优化的含义优化的含义优化的含义优化的含义 （1 1）来源：优化一语来自英文）来源：优化一语来自英文OptimizationOptimization，其本意是寻优的过程；，其本意是寻优的过程；（2 2）优化过程：是找寻约束空间下给）优化过程：是找寻约束空间下给

3、定函数取极大值（以定函数取极大值（以maxmax表示表示)或微小或微小(以以minmin表示表示)的过程。优化方法也称数学规划，是的过程。优化方法也称数学规划，是用科学方法和手段进行决策及确定最优解的用科学方法和手段进行决策及确定最优解的数学。数学。2.2.2.2.优化的发展概况优化的发展概况优化的发展概况优化的发展概况 历史上最早记载下来的最优化问题可追溯到古希腊的欧几历史上最早记载下来的最优化问题可追溯到古希腊的欧几里得（里得（EuclidEuclid，公元前，公元前300300年左右），他指出：在周长相同的一年左右），他指出：在周长相同的一切矩形中，以正方形的面积为最大。十七、十八世纪微

4、积分的切矩形中，以正方形的面积为最大。十七、十八世纪微积分的建立给出了求函数极值的一些准则，对最优化的探讨供应了某建立给出了求函数极值的一些准则，对最优化的探讨供应了某些理论基础。然而，在以后的两个世纪中，最优化技术的进展些理论基础。然而，在以后的两个世纪中，最优化技术的进展缓慢，主要考虑了有约束条件的最优化问题，发展了变分法。缓慢，主要考虑了有约束条件的最优化问题，发展了变分法。直到上世纪直到上世纪4040年头初，由于军事上的须要产生了运筹学，年头初，由于军事上的须要产生了运筹学，并使优化技术首先应用于解决斗争中的实际问题，例如轰炸机并使优化技术首先应用于解决斗争中的实际问题，例如轰炸机最佳

5、俯冲轨迹的设计等。最佳俯冲轨迹的设计等。近十几年来，最优化方法已接连用到建筑结构、化工、冶金、铁路、航天航空、造船、机床、汽车、自动限制系统、电力系统以及电机、电器等工程设计领域，并取得了显著效果。50年头末数学规划方法被首次用于结构最优化，并成为优化设计中求优方法的理论基础。数学规划方法是在其次次世界大战期间发展起来的一个新的数学分支，线性规划与非线性规划是其主要内容。大型电子计算机的出现，使最优化方法及其理论蓬勃发展，成为应用数学中的一个重要分支，并在很多科学技术领域中得到应用。l l第一阶段人类智能优化：与人类史同步，干脆凭借人类的第一阶段人类智能优化：与人类史同步，干脆凭借人类的第一阶

6、段人类智能优化：与人类史同步，干脆凭借人类的第一阶段人类智能优化：与人类史同步，干脆凭借人类的直觉或逻辑思维，如黄金分割法、穷举法和瞎子爬山法等。直觉或逻辑思维，如黄金分割法、穷举法和瞎子爬山法等。直觉或逻辑思维，如黄金分割法、穷举法和瞎子爬山法等。直觉或逻辑思维，如黄金分割法、穷举法和瞎子爬山法等。l 其次阶段数学规划方法优化：从三百多年前牛顿独创微积其次阶段数学规划方法优化：从三百多年前牛顿独创微积分算起，电子计算机的出现推动数学规划方法在近五十年来得分算起，电子计算机的出现推动数学规划方法在近五十年来得到快速发展。到快速发展。l 第三阶段工程优化：近二十余年来，计算机技术的发展给第三阶段

7、工程优化：近二十余年来，计算机技术的发展给解决困难工程优化问题供应了新的可能，非数学领域专家开发解决困难工程优化问题供应了新的可能，非数学领域专家开发了一些工程优化方法，能解决不少传统数学规划方法不能胜任了一些工程优化方法，能解决不少传统数学规划方法不能胜任的工程优化问题。在处理多目标工程优化问题中，基于阅历和的工程优化问题。在处理多目标工程优化问题中，基于阅历和直觉的方法得到了更多的应用。优化过程和方法学探讨，尤其直觉的方法得到了更多的应用。优化过程和方法学探讨，尤其是建模策略探讨引起重视，开拓了提高工程优化效率的新的途是建模策略探讨引起重视，开拓了提高工程优化效率的新的途径。径。l 第四阶

8、段现代优化方法：如遗传算法、第四阶段现代优化方法：如遗传算法、模拟退火算法、模拟退火算法、蚁群算法、蚁群算法、神经网络算法等，并接受专家系统技术实现寻优神经网络算法等，并接受专家系统技术实现寻优策略的自动选择和优化过程的自动限制，智能寻优策略快速发策略的自动选择和优化过程的自动限制，智能寻优策略快速发展。展。已知：制造一体积为已知：制造一体积为已知：制造一体积为已知：制造一体积为100m100m100m100m3 3 3 3，长度不小于，长度不小于，长度不小于，长度不小于5m5m5m5m，不，不，不，不带上盖的箱盒，试确定箱盒的长带上盖的箱盒，试确定箱盒的长带上盖的箱盒，试确定箱盒的长带上盖的

9、箱盒，试确定箱盒的长x x x x1 1 1 1，宽，宽，宽，宽x x x x2 2 2 2，高，高，高，高x x x x3 3 3 3，使箱盒用料最省。使箱盒用料最省。使箱盒用料最省。使箱盒用料最省。分析：分析：分析：分析：（1 1 1 1）箱盒的表面积的表达式；）箱盒的表面积的表达式；）箱盒的表面积的表达式；）箱盒的表面积的表达式；（2 2 2 2）优化变量确定：长）优化变量确定：长）优化变量确定：长）优化变量确定：长x x x x1 1 1 1，宽，宽，宽，宽x x x x2 2 2 2，高，高，高，高x x x x3 3 3 3 ；（3 3 3 3）优化约束条件：）优化约束条件：）优化

10、约束条件：）优化约束条件：（a a a a）体积要求；）体积要求；）体积要求；）体积要求；（b b b b）长度要求；）长度要求；）长度要求；）长度要求；x x1 1x x2 2x x3 3箱盒的优化问题箱盒的优化问题1-2 1-2 优化问题示例优化问题示例数学模型数学模型优化变量：优化变量：目标函数：目标函数：约束条件：约束条件：某工厂生产某工厂生产某工厂生产某工厂生产A A A A 和和和和B B B B 两种产品，两种产品，两种产品，两种产品，A A A A 产品单位价格产品单位价格产品单位价格产品单位价格为为为为PA PA PA PA 万元，万元，万元，万元，B B B B 产品单位价

11、格为产品单位价格为产品单位价格为产品单位价格为PB PB PB PB 万元。每生产一个单万元。每生产一个单万元。每生产一个单万元。每生产一个单位位位位A A A A 产品需消耗煤产品需消耗煤产品需消耗煤产品需消耗煤aC aC aC aC 吨，电吨，电吨，电吨，电aE aE aE aE 度，人工度，人工度，人工度，人工aL aL aL aL 个人日；每个人日；每个人日；每个人日；每生产一个单位生产一个单位生产一个单位生产一个单位B B B B 产品需消耗煤产品需消耗煤产品需消耗煤产品需消耗煤bC bC bC bC 吨，电吨，电吨，电吨，电bE bE bE bE 度，人工度，人工度，人工度，人工b

12、L bL bL bL 个人日。现有可利用生产资源煤个人日。现有可利用生产资源煤个人日。现有可利用生产资源煤个人日。现有可利用生产资源煤C C C C 吨，电吨，电吨，电吨，电E E E E 度，劳动力度，劳动力度，劳动力度，劳动力L L L L 个人日，欲找出其最优安排方案，使产值最大。个人日，欲找出其最优安排方案，使产值最大。个人日，欲找出其最优安排方案，使产值最大。个人日，欲找出其最优安排方案，使产值最大。分析：分析：分析：分析：（1 1 1 1）产值的表达式；）产值的表达式；）产值的表达式；）产值的表达式；（2 2 2 2）优化变量确定：）优化变量确定：）优化变量确定：）优化变量确定：A

13、 A A A 产品产品产品产品xAxAxAxA，B B B B 产品产品产品产品xB xB xB xB；（3 3 3 3）优化约束条件：）优化约束条件：）优化约束条件：）优化约束条件：（a a a a）生产资源煤约束；）生产资源煤约束；）生产资源煤约束；）生产资源煤约束；（b b b b）生产资源电约束；）生产资源电约束；）生产资源电约束；）生产资源电约束；（b b b b）生产资源劳动力约束；）生产资源劳动力约束；）生产资源劳动力约束；）生产资源劳动力约束；最大产值生产资源安排问题最大产值生产资源安排问题 数学模型数学模型优化变量：优化变量：目标函数：目标函数：约束条件：约束条件：1-31-

14、3 最优化的数学模型最优化的数学模型 1.1.1.1.优化变量优化变量优化变量优化变量 一个优化问题可以用一组基本参数的数值来表一个优化问题可以用一组基本参数的数值来表一个优化问题可以用一组基本参数的数值来表一个优化问题可以用一组基本参数的数值来表示，在优化过程中进行选择并最终必需确定的各项示，在优化过程中进行选择并最终必需确定的各项示，在优化过程中进行选择并最终必需确定的各项示，在优化过程中进行选择并最终必需确定的各项独立的基本参数，称作优化变量，又叫做决策变量。独立的基本参数，称作优化变量，又叫做决策变量。独立的基本参数，称作优化变量，又叫做决策变量。独立的基本参数，称作优化变量，又叫做决

15、策变量。最优化的数学模型是描述实际优化问题目标函数、最优化的数学模型是描述实际优化问题目标函数、变量关系、有关约束条件和意图的数学表达式，它反变量关系、有关约束条件和意图的数学表达式，它反映了物理现象各主要因素的内在联系，是进行最优化映了物理现象各主要因素的内在联系，是进行最优化的基础。的基础。优化变量的全体事实上是一组变量，可用一个列优化变量的全体事实上是一组变量，可用一个列优化变量的全体事实上是一组变量，可用一个列优化变量的全体事实上是一组变量，可用一个列向量表示。优化变量的数目称为优化问题的维数，如向量表示。优化变量的数目称为优化问题的维数，如向量表示。优化变量的数目称为优化问题的维数，

16、如向量表示。优化变量的数目称为优化问题的维数，如n n n n个优化变量，则称为个优化变量，则称为个优化变量，则称为个优化变量，则称为n n n n维优化问题。维优化问题。维优化问题。维优化问题。依据优化变量的取值特点，可分为连续变量（例依据优化变量的取值特点，可分为连续变量（例如轴径、轮廓尺寸等）和离散变量（例如各种标准规格如轴径、轮廓尺寸等）和离散变量（例如各种标准规格等）。等）。图1-1 优化变量所组成的优化空间优化变量所组成的优化空间（a a）二维问题）二维问题 （b b）三维问题）三维问题 只只有有两两个个优优化化变变量量的的二二维维优优化化问问题题可可用用图图（a a）所所示示的的

17、平平面面直直角角坐坐标标表表示示；有有三三个个优优化化变变量量的的三三维维问题可用图（问题可用图（b b）所表示的空间直角坐标表示。）所表示的空间直角坐标表示。优化问题的维数表征优化的自由度，优化变量愈优化问题的维数表征优化的自由度，优化变量愈多，则问题的自由度愈大、可供选择的方案愈多，但多，则问题的自由度愈大、可供选择的方案愈多，但难度亦愈大、求解亦愈困难。难度亦愈大、求解亦愈困难。小型优化问题：一般含有小型优化问题：一般含有210210个优化变量；个优化变量；中型优化问题：中型优化问题：10501050个优化变量；个优化变量；大型优化问题：大型优化问题：5050个以上的优化变量。个以上的优

18、化变量。如何选定优化变量？如何选定优化变量？任任何何一一项项产产品品，是是众众多多变变量量标标记记结结构构尺尺寸寸的的综综合合体体。变变量量越越多多，可可以以淋淋漓漓尽尽致致地地描描述述产产品品结结构构，但但会会增增加加建建模模的的难难度度和和造造成成优优化化规规模模过过大大。所所以以确确定定优优化化变量时应留意以下几点：变量时应留意以下几点：（1 1）抓主要，舍次要。）抓主要，舍次要。对对产产品品性性能能和和结结构构影影响响大大的的参参数数可可取取为为优优化化变变量量，影影响响小小的的可可先先依依据据阅阅历历取取为为摸摸爽爽性性的的常常量量，有有的的甚甚至至可以不考虑。可以不考虑。（2 2）

19、依据要解决问题的特殊性来选择优化变量。）依据要解决问题的特殊性来选择优化变量。例例如如，圆圆柱柱螺螺旋旋拉拉压压弹弹簧簧的的优优化化变变量量有有4 4个个，即即钢钢丝丝直直径径d d，弹弹簧簧中中径径D D，工工作作圈圈数数n n和和自自由由高高度度H H。在在建建模模中中，将将材材料料的的许许用用剪剪切切应应力力 和和剪剪切切模模量量等等作作为为优优化化常常量量。在在给给定定径径向向空空间间内内设设计计弹弹簧簧，则则可可把把弹弹簧簧中径中径D D作为优化常量。作为优化常量。2.2.约束条件约束条件 优化问题中有些是工程上所不能接受的，在优化优化问题中有些是工程上所不能接受的，在优化中对优化变

20、量取值有一些限制条件，这些限制条件称中对优化变量取值有一些限制条件，这些限制条件称作作约束条件约束条件，简称，简称约束约束。约束又可按其数学表达形式分成等式约束和约束又可按其数学表达形式分成等式约束和不等式约束两种类型：不等式约束两种类型：(1)(1)等式约束等式约束(2)(2)不等式约束不等式约束依据约束的性质可以把它们区分成：依据约束的性质可以把它们区分成：性能约束性能约束针对性能要求而提出的限制条件称作性能针对性能要求而提出的限制条件称作性能约束。例如，选择某些结构必需满足受力的强度、刚度约束。例如，选择某些结构必需满足受力的强度、刚度或稳定性等要求；或稳定性等要求；边界约束边界约束只是

21、对设计变量的取值范围加以限制的约只是对设计变量的取值范围加以限制的约束称作边界约束。例如，允许机床主轴选择的尺寸范围，束称作边界约束。例如，允许机床主轴选择的尺寸范围，对轴段长度的限定范围就属于边界约束。对轴段长度的限定范围就属于边界约束。图图1-2 1-2 优化问题中的约束面（或约束线）优化问题中的约束面（或约束线）(a)(a)二变量问题的约束线二变量问题的约束线 (b)(b)三变量问题的约束面三变量问题的约束面 如图如图1-31-3上画出了满足两项约束条件上画出了满足两项约束条件g1g1（X X）=x12=x12x2216 0 x2216 0和和g2g2（X X）2x202x20的二维设计

22、问题的可行域的二维设计问题的可行域D D，它位于，它位于x2=2x2=2的上的上面和圆面和圆 x12 x12x22=16x22=16的圆弧的圆弧ABCABC下面并包括线段下面并包括线段ACAC和圆弧和圆弧ABCABC在内。在内。图图1-3 1-3 约束条件规定的可行域约束条件规定的可行域D D 可行域可行域:在优化问题中，满足全部约束条件的点所构成在优化问题中，满足全部约束条件的点所构成的集合。的集合。满足满足 的约束为起作用约束的约束为起作用约束,否则为否则为不起作用的约束不起作用的约束.(.(等式约束确定是起作用约束等式约束确定是起作用约束)一般状况下，可行域可表示为：一般状况下，可行域可

23、表示为：不行行域不行行域:可行点和不行行点可行点和不行行点 D D内的点为可行点内的点为可行点,否则为不行否则为不行行点（外点）。行点（外点）。边界点与内点边界点与内点约束边界上的可行点为边界点约束边界上的可行点为边界点,其其余可行点为内点。余可行点为内点。起作用的约束与不起作用的约束起作用的约束与不起作用的约束3.3.目标函数目标函数 在优化过程中，通过优化变量的不断向在优化过程中，通过优化变量的不断向f(X)f(X)值改善的方向值改善的方向自动调整，最终求得自动调整，最终求得f(X)f(X)值最好或最满足的值最好或最满足的X X值。在构造目标值。在构造目标函数时，目标函数的最优值可能是最大

24、值，也可能是最小值。函数时，目标函数的最优值可能是最大值，也可能是最小值。在机械设计中，可作为参考目标函数的有：在机械设计中，可作为参考目标函数的有：体积最小、重量最轻、效率最高、承载实力最大、结构运体积最小、重量最轻、效率最高、承载实力最大、结构运动精度最高、振幅或噪声最小、成本最低、耗能最小、动负荷动精度最高、振幅或噪声最小、成本最低、耗能最小、动负荷最小等等。最小等等。为了对优化进行定量评价，必须构造包含优化变量的评价为了对优化进行定量评价，必须构造包含优化变量的评价函数，它是优化的目标，称为函数，它是优化的目标，称为目标函数目标函数，以，以f(X)表示。表示。在优化问题中，可以只有一个

25、目标函数，称为单目标函数。在优化问题中，可以只有一个目标函数，称为单目标函数。当在同一设计中要提出多个目标函数时，这种问题称为多目标函当在同一设计中要提出多个目标函数时，这种问题称为多目标函数的最优化问题。在一般的最优化问题中，多目标函数的状况较数的最优化问题。在一般的最优化问题中，多目标函数的状况较多。目标函数愈多，建模的综合效果愈好，但问题的求解亦愈困多。目标函数愈多，建模的综合效果愈好，但问题的求解亦愈困难。难。在实际工程问题中，常常会遇到在多目标函数的某些目标在实际工程问题中，常常会遇到在多目标函数的某些目标之间存在冲突的状况，这就要求建模者正确处理各目标函数之之间存在冲突的状况，这就

26、要求建模者正确处理各目标函数之间的关系。间的关系。目标函数等值（线）面目标函数等值（线）面目标函数等值（线）面目标函数等值（线）面 目标函数是目标函数是n n维变量的函数，它的函数图像只能在维变量的函数，它的函数图像只能在n+1n+1维空维空间中描述出来。为了在间中描述出来。为了在n n维设计空间中反映目标函数的变更状维设计空间中反映目标函数的变更状况，常接受目标函数等值面的方法。况，常接受目标函数等值面的方法。目标函数的等值面（线）数学表达式为：目标函数的等值面（线）数学表达式为：c c为一系列常数，代表一族为一系列常数，代表一族n n维超曲面。如在二维优化维超曲面。如在二维优化问题中，问题

27、中，f(x1,x2)=c 代表代表x1-x2平面上的一族曲线。平面上的一族曲线。对于具有相等目标函数值的自变量构成的平面曲线或对于具有相等目标函数值的自变量构成的平面曲线或曲面称为曲面称为等值线等值线或或等值面等值面。图图1-4 1-4 等值线等值线 图1-4表示目标函数f（X）与两个优化变量x1，x2阶所构成的关系曲面上的等值线，它是由很多具有相等目标函数值的点所构成的平面曲线。当给目标函数以不同值时，可得到一系列的等值线，它们构成目标函数的等值线族。在极值处目标函数的等值线聚成一点，并位于等值线族的中心。当目标函数值的变更范围确定时，等值线愈稀疏说明目标函数值的变更愈平缓。利用等值线的概念

28、可用几何图象形象地表现出目标函数的变更规律。从等值线上，可以清晰地看到函数值的变更状况。其中从等值线上，可以清晰地看到函数值的变更状况。其中f=40f=40的等值线就是使的等值线就是使f(x1,x2)=40f(x1,x2)=40的各点的各点x1,x2Tx1,x2T所组成的所组成的连线。连线。如图函数如图函数 的等值线图。的等值线图。图图1-5 1-5 等值线等值线4.4.优化问题一般数学形式：优化问题一般数学形式：满足约束条件满足约束条件满足约束条件满足约束条件 ：求优化变量向量求优化变量向量使目标函数使目标函数 对于困难的问题，要建立能反映客观工程实际的、完对于困难的问题，要建立能反映客观工

29、程实际的、完善的数学模型往往会遇到很多困难，有时甚至比求解更为善的数学模型往往会遇到很多困难，有时甚至比求解更为困难。这时要抓住关键因素，适当忽视不重要的成分，使困难。这时要抓住关键因素，适当忽视不重要的成分，使问题合理简化，以易于列出数学模型，这样不仅可节约时问题合理简化，以易于列出数学模型，这样不仅可节约时间，有时也会改善优化结果。间，有时也会改善优化结果。最最优优化化问问题题的的目目标标函函数数通通常常为为求求目目标标函函数数的的最最小小值值。若若目目标标函函数数的的最最优优点点为为可可行行域域中中的的最最大大值值时时，则则可可看看成成是是求求-f（X）的的最最小小值值，因因为为minm

30、in-f（X）与与max f（X）是等价的。是等价的。5.5.建模实例建模实例1 1）依据问题要求，应用专业范围内的现行理论和阅历等，对）依据问题要求，应用专业范围内的现行理论和阅历等，对优化对象进行分析。必要时，须要对传统问题中的公式进行改优化对象进行分析。必要时，须要对传统问题中的公式进行改进，并尽可以反映该专业范围内的现代技术进步的成果。进，并尽可以反映该专业范围内的现代技术进步的成果。2 2）对诸参数进行分析，以确定问题的原始参数、优化常数和）对诸参数进行分析，以确定问题的原始参数、优化常数和优化变量。优化变量。3 3）依据问题要求，确定并构造目标函数和相应的约束条件，）依据问题要求，

31、确定并构造目标函数和相应的约束条件，有时要构造多目标函数。有时要构造多目标函数。4 4）必要时对数学模型进行规范化，以消退诸组成项间由于量）必要时对数学模型进行规范化，以消退诸组成项间由于量纲不同等缘由导致的数量悬殊的影响。纲不同等缘由导致的数量悬殊的影响。建立优化问题的数学模型一般步骤：建立优化问题的数学模型一般步骤：建立优化问题的数学模型一般步骤：建立优化问题的数学模型一般步骤：配料配料配料配料每磅配料中的营养含量每磅配料中的营养含量每磅配料中的营养含量每磅配料中的营养含量钙钙钙钙蛋白质蛋白质蛋白质蛋白质纤维纤维纤维纤维每磅成本（元）每磅成本（元）每磅成本（元）每磅成本（元）石灰石石灰石石

32、灰石石灰石谷物谷物谷物谷物大豆粉大豆粉大豆粉大豆粉0.380 0.00 0.000.380 0.00 0.000.001 0.09 0.020.001 0.09 0.020.002 0.50 0.080.002 0.50 0.08 0.0164 0.0164 0.0463 0.0463 0.1250 0.1250 以最低成本确定满足动物所需养分的最优混合饲料。设每天须要混合饲料的批量为100磅，这份饲料必需含：至少0.8%而不超过1.2%的钙;至少22%的蛋白质;至多5%的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要养分成分为：混合饲料协作混合饲料协作解解:根据前面介绍的建模要

33、素得出此问题的数学模型如下根据前面介绍的建模要素得出此问题的数学模型如下:设设 是生产是生产100100磅混合饲料磅混合饲料所须的石灰石、谷物、大豆粉的量（磅）。所须的石灰石、谷物、大豆粉的量（磅）。6.6.优化设计的分类优化设计的分类对于最优化问题一般可作如下分类：对于最优化问题一般可作如下分类：还有其它的一些划分方法：还有其它的一些划分方法：如按优化变量的性质分：连续变量、离散变量、整数变如按优化变量的性质分：连续变量、离散变量、整数变量规划问题量规划问题:二次规划、几何规划、随机规划等。二次规划、几何规划、随机规划等。一、几何说明一、几何说明1-4 1-4 优化问题的几何说明和基本解法优

34、化问题的几何说明和基本解法l无约束优化问题就是在没有限制的条件下，对优化变无约束优化问题就是在没有限制的条件下，对优化变量求目标函数的微小点。在优化空间内，目标函数是量求目标函数的微小点。在优化空间内，目标函数是以等值面的形式反映出来的，则无约束优化问题的微以等值面的形式反映出来的，则无约束优化问题的微小点即为等值面的中心。小点即为等值面的中心。l约束优化问题是在可行域内对设计变量求目标函约束优化问题是在可行域内对设计变量求目标函数的微小点，此微小点在可行域内或在可行域边界数的微小点，此微小点在可行域内或在可行域边界上。上。等值线等高线等值线等高线：等值线等高线：它是由很多具有相它是由很多具有

35、相同目标函数值的点同目标函数值的点所构成的平面曲线所构成的平面曲线目标函数的等值线目标函数的等值线数学表达式为：数学表达式为：例例1 1：如下二维非线性规划问题：如下二维非线性规划问题例题例题 通过二维约束优化问题的几何求解来直观地描述优化问通过二维约束优化问题的几何求解来直观地描述优化问题的基本思想。题的基本思想。目标函数等值线是以点（目标函数等值线是以点（2 2，0 0）为圆心的一组同心圆。）为圆心的一组同心圆。如不考虑约束，本例的无约束最优解是：如不考虑约束，本例的无约束最优解是：，约束方程所围成的可行域是约束方程所围成的可行域是D D。图图图图1-91-91-91-9l由图易见约束直线

36、与等值线的切点是最优点，利用解析几由图易见约束直线与等值线的切点是最优点，利用解析几何的方法得该切点为何的方法得该切点为 ，对应的最优值为对应的最优值为 l (见图）见图）例例例例2 2：解：先画出目标函数等值线，再画出约束曲线，本处约束曲线解：先画出目标函数等值线，再画出约束曲线，本处约束曲线是一条直线，这条直线就是可行集。而最优点就是可行域上使是一条直线，这条直线就是可行集。而最优点就是可行域上使等值线具有最小值的点。等值线具有最小值的点。解：解：先画出等式约束曲线先画出等式约束曲线 的图形。的图形。这是一条抛物线，如图这是一条抛物线，如图例例例例3 3：再画出不等式约束区域，如图（选定哪

37、侧区域）再画出不等式约束区域，如图（选定哪侧区域）最终画出目标函数等值线，特殊留意可行集边界点，最终画出目标函数等值线，特殊留意可行集边界点，ABCD 以及等值线与可行集的切点，易以及等值线与可行集的切点，易以及等值线与可行集的切点，易以及等值线与可行集的切点，易见可行域为曲线段见可行域为曲线段见可行域为曲线段见可行域为曲线段ABCDABCD。当动点。当动点。当动点。当动点沿抛物曲线段沿抛物曲线段沿抛物曲线段沿抛物曲线段ABCDABCD由由由由A A点动身时，点动身时，点动身时，点动身时，ABAB段目标函数值下降。过点段目标函数值下降。过点段目标函数值下降。过点段目标函数值下降。过点B B后，

38、后，后，后，在在在在BCBC段目标函数值上升。过段目标函数值上升。过段目标函数值上升。过段目标函数值上升。过C C点点点点后，在后，在后，在后，在CDCD段目标函数值再次下降。段目标函数值再次下降。段目标函数值再次下降。段目标函数值再次下降。D D点是使目标函数值最小的可行点，点是使目标函数值最小的可行点，点是使目标函数值最小的可行点，点是使目标函数值最小的可行点，其坐标可通过解方程组：其坐标可通过解方程组：其坐标可通过解方程组：其坐标可通过解方程组：l得出：得出：ABCD 由以上例子可见，对二维最优化问题。我们总可由以上例子可见，对二维最优化问题。我们总可由以上例子可见，对二维最优化问题。我

39、们总可由以上例子可见，对二维最优化问题。我们总可以用图解法求解，而对三维或高维问题，已不便在以用图解法求解，而对三维或高维问题，已不便在以用图解法求解，而对三维或高维问题，已不便在以用图解法求解，而对三维或高维问题，已不便在平面上作图，此法失效。平面上作图，此法失效。平面上作图，此法失效。平面上作图，此法失效。在三维和三维以上的空间中，使目标函数取同一在三维和三维以上的空间中，使目标函数取同一在三维和三维以上的空间中，使目标函数取同一在三维和三维以上的空间中，使目标函数取同一常数值的是常数值的是常数值的是常数值的是 X|f(X)=C,C X|f(X)=C,C是常数是常数是常数是常数 称为目标函

40、数的称为目标函数的称为目标函数的称为目标函数的等值面。等值面。等值面。等值面。等值面具有以下性质：等值面具有以下性质：等值面具有以下性质：等值面具有以下性质：（1 1）不同值的等值面之间不相交，因为目标函数是）不同值的等值面之间不相交，因为目标函数是）不同值的等值面之间不相交，因为目标函数是）不同值的等值面之间不相交，因为目标函数是单值函数；单值函数；单值函数；单值函数；（2 2）等值面稠的地方，目标函数值变更得较快，而）等值面稠的地方，目标函数值变更得较快，而）等值面稠的地方，目标函数值变更得较快，而）等值面稠的地方，目标函数值变更得较快，而稀疏的地方变更得比较慢；稀疏的地方变更得比较慢；稀

41、疏的地方变更得比较慢；稀疏的地方变更得比较慢；（3 3）一般地，在极值点旁边，等值面（线）近似地）一般地，在极值点旁边，等值面（线）近似地）一般地，在极值点旁边，等值面（线）近似地）一般地，在极值点旁边，等值面（线）近似地呈现为同心椭球面族（椭圆族）。呈现为同心椭球面族（椭圆族）。呈现为同心椭球面族（椭圆族）。呈现为同心椭球面族（椭圆族）。求解优化问题的基本解法有：求解优化问题的基本解法有：求解优化问题的基本解法有：求解优化问题的基本解法有：二、优化问题的基本解法二、优化问题的基本解法解析法解析法数值解法数值解法解解析析法法：即即利利用用数数学学分分析析(微微分分、变变分分等等）的的方方法法，

42、依依据据函函数数（泛泛函函）极极值值的的必必要要条条件件和和充充分分条条件件求求出出其其最最优优解解析析解解的的求求解解方方法法 。在在目目标标函函数数比比较较简简洁时，求解还可以。洁时，求解还可以。局限性：工程优化问题的目标函数和约束条件往往局限性：工程优化问题的目标函数和约束条件往往比较困难，有时甚至还无法用数学方程描述，在这比较困难，有时甚至还无法用数学方程描述，在这种状况下应用数学分析方法就会带来麻烦。种状况下应用数学分析方法就会带来麻烦。最优化方法是与近代电子计算机的发展紧密相联系的，数值计算法比解析法更能适应电子计算机的工作特点，因为数值计算的迭代方法具有以下特点：1）是数值计算而

43、不是数学分析方法；2）具有简洁的逻辑结构并能进行反复的同样的算术计算；3）最终得出的是靠近精确解的近似解。这些特点正与计算机的工作特点相一样。数值解法数值解法：这是一种数值近似计算方法，又称为这是一种数值近似计算方法，又称为数值迭代数值迭代方法方法。它是根据目标函数的变化规律，以适当的步长沿着能使目。它是根据目标函数的变化规律，以适当的步长沿着能使目标函数值下降的方向，逐步向目标函数值的最优点进行探索，逐标函数值下降的方向，逐步向目标函数值的最优点进行探索，逐步逼近到目标函数的最优点或直至达到最优点。数值解法（迭代步逼近到目标函数的最优点或直至达到最优点。数值解法（迭代法）是优化设计问题的基本

44、解法。法）是优化设计问题的基本解法。其中也可能用到解析法，如最速下降方向的选取、最优步长的确定等。数值迭代法的基本思路：是进行反复的数值计数值迭代法的基本思路：是进行反复的数值计算，寻求目标函数值不断下降的可行计算点，直到算，寻求目标函数值不断下降的可行计算点，直到最终获得足够精度的最优点。这种方法的求优过程最终获得足够精度的最优点。这种方法的求优过程大致可归纳为以下步骤：大致可归纳为以下步骤：1 1）首先初选一个尽可能靠近最小点的初始点）首先初选一个尽可能靠近最小点的初始点X X（0 0），从），从X X（0 0）动身依据确定的原则找寻可行方向和初始步长，向前跨）动身依据确定的原则找寻可行方

45、向和初始步长，向前跨出一步达到出一步达到X X（1 1）点；）点；2 2）得到新点）得到新点X X（1 1）后再选择一个新的使函数值快速下降）后再选择一个新的使函数值快速下降的方向及适当的步长，从的方向及适当的步长，从X X（1 1）点动身再跨出一步，达到）点动身再跨出一步，达到X X（2 2）点，并依此类推，一步一步地向前探究并重复数值计算，）点，并依此类推，一步一步地向前探究并重复数值计算，最终达到目标函数的最优点。最终达到目标函数的最优点。1.1.求解步骤求解步骤在中间过程中每一步的迭代形式为：在中间过程中每一步的迭代形式为：图图1-8 1-8 迭代计算机逐步逼近最优点过程示意图迭代计算

46、机逐步逼近最优点过程示意图 上上式式中中：X X（k k）第第k k步步迭迭代代计计算算所所得得到到的的点点，称称第第k k步步迭迭代代点，点，亦为第亦为第k k步设计方案；步设计方案；a a（k k）第第k k步迭代计算的步长；步迭代计算的步长；S S（k k）第第k k步迭代计算的探究方向。步迭代计算的探究方向。用用迭迭代代法法逐逐步步靠靠近近最最优优点点的探究过程如图的探究过程如图1-81-8所示。所示。运用迭代法，每次迭代所得新的点的目标函数运用迭代法，每次迭代所得新的点的目标函数运用迭代法，每次迭代所得新的点的目标函数运用迭代法，每次迭代所得新的点的目标函数都应满足函数值下降的要求：

47、都应满足函数值下降的要求：都应满足函数值下降的要求：都应满足函数值下降的要求：（1 1）选择搜寻方向）选择搜寻方向（2 2）确定步长因子）确定步长因子（3 3）给定收敛准则）给定收敛准则迭代法要解决的问题：迭代法要解决的问题：柯西收敛准则 点列点列 收敛的必要和充要条件是：对于随意指定的实数收敛的必要和充要条件是：对于随意指定的实数 ，都存在一个只与，都存在一个只与 有关而与有关而与 无关的自然数无关的自然数 N N，使得，使得当两自然数当两自然数mm，p Np N时时,满足满足 或或 或或2.2.迭代终止准则迭代终止准则（1 1）点距准则）点距准则或或ffkfk+1f*xkoxk+1x*x(a)（2）函数值下降量函数值下降量 准则准则或或xoffkfk+1f*xkxk+1x*(b)精品课件精品课件！精品课件精品课件！（3 3 3 3）目标函数梯度）目标函数梯度）目标函数梯度）目标函数梯度 准则准则准则准则 上述准则都在确定程度上反映了靠近最优点的程度，但都有确定的局限性。在实际应用中，可取其中一种或多种同时满足来进行判定。接受哪种收敛准则，可视具体问题而定。可以取：接受哪种收敛准则，可视具体问题而定。可以取：