管理运筹学06非线性规划课件

第六章非线性规划非线性规划问题及其数学模型极值问题凸规划一维搜索无约束极值问题约束极值问题2/6/202311.非线性规划问题及其数学模型非线性规划问题举例：

Example1：第82页例6-1

Example2：第82页例6-2非线性规划问题的数学模型非线性规划问题的图示2/6/202321.1非线性规划问题举例Example1:某商店经销A、B两种产品，售价分别为20和380元。据统计，售出一件A产品的平均时间为0.5小时，而售出一件B产品的平均时间与其销售的数量成正比，表达式为1+0.2n。若该商店总的营业时间为1000小时，试确定使其营业额最大的营业计划。

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

2/6/202351.1非线性规划问题举例

a11…a1nJ=……,

an1…ann其中：aij是第i个属性与第j个属性的重要性之比。2/6/202361.1非线性规划问题举例现需要从判断矩阵求出各属性的权重，为使求出的权重向量W在最小二乘意义上能最好地反映判断矩阵的估计，由aij=wi/wj可得：2/6/202371.2非线性规划问题的数学模型由于，,“≤”不等式仅乘“-1”即可转换为“≥”不等式；因此上述数学模型具有一般意义。又因为等价于两个不等式：;,因此非线性规划的数学模型也可以表示为：2/6/202391.3非线性规划问题的图示若令其目标函数f(X)=c,目标函数成为一条曲线或一张曲面；通常称为等值线或等值面。此例，若设f(X)=2和f(X)=4可得两个圆形等值线，见下图：2/6/2023101.3非线性规划问题的图示由左图可见,等值线f(X)=2和约束条件直线6-6相切，切点D即为此问题的最优解，X*=(3,3)，其目标函数值f(X*)=2。3232066x1x2f(X)=4f(X)=22/6/2023111.3非线性规划问题的图示[注]线性规划存在最优解，最优解只能在其可行域的边缘上（特别能在可行域的顶点上）得到；而非线性规划的最优解（如果存在）则可能在可行域的任意一点上得到。2/6/2023132.极值问题局部极值与全局极值极值点存在的条件凸函数和凹函数凸函数的性质函数凸性的判定2/6/2023142.1局部极值与全局极值线性规划最优解全局最优解非线性规划局部最优解未必全局最优2/6/202315全局极值对于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*)为严格全局极小值。2/6/2023172.2极值点存在的条件必要条件设R是En上的一个开集，f(X)在R上有一阶连续偏导数，且在点取得局部极值，则必有

或2/6/202318必要条件为函数f(X)在X*点处的梯度。由数学分析可知，的方向为X*点处等值面（等值线）的法线方向，沿这一方向函数值增加最快，如图所示。2/6/202319充分条件充分条件设R是En上的一个开集，f(X)在R上具有二阶连续偏导数，对于，若且对任何非零向量有：则X*为f(X)的严格局部极小点。称为f(X)在点X*处的海赛（Hesse）矩阵。2/6/202321充分条件2/6/202322充分条件（充分条件）等价于：如果函数f(X)在X*点的梯度为零且海赛矩阵正定，则X*为函数f(X)的严格局部极小点。2/6/202323凸函数和凹函数示意图X(1)X(2)f(X)X凸函数X(1)X(2)f(X)X凹函数2/6/202325非凹非凸函数示意图f(X(2))f(X(1))X(1)+(1-)X(2)X(1)X(2)f(X)X非凸非凹函数2/6/2023262.5函数凸性的判定根据凸函数的定义进行判定；根据一阶条件进行判定；根据二阶条件进行判定；2/6/202329一阶条件设R为En上的开凸集，f(X)在R上具有一阶连续偏导数，则f(X)为R上的凸函数的充分必要条件是，对于属于R的任意两个不同点X(1)和X(2)恒有：2/6/202330二阶条件设R为En上的开凸集，f(X)在R上具有二阶连续偏导数，则f(X)为R上的凸函数的充分必要条件是：f(X)的海赛矩阵H(X)在R上处处半正定（ZTH(X)Z≥0）。2/6/2023313.凸规划凸规划的定义下降迭代算法2/6/2023323.1凸规划的定义考虑非线性规划：假定其中f(X)为凸函数，gj(X)为凹函数（-gj(X)为凸函数），这样的非线性规划称为凸规划。2/6/2023333.1凸规划的定义凸规划：可行域是凸集、局部最优即为全局最优；若为严格凸函数，最优解若存在必唯一。2/6/2023343.2下降迭代算法基本思想：给定一个初始估计解X(0)，然后按某种规则（即算法）找出一个比X(0)更好的解X(1)，如此递推即可得到一个解的序列{X(k)}，若这一解的序列有极限X*，即则称X*为最优解。2/6/2023353.2下降迭代算法基本问题：递推步骤的有限性，一般说很难得到精确解，当满足所要求的精度时即可停止迭代而得到一个近似解。2/6/2023363.2下降迭代算法下降算法：若产生的解序列{X(k)}能使目标函数f(X(k))逐步减少，就称此算法为下降算法。“下降”的要求很容易满足，因此它包括了很多具体的算法。2/6/2023373.2下降迭代算法若从X(k)出发沿任何方向移动都不能使目标函数值下降，则X(k)是一个局部极小点；若从X(k)出发至少存在一个方向能使目标函数下降，则可选定某一下降方向P(k)，沿这一方向前进一步，得到下一个点X(k+1)。沿P(k)方向前进一步相当于在射线上选定新的点,其中P(k)为搜索方向，为步长。2/6/2023383.2下降迭代算法确定搜索方向P(k)是关键的一步，各种算法的区别主要在于确定搜索方向P(k)的方法不同。步长的选定一般都是以使目标函数在搜索方向上下降最多为依据的，称为最佳步长，即沿射线求目标函数的极小值由于确定步长是通过求以为变量的一元函数的极小点来实现的，故称这一过程为一维搜索。2/6/2023394.一维搜索一维搜索即沿某一已知方向求目标函数的极小点，一维搜索的方法很多，在此只介绍斐波那契法和黄金分割法。2/6/2023404.1斐波那契法

一维搜索过程是建立在一个被称为斐波那契数序列基础上的。斐波那契数序列是具有如下递推关系的无穷序列：F0=F1=1Fn=Fn-1+Fn-2，n=2,3,…n012345678Fn1123581321342/6/2023414.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]内。2/6/2023424.1斐波那契法f(x)oaa1

x*b1bx图(1)2/6/2023434.1斐波那契法f(x)oaa1

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

，可以证明这两个数列收敛于同一个极限。2/6/2023494.2黄金分割法以不变的区间缩减率，代替斐波那契法每次不同的缩减率，就得到了黄金分割法。黄金分割法是一种等速对称的搜索方法，每次试点均取在区间长度的倍和倍处。2/6/202350黄金分割法例(第92页例6-7)例6-7：求二次函数f(x)=3x2-21x-1在区间[0,20]上的极小点，要求缩短后的区间长度不大于原区间长