文档介绍：非线性规划
如果目标函数或约束条件中含有一个或多个是变量的非线性函数,我们称这类规划问题为非线性规划(nonlinear programming,可简记为NP)。
一般地,解非线性规划问题要比解线性规划问题困难的多,因为它不像解线性规划问题有单纯形法这一通用的方法,非线性规划目前还没有适合于各种问题的一般算法,各个方法都有自己特定的应用范围。
非线性规划的基本概念和基本原理
第一节非线性规划的数学模型
例:某金属制品厂要加工一批容积为1米3的长方形容器,按规格要求,上下底的材料为25元/m2,侧面的材料为40元/m2,试确定长、宽、高的尺寸,使这个容器的成本最低。
设容器的长为,宽为,则高为。
根据题意得:
例:某公司经营两种设备,第一种设备每件售价30元,第二种设备每件售价为450元,根据统计,,第二种设备为时,其中是第二种设备的售出数量,已知该公司在这段时间内的总营业时间为800小时,试决定使其营业额最大的营业计划。
解:设该公司计划经营第一种设备为件,第二种设备为件,根据题意得:
由这两个例子可以看出,这两个例子在高等数学中代表了两类不同类型的极值问题。例1是无条件极值;例2是有条件极值。
如果令是n维空间上的点,则一般非线性的数学模型为:
为目标函数,为约束条件,X为自变量。若某个约束条件是的不等式,不等式两边乘以“-1”。
第二节极值问题
设是定义在n维欧式空间空间上某一区域上的n元函数,其中。
对于,如果存在某一个,使得所有与的距离小于的,(即),均满足,则称为在上的局部极小点。为局部极小值。
若所有,且,有,则称为在上的严格局部极小点。为严格局部极小值。
若点,对于所有的,均满足,则称为在上的全局极小点。为全局极小值。
若对于所有,且,都有,则称为在上的严格全局极小点。为严格全局极小值。
如果将上述不等式反向,即可得到局部极大值与全局极大值的定义。
定理1:极值的必要条件
设是定义在上某一区域上的函数,是内的一点,若在处可微且取得局部极值,则必有或,上式的点称为驻点,或平稳点。即在区域内部,极点必是驻点。称为在点X处的梯度。但反过来,驻点不一定是极值点。如点(0,0)是函数的驻点,但不是极值点。
定理2:极值的充要条件
设是定义在上某一区域上的函数,且在上二次连续可微,是内的一点,若在处满足,且对任意非零向量Y,有则称在点处取得严格局部极小值。这里是在点
处的海赛矩阵。
若,则在点处取得严格局部极大值。
由定理2 看出,驻点处的海赛矩阵是正定矩阵时,函数在点处取得极小值。驻点处的海赛矩阵是负定矩阵时,函数在点处取得极大值。
定理3:设是定义在上的函数,且在点处存在二阶连续偏导数,若是的局部极小点,则,且半正定。
需要指出的是,定理2不是必要条件,定理3不是充分条件。
例:对于无约束问题
解:由于
令,得驻点,
并且,
所以
不是正定矩阵,但在点处取得最小值,即为严格局部极小点。
例:
解:由于
令,得
是不定的,因此不是极值点;是负定的,故是极大点。是正定的,故是严格极小点。
例:
解:因为,
令,得
是半正定矩阵,但在的任意邻域内,总可以取到,使得,即不是局部极小点。
例:
解:因为
令,得
是不定的,因此不是极值点;
是负定的,故是极大点。是正定的,故是严格极小点。
非线性规划的图解问题
图解法可以给人以直观概念,当只有两个自变量时,非线性规划也像线性规划一样,可以利用图解法。
例:用图解法求解非线性规划。
若令目标函数,C为某一常数。则就代表一条曲线,称为等值线或等高线。等值线与直线AB相切,切点为。
例:用图解法求解非线性规划。
解:画出目标函数的等值线
,它表示一族中心在(2,1)上的同心圆。
画出约束区域:先画,这是一条抛物线,再画不等式,所代表的约束区域。则抛物线弧ABCD为约束集。由动点A出发抛物线ABCD移动时,弧AB段,目标函数值下降,在BC段函数值上升,弧CD段,目标函数值下降,而且在D点是可行域上使目标函数值最小的点,它是全局最优点。其坐标由约束方程组可得。最优点(4,1),最优值。
第三节凸函数及其性质
一、凸函数
凸集、凸函数是研究非线性规划问题所不可缺少的内容,有关凸集的概念参见线性规划部分,这里主要介绍凸函数的概念。
定义:设是定义在n维欧式空间空间中某个凸集上的函数,若对任意一个实数以及中的任意两点和,恒有,
则称是定义在凸集上的凸函数。
若对任意一个实数以及、,恒有,则称是定义在凸集上的严格凸函数。
若上述不等式反向,称分别为上的凹函数及严格凹函数。
下面给出凸函数与凹函数的几何意义
X(1)
图下面