非线性规划管理运筹学李军

2024/11/511.非线性规划问题及其数学模型非线性规划问题举例：

Example1：第82页例6-1

Example2：第82页例6-2非线性规划问题的数学模型非线性规划问题的图示2024/11/521.1非线性规划问题举例Example1:

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

2024/11/531.1非线性规划问题举例[解]设x1和x2分别为商店经销A、B两种产品的件数，于是有如下数学模型：

2024/11/541.1非线性规划问题举例Example2:

在层次分析（AnalyticHierarchyProcess,简记为AHP）中，为进行多属性的综合评价，需要确定每个属性的相对重要性，即它们的权重。为此，将各属性进行两两比较，从而得出如下判断矩阵：

2024/11/551.1非线性规划问题举例

a11…a1nJ=……,

an1…ann其中：aij是第i个属性与第j个属性的重要性之比。2024/11/561.1非线性规划问题举例

现需要从判断矩阵求出各属性的权重，为使求出的权重向量W在最小二乘意义上能最好地反映判断矩阵的估计，由aij=wi/wj可得：2024/11/571.2非线性规划问题的数学模型s.t.

其中是n维欧氏空间En中的向量点。2024/11/581.2非线性规划问题的数学模型

由于，,“≤”不等式仅乘“-1”即可转换为“≥”不等式；因此上述数学模型具有一般意义。又因为等价于两个不等式：;,因此非线性规划的数学模型也可以表示为：2024/11/591.3非线性规划问题的图示

若令其目标函数f(X)=c,目标函数成为一条曲线或一张曲面；通常称为等值线或等值面。此例，若设f(X)=2和f(X)=4可得两个圆形等值线，见下图：2024/11/5101.3非线性规划问题的图示

由左图可见,等值线f(X)=2和约束条件直线6-6相切，切点D即为此问题的最优解，X*=(3,3)，其目标函数值f(X*)=2。3232066x1x2f(X)=4f(X)=22024/11/5111.3非线性规划问题的图示

在此例中，约束对最优解发生了影响，若以代替原约束，则非线性规划的最优解是，即图中的C点，此时。由于最优点位于可行域的内部，故事实上约束并未发挥作用，问题相当一个无约束极值问题。2024/11/5121.3非线性规划问题的图示[注]线性规划存在最优解，最优解只能在其可行域的边缘上（特别能在可行域的顶点上）得到；而非线性规划的最优解（如果存在）则可能在可行域的任意一点上得到。2024/11/5132.极值问题局部极值与全局极值极值点存在的条件凸函数和凹函数凸函数的性质函数凸性的判定2024/11/5142.1局部极值与全局极值线性规划最优解全局最优解非线性规划局部最优解未必全局最优2024/11/515局部极值对于

X-X*<均有不等式f(X)≥f(X*)，则称X*为f(X)在R上的局部极小点，f(X*)为局部极小值；对于

X-X*<

均有不等式f(X)>f(X*)，则称X*为f(X)在R上的严格局部极小点，f(X*)为严格局部极小值；2024/11/516全局极值对于X,X*∈R均有不等式f(X)≥f(X*)，则称X*为f(X)在R上的全局极小点，f(X*)为全局极小值；对于X,X*∈R均有不等式f(X)>f(X*)，则称X*为f(X)在R上的严格全局极小点，f(X*)为严格全局极小值。2024/11/5172.2极值点存在的条件必要条件设R是En上的一个开集，f(X)在R上有一阶连续偏导数，且在点取得局部极值，则必有

或2024/11/518必要条件

为函数f(X)在X*点处的梯度。由数学分析可知，的方向为X*点处等值面（等值线）的法线方向，沿这一方向函数值增加最快，如图所示。2024/11/519必要条件

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

2024/11/520充分条件充分条件设R是En上的一个开集，f(X)在R上具有二阶连续偏导数，对于，若且对任何非零向量有：则X*为f(X)的严格局部极小点。称为f(X)在点X*处的海赛（Hesse）矩阵。2024/11/521充分条件2024/11/522充分条件（充分条件）等价于：如果函数f(X)在X*点的梯度为零且海赛矩阵正定，则X*为函数f(X)的严格局部极小点。2024/11/5232.3凸函数和凹函数

设f(X)为定义在En中某一凸集R上的函数，若对于任何实数

（0<

<1）以及R中的任意两点X(1)和X(2)

，恒有：则称f(X)为定义在R上的凸函数；若上式为严格不等式，则称f(X)为定义在R上的严格凸函数。改变不等号的方向，即可得到凹函数和严格凹函数的定义。2024/11/524凸函数和凹函数示意图X(1)X(2)f(X)X凸函数X(1)X(2)f(X)X凹函数2024/11/525非凹非凸函数示意图f(X(2))f(X(1))

X(1)+(1-

)X(2)X(1)X(2)f(X)X非凸非凹函数2024/11/5262.4凸函数的性质设f(X)为定义在凸集R上的凸函数，则对于任意实数

≥0

,函数

f(X)也是定义在R上的凸函数。设f1(X)和f

2(X)为定义在凸集R上的两个凸函数，则其和f(X)=f1(X)+f

2(X)仍然是定义在R上的凸函数。设f(X)为定义在凸集R上的凸函数，则对于任意实数

,集合S

