第四章非线性规划精选PPT.ppt

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