运筹学-非线性规划(一)(名校讲义)

运筹学-非线性规划(一)(名校讲义).ppt§1非线性规划问题的现实来源－问题的提出

（1）

在规划模型中，如果在目标函数或在约束条件中有一个或多个是自变量的非线性函数，则称这种规划为非线性规划问题。就现实问题，严格讲来，基本属于非线性规划模型。

现举例说明非线性规划的现实背景。[例4-1]某公司经营两种设备。第一种设备每件售价为30元，第二种设备每件售价为450元。且知，售出第一、二种设备分别需时为每件约0.5小时和（2+0.25x2）小时，其中x2为第二种设备售出数量。公司的总营业时间为800小时。

求：公司为获取最大营业额（销售额）的最优营业计划。

§1非线性规划问题的现实来源－问题的提出

（2）

[解]设公司应经营销售第一、二种设备数额分别为x1件和x2件，追求的目标为最大销售额，即：目标函数f(X)=30x1+450x2取极大由于营业时间有限，必须满足：0.5x1+(2+0.25x2)x2≤800当然，销售设备数不会为负数，即：x1≥0，x2≥0综合得出该问题数学模型为：

目标函数max：f(X)=30x1+450x2约束条件0.5x1+2x2+0.25x22≤800

x1≥0，x2≥0§2非线性规划的数学模型及特点

（1）

非线性规划的数学模型通常表示成以下形式。minf(X)

hi(X)=0i=1，2，…，m

gj(X)≥0j=1，2，…，l[例4-3]求解下述非线性规划minf(X)=(x1－2)2+(x2－2)2

h(X)=x1+x2－6=0 显然，与直线AB相切的点必为最优解。图4-1(a)中的D点即为最优点，此时目标函数值为：f(X*)=2，x1*=x*2=3Af(X)=4f(X)=2x1x26320236BCD图4-1(a)§2非线性规划的数学模型及特点

（2）[例4-4]非线性规划为minf(X)=(x1－2)2+(x2－2)2

h(X)=x1+x2－6≤0显然，此时的最优解为C点(x1*=x2*=2，f(X*)=0)，该点落在可行或内部，其边界约束失去作用。从前面例中看出，非线性规划的最优解（如果存在）可在其可行域上任一点达到。因而，非线性规划数学模型可以没有约束条件，即存在无约束最优化问题。

§2非线性规划的数学模型及特点

（3）§3解和算法的基本性质

（1）

1．极小点、凸集及其关系①极小点定义i)对于X*

Q，如果存在一个

>0，使所有与X*的距离小于

的X

Q（即X

Q，且|X－X*|<

）都满足不等式f(X)≥f(X*)，则称X*为f在Q上的一个相对极小点或局部极小点。若对于所有X

Q，X≠X*且与X*距离小于

，有f(X)>f(X*)，则称X*为f在Q上的一个严格相对极小点。§3解和算法的基本性质

（2）

ii)点X*

Q，如果对于所有X

Q成立f(X)≥f(X*)，则称X*为f在Q上的全局极小点。同样，若对于所有X

Q，X≠X*时，存在f(X)>f(X*)，则称X*为f在Q上的严格全局极小点。尽管问题的提法往往求全局极小点，然而，无论从理论上或从计算观点看，实践现实性表明我们必须以很多情形上满足一个相对极小点。当然，对于凸规划，这二者是统一的。

§3解和算法的基本性质

（3）

②相对极小点的判定可行方向概念：沿给定方向作离开该点运动，若运动轨迹在可行域内，则称该运动方向为可行方向（通常用d表示）。若从某点开始，沿任一可行方向运动（运动距离很小）都不能使目标函数减少，则据定义，知该点即为相对极小点。i)判定极小点的必要条件（证明从略）

§3解和算法的基本性质

（4）

命题1（一阶必要条件）：设

是En子集，f(X)

C1(C1表明存在一阶导数)是

上函数，若X*是f(

X)在

上一个相对极小点，则对于任一X*的可行方向d

En必有▽f(X*)·d≥0。（其中，▽f(X*)表示函数f(

X)的一阶梯度或导数）命题2（二阶必要条件——有约束情况）：设

是En的一个子集，且f(

X)

Ｃ2（Ｃ2表明存在二阶导数）是

上的一个函数。若X*是f(

X)在

上的一个相对极小点。则对于任一X*处的可行方向d

Ｅn有：A)▽f(X*)·d≥0B)▽f(X*)·d=0，则必有dT·▽2f(X*)·d≥0▽2f(

X)表示f(

X)的第二阶梯度或二阶导数，又称Hess或海森阵，亦可用H或F表示。

§3解和算法的基本性质

（5）

命题3（二阶必要条件——无约束情况）：设X*是集合

的内点，且X*是函数f(X)

C2在

上一个相对极小点。则：A)▽f(X*)=0B)对于所有d，则dT▽2f(X*)·d≥0ii)判断极小点的充分条件命题（二阶充分条件——无约束）：设f(X)

C2是定义在以X*为内点的一个区域上的函数，若A)▽f(X*)=0B)Hess阵H(X*)正定（或负定）则X*是f(X)的严格极小点（或极大点）

§3解和算法的基本性质

（6）

iii)极小点的充分必要条件——无约束情形。（略）③凸函数与凹函数i)定义：·凸集：若在X集合

中，任意两点之联线都落在该集合

内，则称该集合

为X的凸集。·凸函数：定义在凸集

上的函数f(X)称为凸函数，条件是对于每一对x1，x2

及每一个a，0≤a≤1存在：f(ax1+(1－a)x2)≤af(x1)+1(1－a)f(x2)

上式中，若≤变为<，则称为严格凸函数。

§3解和算法的基本性质

（7）凸函数在2维空间的形状象一口锅的纵剖面，参见图4-2。·凹函数：定义在凸集

上的函数g(X)称为凹函数，条件是函数f(X)=－g(X)是凸的。若

－g(X)是严格凸的，则g(X)是严格凹的，因此凸与凹是严格对应的，以后就只研究凸函数即可。

(a)严格凸x凸x非凸x图4-2(b)(c)§3解和算法的基本性质

（8）

ii）有关性质（凸函数性质）·设f1(X)，f2(X)是凸集

上的凸函数，则函数f1(X)+f2(X)在

上也是凸函数。·设f(X)是凸集

上的凸函数，则对任意的a≥0，函数af(X)是凸的。·设f(X)是凸集

上的凸函数，对每一个实数C，则集合

C＝{x：x

，f(X)

C}是凸集。iii)凸函数的判定（略）

§3解和算法的基本性质

（9）

④凸规划定义：已知非线性规划：minf(X)gj(X)≥0若f(X)为凸函数，gj(X)为凹函数，则称该规划为凸规划。凸规划的局部极值点即为全局极值点。线性规划为凸规划。2．下降算法的收敛性问题（定性分析）（略）

§4非线性规划求解方法分类（1）

1．一维最优化①斐波那契（Fibonacci）法②黄金分割法（0.618法）③牛顿法（切线法）④抛物线逼近法⑤成功和失败法§4非线性规划求解方法分类（2）

2．