非线性规划基本概念精选PPT讲稿.ppt

关于非线性规划基本概念1第一页，讲稿共二十五页哦2引引 言言在科学管理和其他领域中，很多实际问题可归结为线性规划问在科学管理和其他领域中，很多实际问题可归结为线性规划问题。但也有很多问题，其目标函数和题。但也有很多问题，其目标函数和(或或)约束条件很难用线性约束条件很难用线性函数表达。如果目标函数或约束条件中含有非线性函数，就称函数表达。如果目标函数或约束条件中含有非线性函数，就称这种问题为非线性规划问题。这种问题为非线性规划问题。解这类问题需要用非线性规划方法。目前，非线性规划已成解这类问题需要用非线性规划方法。目前，非线性规划已成为运筹学一个重要分支，在最优设计、管理科学、系统控制为运筹学一个重要分支，在最优设计、管理科学、系统控制等许多领域得到越来越广泛的应用。等许多领域得到越来越广泛的应用。一般说来，由于非线性函数的复杂性，解非线性规划问题要比解线性一般说来，由于非线性函数的复杂性，解非线性规划问题要比解线性规划问题困难得多。而且，也不像线性规划那样有单纯形法等通用方规划问题困难得多。而且，也不像线性规划那样有单纯形法等通用方法。非线性规划目前还没有适于各种问题的一般性算法，各个方法都法。非线性规划目前还没有适于各种问题的一般性算法，各个方法都有自己特定的适用范围。有自己特定的适用范围。第二页，讲稿共二十五页哦3基本概念基本概念问题问题的提出的提出例例1 某公司某公司经营经营两种两种产产品，第一种品，第一种产产品每件售价品每件售价30元，第二种元，第二种产产品每件售品每件售价价450元。根据元。根据统计统计，售出一件第一种，售出一件第一种产产品所需要的服品所需要的服务时间务时间平均是平均是0.5小小时时，第二种第二种产产品是品是(2+0.25x2)小小时时，其中，其中x2是第二种是第二种产产品的售出数量。已知品的售出数量。已知该该公司公司在在这这段段时间时间内的内的总总服服务时间为务时间为800小小时时，试试决定使其决定使其营业额营业额最大的最大的营业计营业计划。划。设该设该公司公司计计划划经营经营第一种第一种产产品品x1件，第二种件，第二种产产品品x2件。根据件。根据题题，其，其营业额为营业额为由于服由于服务时间务时间的限制，的限制，该计该计划必划必须满须满足足此外，此外，这这个个问题还应满问题还应满足足 ，得到本得到本问题问题数学模型数学模型为为：第三页，讲稿共二十五页哦4非线性规划问题的数学模型非线性规划问题的数学模型非线性规划的数学模型常表示成以下形式非线性规划的数学模型常表示成以下形式其中自其中自变变量量是是n维维欧氏空欧氏空间间中的向量中的向量(点点)；为为目目标标函数，函数，和和为约为约束条件。束条件。第四页，讲稿共二十五页哦5由于由于当需使目当需使目标标函数极大化函数极大化时时，只需使其，只需使其负值负值极小化即可。因而极小化即可。因而仅仅考考虑虑目目标标函数极小化，函数极小化，这这无无损损于一般性。于一般性。若某若某约约束条件是束条件是“”不等式不等式时时，仅仅需用需用“-1”乘乘该约该约束的两端，即可束的两端，即可将将这这个个约约束束变为变为“”的形式。的形式。由于等式由于等式约约束束等价于下述两个不等式约束：因而，也可将非因而，也可将非线线性性规规划的数学模型写成以下形式划的数学模型写成以下形式数学模型数学模型第五页，讲稿共二十五页哦6图解法图解法例例1：用图解法求解非线性规划：用图解法求解非线性规划第六页，讲稿共二十五页哦7在在x1Ox2坐标平面上画坐标平面上画出目标函数的等值线，出目标函数的等值线，它是以点它是以点(2，1)为圆为圆心的同心圆。心的同心圆。1x1x112354O0解题步骤解题步骤第七页，讲稿共二十五页哦8二维问题的图解二维问题的图解根据约束条件画出可行域，根据约束条件画出可行域，它是抛物线段它是抛物线段ABCD1x1x112354O0ABCD分析：分析：令动点从令动点从A出发沿抛物线出发沿抛物线ABCD移动，当动点从移动，当动点从A移移向向B时，目标函数值下降；时，目标函数值下降；当动点由当动点由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这样的这样的点称全局极小点点称全局极小点(最小点最小点)，或，或绝对极小点。全局极小点当绝对极小点。全局极小点当然也是局部极小点，但局部然也是局部极小点，但局部极小点不一定是全局极小点。极小点不一定是全局极小点。1x1x112354O0ABCD第十一页，讲稿共二十五页哦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*)，则称，则称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上有连续一阶偏导数，且在点上有连续一阶偏导数，且在点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；反之，一个对称矩阵；反之，一个对称矩阵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为正定、负定、不定、半正定或半负定，则称它的对称矩阵为正定、负定、不定、半正定或半负定，则称它的对称矩阵A分别分别为正定、负定、不定、半正定或半负定。为正定、负定、不定、半正定或半负定。几个定义几个定义第十七页，讲稿共二十五页哦18实二次型实二次型XTAX为为正定正定的充要条件是，它的矩阵的充要条件是，它的矩阵A的左上角顺序各的左上角顺序各阶主子式都大于零，即阶主子式都大于零，即第十八页，讲稿共二十五页哦19实二次型实二次型XTAX为为负定负定的充要条件是，它的矩阵的充要条件是，它的矩阵A的左上角顺序的左上角顺序各阶主子式负、正相间，即各阶主子式负、正相间，即第十九页，讲稿共二十五页哦20例例2：判断矩阵的正定性：判断矩阵的正定性解：解：所以所以A正定正定。第二十页，讲稿共二十五页哦21练习练习 判定以下矩阵的正定性：判定以下矩阵的正定性：解：对矩阵解：对矩阵A：所以，所以，A负定。负定。对矩阵对矩阵B:所以，所以，B不定。不定。第二十一页，讲稿共二十五页哦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第二十四页，讲稿共二十五页哦18.10.2022感感谢谢大大家家观观看看第二十五页，讲稿共二十五页哦