运筹学-非线性规划一名校讲义.ppt

第二十一讲 非线性规划（一） §1 非线性规划问题的现实来源－问题的提出 §2 非线性规划的数学模型及特点 §3 解和算法的基本性质 §4 非线性规划求解方法分类 §1 非线性规划问题的现实来源－问题的提出 （1） 在规划模型中，如果在目标函数或在约束条件中有一个或多个是自变量的非线性函数，则称这种规划为非线性规划问题。 就现实问题，严格讲来，基本属于非线性规划模型。 现举例说明非线性规划的现实背景。 [例4-1]某公司经营两种设备。第一种设备每件售价为30元，第二种设备每件售价为450元。且知，售出第一、二种设备分别需时为每件约0.5小时和（2+0.25x2）小时，其中x2为第二种设备售出数量。公司的总营业时间为800小时。 ? 求：公司为获取最大营业额（销售额）的最优营业计划。 §1 非线性规划问题的现实来源－问题的提出 （2） [解]设公司应经营销售第一、二种设备数额分别为x1件和x2件，追求的目标为最大销售额，即： 目标函数f(X)=30x1+450x2取极大 由于营业时间有限，必须满足：0.5x1+(2+0.25x2)x2≤800 当然，销售设备数不会为负数，即：x1≥0，x2≥0 综合得出该问题数学模型为： 目标函数 max：f(X) =30x1+450x2 约束条件 0.5x1+2x2+0.25x22≤800 x1≥0，x2≥0 §2 非线性规划的数学模型及特点 （1） 非线性规划的数学模型通常表示成以下形式。 min f(X) hi(X)=0 i=1，2，…，m gj(X)≥0 j=1，2，…，l [例4-3]求解下述非线性规划 min f(X)=(x1－2)2+(x2－2)2 h(X)=x1+x2－6=0 显然，与直线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 3 6 B C D 图4-1 (a) §2 非线性规划的数学模型及特点 （2） [例4-4]非线性规划为 min f(X)=(x1－2)2+(x2－2)2 h(X)=x1+x2－6≤0 显然，此时的最优解为C点(x1*=x2*=2 ，f(X*)=0)，该点落在可行或内部，其边界约束失去作用。 从前面例中看出，非线性规划的最优解（如果存在）可在其可行域上任一点达到。因而，非线性规划数学模型可以没有约束条件，即存在无约束最优化问题。 §2 非线性规划的数学模型及特点 （3） §3 解和算法的基本性质 （1） 1．极小点、凸集及其关系 ①极小点定义 i) 对于X* ?Q，如果存在一个? 0，使所有与X*的距离 小于? 的X ?Q（即X ?Q，且|X－X*|?）都满足不等式 f(X)≥f(X*)，则称X*为f在Q上的一个相对极小点或局部极 小点。若对于所有X ?Q，X≠X*且与X*距离小于? ，有 f(X)f(X*)，则称X*为f在Q上的一个严格相对极小点。 §3 解和算法的基本性质 （2） ii)点X* ?Q，如果对于所有X ?Q成立f(X)≥f(X*)，则称X* 为f在Q上的全局极小点。同样，若对于所有X ?Q， X≠X*时，存在f(X)f(X*)，则称X*为f在Q上的严格全局极 小点。 尽管问题的提法往往求全局极小点，然而，无论从 理论上或从计算观点看，实践现实性表明我们必须以很 多情形上满足一个相对极小点。当然，对于凸规划，这 二者是统一的。 §3 解和算法的基本性质 （3） ②相对极小点的判定 可行方向概念：沿给定方向作离开该点运动，若运动轨迹在可行域内，则称该运动方向为可行方向（通常用d表示）。 若从某点开始，沿任一可行方向运动（运动距离很小）都不能使目标函数减少，则据定义，知该点即为相对极小点。 i) 判定极小点的必要条件（证明从略） §3 解和算法的基本性质 （4） 命题1 （一阶必要条件）：设?是En子集，f(X) ?C1(C1表明存在一阶导数)是?上函数，若X*是f(?X)在?上一个相对极小点，则对于任一X*的可行方向d?En必有▽f(X*)·d≥0。（其中，▽f(X*)表示函数f(?X)的一阶梯度或导数） 命题2　（二阶必要条件——有约束情况）：设?是En的一个子集，且f(?X) ?Ｃ2（Ｃ2表明存在二阶导数）是?上的一个函数。若X*是f(?X)在?上的一个相对极小点。则对于