非线性规划基本概念

关于非线性规划基本概念12引言在科学管理和其他领域中，很多实际问题可归结为线性规划问题。但也有很多问题，其目标函数和(或)约束条件很难用线性函数表达。如果目标函数或约束条件中含有非线性函数，就称这种问题为非线性规划问题。解这类问题需要用非线性规划方法。目前，非线性规划已成为运筹学一个重要分支，在最优设计、管理科学、系统控制等许多领域得到越来越广泛的应用。一般说来，由于非线性函数的复杂性，解非线性规划问题要比解线性规划问题困难得多。而且，也不像线性规划那样有单纯形法等通用方法。非线性规划目前还没有适于各种问题的一般性算法，各个方法都有自己特定的适用范围。第2页,共25页，2024年2月25日，星期天3基本概念－问题的提出例1

某公司经营两种产品，第一种产品每件售价30元，第二种产品每件售价450元。根据统计，售出一件第一种产品所需要的服务时间平均是0.5小时，第二种产品是(2+0.25x2)小时，其中x2是第二种产品的售出数量。已知该公司在这段时间内的总服务时间为800小时，试决定使其营业额最大的营业计划。设该公司计划经营第一种产品x1件，第二种产品x2件。根据题，其营业额为由于服务时间的限制，该计划必须满足此外，这个问题还应满足

，得到本问题数学模型为：第3页,共25页，2024年2月25日，星期天4非线性规划问题的数学模型非线性规划的数学模型常表示成以下形式其中自变量是n维欧氏空间中的向量(点)；为目标函数，和为约束条件。

第4页,共25页，2024年2月25日，星期天5由于当需使目标函数极大化时，只需使其负值极小化即可。因而仅考虑目标函数极小化，这无损于一般性。若某约束条件是“≤”不等式时，仅需用“-1”乘该约束的两端，即可将这个约束变为“≥”的形式。由于等式约束等价于下述两个不等式约束：因而，也可将非线性规划的数学模型写成以下形式数学模型第5页,共25页，2024年2月25日，星期天6图解法例1：用图解法求解非线性规划第6页,共25页，2024年2月25日，星期天7在x1Ox2坐标平面上画出目标函数的等值线，它是以点(2，1)为圆心的同心圆。1x1x112354O0解题步骤第7页,共25页，2024年2月25日，星期天8二维问题的图解根据约束条件画出可行域，它是抛物线段ABCD1x1x112354O0ABCD分析：令动点从A出发沿抛物线ABCD移动，当动点从A移向B时，目标函数值下降；当动点由B移向C时，目标函数值上升。从而可知，在可行域AC这一范围内，B点的目标函数值f(B)最小，因而点B是一个极小点。当动点由C向D移动时，目标函数值再次下降，在D点(其坐标为(4，1))目标函数值最小。第8页,共25页，2024年2月25日，星期天9练习：图解法求解非线性规划最优解：x1*=x2*=3，目标函数值：f(X*)=2。第9页,共25页，2024年2月25日，星期天10作业：用图解法求解第10页,共25页，2024年2月25日，星期天11在例1中，目标函数值f(B)仅是目标函数f(X)在一部分可行域上的极小值，而不是在整个可行域上的极小值，这样的极小值称为局部极小值(或相对极小值)。像B这样的点称为局部极小点(或相对极小点)。f(D)是整个可行域上的极小值，称全局极小值(最小值)，或绝对极小值；像D这样的点称全局极小点(最小点)，或绝对极小点。全局极小点当然也是局部极小点，但局部极小点不一定是全局极小点。1x1x112354O0ABCD第11页,共25页，2024年2月25日，星期天12局部极小：全局极小：设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):REn→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*)为严格局部极小值。第12页,共25页，2024年2月25日，星期天13一元函数极值点存在的条件二阶可微的一元函数f(x)极值点存在的条件如下：必要条件：

充分条件：对于极小点：且对于极大点：且第13页,共25页，2024年2月25日，星期天14多元函数极值点存在的条件对于无约束多元函数，其极值点存在的必要条件和充分条件，与一元函数极值点的相应条件类似。1.必要条件下述定理1给出了n元实函数f(X)在X*点取得极值的必要条件。设R是n维欧氏空间En上的某一开集，f(X)在R上有连续一阶偏导数，且在点X*∈R取得局部极值，则必有或写成：其中，为函数f(X)在点X*处的梯度。定理1第14页,共25页，2024年2月25日，星期天15多元函数极值点存在的条件函数f(X)的梯度▽f(X)有两个十分重要的性质：(1)函数f(X)在某点X0的梯度▽f(X0)必与函数过该点的等值面(或等值线)正交(设▽f(X0)不为零)；(2)梯度向量的方向是函数值(在该点处)增加最快的方向，而负梯度方向则是函数值(在该点处)减少最快的方向。第15页,共25页，2024年2月25日，星期天16二次型二次型是X=(x1,x2,…，xn)T的二次齐次函数：式中，aij=aji，A为n×n对称矩阵。若A的所有元素都是实数，则称上述二次型为实二次型。一个二次型惟一对应一个对称矩阵A；反之，一个对称矩阵A也惟一确定一个二次型。第16页,共25页，2024年2月25日，星期天17若对任意X≠0(即X的元素不全等于零)，实二次型f(X)=XTAX总为正，则称该二次型是正定的。若对任意X≠0，实二次型f(X)=XTAX总为负，则称该二次型是负定的。若对某些X≠0，实二次型f(X)=XTAX＞0；而对另一些X≠0，实二次型f(X)=XTAX＜0，即它既非正定，又非负定，则称它是不定的。若对任意X≠0，总有f(X)=XTAX≥0，即对某些X≠0，f(X)=XTAX＞0，对另外一些X≠0，f(X)=XTAX=0，则称该实二次型半正定。类似地，若对任意X≠0，总有f(X)=XTAX≤0，则称其为半负定。如果实二次型XTAX为正定、负定、不定、半正定或半负定，则称它的对称矩阵A分别为正定、负定、不定、半正定或半负定。几个定义第17页,共25页，2024年2月25日，星期天18实二次型XTAX为正定的充要条件是，它的矩阵A的左上角顺序各阶主子式都大于零，即第18页,共25页，2024年2月25日，星期天19实二次型XTAX为负定的充要条件是，它的矩阵A的左上角顺序各阶主子式负、正相间，即第19页,共25页，2024年2月25日，星期天20例2：判断矩阵的正定性解：所以A正定。第20页,共25页，2024年2月25日，星期天21练习判定以下矩阵的正定性：解：对矩阵A：所以，A负定。对矩阵B:所以，B不定。第21页,共25页，2024年2月25日，星期天22作业：判定以下矩阵的正定性：第22页,共25页，2024年2月25日，星期天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)的严格局部极小点。此处：第23页,共25页，2024年2月25日，星期天24例2

研究函数f(X)=x12-x22是否存在极值点。解:（1）由极值点存在的必要条件求出