管理运筹学06非线性规划.ppt

《管理运筹学06非线性规划.ppt》由会员分享，可在线阅读，更多相关《管理运筹学06非线性规划.ppt（61页珍藏版）》请在三一办公上搜索。

1、2023/11/4,1,第六章 非线性规划,非线性规划问题及其数学模型极值问题凸规划一维搜索无约束极值问题约束极值问题,2023/11/4,2,1.非线性规划问题及其数学模型,非线性规划问题举例：Example1：第82页例6-1 Example2：第82页例6-2非线性规划问题的数学模型非线性规划问题的图示,2023/11/4,3,1.1 非线性规划问题举例,Example1:某商店经销A、B两种产品，售价分别为20和380元。据统计，售出一件A 产品的平均时间为0.5小时，而售出一件B 产品的平均时间与其销售的数量成正比，表达式为1+0.2n。若该商店总的营业时间为1000小时，试确定使其

2、营业额最大的营业计划。,2023/11/4,4,1.1 非线性规划问题举例,解 设x1和x2分别为商店经销A、B两种产品的件数，于是有如下数学模型：,2023/11/4,5,1.1 非线性规划问题举例,Example 2:在层次分析（Analytic Hierarchy Process,简记为 AHP）中，为进行多属性的综合评价，需要确定每个属性的相对重要性，即它们的权重。为此，将各属性进行两两比较，从而得出如下判断矩阵：,2023/11/4,6,1.1 非线性规划问题举例,a11 a1nJ=,an1 ann其中：aij是第i个属性与第j个属性的重要性之比。,2023/11/4,7,1.1 非

3、线性规划问题举例,现需要从判断矩阵求出各属性的权重，为使求出的权重向量W在最小二乘意义上能最好地反映判断矩阵的估计，由aij=wi/wj可得：,2023/11/4,8,1.2 非线性规划问题的数学模型,s.t.其中 是n维欧氏空间En中的向量点。,2023/11/4,9,1.2 非线性规划问题的数学模型,由于，,“”不等式仅乘“-1”即可转换为“”不等式；因此上述数学模型具有一般意义。又因为等价于两个不等式：;,因此非线性规划的数学模型也可以表示为：,2023/11/4,10,1.3 非线性规划问题的图示,若令其目标函数f(X)=c,目标函数成为一条曲线或一张曲面；通常称为等值线或等值面。此例

4、，若设f(X)=2和f(X)=4可得两个圆形等值线，见下图：,2023/11/4,11,1.3 非线性规划问题的图示,由左图可见,等值线f(X)=2和约束条件直线6-6相切，切点D即为此问题的最优解，X*=(3,3)，其目标函数值 f(X*)=2。,2023/11/4,12,1.3 非线性规划问题的图示,在此例中，约束 对最优解发生了影响，若以 代替原约束，则非线性规划的最优解是，即图中的C点，此时。由于最优点位于可行域的内部，故事实上约束 并未发挥作用，问题相当一个无约束极值问题。,2023/11/4,13,1.3 非线性规划问题的图示,注 线性规划存在最优解，最优解只能在其可行域的边缘上（

5、特别能在可行域的顶点上）得到；而非线性规划的最优解（如果存在）则可能在可行域的任意一点上得到。,2023/11/4,14,2.极值问题,局部极值与全局极值极值点存在的条件凸函数和凹函数凸函数的性质函数凸性的判定,2023/11/4,15,2.1 局部极值与全局极值,线性规划 最优解 全局最优解非线性规划 局部最优解 未必全局最优,2023/11/4,16,局部极值,对于X-X*f(X*)，则称 X*为 f(X)在 R上的严格局部极小点，f(X*)为严格局部极小值；,2023/11/4,17,全局极值,对于X,X*R均有不等式 f(X)f(X*)，则称 X*为 f(X)在 R上的全局极小点，f(

6、X*)为全局极小值；对于X,X*R均有不等式f(X)f(X*)，则称X*为f(X)在R上的严格全局极小点，f(X*)为严格全局极小值。,2023/11/4,18,2.2 极值点存在的条件,必要条件 设R是En上的一个开集，f(X)在R上有一阶连续偏导数，且在点 取得局部极值，则必有 或,2023/11/4,19,必要条件,为函数 f(X)在 X*点处的梯度。由数学分析可知，的方向为X*点处等值面（等值线）的法线方向，沿这一方向函数值增加最快，如图所示。,2023/11/4,20,必要条件,满足 的点称为平稳点或驻点。极值点一定是驻点；但驻点不一定是极值点。,2023/11/4,21,充分条件,