={X|X∈R,f(X)≤

}是凸集。2024/11/5272.4凸函数的性质设f(X)为定义在凸集R上的凸函数，则它的任一极小点就是它在R上的最小点（全局极小点）；而且它的极小点形成一个凸集。设f(X)为定义在凸集R上的可微凸函数，若它存在点X*∈R，使得对于所有的X∈R有▽f(X*)T(X-X*)≥0，则X*是f(X)在R上的最小点（全局极小点）。2024/11/5282.5函数凸性的判定根据凸函数的定义进行判定；根据一阶条件进行判定；根据二阶条件进行判定；2024/11/529一阶条件

设R为En上的开凸集，f(X)在R上具有一阶连续偏导数，则f(X)为R上的凸函数的充分必要条件是，对于属于R的任意两个不同点X(1)和X(2)恒有：2024/11/530二阶条件

设R为En上的开凸集，f(X)在R上具有二阶连续偏导数，则f(X)为R上的凸函数的充分必要条件是：f(X)的海赛矩阵H(X)在R上处处半正定（ZTH(X)Z≥0

）。2024/11/5313.凸规划凸规划的定义下降迭代算法2024/11/5323.1凸规划的定义

考虑非线性规划：假定其中f(X)为凸函数，gj(X)为凹函数（-gj(X)为凸函数），这样的非线性规划称为凸规划。2024/11/5333.1凸规划的定义

凸规划：可行域是凸集、局部最优即为全局最优；若为严格凸函数，最优解若存在必唯一。2024/11/5343.2下降迭代算法基本思想：给定一个初始估计解X(0)，然后按某种规则（即算法）找出一个比X(0)更好的解X(1)

，如此递推即可得到一个解的序列{X(k)}，若这一解的序列有极限X*

，即则称X*为最优解。2024/11/5353.2下降迭代算法基本问题：递推步骤的有限性，一般说很难得到精确解，当满足所要求的精度时即可停止迭代而得到一个近似解。2024/11/5363.2下降迭代算法下降算法：若产生的解序列{X(k)}能使目标函数f(X(k))逐步减少，就称此算法为下降算法。“下降”的要求很容易满足，因此它包括了很多具体的算法。2024/11/5373.2下降迭代算法若从X(k)出发沿任何方向移动都不能使目标函数值下降，则X(k)是一个局部极小点；若从X(k)出发至少存在一个方向能使目标函数下降，则可选定某一下降方向P(k)

，沿这一方向前进一步，得到下一个点X(k+1)

。沿P(k)方向前进一步相当于在射线上选定新的点,其中P(k)为搜索方向，为步长。2024/11/5383.2下降迭代算法确定搜索方向P(k)是关键的一步，各种算法的区别主要在于确定搜索方向P(k)的方法不同。步长的选定一般都是以使目标函数在搜索方向上下降最多为依据的，称为最佳步长，即沿射线求目标函数的极小值由于确定步长是通过求以为变量的一元函数的极小点来实现的，故称这一过程为一维搜索。2024/11/5394.一维搜索

一维搜索即沿某一已知方向求目标函数的极小点，一维搜索的方法很多，在此只介绍斐波那契法和黄金分割法。2024/11/5404.1斐波那契法

一维搜索过程是建立在一个被称为斐波那契数序列基础上的。斐波那契数序列是具有如下递推关系的无穷序列：F0=F1=1Fn=Fn-1+Fn-2，n=2,3,…n012345678Fn1123581321342024/11/5414.1斐波那契法斐波那契法成功地实现了单峰函数极值范围的缩减。设某一单峰函数在[a,b]上有一极小点x*，在此区间内任意取两点a1和b1，使a1<b1

，计算其函数值可能出现以下两种情况：

(1)f(a1)＜

f(b1)，如图(1)所示；此时极小点x*必在期间[a,b1]内。

(2)f(a1)≥

f(b1)，如图(2)所示；此时极小点x*必在期间[a1,b]内。2024/11/5424.1斐波那契法f(x)oaa1

x*b1bx图(1)2024/11/5434.1斐波那契法f(x)oaa1

x*b1bx图(2)2024/11/5444.1斐波那契法只要在区间[a,b]内任意取两点a1和b1，使a1<b1并计算其函数值加以比较，就可以把搜索区间[a,b]缩减成[a,b1]或[a1,b]。若要继续缩小搜索期间[a,b1]或[a1,b]，只需在期间内再取一点算出其函数值并与f(a1)或f(b1)加以比较即可。由此可见，计算函数的次数越多，搜索期间就缩得越小，即区间的缩短率（缩短后的区间长度与原区间长度之比）与函数的计算次数有关。2024/11/545斐波那契法的具体步骤1.根据相对精度或绝对精度，确定试点个数；2.确定两个试点的位置a1、b1（对称搜索）；Fn-2Fn-1aba1b1Fn-2Fn-12024/11/546斐波那契法的具体步骤3.计算函数值和并比较其大小，从而缩减搜索区间；4.重复2、3两步，直到得到近似最小点。2024/11/547斐波那契法例(第90页例6-6)例6-6：用斐波那契法求函数f(x)=3x2-12x+10的近似极小点和极小值，要求缩短后的区间不大于初始区间[1,4]的0.05倍。2024/11/5484.2黄金分割法

用斐波那契法以