非线性规划管理运筹学.pptx

<p>2024/4/25 周四11.非线性规划问题及其数学模型w非线性规划问题举例：Example1：第82页例6-1 Example2：第82页例6-2w非线性规划问题的数学模型w非线性规划问题的图示2024/4/25 周四21.1 非线性规划问题举例 Example1:某商店经销A、B两种产品，售价分别为20和380元。据统计，售出一件A 产品的平均时间为0.5小时，而售出一件B 产品的平均时间与其销售的数量成正比，表达式为1+0.2n。若该商店总的营业时间为1000小时，试确定使其营业额最大的营业计划。2024/4/25 周四31.1 非线性规划问题举例解 设x1和x2分别为商店经销A、B两种产品的件数，于是有如下数学模型：2024/4/25 周四41.1 非线性规划问题举例Example 2:在层次分析（Analytic Hierarchy Process,简记为 AHP）中，为进行多属性的综合评价，需要确定每个属性的相对重要性，即它们的权重。为此，将各属性进行两两比较，从而得出如下判断矩阵：2024/4/25 周四51.1 非线性规划问题举例 a11 a1nJ=,an1 ann其中：aij是第i个属性与第j个属性的重要性之比。2024/4/25 周四61.1 非线性规划问题举例 现需要从判断矩阵求出各属性的权重，为使求出的权重向量W在最小二乘意义上能最好地反映判断矩阵的估计，由aij=wi/wj可得：2024/4/25 周四71.2 非线性规划问题的数学模型 s.t.其中 是n维欧氏空间En中的向量点。2024/4/25 周四81.2 非线性规划问题的数学模型 由于，,“”不等式仅乘“-1”即可转换为“”不等式；因此上述数学模型具有一般意义。又因为等价于两个不等式：;,因此非线性规划的数学模型也可以表示为：2024/4/25 周四91.3 非线性规划问题的图示 若令其目标函数f(X)=c,目标函数成为一条曲线或一张曲面；通常称为等值线等值线或等等值面值面。此例，若设f(X)=2和f(X)=4可得两个圆形等值线，见下图：2024/4/25 周四101.3 非线性规划问题的图示 由左图可见,等值线f(X)=2和约束条件直线6-6相切，切点D即为此问题的最优解，X*=(3,3)，其目标函数值 f(X*)=2。3232066x1x2f(X)=4f(X)=22024/4/25 周四111.3 非线性规划问题的图示 在此例中，约束 对最优解发生了影响，若以 代替原约束，则非线性规划的最优解是 ，即图中的C点，此时 。由于最优点位于可行域的内部，故事实上约束 并未发挥作用，问题相当一个无约束极值问题。2024/4/25 周四121.3 非线性规划问题的图示 注注 线性规划存在最优解，最优解只能在线性规划存在最优解，最优解只能在其可行域的边缘上（特别能在可行域的顶其可行域的边缘上（特别能在可行域的顶点上）得到；而非线性规划的最优解（如点上）得到；而非线性规划的最优解（如果存在）则可能在可行域的任意一点上得果存在）则可能在可行域的任意一点上得到。到。2024/4/25 周四132.极值问题w局部极值与全局极值w极值点存在的条件w凸函数和凹函数w凸函数的性质w函数凸性的判定2024/4/25 周四142.1 局部极值与全局极值w线性规划 最优解 全局最优解w非线性规划 局部最优解 未必全局最优2024/4/25 周四15局部极值w对于X-X*均有不等式 f(X)f(X*)，则称 X*为 f(X)在 R上的局部极小点局部极小点，f(X*)为局部极小值局部极小值；w对于X-X*f(X*)，则称 X*为 f(X)在 R上的严格局部极小点严格局部极小点，f(X*)为严格局部极小值严格局部极小值；2024/4/25 周四16全局极值w对于X,X*R均有不等式 f(X)f(X*)，则称 X*为 f(X)在 R上的全局极小点全局极小点，f(X*)为全局极小值全局极小值；w对于X,X*R均有不等式f(X)f(X*)，则称X*为f(X)在R上的严格全局极小点严格全局极小点，f(X*)为严格全局极小值。严格全局极小值。2024/4/25 周四172.2 极值点存在的条件w必要条件 设R是En上的一个开集，f(X)在R上有一阶连续偏导数，且在点 取得局部极值局部极值，则必有 或2024/4/25 周四18必要条件 为函数 f(X)在 X*点处的梯度梯度。由数学分析可知，的方向为X*点处等值面（等值线）的法线方向法线方向，沿这一方向函数值增加最快，如图所示。2024/4/25 周四19必要条件 满足 的点称为平稳点平稳点或驻点驻点。极值点极值点一定是驻点；驻点；但驻点驻点不一定是极值极值点点。2024/4/25 周四20充分条件w充分条件 设R是En上的一个开集，f(X)在R上具有二阶连续偏导数，对于 ，若 且对任何非零向量有：则X*为 f(X)的严格局部极小点严格局部极小点。称为 f(X)在点X*处的海赛海赛（Hesse）矩阵矩阵。2024/4/25 周四21充分条件2024/4/25 周四22充分条件（充分条件）等价于：如果函数f(X)在X*点的梯度为零梯度为零且海赛矩海赛矩阵正定阵正定，则X*为函数f(X)的严格局部极小严格局部极小点点。2024/4/25 周四232.3 凸函数和凹函数 设 f(X)为定义在En中某一凸集R上的函数，若对于任何实数（01）以及R中的任意两点X(1)和X(2)，恒有：则称 f(X)为定义在R上的凸函数凸函数；若上式为严格不等式，则称 f(X)为定义在R上的严格凸函数严格凸函数。改变不等号的方向，即可得到凹函数凹函数和严格凹函数严格凹函数的定义。2024/4/25 周四24凸函数和凹函数示意图X(1)X(2)f(X)X凸函数凸函数X(1)X(2)f(X)X凹函数凹函数2024/4/25 周四25非凹非凸函数示意图f(X(2)f(X(1)X(1)+(1-)X(2)X(1)X(2)f(X)X非凸非凹函数非凸非凹函数2024/4/25 周四262.4 凸函数的性质w设f(X)为定义在凸集R上的凸函数，则对于任意实数0,函数 f(X)也是定义在R上的凸函数。w设f1(X)和f 2(X)为定义在凸集R上的两个凸函数，则其和f(X)=f1(X)+f 2(X)仍然是定义在R上的凸函数。w设f(X)为定义在凸集R上的凸函数，则对于任意实数,集合S=X|XR,f(X)是凸集。2024/4/25 周四272.4 凸函数的性质w设f(X)为定义在凸集R上的凸函数，则它的任一极小点就是它在R上的最小点（全局极小点）；而且它的极小点形成一个凸集。w设f(X)为定义在凸集R上的可微凸函数，若它存在点X*R，使得对于所有的XR有 f(X*)T(X-X*)0，则X*是f(X)在R上的最小点（全局极小点）。2024/4/25 周四282.5 函数凸性的判定w根据凸函数的定义进行判定；w根据一阶条件进行判定；w根据二阶条件进行判定；2024/4/25 周四29一阶条件 设R为En上的开凸集，f(X)在R上具有一阶连续偏导数，则f(X)为R上的凸函数的充分必要条件是，对于属于R的任意两个不同点X(1)和X(2)恒有：2024/4/25 周四30二阶条件 设R为En上的开凸集，f(X)在R上具有二阶连续偏导数，则 f(X)为R上的凸函数的充分必要条件是：f(X)的海赛矩阵海赛矩阵H(X)在R上处处半正定（半正定（ZTH(X)Z0）。2024/4/25 周四313.凸规划w凸规划的定义w下降迭代算法2024/4/25 周四323.1 凸规划的定义 考虑非线性规划：假定其中 f(X)为凸函数，g j(X)为凹函数（-g j(X)为凸函数），这样的非线性规划称为凸规划凸规划。2024/4/25 周四333.1 凸规划的定义 凸规划：可行域是凸集、局部最优即为全局最优；若为严格凸函数，最优解若存在必唯一。2024/4/25 周四343.2 下降迭代算法基本思想基本思想：给定一个初始估计解初始估计解X(0)，然后按某种规则（即算法）找出一个比X(0)更好的解X(1)，如此递推即可得到一个解的序列X(k)，若这一解的序列有极限X*，即 则称X*为最优解。2024/4/25 周四353.2 下降迭代算法基本问题基本问题：递推步骤的有限性，一般说很难得到精精确解确解，当满足所要求的精度时即可停止迭代而得到一个近似解近似解。2024/4/25 周四363.2 下降迭代算法下降算法下降算法：若产生的解序列X(k)能使目标函数f(X(k)逐步减少，就称此算法为下降算法。“下降”的要求很容易满足，因此它包括了很多具体的算法很多具体的算法。2024/4/25 周四373.2 下降迭代算法w若从 X(k)出发沿任何方向移动都不能使目标函数值下降，则 X(k)是一个局部极小点；若从 X(k)出发至少存在一个方向能使目标函数下降，则可选定某一下降方向 P(k)，沿这一方向前进一步，得到下一个点 X(k+1)。w沿P(k)方向前进一步相当于在射线 上选定新的点 ,其中P(k)为搜索方为搜索方向，向，为步长为步长。2024/4/25 周四383.2 下降迭代算法w确定搜索方向P(k)是关键的一步，各种算法的区别主要在于确定搜索方向P(k)的方法不同。w步长 的选定一般都是以使目标函数在搜索方向上下降最多为依据的，称为最佳步长最佳步长，即沿射线 求目标函数的极小值w由于确定步长是通过求以 为变量的一元函数 的极小点来实现的，故称这一过程为一维搜索一维搜索。2024/4/25 周四394.一维搜索 一维搜索即沿某一已知方向求目标函数的极小点，一维搜索的方法很多，在此只介绍斐波那契法和黄金分割法。2024/4/25 周四404.1 斐波那契法斐波那契法 一维搜索过程是建立在一个被称为斐波那契斐波那契数序列基础上的。斐波那契斐波那契数序列是具有如下递推关系的无穷序列：F0=F1=1Fn=Fn-1+Fn-2，n=2,3,n012345678Fn1123581321342024/4/25 周四414.1 斐波那契法斐波那契法w斐波那契法斐波那契法成功地实现了单峰函数单峰函数极值范围的缩减。w设某一单峰函数在a,b上有一极小点 x*，在此区间内任意取两点a1和b1，使a1b1，计算其函数值可能出现以下两种情况：(1)f(a1)f(b1)，如图(1)所示；此时极小点x*必在期间a,b1内。(2)f(a1)f(b1)，如图(2)所示；此时极小点x*必在期间a1,b内。2024/4/25 周四424.1 斐波那契法斐波那契法f(x)o a a1 x*b1 b x图(1)2024/4/25 周四434.1 斐波那契法斐波那契法f(x)o a a1 x*b1 b x图(2)2024/4/25 周四444.1 斐波那契法斐波那契法w只要在区间a,b内任意取两点a1和b1，使a1b1并计算其函数值加以比较，就可以把搜索区间a,b缩减成a,b1或a1,b。若要继续缩小搜索期间a,b1或a1,b，只需在期间内再取一点算出其函数值并与f(a1)或 f(b1)加以比较即可。w由此可见，计算函数的次数越多，搜索期间就缩得越小，即区间的缩短率（缩短后的区间长度与原区间长度之比）与函数的计算次数有关。2024/4/25 周四45斐波那契法的具体步骤斐波那契法的具体步骤w1.根据相对精度或绝对精度，确定试点个数；w2.确定两个试点的位置a1、b1（对称搜索对称搜索）；Fn-2Fn-1aba1b1Fn-2Fn-12024/4/25 周四46斐波那契法的具体步骤斐波那契法的具体步骤w3.计算函数值和并比较其大小，从而缩减搜索区间；w4.重复2、3两步，直到得到近似最小点。2024/4/25 周四47斐波那契法例斐波那契法例(第第90页例页例6-6)例6-6：用斐波那契法求函数 f(x)=3x2-12x+10的近似极小点和极小值，要求缩短后的区间不大于初始区间1,4的0.05倍。2024/4/25 周四484.2 黄金分割法 用斐波那契法斐波那契法以n个点缩减某一区间时，区间长度的缩减率依次为：Fn-1/Fn,Fn-2/Fn-1,F1/F2。现将以上数列分为奇数项奇数项F2k-2/F2k和偶数项偶数项F2k/F2k+1，可以证明这两个数列收敛于同一个极限。2024/4/25 周四494.2 黄金分割法w以不变的区间缩减率，代替斐波那契斐波那契法每次不同的缩减率，就得到了黄金分割法黄金分割法。w黄金分割法黄金分割法是一种等速对称等速对称的搜索方法，每次试点均取在区间长度的倍和倍处。2024/4/25 周四50黄金分割法例黄金分割法例(第第92页例页例6-7)例6-7：求二次函数 f(x)=3x2-21x-1在区间0,20上的极小点，要求缩短后的区间长度不大于原区间长度的5%。2024/4/25 周四515.无约束极值问题迭代法解析法直接法用到函数的一、二阶导数，即函数的解析性质只用到函数值，而不要求函数的解析性质2024/4/25 周四52三种方法w梯度法（最速下降法）w牛顿法w变尺度法2024/4/25 周四535.1 梯度法（最速下降法）w基本原理2024/4/25 周四545.1 梯度法（最速下降法）w基本步骤2024/4/25 周四555.1 梯度法（最速下降法）w第94页例6-8 试用梯度法求 的极小点，已知=0.01 2024/4/25 周四565.2 牛顿法2024/4/25 周四575.2 牛顿法w第96页例6-10 试用牛顿法求 的极小值。</p>