《第九讲 非线性规划基本概念课件》由会员分享，可在线阅读，更多相关《第九讲 非线性规划基本概念课件（25页珍藏版）》请在金锄头文库上搜索。
1、1,第九讲： 非线性规划基本概念,讲授: 白丹宇,2,引 言,在科学管理和其他领域中，很多实际问题可归结为线性规划问题。但也有很多问题，其目标函数和(或)约束条件很难用线性函数表达。如果目标函数或约束条件中含有非线性函数，就称这种问题为非线性规划问题。 解这类问题需要用非线性规划方法。目前，非线性规划已成为运筹学一个重要分支，在最优设计、管理科学、系统控制等许多领域得到越来越广泛的应用。 一般说来，由于非线性函数的复杂性，解非线性规划问题要比解线性规划问题困难得多。而且，也不像线性规划那样有单纯形法等通用方法。非线性规划目前还没有适于各种问题的一般性算法，各个方法都有自己特定的适用范围。,3,
2、基本概念问题的提出,例1 某公司经营两种产品，第一种产品每件售价30元，第二种产品每件售价450元。根据统计，售出一件第一种产品所需要的服务时间平均是0.5小时，第二种产品是(2+0.25x2)小时，其中x2是第二种产品的售出数量。已知该公司在这段时间内的总服务时间为800小时，试决定使其营业额最大的营业计划。,设该公司计划经营第一种产品x1件，第二种产品x2件。根据题，其营业额为,由于服务时间的限制，该计划必须满足,此外，这个问题还应满足,，得到本问题数学模型为：,4,非线性规划问题的数学模型,非线性规划的数学模型常表示成以下形式,其中自变量,是n维欧氏空间,中的向量(点)；,为目标函数，,
3、和,为约束条件。,5,由于,当需使目标函数极大化时，只需使其负值极小化即可。因而仅考虑目标 函数极小化，这无损于一般性。 若某约束条件是“”不等式时，仅需用“-1”乘该约束的两端，即可 将这个约束变为“”的形式。 由于等式约束,等价于下述两个不等式约束：,因而，也可将非线性规划的数学模型写成以下形式,数学模型,6,图解法,例1：用图解法求解非线性规划,7,在x1Ox2坐标平面上画出目标函数的等值线，它是以点(2，1)为圆心的同心圆。,解题步骤,8,二维问题的图解,根据约束条件画出可行域，它是抛物线段ABCD,分析： 令动点从A出发沿抛物线ABCD移动，当动点从A移向B时，目标函数值下降；当动点
4、由B移向C时，目标函数值上升。从而可知，在可行域AC这一范围内，B点的目标函数值f(B)最小，因而点B是一个极小点。 当动点由C向D移动时，目标函数值再次下降，在D点(其坐标为(4，1)目标函数值最小。,9,练习：图解法求解非线性规划,最优解：x1*=x2*=3，目标函数值：f(X*)=2。,10,作业：用图解法求解,11,在例1中，目标函数值f(B)仅是目标函数f(X)在一部分可行域上的极小值，而不是在整个可行域上的极小值，这样的极小值称为局部极小值(或相对极小值)。像B这样的点称为局部极小点(或相对极小点)。f(D)是整个可行域上的极小值，称全局极小值(最小值)，或绝对极小值；像D这样的点
5、称全局极小点(最小点)，或绝对极小点。全局极小点当然也是局部极小点，但局部极小点不一定是全局极小点。,12,局部极小：,全局极小：,设f(X)为定义在En的某一区域R上的n元实函数，若存在X*R，对所有XR都有f(X)f(X*)，则称X*为f(X)在R上的全局极小点，f(X*)为全局极小值。若对于所有XR且XX*，都有f(X)f(X*)，则称X*为f(X)在R上的严格全局极小点，f(X*)为严格全局极小值。,设f(X)为定义在n维欧氏空间En的某一区域R上的n元实函数(可记为f(X):R EnE1)，对于X*R，如果存在某个0，使所有与X*的距离小于的XR(即XR且XX*)，都有f(X)f(X
6、*)，则称X*为f(X)在R上的局部极小点，f(X*)为局部极小值。若对于所有XX*且与X*的距离小于的XR，都有f(X)f(X*)，则称X*为f(X)在R上的严格局部极小点，f(X*)为严格局部极小值。,13,一元函数极值点存在的条件,二阶可微的一元函数f(x)极值点存在的条件如下： 必要条件： 充分条件： 对于极小点： 且 对于极大点： 且,14,多元函数极值点存在的条件,对于无约束多元函数，其极值点存在的必要条件和充分条件，与一元函数极值点的相应条件类似。,1. 必要条件 下述定理1给出了n元实函数f(X)在X*点取得极值的必要条件。,设R是n维欧氏空间En上的某一开集，f(X)在R上有
7、连续一阶偏导数，且在点X*R取得局部极值，则必有,或写成：,其中，,为函数f(X)在点X*处的梯度。,定理1,15,多元函数极值点存在的条件,函数f(X)的梯度f(X)有两个十分重要的性质：,(1)函数f(X)在某点X0的梯度f(X0)必与函数过该点的等值面(或等值线)正交(设f(X0)不为零)； (2)梯度向量的方向是函数值(在该点处)增加最快的方向，而负梯度方向则是函数值(在该点处)减少最快的方向。,16,二次型 二次型是X=(x1,x2,，xn)T的二次齐次函数：,式中，aij=aji，A为nn对称矩阵。若A的所有元素都是实数，则称上述二次型为实二次型。,一个二次型惟一对应一个对称矩阵A
8、；反之，一个对称矩阵A也惟一确定一个二次型。,17,若对任意X0(即X的元素不全等于零)，实二次型f(X)=XTAX总为正，则称该二次型是正定的。 若对任意X0，实二次型f(X)=XTAX总为负，则称该二次型是负定的。 若对某些X0，实二次型f(X)=XTAX0；而对另一些X0，实二次型f(X)=XTAX0，即它既非正定，又非负定，则称它是不定的。 若对任意X0，总有f(X)=XTAX0，即对某些X0，f(X)=XTAX0，对另外一些X0，f(X)=XTAX=0，则称该实二次型半正定。 类似地，若对任意X0，总有f(X)=XTAX0，则称其为半负定。 如果实二次型XTAX为正定、负定、不定、半
9、正定或半负定，则称它的对称矩阵A分别为正定、负定、不定、半正定或半负定。,几个定义,18,实二次型XTAX为正定的充要条件是，它的矩阵A的左上角顺序各阶主子式都大于零，即,19,实二次型XTAX为负定的充要条件是，它的矩阵A的左上角顺序各阶主子式负、正相间，即,20,例2：判断矩阵的正定性,解：,所以A正定。,21,练习 判定以下矩阵的正定性：,22,作业 ： 判定以下矩阵的正定性：,23,多元函数极值点存在的条件充分条件：,X*是f(X)的极小点的充分条件由下面的定理2给出。,为f(X)在点X*处的黑塞(Hesse)矩阵。,若将 2f(X*)正定改为负定，定理2就变成了X*为f(X)的严格局部极大点的充分条件。,定理2,设R是n维欧氏空间En上的某一开集，f(X)在R上具有连续二阶偏导数，若 f(X*)=0，且 2f(X*)正定，则X*R为f(X)的严格局部极小点。此处：,24,例2 研究函数f(X)=x12-x22是否存在极值点。,解: （1）由极值点存在的必要条件求出稳定点：,（2）再用充分条件进行检验：,由于其黑塞矩阵 2f(X)不定，故X=(0,0)T不是极值点，而是一个鞍点。,令 f(X)=0，即：2x1=0和2x2=0，得稳定点X=(x1,x2)T=(0,0)T,25,作业,判断函数是否存在极值点,
