运筹学-非线性规划

《运筹学-非线性规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、高级运筹学非线性规划教材及参考书指定教材：沈荣芳，运筹学高级教程（第二版），高等教育出版社，2008.8参考资料：1.韩伯棠，管理运筹学（第三版），高等教育出版社，2013.122.FREDERICKS.HILLIERGERALDJ.LIEBERMAN，INTRODUCTIONTOOPERATIONSRESEARCH，NinthEdition,20103.吴祈宗，运筹学与最优化方法（第二版），机械工业出版社，20124.DavidG.Luenberger，LinearandNonlinearProgramming，

2、Springer，2008非线性规划非线性规划在科学管理和其他领域中，大量应用问题可以归结为线性规划问题，但是，也有另外一些问题，其目标函数和（或）约束条件很难用线性函数表达。如果目标函数和（或）约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划。一般来说，求解非线性规划问题比线性规划问题困难得多。而且，也不象线性规划那样有单纯形法这一通用的方法，非线性规划目前还没有适合于各种问题的一般算法，这是需要深入研究的一个领域。非线性规划研究核心问题：最优性条件（必要条件，充分条件，Lagrange乘子理

3、论，灵敏性分析，对偶理论）迭代算法解:设投资决策变量为问题归结为总资金的限制条件下,极大化总收益和总投资之比,数学模型为î1,(i=1,2,…,n)0,iixiiì=í决定投资第个项目决定不投资第个项目例：投资决策问题某企业有n个项目可供选择投资,并且至少要对其中一个项目投资.已知该企业拥有总资金A元,投资于第i(i=1,2,…,n)个项目需要花资金ai元,并预计收益为bi元,试选择最佳投资方案使得总收益和总投资之比最大.一般地，非线性规划的数学模型为其中X称为可行域可行域中的点称为可行点，f(x)称为目标函数当时

4、，非线性规划模型称为无约束问题；当时，非线性规划模型称为有约束问题使f(x)在X上取得最小值的点称为最优解，对应的目标函数值称为最优值定义：如果目标函数或约束条件中至少有一个是非线性函数，则称这种规划为非线性规划问题。为统一起见,称以下模型minf(x)s.t.gi(x)≤0i=1，2，…，m（1）hj(x)=0j=1，2，…，l为标准的非线性规划模型,其中f(x),gi(x),hj(x)中至少有一个是x的非线性函数.称gi(x)≤0为不等式约束,hj(x)=0为等式约束.满足所有约束条件的x称为可行解,所有可行解

5、构成的集合称为可行域。例:考虑如下非线性规划问题：minf(x)=[(x－14)2+(y－15)2]1/2s.t.(x-8)2+(y-9)2≤49x≥2，x≤13x+y≤24非线性规划的最优解未必在顶点处达到；非线性规划的最优解是一组同心圆最先与可行域相交的点，在可行域的边界上达到二维非线性规划问题的图解分析例：请考虑如下非线性规划问题：minf(x)=(x－8)2+(y－8)2s.t.(x-8)2+(y-9)2≤49x≥2，x≤13x+y≤24非线性规划的最优解在可行域内部达到可以看出,x2,x3,x4是局部最优

6、解,且x3还是全局最优解,x1,x2,x3,x5是严格局部最优解,x4不是严格局部最优解.xf0x1x2x3x4x5f(x)D一个全局最优解一定是局部最优解，反之不真。对求极小化非线性规划问题，如果目标函数为凸函数，可行域为凸集，则局部最优解一定为全局最优解。与线性规划不同,非线性规划有局部最优解和全局最优解之分.凸集定义——非空集合D称为凸集,如果对于任意的x1,x2D及任意实数a,0

7、x1x2D凸集不是凸集凸集、凸函数和凸规划(1)集合D={x∈En

8、Ax≤b,x≥0}是凸集。例：定理：设D1,D2是En中的凸集，则凸函数与凹函数定义:D为凸集,若对任意x1,x2D及任意实数a,0≤a≤1有f(ax1+(1－a)x2)≤af(x1)+(1－a)f(x2)则称f(x)为凸函数;若≤变为<,称f(x)为严格凸函数。若上式中的≤(<)变为≥(>),则称f(x)为凹函数/严格凹函数。凸函数的特征是，曲线上任意两点的连线总是位于这两点间曲线的上方。凸函数的判定(一阶条件)：设f(x)在凸集D上有一阶连续

9、导数，则f(x)是D上凸函数的充要条件是对任意两点x,z∈D,x≠z,必有如果上式严格成立，则是严格凸函数的充要条件。几何意义：凸函数f(x)在曲线上任何一点做曲线的切线，那么f(x)都在切线上方。(二阶条件)：设D是一个非空开凸集，设f在D上二次可微，则f(x)是凸函数，当且仅当对所有x∈D,Hessian矩阵是半正定矩阵;注意：Hesse矩阵在D中的每一