数学模型与数学建模5.2--非线性规划

5.2非线性规划若目标函数或约束条件中至少有一个是变量的非线性函数，称这类规划问题为非线性规划问题（NonlinearProgramming;NP）。非线性规划的系统研究始于上个世纪四十年代末，1951年Kuhn和Tucker提出了著名的Kuhn-Tucker条件，加上电子计算机的迅速发展，使得非线性规划无论在基本理论还是实用算法都有了长足的发展，使之逐渐成为运筹学的一个非常重要的分支。5.2.1非线性规划问题的数学模型和基本概念例5.2.1某公司准备建一临时混凝土搅拌站，向各工地供应商品混凝土，现需确定搅拌站建在什么位置，才能使它向各工地供应混凝土的费用最低。设共有个工地，第个工地的混凝土需求量为（），单位混凝土的运费为（元／吨千米）。如图5.2.1，设混凝土搅拌站位置的坐标为，niiq1,2,,in00,xy各工地位置的坐标为，则第个工地与搅拌站的距离可用两点间的距离公式求得.图5.2.1混凝土搅拌站与工地分布图,iixyi2200iiidxxyy搅拌站向第个工地供应原料的运费为,搅拌站向各工地供应原料的总费用为因此有以下数学模型：iiiicqd2200111nnniiiiiiiiiCcqdqxxyy22001minniiiiCqxxyy根据该模型，可选择适当的就可使达到最小。该模型的目标函数为非线性函数，故该问题为非线性规划问题。又因为该模型没有约束条件，故又称该问题为无约束极值问题，否则称为约束极值问题。00xy、C例5.2.2设某企业的生产函数为，生产要素和的投入价格分别为8和2，若要求产出量达到128，试求使总成本最小的投入。根据问题的要求，易得如下模型13234QKLKLmin82CKL1323..4128stKL该问题有约束条件，即为约束极值问题。该问题的约束条件为非线性函数，故该问题也为非线性规划问题。一般地，非线性规划（NP）问题的数学模型可表述为（5.2.1）其中，是欧式空间中的向量。min()()0,1,2,,...()0,1,2,,.ijfXhXimstgXjl12,,,TnXxxxnE以上（NP）模型称为非线性规划的一般形式。若模型的目标函数为极大化时，则可将其负值极小化，若某个约束条件是“”形式，则只需要将不等式两端乘上“”即可将这种不等式的约束变成“”的形式。又因为等式约束等价于以下两个不等式约束（5.2.2）1()0,1,2,,ihXim()0,1,2,,()0,1,2,,iihXimhXim所以，非线性规划问题的数学模型又可写成（5.2.3）下面给出局部极小点和全局极小点的定义。min()..()0,1,2,,.jfXstgXjl定义5.2.1设为定义在维欧式空间某一区域上的实函数，对于，若存在某个，使得满足的所有的，都有（5.2.4）则称为在上的局部极小点，为局部极小值。若，则称为在上的严格局部极小点，为严格局部极小值。()fXnnER*nXRE0*XXX*()()fXfX*X()fXR*()fX*()()fXfX*X()fXR*()fX定义5.2.2设为定义在维欧式空间某一区域上的实函数，对于，若对所有的，都有（5.2.5）则称为在上的全局极小点，为全局极小值。若，则称为在上的严格全局极小点，为严格全局极小值。()fXnnER*nXREXR*()()fXfX*X()fXR*()fX*()()fXfX*X()fXR*()fX5.2.2凸函数首先介绍凸函数的概念和性质，再介绍凸规划的概念与性质。凸函数是一类很重要的函数。非线性规划的理论和算法中的许多重要结论都依赖于所研究的函数的凸性。一、凸（凹）函数的定义定义5.2.3设为定义在非空凸集上的函数。若对任意的及中任意两点和，有（5.2.6）成立，则称为上的凸函数，或称在上是凸的。()fXnDE(0,1)D(1)X(2)X(1)(2)(1)(2)((1))()(1)()fXXfXfX()fXD()fXD若对任意的及任意两点，有（5.2.7）成立，则称为上的严格凸函数，或称在上是严格凸的。若是上的（严格）凸函数，则称是上的（严格）凹函数。根据凸函数的定义，易证凸函数有如下的基本性质。(0,1)(1)(2)XXD(1)(2)(1)(2)((1))()(1)()fXXfXfX()fXD()fXDfDfD性质5.2.1设是凸集上的凸函数，为实数，则也是上的凸函数。性质5.2.2设和均为凸集上的凸函数，则也是上的凸函数。性质5.2.3若均为凸集上的凸函数，且。则线性组合也是上的凸函数。()fXD0()fXD1()fX2()fXD12()()()fXfXfXD1(),,()mfXfXD0,1,2,,iim1122()()()mmfXfXfXD性质5.2.4设是凸集上的凸函数，对任一实数，集合是凸集（称为水平集）。我们可以根据凸函数的定义来判定一个函数是否为凸函数，但如果该函数是可微函数，那么可按下述法则判别。()fXD|,()SXXDfXS定理5.2.1（函数凸性的一阶条件）设是的非空开凸集，函数具有一阶连续的偏导数，则函数为凸函数的充要条件是恒有其中为函数在处的梯度向量。DnE1:fDE(2)(1)(1)(2)(1)(1)(2)()()()(),,fXfXfXXXXXD(1)()fXf(1)X定理5.2.2（函数凸性的二阶条件）设是的非空开凸集，函数具有二阶连续的偏导数，函数为凸函数的充要条件是函数的Hesse矩阵在上为半正定矩阵。函数为严格凸函数的充要条件是函数的Hesse矩阵在为正定矩阵。DnE1:fDEff()HxDf()HxD例5.2.3判断是否为凸函数。解用二阶条件。,从而有，因为顺序主子式，所以正定，故为严格凸函数。221122()10648fXxxxx2122121()()()206,88,20fXfXfXxxxxx222221221()()()8,0fXfXfXxxxxx200()08HX12200|20|200,160008DD()HX()fX5.2.3凸规划及其性质。考虑非线性规划问题（5.2.8）这里，约束可表示为min()()0,1,2,,..()0,1,2,,jifXgXjlsthXimXDD|()0,1,2,,;()0,1,2,,jiDXgXjlhXim若为凸函数，为凹函数（或说为凸函数），则称以上非线性规划为凸规划。凸规划是一类比较简单，而且具有一些良好性质的非线性规划。前面已经指出，凸规划的可行域为凸集，其局部极小点就是全局极小点，而且局部极小点的全体构成一个凸集。当凸规划的目标函数为严格凸函数是，其全局极小点唯一。()fX()(1,2,,)jgXjl()jgX()fX例5.2.4验证下述非线性规划为凸规划。22212313121222112321233123min()222()0.()216()0fXxxxxxxxxxgXxxxstgXxxxgXxxx解目标函数可写成的海赛矩阵为,它的顺序主子式均大于0，故为正定矩阵，即为严格凸函数。同理可以验证为严格凸函数，是线性函数，所以此规划的可行域为凸集，因此上述非线性规划为凸规划。()fX2411()120104fX2()fX()fX1()gX23(),()gXgX若非线性规划的目标函数为的二次函数或二次型，约束条件又全是线性函数，则称之为二次规划。二次规划的数学模型可表示为（5.2.9）这里，X11111min()2..,1,2,,;0,1,2,,nnnjjjkjkjjknijjijjfXcxcxxstaxbimxjn,1,2,,kjjkcckn若目标函数第二项的二次型为正定（或半正定）的，则目标函数必为严格凸函数（或凸函数）。二次规划的可行域为凸集，故此时为凸规划，它是非线性规划中比较简单的一类，较容易求解。许多实际问题，均可归结为二次规划模型。5.2.4含不等式约束的非线性规划问题的最优性条件下面考虑如下非线性规划问题的最优性条件。（5.2.10）其中具有一阶连续偏导数，为凸函数。min,s.t.()0,1,2,,ifXgXim(),()ifXgX()igX1,2,,im记，则称为式（5.2.10）表示的非线性规划问题的可行域，称为其可行解。定义5.2.4设是一个可行点，对某一方向而言，若存在实数，使对于任意的，均有，则称方向是点处的一个可行方向。()0,1,2,,iDXgXimDXD0XDP000[0,]0XPDP0X当得知可行点不是极小点时，则需要点搜寻可使目标函数减小的点，这样的点应该在能使目标函数减小的可行方向上，这个方向称为可行下降方向。将目标函数在处作一阶泰勒展开，可知可行下降方向应满足。0X0X()fX0X00()()()fXfXfXP0()0fXP定义5.2.5设为非线性规划问题式（5.2.10）的可行解，若对所有的（在处可微，且存在非负实数，满足（5.2.11）则称在为Kuhn-Tucker点或满足Kuhn-Tucker条件。*XD1:nigRR1,2,,)im*X12,,,m0***1()(),(),,,,miiiiifXgXgim0012x*X*XKuhn和Tucker提出了关于约束非线性规划问题最优解的著名的必要条件。这是非线性规划领域中最重要的理论成果之一，是一般非线性规划问题中确定某点为极值点的必要条件。虽然不是充分条件，但是，对于凸规划而言，它是充分必要条件，结论如下：定理5.2.3设函数和在处可微，在处连续，函数和，是凸函数，若为Kuhn-Tucker点，则是非线性规划问题式（5.2.10）的最优解。1:nfER1*:,()nigERiNX*X*,()igiNX*Xf*,()igiNX*X*X5.2.5应用LINGO、MATLAB软件求解非线性规划下面通过几个例子来说明LINGO软件在非线性规划中的应用。例5.2.5求解下列非线性规划问题。2211221212min()10460..()80fXxxxxxxsthXxx解：LINGO程序编制如下：min=x1^2-x1*x2+x2^2-10*x1-4*x2+60;x1+x2=8;end求解结果如下：经过21次迭代，得到目标的极小值为17，此时。也可以应用MATLAB软件求解非线性规划，即用指令fminsearch：[x,fval,exitflag]=fminsearch(fun,x0)125,3xx在输入部分，fun是所给函数，x0时自取的自变量的初始值，在输出部分x是函数取最小值的自变量的点，fval是函数的最小值；exitflag是输出标记，当exitflag=1时，表示解是收敛的，所求的x,fval有效，当exitflag=0时，表示无解，所求的x,fval无效。例5.2.6求函数的极小点。解：Matlab编程如下：f='(x(1)-2)^2+(x(2)-1)^2'x0=[1,1];[x,fval,exitflag]=fminsearch(f,x0)结果如下：x=2.00001.0000；fval=8.1568e-010；exitflag=12212()(2)(1)fXxx为求有约束非线性多元函数的最小值，也可以调用函数fmincon:[x,fval,exitflag]=fmincon(fun,x0,a,b,aeq,beq,lb,ub,nonlcon)在输入部分，fun是所给函数，x0