《第四章非线性规划精选文档.ppt》由会员分享，可在线阅读，更多相关《第四章非线性规划精选文档.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章非线性规划本讲稿第一页，共三十八页第第4章章 非线性规划非线性规划非线性规划问题非线性规划问题一维搜索方法一维搜索方法 寻求一元函数在某区间上的最优解的方法。这类方寻求一元函数在某区间上的最优解的方法。这类方法不仅有实用价值，而且大量多维最优化方法都依赖于法不仅有实用价值，而且大量多维最优化方法都依赖于一系列的一维最优化。常用的一维最优化方法有黄金分一系列的一维最优化。常用的一维最优化方法有黄金分割法、切线法和插值法。割法、切线法和插值法。本讲稿第二页，共三十八页4.1 非线性规划问题非线性规划问题引例引例建立整数线性规划模型建立整数线性规划模型非线性规划的数学模型非线性规划的数学模型本
2、讲稿第三页，共三十八页1 引例引例建立非线性规划模型建立非线性规划模型 例例 某单位拟建一排厂房，厂房建筑平面如图所示。由于资某单位拟建一排厂房，厂房建筑平面如图所示。由于资金及材料的限制，围墙及隔墙的总长度不能超过金及材料的限制，围墙及隔墙的总长度不能超过8080米。为使建米。为使建筑面积最大，应如何选择长宽尺寸？筑面积最大，应如何选择长宽尺寸？解：解：本讲稿第四页，共三十八页1 引例引例建立非线性规划模型建立非线性规划模型例例 设某物理过程具有如下规律设某物理过程具有如下规律 用试验法求得用试验法求得 现要确定参数现要确定参数 使所得试验点构成的曲使所得试验点构成的曲线与理论曲线误差平方和
3、为最小，且满足线与理论曲线误差平方和为最小，且满足 本讲稿第五页，共三十八页2 非线性规划的数学模型非线性规划的数学模型数学数学规划模型规划模型简称：简称：MP问题（问题（Mathematical programming）如果目标函数或约束条件中存在非线性函数，则称为非线如果目标函数或约束条件中存在非线性函数，则称为非线性规划。非线性规划问题一般分为约束非线性规划和无约性规划。非线性规划问题一般分为约束非线性规划和无约束非线性规划问题。束非线性规划问题。约束集约束集/可行域可行域本讲稿第六页，共三十八页2 非线性规划的数学模型非线性规划的数学模型定义定义1.1.对于非线性规划问题对于非线性规划
4、问题(MP)(MP)，如果，如果 并且有：并且有：则称则称x*是是(MP)(MP)的整体最优解或整体极小点，的整体最优解或整体极小点，f(x*)是是(MP)(MP)的的整体最优值或整体极小值。整体最优值或整体极小值。本讲稿第七页，共三十八页2 非线性规划的数学模型非线性规划的数学模型定义定义2.2.对于非线性规划问题对于非线性规划问题(MP)(MP)，如果，如果 并且存在并且存在x*的一个邻域的一个邻域 ，使：，使：则称则称x*是是(MP)(MP)的局部最优解或局部极小点，的局部最优解或局部极小点，f(x*)是是(MP)(MP)的的局部最优值或局部极小值。局部最优值或局部极小值。本讲稿第八页，
5、共三十八页3 非线性规划问题的求解非线性规划问题的求解例例 求解如下非线性规划问题求解如下非线性规划问题o2266本讲稿第九页，共三十八页4.3 一维搜索（线搜索）方法一维搜索（线搜索）方法0.618方法（近似黄金分割法）方法（近似黄金分割法）Newton法法一维最优化方法是优化设计中最简单、最基本的方法，一一维最优化方法是优化设计中最简单、最基本的方法，一维问题是多维问题的基础，在数值方法迭代计算过程中，维问题是多维问题的基础，在数值方法迭代计算过程中，都要进行一维搜索，也可以把多维问题化为一些一维问题都要进行一维搜索，也可以把多维问题化为一些一维问题来处理。来处理。一维问题算法的好坏，直接
6、影响到最优化问题的求解速度。一维问题算法的好坏，直接影响到最优化问题的求解速度。本讲稿第十页，共三十八页本讲稿第十一页，共三十八页1近似黄金分割法（近似黄金分割法（0.618方法）方法）0.618法适用于确定区间上的任何单谷函数求极小值的问法适用于确定区间上的任何单谷函数求极小值的问题。对函数除要求单谷之外没有任何其它要求。题。对函数除要求单谷之外没有任何其它要求。高高低低高高本讲稿第十二页，共三十八页1近似黄金分割法（近似黄金分割法（0.618方法）方法）定义：函数定义：函数 称为区间称为区间a,b上的单谷函数，如果上的单谷函数，如果存在一个存在一个t*a,b,使得函数在使得函数在a,t*上
7、严格减少，上严格减少，且在且在t*,b上严格递增。区间上严格递增。区间a,b称为称为 的单谷的单谷区间。区间。高高低低高高本讲稿第十三页，共三十八页1近似黄金分割法（近似黄金分割法（0.618方法）方法）算法原理：区间消去原理算法原理：区间消去原理为简化计算，第三种情况可以合并入前两种情况之一。为简化计算，第三种情况可以合并入前两种情况之一。本讲稿第十四页，共三十八页区间消去法原理：搜索区间确定之后，采用区间消去法，区间消去法原理：搜索区间确定之后，采用区间消去法，选取计算点选取计算点计算计算函数值函数值并比较它们的大小，并比较它们的大小，消去不可能包含消去不可能包含极小点的区间，逐步缩短搜索
8、区间，从而找到极小点的数值近极小点的区间，逐步缩短搜索区间，从而找到极小点的数值近似解。似解。1近似黄金分割法（近似黄金分割法（0.618方法）方法）关键：如何不断消去部分区间而不丢掉极小点？关键：如何不断消去部分区间而不丢掉极小点？任何保证区间缩小率？任何保证区间缩小率？本讲稿第十五页，共三十八页1b要求插入点要求插入点a1、b1的位置相对于区间的位置相对于区间a,b两端点具有对称性。两端点具有对称性。除对称要求外，黄金分割法还要求在保留下来的区间再插入一点除对称要求外，黄金分割法还要求在保留下来的区间再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。所形成的区间新三段，与原
9、来区间的三段具有相同的比例分布。1近似黄金分割法（近似黄金分割法（0.618方法）方法）本讲稿第十六页，共三十八页1b1近似黄金分割法（近似黄金分割法（0.618方法）方法）所谓的所谓的“黄金分割黄金分割”是指将一线段分成两是指将一线段分成两段的方法，使整段长与较长段的长度比值段的方法，使整段长与较长段的长度比值等于较长段与较短段的比值，即等于较长段与较短段的比值，即本讲稿第十七页，共三十八页1近似黄金分割法（近似黄金分割法（0.618方法）方法）本讲稿第十八页，共三十八页迭代迭代 a b a1 b1 f(a1)f(b b1 1)1近似黄金分割法（近似黄金分割法（0.618方法）方法）例：对函
10、数例：对函数f(x)=x3-2x+1,当给定搜索区间当给定搜索区间0,3时，试时，试用黄金分割法求极小点。其中精度用黄金分割法求极小点。其中精度0 0 3 1.146 1.854 0.2131 3.66481 0 1.854 0.708 1.146 -0.0611 0.21312 0 1.146 0.438 0.708 0.2082 -0.06113 0.438 1.146 0.708 0.876 -0.0611 -0.07984 0.708 1.146近似最优解为近似最优解为x=0.792。本讲稿第十九页，共三十八页迭代迭代 a b a1 b1 f(a1)f(b b1 1)0 0 3 1.1
11、46 1.854 0.2131 3.66481 0 1.854 0.708 1.146 -0.0611 0.21312 0 1.146 0.438 0.708 0.2082 -0.06113 0.438 1.146 0.708 0.876 -0.0611 -0.07984 0.708 1.1461近似黄金分割法（近似黄金分割法（0.618方法）方法）本讲稿第二十页，共三十八页1近似黄金分割法（近似黄金分割法（0.618方法）方法）关于黄金分割关于黄金分割比例比例的起源大多认为来自的起源大多认为来自毕达哥拉斯毕达哥拉斯，据说在，据说在古希腊古希腊，有一天毕达哥拉斯走在街上，在经过铁匠铺前他听到铁
12、匠打铁的有一天毕达哥拉斯走在街上，在经过铁匠铺前他听到铁匠打铁的声音非常好听，于是驻足倾听。他发现声音非常好听，于是驻足倾听。他发现铁匠铁匠打铁节奏很有规律，这打铁节奏很有规律，这个声音的比例被毕达哥拉斯用个声音的比例被毕达哥拉斯用数理数理的方式表达出来，被应用在很多领域。的方式表达出来，被应用在很多领域。后来很多人专门研究过，后来很多人专门研究过，开普勒开普勒称其为称其为“神圣分割神圣分割”也有人称其为也有人称其为“金法金法”。在金字塔建成。在金字塔建成1000年后才出现毕达哥拉斯定律，可见这很年后才出现毕达哥拉斯定律，可见这很早就存在。只是不知这个谜底。早就存在。只是不知这个谜底。本讲稿第
13、二十一页，共三十八页1近似黄金分割法（近似黄金分割法（0.618方法）方法）古希腊帕特农神庙古希腊帕特农神庙 本讲稿第二十二页，共三十八页1近似黄金分割法（近似黄金分割法（0.618方法）方法）埃及金字塔埃及金字塔 本讲稿第二十三页，共三十八页1近似黄金分割法（近似黄金分割法（0.618方法）方法）故宫故宫 本讲稿第二十四页，共三十八页1近似黄金分割法（近似黄金分割法（0.618方法）方法）本讲稿第二十五页，共三十八页1近似黄金分割法（近似黄金分割法（0.618方法）方法）本讲稿第二十六页，共三十八页1近似黄金分割法（近似黄金分割法（0.618方法）方法）本讲稿第二十七页，共三十八页1近似黄金
14、分割法（近似黄金分割法（0.618方法）方法）本讲稿第二十八页，共三十八页1近似黄金分割法（近似黄金分割法（0.618方法）方法）本讲稿第二十九页，共三十八页1近似黄金分割法（近似黄金分割法（0.618方法）方法）本讲稿第三十页，共三十八页1近似黄金分割法（近似黄金分割法（0.618方法）方法）本讲稿第三十一页，共三十八页1近似黄金分割法（近似黄金分割法（0.618方法）方法）本讲稿第三十二页，共三十八页2 Newton法法考虑如下问题：考虑如下问题：其中其中 二次可微，且二次可微，且 牛顿法基本思想：用二阶泰勒展开式对函数作近似；牛顿法基本思想：用二阶泰勒展开式对函数作近似；用用g(t)的最小点作为新的探索点；的最小点作为新的探索点；当当 时（满足计算终止误差），计算结束，时（满足计算终止误差），计算结束，tk为最小为最小点近似。点近似。本讲稿第三十三页，共三十八页2 Newton法法本讲稿第三十四页，共三十八页2 Newton法法本讲稿第三十五页，共三十八页2 Newton法法本讲稿第三十六页，共三十八页2 Newton法法本讲稿第三十七页，共三十八页第第4章章 非线性规划非线性规划结束结束本讲稿第三十八页，共三十八页