非线性规划(教案).docxVIP

1

非线性规划

线性规划及其扩展问题的约束条件和目标函数都是关于决策变量的一次函数。虽然大量的实际问题可以简化为线性规划及其扩展问题来求解，但是还有相当多的问题很难用线性函数加以描述。如果目标函数或约束条件中包含有非线性函数，就称这样的规划问题为非线性规划问题。由于人们对实际问题解的精度要求越来越高，非线性规划自20世纪70年代以来得到了长足的发展；目前，已成为运筹学的一个重要分

支，在管理科学、最优设计、系统控制等许多领域得到了广泛的应用。

一般来讲，非线性规划问题的求解要比线性规划问题的求解困难得多；而且也不象线性规划问题那样具有一种通用的求解方法(单纯形法)。非线性规划没有能够适应所有问题的一般求解方法，各种方法都

只能在其特定的范围内发挥作用。

本章在简要介绍非线性规划基本概念和一维有哪些信誉好的足球投注网站的基础上，重点介绍无约束极值问题和约束极值问题

的求解方法。

§1非线性规划的数学模型

1.1非线性规划问题

[例1]某商店经销A、B两种产品，售价分别为20和380元。据统计，售出一件A产品的平均时间为0.5小时，而售出一件B产品的平均时间与其销售的数量成正比，表达式为1+0.2n。若该商店总的营

业时间为1000小时，试确定使其营业额最大的营业计划。

解：设x?和x?分别代表商店经销A、B两种产品的件数，于是有如下数学模型：

maxf(x)=20x?+38Qx?

1.2非线性规划问题的数学模型

同线性规划问题的数学模型一样，非线性规划问题的数学模型可以具有不同的形式；但由于我们可以

自由地实现不同形式之间的转换，因此我们可以用如下一般形式来加以描述：

minf(X),X∈E”

其中X=(xj,x?,…,x,)′是n维欧氏空间E”中的向量点。

2

又因h(X)=0等价于两个不等式：

h(X)≥0;-h(X)≥0

因此非线性规划的数学模型也可以表示为：

1.3非线性规划问题的图示

[例3]求解下述非线性规划问题

若令其目标函数f(X)=c,目标函数成为一条曲线或一张曲面；通常称为等值线或等值面。此例，

若设f(X)=2和f(X)=4可得两个圆形等值线，见图1。

X?

图1图解示意图

由图1可见，等值线f(X)=2和约束条件直线6-6相切，切点D即为此问题的最优解，X*=(3,3)

其目标函数值f(X*)=2。

在此例中，约束h(X)=x?+x?-6=0对最优解发生了影响，若以h(X)=x?+x?-6≤0

代替原来的约束h(X)=x?+x?-6=0,则新的非线性规划的最优解变为X*=(2,2),即图1中的C点，

此时f(X)=0。由于此最优点位于可行域的内部，故事实上约束

3

h(X)=x?+x?-6≤0

并未发挥约束作用，问题相当于一个无约束极值问题。

注意：线性规划存在最优解，最优解只能在其可行域的边缘上(特别能在可行域的顶点上)得到；而

非线性规划的最优解(如果存在)则可能在可行域的任意一点上得到，并非仅局限在边缘上。

§2极值问题

2-1局部极值与全局极值

因为线性规划的目标函数和约束条件都是线性函数，所以其可行域是凸集，因此求得的最优解就一定是整个可行域上的全局最优解。非线性规划则不然，局部最优解未必就一定是全局最优解。下面就局部和

全局极值问题给出如下一些定义：

(1)对于|X-X*|ε均有不等式f(X)≥f(X*),则称X*为f(X)在R上的局部极小点，

f(X*)为局部极小值；

(2)对于|X-X*|ε均有不等式f(X)f(X*),则称X*为f(X)在R上的严格局部极小点，

f(X*)为严格局部极小值；

(3)对于X,X*∈R均有不等式f(X)≥f(X*),

则称X*为f(X)在R上的全局极小点，f(X*)

为全局极小值；

(4)对于X,X*∈R均有不等式f(X)f(X*),

则称X*为f(X)在R上的严格全局极小点，

f(X*)为严格全局极小值。

2-2极值点存在的条件

[定理1(必要条件)]设R是E”上的一个开集，f(X)在R上有一阶连续偏导数，且在点X*∈R取

得局部极值，则必有

(1)

或

▽f(X*)=0(2)

式(2

式(2)中

由数学分析可知，▽f(X*)的方向为X*点处等值面(等值线)的法线方向，沿这一方向函数值增加

最快，见图2。

4

图2梯度方向示意图

满足的点称为平稳点或驻点。极值点一定是驻点，