chapter6非线性规划

第六章非线性规划概述一、问题提出–生产管理中很多问题的运行过程都是以非线性形式运行的，如生产成本往往是生产量的非线性函数，产品的需求量是其价格的非线性函数等等。这样，我们在建立一个决策问题的数学模型时，目标函数或者约束条件常常会出现非线性形式。–当一个规划问题的目标函数或约束条件中至少一个表现为非线性函数，该问题就称为非线性规划问题。–通常情况下，非线性规划的求解工作非常困难，到目前为止，也没有一个求解所有形式非线性规划问题的通用方法。但随着计算机技术的迅速发展，非线性规划理论和方法也得到了越来越广泛的应用。第一节非线性规划问题及其数学模型一、问题提出–例6.1某工厂的甲乙两个分厂位于河流的同一侧（如图6-1），到河岸的垂直距离分别为a和b，两垂足A、B间的距离为d，问如何选择码头地址C，才能使得连接两个分厂与码头的铁路专用线里程最短？甲乙baBAdC图6-1第一节非线性规划问题及其数学模型–设码头所在地C距A点位x1公里，距B点位x2公里。问题可表述为：2222121212min..,0fxaxbstxxdxx–称之为上述问题的数学模型，显然模型中目标函数为非线性函数。–例6.2某公司计划生产两种类型的旅行包，即标准包和高档包。生产过程为：切割并印染原材料、缝合、成型、检查和包装。生产标准包和高档包在各过程中的单位用时以及各过程的总用时等数据如表6-1所示。单位用时产品过程标准包高档包总时间(h)切割并印染缝合成型检查和包装7/101/211/1015/62/31/4630600700135–根据市场调查，这种两种旅行包的需求量是市场价格的函数，具体的关系如下：x1=2250-15p1x2=1500-5p2–其中，x1和x2分别为标准包和高档包的需求量，p1和p2分别为标准包和高档包的市场价格。–此外，生产标准包和高档包的单位成本分别是70元/个和150元/个，问公司应该如何安排生产使获得的利润最大？–显然，问题的目标是使公司利润最大，依题意，问题的利润可描述如下：f=p1×x1+p2×x2－70x1－150x2=(150－x1/15)x1+(300－x2/5)x2=80x1－(1/15)x12+150x2－(1/5)x22–考虑各个过程的时间限制，得到该问题的数学模型如下：maxf=80x1－(1/15)x12+150x2－(1/5)x22s.t.(7/10)x1+x2=630(1/2)x1+(5/6)x2=600x1+(2/3)x2=700(1/10)x1+(1/4)x2=135x1、x2≥0第一节非线性规划问题及其数学模型二、非线性规划模型的一般形式–minf(X)–s.t.–hi(X)=0i=1,2,…,m;–gj(X)≥0j=1,2,…,l–其中，X=(x1，x2，…，xn)T是n维欧式空间En中的向量（点）；f(X)为目标函数，hi(X)=0(i=1,2,…,m)，gj(X)≥0(j=1,2,…,l)为约束条件。–对于极大化目标函数的非线性规划问题–gj(X)≤0等价与－gj(X)≥0，–hi(X)=0等价于hi(X)≥0和－hi(X)≥0，–因此，非线性规划问题的一般形式也可简化成如下形式。minf(X)s.t.gi(X)≥0i=1,2,…,l;–对于上述非线性规划，称满足所有约束条件的点为可行点，全体可行点组成的集合R称为可行域，即R={X|gi(X)≥0i=1,2,…,l}–若存在X*=(x1*，x2*，…，xn*)T∈R使f(X)最小，则称X*为该非线性规划的最优解，f(X*)为最优值。三、非线性规划的图解–与线性规划问题一样，对于二维的非线性规划问题，也可以通过图解的方法得到其最优解。–例6.3图示下列非线性规划的最优解–Minf(X)=(x1-3)2+(x2-3)2–s.t.–x1+x2≤3–x1≤2–x2≤2–x1≥0–x2≥0图6-2x2x1BOAD4.50.5在上述非线性规划问题中，若f(X)=(x1-1)2+(x2-1)2，则问题的最优解为(1，1)T，该点在可行域的内部。第二节非线性规划问题解的性质一、局部最优解与全局最优解1.可行域与最优解–满足所有约束条件的点称为可行点，全体可行点的集合R称为可行域，即R={X|gi(X)≥0i=1,2,…,l}–若存在X*=(x1*,x2*,…,xn*)T∈R使f(X)最小，则称X*为最优解，f(X*)为最优值2.梯度——对于是函数f(X)=f(x1,x2,…,xn)，称下式为f(X)=在X(1)处的梯度(1)(1)(1)(1)12()()()()TnfXfXfXfXxxx，，，例求f(X)=2x12-8x1+2x22-4x2的梯度及海森矩阵2222121122222122222212()()()()()()()()()()nnnnnfXfXfXxxxxxfXfXfXHXxxxxxfXfXfXxxxxx3.海森矩阵–4.δ的邻域——n维空间中到某点X0的距离小于某个正数δ的所有点的集合，叫做X0的一个δ的邻域，记为：N(X0，δ)={X|||X－X0||δ}–5.局部最优解——对于非线性规划minf=f(X)，gi(X)≥0（i=1,2,…,l;），设X0∈R(R为非线性规划问题的可行域)，如果存在δ0使得对于任何X∈N(X0，δ)∩R均有f(X0)≤f(X)，则称X0为非线性规划问题在R上的一个局部最优解。若X0≠X时，f(X0)f(X)严格成立，称X0为严格局部最优解。–6.全局最优解——对于非线性规划minf=f(X)，gi(X)≥0（i=1,2,…,l;），设X0∈R，对于任何X∈R均有f(X0)≤f(X)，则称X0为非线性规划问题在R上的一个全局最优解。若X0≠X时，f(X0)f(X)严格成立，称X0为严格全局最优解。第二节非线性规划问题解的性质二、凸函数与凸规划1.凸函数的定义一元凸函数——对于一元函数f(x)，任取x1，x2∈[a，b]及任意α∈[0，1]恒有：f(αx1+(1-α)x2)≤αf(x1)+(1-α)f(x2)则称f(x)为[a，b]上的一元凸函数f(x)xOx1x2x–凸函数——设f(X)为定义在n维空间En的某个凸集R上的函数，如果对于R中任意两点X(1)、X(2)以及任意实数及任意α（0α1），恒有：f(αX(1)+(1-α)X(2))≤αf(X(1))+(1-α)f(X(2))–则称f(X)为凸集R上的凸函数。–若对于α（0α1）和X(1)≠X(2)恒有：f(αX(1)+(1-α)X(2))αf(X(1))+(1-α)f(X(2))–则称f(X)为凸集R上的严格凸函数。–此外，若将上述关于凸函数定义中两个不等式中的不等号改为“≥”和“”，则分别称f(X)为凸集R上的凹函数和严格凹函数。–2.凸函数的性质（1）若f(X)为凸函数，则－f(X)必为凹函数，反之亦然；（2）若f(X)为凸集R上的凸函数，则对于任意非负实数α，函数αf(X)亦为凸集R上的凸函数；（3）若f(X)，g(X)均为为凸集R上的凸函数，则f(X)+g(X)也为为凸集R上的凸函数；–3.函数的凸性的判别–定理6.1（一阶条件）设R是n维欧式空间上的开凸集，f(X)在R上具有一阶连续偏导数，则f(X)为R上的凸函数的充分必要条件是，对于任意两个不同点X(1)∈R和X(2)∈R，恒有(2)(1)(1)(2)(1)()()()()TfXfXfXXX定理6.2（二阶条件）设R是n维欧式空间上的某一开凸集，f(X)在R上具有二阶连续偏导数，则f(X)为R上的凸函数的充分必要条件是：f(X)的海森矩阵H(X)在R上处处半正定。–举例：试判断下列函数的凸凹性f(X)=x12+x22该函数的海森矩阵在E2中处处正定。所谓正定：对于任意向量Z，有ZTHZ0正定ZTHZ=0半正定ZTHZ0负定ZTHZ=0半负定ZTHZ时正时负不定4.凸函数的极值–定理6.3若f(X)为定义在凸集R上的凸函数，则它的任意极小点就是它在R上的最小点（全局极小点），而且它的极小点形成一个凸集。–定理6.4若f(X)为定义在凸集R上的可微凸函数，若存在点X*∈R，使得对于所有的X∈R有–则X*为f(X)在R上的最小点（全局极小点）。–由定理6.1可知：–此条件，等价于**()()0TfXXX***()()()()TfXfXfXXX*()=0TfX5.凸规划–如果一个数学规划问题的可行域为凸集，目标函数为极小化，且为R上的凸函数，则称该规划问题为凸规划。对于非线性规划minf(X)X∈RR={X|gi(X)≥0i=1,2,…,l}–若f(X)为R上的凸函数，而gi(X)(i=1,2,…,l)为凹函数（或－gi(X)(i=1,2,…,l)为凸函数），则该规划问题为凸规划。–对于非线性规划–minf(X)–X∈R–R={X|hi(X)=0i=1,2,…,m;gi(X)≥0i=1,2,…,l}–若f(X)为R上的凸函数，gi(X)(i=1,2,…,l)为凹函数，hi(X)=0(i=1,2,…,m)为线性函数时，则该规划问题为凸规划。–显然，线性规划也是凸规划。–由凸函数的性质和凸规划的定义可知，凸规划的局部最优解就是全局最优解，且最优解构成一个凸集。若凸规划的目标函数为严格凸函数，且存在极小点，则该极小点为规划问题的唯一全局极小点。–例6.4判断下列非线性规划问题是否为凸规划Minf(X)=x12+x22－4x1+4s.t.g1(X)=x1－x2+2≥0g2(X)=－x12+x2－1≥0g3(X)=x1≥0g4(X)=x2≥0三、非线性规划问题的最优性条件–1.无约束问题的最优性条件–当一个优化问题没有约束条件时，此问题可称为无约束的最优化问题，即求一个多元函数的极值问题。无约束的最优化问题的形式可描述为minf(X)X∈En–以下给出无约束最优化问题的一阶必要条件和二阶充分条件。–定理6.5（一阶必要条件）若f(X)在En中的某个区域R上一阶可微，若X*为R的内点，且为无约束优化问题的局部最优解，则–定理6.6（二阶充分条件）若f(X)在En中的某个区域R上的二阶可微，若X*为R的内点，如果函数f(X)在X*处满足–且H(X*)正定–则X*为无约束问题的严格局部最优解。*()0fX*()0fX–例6.5用无约束问题的最优性条件求解下列问题–minf(X)=100(x2－x12)2+(1－x1)2212112210400()2(1)()0200()xxxxfXxx*802400()400200HX2.有约束的非线性规划问题最优性条件–带有约束的非线性优化问题，称为非线性规划问题。其具体形式如下：minf(X)s.t.gi(X)≥0i=1,2,…,l;（1）起作用约束和不起作用约束–设X(0)是上述非线性规划的一个可行解，则X(0)必满足所有约束条件，但X(0)满足某一约束条件gi(X)≥0有两种可能：–①gi(X(0))0②gi(X(0))=0–对于①，存在充分小的λ，仍能使gi(X(0)+λD)0，其中D为一个方向。–对于②，X(0)在gi(X)的边界上，它的移动要受到限制，因此有定义：–定义6.6若X(0)为上述非线性规划问题的一个可行解，如果使gi(X(0))0，则称gi(X)≥0为X(0)点的不起作用约束条件，如果使gi(X(0))=0，则称gi(X)≥0为X(0)点的起作用约束条件；–（2）可行方向–定义6.7设X(0)为非线性规划minf(X)X∈R={X|gi(X)≥0i=1,2,…,l;}的一个可行解，对于某一方向D，若存在λ00，使对任意λ∈[0，λ0]均有–X(0)+λD∈R–则称D为X(0)点的一个可行方向。–可行方向的性质：设gi(X)≥0具有一阶连续偏导数，若D为可行点X(0)的一个可行方向，g