数模(非线性规划模型).ppt

《数模(非线性规划模型).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1数学模型电子教案重庆邮电大学数理学院沈世云2第四章非线性规划一、非线性规划引例线性规划和整数规划它们的目标函数和约束条件都是自变量的线性函数，在实际中还有大量的问题，其目标函数或约束条件很难用线性函数来表示。如果目标函数或约束条件中含有非线性函数，则称这种规划问题为非线性规划问题。先看两个实例。问题1容器设计问题问题提出某公司生产贮藏用容器，订货合同要求该公司制造一种敞口的长方体容器，容积为12立方米，该容器的底为正方形，容器总重量不超过68公斤。已知用作容器四壁的材料为每平方米10元，重3公斤；用作容器底的材料每平方米20元，

2、重2公斤。试问制造该容器所需的最小费用是多少？3模型建立设该容器的底边长和高分别为则问题的数学模型为45定义如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题．二非现性规划的基本概念一般形式:（1）其中，是定义在En上的实值函数，简记:其它情况:求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式．6定义1把满足问题（1）中条件的解称为可行解（或可行点），所有可行点的集合称为可行集（或可行域）．记为D．即问题(1)可简记为．定义2对于问题(1)，设，若存在,使得对一切，且

3、，都有，则称X*是f(X)在D上的局部极小值点（局部最优解）．特别地当时，若，则称X*是f(X)在D上的严格局部极小值点（严格局部最优解）．定义3对于问题(1),设,对任意的,都有则称X*是f(X)在D上的全局极小值点（全局最优解）．特别地当时，若，则称X*是f(X)在D上的严格全局极小值点（严格全局最优解）．7定义如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题．非现性规划的基本概念一般形式:（1）其中，是定义在En上的实值函数，简记:其它情况:求目标函数的最大值或约束条件为小于等于零的情况，都可

4、通过取其相反数化为上述一般形式．8定义1把满足问题（1）中条件的解称为可行解（或可行点），所有可行点的集合称为可行集（或可行域）．记为D．即问题(1)可简记为．定义2对于问题(1)，设，若存在,使得对一切，且，都有，则称X*是f(X)在D上的局部极小值点（局部最优解）．特别地当时，若，则称X*是f(X)在D上的严格局部极小值点（严格局部最优解）．定义3对于问题(1),设,对任意的,都有则称X*是f(X)在D上的全局极小值点（全局最优解）．特别地当时，若，则称X*是f(X)在D上的严格全局极小值点（严格全局最优解）．9三.非线性规划

5、的图解法10三角形表示的是可行域。同心圆表示的是目标函数的等值线。最优解为（1/2，1/2）最优值为1/2问题：(1/2,1/2)是整体的还是局部的？是严格的还是非严格的？1/21/2112、非线性规划方法概述微分学方法的局限性：实际的问题中，函数可能是不连续或者不可微的。需要解复杂的方程组，而方程组到目前仍没有有效的算法。实际的问题可能含有不等式约束，微分学方法不易处理。12数值方法的基本思路：迭代给定初始点x0根据x0,依次迭代产生点列{xk}{xk}的最后一点为最优解{xk}有限{xk}无限{xk}收敛于最优解13迭代格式x

6、kxk+1pk称pk为第k轮搜索方向，tk为第k轮沿pk方向的步长。产生tk和pk的不同方法，形成了不同的算法。14定义：下降方向15定义解非线性规划问题，关键在于找到某个方向，使得在此方向上，目标函数得到下降，同时还是可行方向。这样的方向称为可行下降方向。16第二节凸函数和凸规划1、凸函数及其性质：定义，17定理:关于凸函数的一些结论定理:是凸集。函数f在集合S上关于c的水平集18定理n=1时几何意义：可微函数是凸的等价于切线不在函数图像上方。19202、凸规划及其性质：凸规划定义：21凸规划性质：凸规划的任一局部最优解都是它的

7、整体最优解。凸规划是以后重点讨论的一类非线性规划凸函数线性函数22第三节一维搜索方法t为实数一维搜索问题指目标函数为单变量的非线性规划问题。又称线性搜索问题。其模型为：什么叫一维搜索问题？或一般一维搜索问题有效一维搜索问题23一维搜索问题的算法分类：精确一维搜索（最优一维搜索）非精确一维搜索（可接受一维搜索）本节内容：两种精确一维搜索方法：0.618法，Newton法。两种非精确一维搜索方法：Goldstein法,Armijo法。241、0.618法（近似黄金分割法）问题：凸函数是不是单谷函数？严格凸函数是不是单谷函数

8、？单谷函数是不是凸函数？单谷函数25搜索法求解：或基本过程：给出[a,b],使得t*在[a,b]中。[a,b]称为搜索区间。迭代缩短[a,b]的长度。当[a,b]的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止。26假定