第九讲非线性规划基本概念.ppt

第九讲： 非线性规划基本概念 讲授: 白丹宇 引 言 在科学管理和其他领域中，很多实际问题可归结为线性规划问题。但也有很多问题，其目标函数和(或)约束条件很难用线性函数表达。如果目标函数或约束条件中含有非线性函数，就称这种问题为非线性规划问题。 解这类问题需要用非线性规划方法。目前，非线性规划已成为运筹学一个重要分支，在最优设计、管理科学、系统控制等许多领域得到越来越广泛的应用。 一般说来，由于非线性函数的复杂性，解非线性规划问题要比解线性规划问题困难得多。而且，也不像线性规划那样有单纯形法等通用方法。非线性规划目前还没有适于各种问题的一般性算法，各个方法都有自己特定的适用范围。 基本概念－问题的提出 例1 某公司经营两种产品，第一种产品每件售价30元，第二种产品每件售价450元。根据统计，售出一件第一种产品所需要的服务时间平均是0.5小时，第二种产品是(2+0.25x2)小时，其中x2是第二种产品的售出数量。已知该公司在这段时间内的总服务时间为800小时，试决定使其营业额最大的营业计划。 非线性规划问题的数学模型 数学模型 图解法 例1：用图解法求解非线性规划 解题步骤 在x1Ox2坐标平面上画出目标函数的等值线，它是以点(2，1)为圆心的同心圆。 二维问题的图解 练习：图解法求解非线性规划 最优解：x1*=x2*=3，目标函数值：f(X*)=2。 作业：用图解法求解 一元函数极值点存在的条件 多元函数极值点存在的条件 多元函数极值点存在的条件 例2：判断矩阵的正定性 解： 作业 判断函数是否存在极值点 * 设该公司计划经营第一种产品x1件，第二种产品x2件。根据题，其营业额为 由于服务时间的限制，该计划必须满足 此外，这个问题还应满足 ，得到本问题数学模型为： 非线性规划的数学模型常表示成以下形式 其中自变量 是n维欧氏空间 中的向量(点)； 为目标函数， 和 为约束条件。 由于 当需使目标函数极大化时，只需使其负值极小化即可。因而仅考虑目标 函数极小化，这无损于一般性。 若某约束条件是“≤”不等式时，仅需用“-1”乘该约束的两端，即可 将这个约束变为“≥”的形式。 由于等式约束 等价于下述两个不等式约束： 因而，也可将非线性规划的数学模型写成以下形式 1 x1 x1 1 2 3 5 4 O 0 根据约束条件画出可行域，它是抛物线段ABCD 1 x1 x1 1 2 3 5 4 O 0 A B C D 分析： 令动点从A出发沿抛物线ABCD移动，当动点从A移向B时，目标函数值下降；当动点由B移向C时，目标函数值上升。从而可知，在可行域AC这一范围内，B点的目标函数值f(B)最小，因而点B是一个极小点。 当动点由C向D移动时，目标函数值再次下降，在D点(其坐标为(4，1))目标函数值最小。 在例1中，目标函数值f(B)仅是目标函数f(X)在一部分可行域上的极小值，而不是在整个可行域上的极小值，这样的极小值称为局部极小值(或相对极小值)。像B这样的点称为局部极小点(或相对极小点)。f(D)是整个可行域上的极小值，称全局极小值(最小值)，或绝对极小值；像D这样的点称全局极小点(最小点)，或绝对极小点。全局极小点当然也是局部极小点，但局部极小点不一定是全局极小点。 1 x1 x1 1 2 3 5 4 O 0 A B C D 局部极小： 全局极小： 设f(X)为定义在En的某一区域R上的n元实函数，若存在X*∈R，对所有X∈R都有f(X)≥f(X*)，则称X*为f(X)在R上的全局极小点，f(X*)为全局极小值。若对于所有X∈R且X≠X*，都有f(X)＞f(X*)，则称X*为f(X)在R上的严格全局极小点，f(X*)为严格全局极小值。 设f(X)为定义在n维欧氏空间En的某一区域R上的n元实函数(可记为f(X):R En→E1)，对于X*∈R，如果存在某个ε＞0，使所有与X*的距离小于ε的X∈R(即X∈R且‖X?X*‖＜ε)，都有f(X)≥f(X*)，则称X*为f(X)在R上的局部极小点，f(X*)为局部极小值。若对于所有X≠X*且与X*的距离小于ε的X∈R，都有f(X)＞f(X*)，则称X*为f(X)在R上的严格局部极小点，f(X*)为严格局部极小值。 二阶可微的一元函数f(x)极值点存在的条件如下： 必要条件： 充分条件： 对于极小点： 且 对于极大点： 且 对于无约束多元函数，其极值点存在的必要条件和充分条件，与一元函数极值点的相应条件类似。 1. 必要条件 下述定理1给出了n元实函数f(X)在X*点取得极值的必要条件。 设R是n维欧氏空间En上的某一开集，f(