7、充分条件 设R是En上的一个开集，f(X)在R上具有二阶连续偏导数，对于，若 且对任何非零向量有：则X*为 f(X)的严格局部极小点。称为 f(X)在点X*处的海赛（Hesse）矩阵。,2023/11/4,22,充分条件,2023/11/4,23,充分条件,（充分条件）等价于：如果函数f(X)在X*点的梯度为零且海赛矩阵正定，则X*为函数f(X)的严格局部极小点。,2023/11/4,24,2.3 凸函数和凹函数,设 f(X)为定义在En中某一凸集R上的函数，若对于任何实数（01）以及R中的任意两点X(1)和X(2)，恒有：则称 f(X)为定义在R上的凸函数；若上式为严格不等式，则称 f(X)

8、为定义在R上的严格凸函数。改变不等号的方向，即可得到凹函数和严格凹函数的定义。,2023/11/4,25,凸函数和凹函数示意图,2023/11/4,26,非凹非凸函数示意图,2023/11/4,27,2.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|XR,f(X)是凸集。,2023/11/4,28,2.4 凸函数的性质,设f(X)为定义在凸集R上的

9、凸函数，则它的任一极小点就是它在R上的最小点（全局极小点）；而且它的极小点形成一个凸集。设f(X)为定义在凸集R上的可微凸函数，若它存在点X*R，使得对于所有的XR有 f(X*)T(X-X*)0，则X*是f(X)在R上的最小点（全局极小点）。,2023/11/4,29,2.5 函数凸性的判定,根据凸函数的定义进行判定；根据一阶条件进行判定；根据二阶条件进行判定；,2023/11/4,30,一阶条件,设R为En上的开凸集，f(X)在R上具有一阶连续偏导数，则f(X)为R上的凸函数的充分必要条件是，对于属于R的任意两个不同点X(1)和X(2)恒有：,2023/11/4,31,二阶条件,设R为En上

