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

第九讲非线性规划基本概念1现在学习的是第1页，共22页引引 言言在科学管理和其他领域中，很多实际问题可归结为线性规划问在科学管理和其他领域中，很多实际问题可归结为线性规划问题。但也有很多问题，其目标函数和题。但也有很多问题，其目标函数和(或或)约束条件很难用线性函约束条件很难用线性函数表达。如果目标函数或约束条件中含有非线性函数，就称这种数表达。如果目标函数或约束条件中含有非线性函数，就称这种问题为非线性规划问题。问题为非线性规划问题。解这类问题需要用非线性规划方法。目前，非线性规划已成为运筹学解这类问题需要用非线性规划方法。目前，非线性规划已成为运筹学一个重要分支，在最优设计、管理科学、系统控制等许多领域得到越一个重要分支，在最优设计、管理科学、系统控制等许多领域得到越来越广泛的应用。来越广泛的应用。一般说来，由于非线性函数的复杂性，解非线性规划问题要比解一般说来，由于非线性函数的复杂性，解非线性规划问题要比解线性规划问题困难得多。而且，也不像线性规划那样有单纯形法线性规划问题困难得多。而且，也不像线性规划那样有单纯形法等通用方法。非线性规划目前还没有适于各种问题的一般性算法等通用方法。非线性规划目前还没有适于各种问题的一般性算法，各个方法都有自己特定的适用范围。，各个方法都有自己特定的适用范围。2现在学习的是第2页，共22页基本概念基本概念问题的提出问题的提出例例1 某公司经营两种产品，第一种产品每件售价某公司经营两种产品，第一种产品每件售价30元，第二种产品每件售价元，第二种产品每件售价450元。根据统计，售出一件第一种产品所需要的服务时间平均是元。根据统计，售出一件第一种产品所需要的服务时间平均是0.5小时，第小时，第二种产品是二种产品是(2+0.25x2)小时，其中小时，其中x2是第二种产品的售出数量。已知该公司在这段时是第二种产品的售出数量。已知该公司在这段时间内的总服务时间为间内的总服务时间为800小时，试决定使其营业额最大的营业计划。小时，试决定使其营业额最大的营业计划。12()30450f Xxx设该公司计划经营第一种产品设该公司计划经营第一种产品x1件，第二种产品件，第二种产品x2件。根据题，其营业额为件。根据题，其营业额为由于服务时间的限制，该计划必须满足由于服务时间的限制，该计划必须满足1220.520.25800 xxx12212212max 30450 0.520.25800 0,0fXxxxxxxx120,0 xx此外，这个问题还应满足此外，这个问题还应满足 ，得到本问题数学模型为：得到本问题数学模型为：3现在学习的是第3页，共22页非线性规划问题的数学模型非线性规划问题的数学模型min()(1)()0,=1,2,(2)()0,1,2,(3)ijf XhXimgXjlT12(,)nXx xxnE()f X()0ih X()0jgX 非线性规划的数学模型常表示成以下形式非线性规划的数学模型常表示成以下形式其中自变量其中自变量是是n维欧氏空间维欧氏空间中的向量中的向量(点点)；为目标函数，为目标函数，和和为约束条件。为约束条件。4现在学习的是第4页，共22页max()min()f Xf X()0ih X()0()0iih Xh Xmin()(4)()0,1,2,(5)jf XgXjl由于由于当需使目标函数极大化时，只需使其负值极小化即可。因而仅考虑目标当需使目标函数极大化时，只需使其负值极小化即可。因而仅考虑目标函数极小化，这无损于一般性。函数极小化，这无损于一般性。若某约束条件是若某约束条件是“”不等式时，仅需用不等式时，仅需用“-1”乘该约束的两端，即可乘该约束的两端，即可将这个约束变为将这个约束变为“”的形式。的形式。由于等式约束由于等式约束等价于下述两个不等式约束：因而，也可将非线性规划的数学模型写成以下形式因而，也可将非线性规划的数学模型写成以下形式数学模型数学模型5现在学习的是第5页，共22页图解法图解法 例例1：用图解法求解非线性规划：用图解法求解非线性规划221221221212min()(2)(1)5050.00f Xxxxxxxxstxx6现在学习的是第6页，共22页在在x1Ox2坐标平面上坐标平面上画出目标函数的等值画出目标函数的等值线，它是以点线，它是以点(2，1)为圆心的同心圆。为圆心的同心圆。1x1x112354O02212()(2)(1)f Xxx解题步骤解题步骤7现在学习的是第7页，共22页二维问题的图解二维问题的图解根据约束条件画出可行域，根据约束条件画出可行域，它是抛物线段它是抛物线段ABCD1x1x112354O0ABCD分析：分析：令动点从令动点从A出发沿抛物线出发沿抛物线ABCD移动，当动点从移动，当动点从A移移向向B时，目标函数值下降；时，目标函数值下降；当动点由当动点由B移向移向C时，目标时，目标函数值上升。从而可知，函数值上升。从而可知，在可行域在可行域AC这一范围内，这一范围内，B点的目标函数值点的目标函数值f(B)最小，最小，因而点因而点B是一个极小点。是一个极小点。当动点由当动点由C向向D移动时，移动时，目标函数值再次下降，在目标函数值再次下降，在D点点(其坐标为其坐标为(4，1)目标函数值目标函数值最小。最小。8现在学习的是第8页，共22页练习：图解法求解非线性规划练习：图解法求解非线性规划最优解：最优解：x1*=x2*=3，目目标函数值：标函数值：f(X*)=2。22121212min()(2)(2)()6 000f Xxxh Xxxxx 9现在学习的是第9页，共22页作业：作业：用图解法求解用图解法求解2212221212min()1.42f xxxxxstxx10现在学习的是第10页，共22页在例在例1中，目标函数值中，目标函数值f(B)仅是仅是目标函数目标函数f(X)在一部分可行域在一部分可行域上的极小值，而不是在整个可上的极小值，而不是在整个可行域上的极小值，这样的极小行域上的极小值，这样的极小值称为局部极小值值称为局部极小值(或相对极小或相对极小值值)。像。像B这样的点称为局部这样的点称为局部极小点极小点(或相对极小点或相对极小点)。f(D)是整个可行域上的极小是整个可行域上的极小值，称全局极小值值，称全局极小值(最小值最小值)，或绝对极小值；像，或绝对极小值；像D这样这样的点称全局极小点的点称全局极小点(最小点最小点)，或绝对极小点。全局极小，或绝对极小点。全局极小点当然也是局部极小点，但点当然也是局部极小点，但局部极小点不一定是全局极局部极小点不一定是全局极小点。小点。1x1x112354O0ABCD221221221212min()(2)(1)5050.00f Xxxxxxxxstxx11现在学习的是第11页，共22页局部极小：局部极小：全局极小：全局极小：设设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*)为严格局部极小值。为严格局部极小值。12现在学习的是第12页，共22页一元函数极值点存在的条件一元函数极值点存在的条件二阶可微的一元函数二阶可微的一元函数f(x)极值点存在的条件如下：极值点存在的条件如下：必要条件：必要条件：充分条件：充分条件：对于极小点：对于极小点：且且 对于极大点：对于极大点：且且0)(fx0)(fx0)(fx0)(f x0(x)f 13现在学习的是第13页，共22页多元函数极值点存在的条件多元函数极值点存在的条件对于无约束多元函数，其极值点存在的必要条件和充分条件，与一元函数对于无约束多元函数，其极值点存在的必要条件和充分条件，与一元函数极值点的相应条件类似。极值点的相应条件类似。1.必要条件必要条件下述定理下述定理1给出了给出了n元实函数元实函数f(X)在在X*点取得极值的必要条件。点取得极值的必要条件。设设R是是n维欧氏空间维欧氏空间En上的某一开集，上的某一开集，f(X)在在R上有连续一阶偏导数，且在点上有连续一阶偏导数，且在点X*R取得局部极值，则必有取得局部极值，则必有*12()()().0nfXfXfXxxx或写成：或写成：*()0f X其中，其中，*12()()()()(,.,)Tnf Xf Xf Xf Xxxx为函数为函数f(X)在点在点X*处的梯度。处的梯度。定理定理114现在学习的是第14页，共22页多元函数极值点存在的条件多元函数极值点存在的条件函数函数f(X)的梯度的梯度f(X)有两个十分重要的性质：有两个十分重要的性质：(1)函数函数f(X)在某点在某点X0的梯度的梯度f(X0)必与函数过该点的等值面必与函数过该点的等值面(或等或等值线值线)正交正交(设设f(X0)不为零不为零)；(2)梯度向量的方向是函数值梯度向量的方向是函数值(在该点处在该点处)增加最快的方向，而负梯度增加最快的方向，而负梯度方向则是函数值方向则是函数值(在该点处在该点处)减少最快的方向。减少最快的方向。15现在学习的是第15页，共22页2211 112 12112222323()2.22nnf Xa xa x xa x xa xa x x222.2.nnnnna x xa x11nnTijijija x xX AX二次型二次型二次型是二次型是X=(x1,x2,，xn)T的二次齐次函数：的二次齐次函数：式中，式中，aij=aji，A为为nn对称矩阵。若对称矩阵。若A的所有元素都是实数，则称上述二次型为的所有元素都是实数，则称上述二次型为实二次型。实二次型。一个二次型惟一对应一个对称矩阵一个二次型惟一对应一个对称矩阵A；反之，一个对称矩阵；反之，一个对称矩阵A也惟一确定一也惟一确定一个二次型。个二次型。16现在学习的是第16页，共22页若对任意若对任意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分别为分别为正定、负定、不定、半正定或半负定。正定、负定、不定、半正定或半负定。几个定义几个定义17现在学习的是第17页，共22页实二次型实二次型XTAX为为正定正定的充要条件是，它的矩阵的充要条件是，它的矩阵A的左上角顺序的左上角顺序各阶主子式都大于零，即各阶主子式都大于零，即1 11 21 31 11 21 12 12 22 32 12 23 13 23 30,0,0,.,aaaaaaaaaaaaaa1111.0.nnnnaaaa18现在学习的是第18页，共22页实二次型实二次型XTAX为为负定负定的充要条件是，它的矩阵的充要条件是，它的矩阵A的左上角顺序各的左上角顺序各阶主子式负、正相间，即阶主子式负、正相间，即1 11 21 31 11 21 12 12 22 32 12 23 13 23 30,0,0,.,aaaaaaaaaaaaaa1111.(1).0.nnnnnaaaa19现在学习的是第19页，共22页例例2：判断矩阵的正定性：判断矩阵的正定性 解：解：522211214A 55052541021 20444 16530A 所以所以A正定正定。20现在学习的是第20页，共22页522260204A练习练习 判定以下矩阵的正定性：判定以下矩阵的正定性：011103130B解：对矩阵解：对矩阵A：11121121225250,26026aaaaa 522260800204A 所以，所以，A负定负定。1112112122010,110bbbbb 对矩阵对矩阵B:所以，所以，B不定不定。21现在学习的是第21页，共22页6251243253711210A作业作业：判定以下矩阵的正定性：判定以下矩阵的正定性：2532504234012217B22现在学习的是第22页，共22页