【7A文】生产运筹-非线性规划的基本概念.ppt

《【7A文】生产运筹-非线性规划的基本概念.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第五讲非线性规划的基本概念非线性规划问题非线性规划数学模型非线性规划的图解法梯度、Hesse矩阵、Jacobi阵凸函数和凸规划解非线性规划方法概述一维最优化在科学管理和其他领域中，大量应用问题可以归结为线性规划问题，但是，也有另外许多问题，其目标函数和（或）约束条件很难用线性函数表达。如果目标函数和（或）约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划。非线性规划是运筹学的重要分支之一。最近30多年来发展很快，不断提出各种算法，而其应用范围也越来越广泛。比如在各种预报、管理科学、最优设计、质量控制、系统控制等领域得到广泛且不短深入的应用。一般来

2、说，求解非线性规划问题比线性规划问题困难得多。而且，也不象线性规划那样有单纯形法这一通用的方法。非线性规划的各种算法大都有自己特定的使用范围，都有一定的局限性。到目前为止还没有适合于各种问题的一般算法，这是需要深入研究的一个领域。我们只是对一些模型及应用作简单介绍。非线性规划问题举例例一：选址问题设有个市场，第个市场位置为，它对某种货物的需要量为。现计划建立个仓库，第个仓库的存储容量为试确定仓库的位置，使各仓库对各市场的运输量与路程乘积之和为最小。设第个仓库的位置为第个仓库到第个市场的货物供应量为则第个仓库到第个市场的距离为目标函数为约束条件为（1）每个仓库向各市

3、场提供的货物量之和不能超过它的存储容量。（2）每个市场从各仓库得到的货物量之和应等于它的需要量。（3）运输量不能为负数例2.木梁设计问题把圆形木材加工成矩形横截面的木梁，要求木梁高度不超过，横截面的惯性矩（高度的平方宽度）不小于，而且高度介于宽度与4倍宽度之间。问如何确定木梁尺寸可使木梁成本最小.设矩形横截面的高度为，宽度为，则圆形木材的半径而木梁长度无法改变，因此成本只与圆形木材的横截面积有关。目标函数为约束条件为（1）数学规划模型的一般形式：其中,简记为MP(MathematicalProgramming)2非线性规划问题的数学模型（2）简记形式：引入向量函数

4、符号：（3）数学规划问题的分类：若为线性函数，即为线性规划(LP)；若至少一个为非线性,即为非线性规划(NLP)；对于非线性规划，若没有,即X=Rn,称为无约束非线性规划或无约束最优化问题；否则称为约束非线性规划或约束最优化问题。（4）可行域和可行解：称为MP问题的约束集或可行域。若x在X内，称x为MP的可行解或者可行点。（5）最优解和极小点对于非线性规划（MP），若，并且有如果有定义:如果有定义则称x*是(MP)的局部最优解或局部极小解,例1：用图解法求解minf(x)=(x1－2)2+(x2－2)2s.t.h(x)=x1+x2-6=0x1x2066223

5、3最优解x*=(3，3)T可行解x=(1.5，4.5)T最优级解即为最小圆的半径：f(x)=(x1－2)2+(x2－2)2=23非线性规划问题的图解法对二维最优化问题，总可以用图解法求解，而对三维或高维问题，已不便在平面上作图，此法失效。x1x206622D可行域最优解x*=(2，2)T例2：用图解法求解minf(x)=(x1-2)2+(x2-2)2s.t.h(x)=x1+x2-6≤03非线性规划问题的图解法最优级解即为最小圆的半径：f(x)=(x1-2)2+(x2-2)2=0解：①先画出等式约束曲线的图形——抛物线，例3：用图解法求解②再画出不等式约束区域，③最

6、后画出目标函数等值线，所以最优解x*=(4,1),最优值minf(x)=4.4梯度、Hesse矩阵、Jacobi阵(1)二次函数一般形式:矩阵形式:二次型:矩阵A的正定性:正定、半正定、负定、不定。其中A＝AT。二次型的正定性:正定、半正定、负定、不定。（2）梯度定义：f(x)是定义在En上的可微函数。f(x)的n个偏导数为分量的向量称为f(x)的梯度.性质：设f(x)在定义域内有连续偏导数，即有连续梯度，则梯度有以下两个重要性质：性质一函数在某点的梯度不为零，则该梯度方向必与过该点的等值面垂直;性质二梯度方向是函数具有最大变化率的方向（负梯度方向也叫最速下降方向

7、）。解：由于例：试求目标函数在点x=[0,1]T处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。则函数在x=[0,1]T处的最速下降方向是这个方向上的单位向量是：解：由于例：试求目标函数在点x=[0,1]T处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。新点是：函数值：几个常用的梯度公式：（3）Hesse矩阵多元函数f(x)关于x的二阶导数，称为f(x)的Hesse矩阵.当f(x)的所有二阶偏导数连续时,即Hesse矩阵是对称的.时，几个常用Hessian公式：（4）Jacobi矩阵向量变量值函数：向量值函数g(x)在点x0

8、处的Jac