《运筹学教程 第2版 教学课件 ppt 作者 邱菀华 冯允成 第5章》由会员分享，可在线阅读，更多相关《运筹学教程 第2版 教学课件 ppt 作者 邱菀华 冯允成 第5章（32页珍藏版）》请在金锄头文库上搜索。
1、第五章 非线性规划,第五章 非线性规划,第一节 非线性规划的基本概念 第二节 一维搜索算法 第三节 求解无约束极值问题的解析法 第四节 求解无约束极值问题的直接法,第一节 非线性规划的基本概念,1.1 非线性规划的一般模型及最优解 1.2 非线性规划的几何表示 1.3 非线性规划问题的特性 1.4 凸函数和凸规划,1.1 非线性规划的一般模型及最优解,一般模型： 例5-1：某企业生产两种产品，一定期限内产量分别为和，产量受资源限制的条件如下： 已知单位日产品的收益为6元，而单位A产品的收益随产销量的增加而减少，每单位为 元。要求决定x和y使总收益最大。,由题意写出此规划问题的数学模型为：,非线
2、性规划问题：目标函数是非线性的， 约束条件均为线性函数。,1.1 非线性规划的一般模型及最优解,1.1 非线性规划的一般模型及最优解,定义5-1 点 称为（P）的最优点，若 即对于任意，均有 若上式换为严格不等式 则称 为（P）的严格最优点,，,1.2 非线性规划的几何表示,用图形来描述两个变量的非线性规划的问题，请看一个例子。,1.2 非线性规划的几何表示,如下图所示,1.3 非线性规划问题的特性,非线性规划的某些特性与线性规划是一致的。 例如： 1）可行域有可能是空集，可行域有可能无界； 2）规划问题可能不存在有限的最优解； 3）若最优解存在，可能不唯一。,1.3 非线性规划问题的特性,但
3、由于函数形式的复杂性，线性规划的某些特性在非线性规划中不能满足，例如： 1）线性规划的可行域是凸集，边界是直线，有有限个极点（亦即顶点）；而非线性规划的可行域不一定是凸集，甚至不一定连通（见图52），边界也不一定是直线，如果是曲线边界的话，将有无穷多个极点。 2）线性规划问题只要存在最优解就必然是全局最优解；而非线性规划的解分为全局最优解和局部最优解。 3）线性规划问题只要存在最优解，则至少有一个可行域极点为最优点；而非线性规划的最优点不一定在极点上（见图53），甚至可能在可行域的内部（见图54）。,1.4 凸函数和凸规划,1、凸函数,定义5-3 设 为一凸集，若对任意 ， 以及数 ，有 则称
4、 在 上为凸函数。,1.4 凸函数和凸规划,2凸规划 定义5-7 对于规划问题（P）,若 为凸函数，R为凸集，则（P）称为凸规划,1.4 凸函数和凸规划,定理5-2 凸规划问题(P)有如下性质： （1）最优解集合 为凸集； （2）任何局部最优解都是全局最优解,定理5-3 若凸规划问题（P）存在最优解，且 是严格凸函数，则最优解必唯一。,第二节 一维搜索算法,2.1 切线法 2.2 菲波那契（Fibonacci）法 2.3 黄金分割法（又称0 .618法）,2.1 切线法,切线法又叫牛顿（Newton）法。如单变量实函数 在 点取得局部极值，并且在 点可微，那么 在 点的一阶导数应零，即局部极值
5、点是下列方程的解,2.2 菲波那契（Fibonacci）法,一般来说，当函数形式很复杂时，或者目标函数不能用解析式表达时，用导数的方法求极值是非常困难甚至是不可能的。基于这样的情况，人们又提出了若干种不用导数的计算方法。 我们把这一类不需要计算导数而只需要计算函数值的求极值的方法统称为直接法。菲波那契法是其中的一种，也称为优选法，该方法仅适合于目标函数是单峰函数的情况,2.3 黄金分割法（又称0 .618法）,项目资源计划的目的,项目资源计划的目的是通过分析和识别项目的资源需求(包括人员、设备、材料和资金等)，确定各种项目活动需要的资源种类、数量、质量和资源投入时间，从而确定项目的成本估算。,
6、第三节 求解无约束极值问题的解析法,3.1 梯度法（最速下降法） 3.2 牛顿法 3.3 变尺度法,3.1 梯度法（最速下降法）,最速下降法的概念 最速下降法的迭代步骤,3.1 梯度法（最速下降法）,最速下降法的概念,向量d称为函数 在点 的下降方向，若存在数 ,使得对任意 ，都有 由这一定义，又可说若有 / 0 则d是函数在点的下降方向。在所有下降方向中，使上式所示极限值最小的向量 之称为函数在点的最速下降方向。,梯度法迭代步骤如下：,3.1 梯度法（最速下降法）,1）取初始点 ，允许误差 0，令k：= 0； 2）计算负梯度 = ，及其单位向量 = 3）检验是否满足收敛性判别准则 若满足判别
7、准则，迭代停止，得到点 ；否则，进行（4）： 4）进行一维搜索，即求单变量极值问题的最优解 5）令 = 转到（2）。,3.2 牛顿法,牛顿法迭代步骤如下：,1）取初始点 ，允许误差 ，令 ； 2）检验是否满足收敛性判别准则 若满足判别准则，迭代停止，得到 。否则，进行3）； 3）令 = 4）求单变量极值问题的最优解： 5）令 转到2）。 牛顿法的主要缺点在于计算复杂，要计算二次偏导数，又要计算逆矩阵。尤其在变量较多时，计算量就更大。,3.3 变尺度法,变尺度法迭代步骤如下：,1）初始点 ，允许误差 0； 2）检验是否满足 若满足，则迭代停止，得到 。否则进行3）； 3）取 ， 为nn单位矩阵，
8、 ，令k:=1; 4）令 5）求单变量极值问题的最优解 = 6）令 ： 7）检验是否满足收敛性判别准则 若满足，则迭代停止，得到 。否则，当 时，令 , 转到3）；当kn时，令,3.3 变尺度法,计算 转到8） 8）令k：kl 转到4）。 每迭代n步后，令。此步骤是为一般函数使用而设计的。,第四节 求解无约束极值问题的直接法,4.1 坐标轮换法 4.2 步长加速法,4.1 坐标轮换法,基本原理：在每次搜索中只改变一个变量，保持其它变量为常数，坐标轴方向轮流进行搜索。 具体操作：设起始点为 ，由 点按第一个坐标轴方向 求最优解，得到点 ，即 如此等等，一直到按第n个坐标轴方向 ，求最优解得到,4
9、.1 坐标轮换法,坐标轮换法迭代步骤 1）取初始点 ，允许误差 ，令 ； 2）求单变量极值问题的最优解 3）判别是否满足 ，若 转到4）；否则，令 ，转到2） 4）检验是否满足收敛性判别准则 若满足判别准则，迭代停止，得到 。否则，令 ， 转到2）。,步长加速法（Hooke-Jeeves法）包括两种搜索方式：探测性搜索和模式性搜索 按每次搜索中决定步长的方法不同，又分为两种：线性步长加速法和离散步长加速法。,4.2 步长加速法,4.2 步长加速法,线性步长加速法迭代步骤如下：,1）取初始点 ，允许误差 ； 2）令 ； 3）求单变量极值问题的最优解 = 令 = 4)判别是否满足 ，若 ，令j：=
10、j1转到3）；若j=n，令 ，转到5）； 5） 见后页,4.2 步长加速法,5）检验是否满足收敛性判别准则 若满足，则迭代停止，得到 = 。否则转到6）； 6）令d= ，求单变量极值问题的最优解 令 转到3）。,4.2 步长加速法,离散步长加速法法代步骤如下：,1）取初始点 ，允许误差 0，初始步长 0，步长加速因 子 ，步长缩短系数 。 2）令 。 3） 。 4）判别是否满足 ，若满足，则转到6）；否则， 令 ，转到5）。 5）判别是否满足 ，若满足，则转到6）；否则，令 转到6）。 6）判别是否满足 j=n，若满足，则转到7）；否则，令 ， 转到3）。 7）判别是否满足 ，若满足，则转到8）；否则，转到10）。,4.2 步长加速法,离散步长加速法法代步骤(续),8）令 ， 。 9） 转到3）。 10）判别是否满足 ，若满足，则转到11)；否则，令 ， 转到3）。 11）判别是否满足收敛条件判别标准 ，若满足，迭代停止， 得 ，否则令 ，j=1 转到3）； 由前叙步骤可知，在模式性探索中的步长加速是否被认为有效，要等接着后面的探测性搜索完成后才作判断。,
