运筹学非线性规划一名校讲义PPT学习教案

1、会计学1 运筹学非线性规划一名校讲义运筹学非线性规划一名校讲义 在规划模型中，如果在目标函数或在约束条件中有一个或 多个是自变量的非线性函数，则称这种规划为非线性规划 问题。 就现实问题，严格讲来，基本属于非线性规划模型。 现举例说明非线性规划的现实背景。 例4-1某公司经营两种设备。第一种设备每件售价为30元， 第二种设备每件售价为450元。且知，售出第一、二种设 备分别需时为每件约0.5小时和（2+0.25x2）小时，其中x2 为第二种设备售出数量。公司的总营业时间为800小时。 求：公司为获取最大营业额（销售额）的最优营业计划。 第1页/共19页 解设公司应经营销售第一、二种设备数额分别

2、为x1件和 x2件，追求的目标为最大销售额，即： 目标函数f(X)=30 x1+450 x2取极大 由于营业时间有限，必须满足：0.5x1+(2+0.25x2)x2800 当然，销售设备数不会为负数，即：x10，x20 综合得出该问题数学模型为： 目标函数 max：f(X) =30 x1+450 x2 约束条件 0.5x1+2x2+0.25x22800 x10，x20 第2页/共19页 非线性规划的数学模型通常表示成以下形式。 min f(X) hi(X)=0 i=1，2，m gj(X)0 j=1，2，l 例4-3求解下述非线性规划 min f(X)=(x12)2+(x22)2 h(X)=x1

3、+x26=0 第3页/共19页 显然，与直线AB相切的点 必为最优解。 图4-1(a)中的D点即为最优 点，此时目标函数值为： f(X*)=2，x1*=x*2=3 A f(X)=4 f(X)=2 x1 x2 6 3 2 0 2 36 B C D 图4-1 (a) 第4页/共19页 例4-4非线性规划为 min f(X)=(x12)2+(x22)2 h(X)=x1+x260 显然，此时的最优解为C点(x1*=x2*=2 ，f(X*)=0)，该点落在 可行或内部，其边界约束失去作用。 从前面例中看出，非线性规划的最优解（如果存在）可在其 可行域上任一点达到。因而，非线性规划数学模型可以没有 约束条

4、件，即存在无约束最优化问题。 第5页/共19页 1极小点、凸集及其关系 极小点定义 i) 对于X* Q，如果存在一个 0，使所有与X*的距离 小于 的X Q（即X Q，且|XX*|f(X*)，则称X*为f在Q上的一个严格相对极小点。 第6页/共19页 ii)点X* Q，如果对于所有X Q成立f(X)f(X*)，则称X* 为f在Q上的全局极小点。同样，若对于所有X Q， XX*时，存在f(X)f(X*)，则称X*为f在Q上的严格全局极 小点。 尽管问题的提法往往求全局极小点，然而，无论从 理论上或从计算观点看，实践现实性表明我们必须以很 多情形上满足一个相对极小点。当然，对于凸规划，这 二者是统

5、一的。 第7页/共19页 相对极小点的判定 可行方向概念：沿给定方向作离开该点运动，若运动轨迹 在可行域内，则称该运动方向为可行方向（通常用d表 示）。 若从某点开始，沿任一可行方向运动（运动距离很小）都 不能使目标函数减少，则据定义，知该点即为相对极小点。 i) 判定极小点的必要条件（证明从略） 第8页/共19页 命题1 （一阶必要条件）：设是En子集，f(X) C1(C1表 明存在一阶导数)是上函数，若X*是f( X)在上一个相对 极小点，则对于任一X*的可行方向dEn必有f(X*)d0。 （其中，f(X*)表示函数f( X)的一阶梯度或导数） 命题2（二阶必要条件有约束情况）：设是En的

6、 一个子集，且f( X) 2（2表明存在二阶导数）是上的 一个函数。若X*是f( X)在上的一个相对极小点。则对于 任一X*处的可行方向dn有： A) f(X*)d0 B) f(X*)d=0，则必有dT2 f(X*)d0 2 f( X)表示f( X)的第二阶梯度或二阶导数，又称Hess或海 森阵，亦可用H或F表示。 第9页/共19页 命题3 （二阶必要条件无约束情况）：设X*是集合 的内点，且X*是函数f(X)C2在上一个相对极小点。则： A) f(X*)=0 B) 对于所有d，则dT2 f(X*)d0 ii)判断极小点的充分条件 命题（二阶充分条件无约束）：设f(X)C2 是定义在 以X*为

7、内点的一个区域上的函数，若 A) f(X*)=0 B) Hess阵H(X*)正定（或负定） 则X*是f(X)的严格极小点（或极大点） 第10页/共19页 iii)极小点的充分必要条件无约束情形。（略） 凸函数与凹函数 i)定义： 凸集：若在X集合中，任意两点之联线都落在该集合 内，则称该集合为X的凸集。 凸函数：定义在凸集上的函数f(X)称为凸函数，条件是 对于每一对x1，x2及每一个a，0a1存在： f(ax1+(1a)x2)a f(x1)+1(1a)f(x2) 上式中，若变为，则称为严格凸函数。 第11页/共19页 凸函数在2维空间的形状象一口锅的纵剖面，参见图4-2。 凹函数：定义在凸集

8、上的函数g(X)称为凹函数，条件是 函数f(X)= g(X)是凸的。若 g(X)是严格凸的，则g(X)是 严格凹的，因此凸与凹是严格对应的，以后就只研究凸函 数即可。 (a) 严格凸 x 凸 x 非凸 x 图 4-2 (b)(c) 第12页/共19页 ii）有关性质（凸函数性质） 设f1(X)，f2(X)是凸集上的凸函数，则函数f1(X)+f2(X)在 上也是凸函数。 设f(X)是凸集上的凸函数，则对任意的a0，函数af(X) 是凸的。 设f(X)是凸集上的凸函数，对每一个实数C，则集合 Cx：x，f(X)C是凸集。 iii) 凸函数的判定（略） 第13页/共19页 凸规划定义：已知非线性规划： min f(X) gj(X)0 若f(X)为凸函数，gj(X)为凹函数，则称该规划为凸规划。 凸规划的局部极值点即为全局极值点。 线性规划为凸规划。 2下降算法的收敛性问题（定性分析）（略） 第14页/共19页 1一维最优化 斐波那契（Fibonacci）法 黄金分割法（0.618法） 牛顿法（切线法） 抛物线逼近法 成功和失败法 第15页/共19页 2多维最优化 无约束情形 (i) 采用导数： (a)梯度法 (b)牛顿法 (c)共轭梯度法 (d)变尺度法 第16页/共19页 (ii) 不采用导数： (a)直接法（模式搜索法） (b