10、的开凸集，f(X)在R上具有二阶连续偏导数，则 f(X)为R上的凸函数的充分必要条件是：f(X)的海赛矩阵H(X)在R上处处半正定（ZTH(X)Z0）。,2023/11/4,32,3.凸规划,凸规划的定义下降迭代算法,2023/11/4,33,3.1 凸规划的定义,考虑非线性规划：假定其中 f(X)为凸函数，g j(X)为凹函数（-g j(X)为凸函数），这样的非线性规划称为凸规划。,2023/11/4,34,3.1 凸规划的定义,凸规划：可行域是凸集、局部最优即为全局最优；若为严格凸函数，最优解若存在必唯一。,2023/11/4,35,3.2 下降迭代算法,基本思想：给定一个初始估计解X(0

11、)，然后按某种规则（即算法）找出一个比X(0)更好的解X(1)，如此递推即可得到一个解的序列X(k)，若这一解的序列有极限X*，即 则称X*为最优解。,2023/11/4,36,3.2 下降迭代算法,基本问题：递推步骤的有限性，一般说很难得到精确解，当满足所要求的精度时即可停止迭代而得到一个近似解。,2023/11/4,37,3.2 下降迭代算法,下降算法：若产生的解序列X(k)能使目标函数f(X(k)逐步减少，就称此算法为下降算法。“下降”的要求很容易满足，因此它包括了很多具体的算法。,2023/11/4,38,3.2 下降迭代算法,若从 X(k)出发沿任何方向移动都不能使目标函数值下降，则

12、 X(k)是一个局部极小点；若从 X(k)出发至少存在一个方向能使目标函数下降，则可选定某一下降方向 P(k)，沿这一方向前进一步，得到下一个点 X(k+1)。沿P(k)方向前进一步相当于在射线 上选定新的点,其中P(k)为搜索方向，为步长。,2023/11/4,39,3.2 下降迭代算法,确定搜索方向P(k)是关键的一步，各种算法的区别主要在于确定搜索方向P(k)的方法不同。步长 的选定一般都是以使目标函数在搜索方向上下降最多为依据的，称为最佳步长，即沿射线 求目标函数的极小值由于确定步长是通过求以 为变量的一元函数 的极小点来实现的，故称这一过程为一维搜索。,2023/11/4,40,4.

13、一维搜索,一维搜索即沿某一已知方向求目标函数的极小点，一维搜索的方法很多，在此只介绍斐波那契法和黄金分割法。,2023/11/4,41,4.1 斐波那契法,一维搜索过程是建立在一个被称为斐波那契数序列基础上的。斐波那契数序列是具有如下递推关系的无穷序列：F0=F1=1Fn=Fn-1+Fn-2，n=2,3,2023/11/4,42,4.1 斐波那契法,斐波那契法成功地实现了单峰函数极值范围的缩减。设某一单峰函数在a,b上有一极小点 x*，在此区间内任意取两点a1和b1，使a1b1，计算其函数值可能出现以下两种情况：(1)f(a1)f(b1)，如图(1)所示；此时极小点x*必在期间a,b1内。(2

14、)f(a1)f(b1)，如图(2)所示；此时极小点x*必在期间a1,b内。,2023/11/4,43,4.1 斐波那契法,f(x),o a a1 x*b1 b x,图(1),2023/11/4,44,4.1 斐波那契法,f(x),o a a1 x*b1 b x,图(2),2023/11/4,45,4.1 斐波那契法,只要在区间a,b内任意取两点a1和b1，使a1b1并计算其函数值加以比较，就可以把搜索区间a,b缩减成a,b1或a1,b。若要继续缩小搜索期间a,b1或a1,b，只需在期间内再取一点算出其函数值并与f(a1)或 f(b1)加以比较即可。由此可见，计算函数的次数越多，搜索期间就缩得越

15、小，即区间的缩短率（缩短后的区间长度与原区间长度之比）与函数的计算次数有关。,2023/11/4,46,斐波那契法的具体步骤,1.根据相对精度或绝对精度，确定试点个数；2.确定两个试点的位置a1、b1（对称搜索）；,2023/11/4,47,斐波那契法的具体步骤,3.计算函数值和并比较其大小，从而缩减搜索区间；4.重复2、3两步，直到得到近似最小点。,2023/11/4,48,斐波那契法例(第90页例6-6),例6-6：用斐波那契法求函数 f(x)=3x2-12x+10的近似极小点和极小值，要求缩短后的区间不大于初始区间1,4的0.05倍。,2023/11/4,49,4.2 黄金分割法,用斐波

16、那契法以n个点缩减某一区间时，区间长度的缩减率依次为：Fn-1/Fn,Fn-2/Fn-1,F1/F2。现将以上数列分为奇数项F2k-2/F2k和偶数项F2k/F2k+1，可以证明这两个数列收敛于同一个极限。,2023/11/4,50,4.2 黄金分割法,以不变的区间缩减率，代替斐波那契法每次不同的缩减率，就得到了黄金分割法。黄金分割法是一种等速对称的搜索方法，每次试点均取在区间长度的倍和倍处。,2023/11/4,51,黄金分割法例(第92页例6-7),例6-7：求二次函数 f(x)=3x2-21x-1在区间0,20上的极小点，要求缩短后的区间长度不大于原区间长度的5%。,2023/11/4,

17、52,5.无约束极值问题,2023/11/4,53,三种方法,梯度法（最速下降法）牛顿法变尺度法,2023/11/4,54,5.1 梯度法（最速下降法）,基本原理,2023/11/4,55,5.1 梯度法（最速下降法）,基本步骤,2023/11/4,56,5.1 梯度法（最速下降法）,第94页例6-8 试用梯度法求 的极小点，已知=0.01,2023/11/4,57,5.2 牛顿法,2023/11/4,58,5.2 牛顿法,第96页例6-10 试用牛顿法求 的极小值。,2023/11/4,59,5.3 变尺度法,2023/11/4,60,5.3 变尺度法,第98页例6-12 试用变尺度法求 的极小值，初始搜索点X(0)=(-2,4)T。,2023/11/4,61,6.约束极值问题,约束极值问题 规划问题约束使问题复杂化求解思路：（1）将约束问题转化为无约束问题；（2）将非线性规划转化为线性规划；（3）将复杂的约束问题简单化。,