非线性规划模型.docx

非线性规划模型————————————————————————————————作者:————————————————————————————————日期: 非线性规划模型在上一次作业中,我们对线性规划模型进行了相应的介绍及优缺点,然而在实际问题中并不是所有的问题都可以利用线性规划模型求解。实际问题中许多都可以归结为一个非线性规划问题,即如果目标函数和约束条件中包含有非线性函数,则这样的问题称为非线性规划问题。一般来说,解决非线性的问题要比线性的问题难得多,不像线性规划有适用于一般情况的单纯形法。对于线性规划来说,其可行域一般是一个凸集,只要存在最优解,则其最优解一定在可行域的边界上达到;对于非线性规划,即使是存在最优解,却是可以在可行域的任一点达到,因此,对于非线性规划模型,迄今为止还没有一种适用于一般情况的求解方法,我们在本文中也只是介绍了几个比较常用的几个求解方法。一、非线性规划的分类1无约束的非线性规划当问题没有约束条件时,即求多元函数的极值问题,。对于问题给出的极小点的初始值,按某种规律计算出一系列的,希望点阵的极限就是的一个极小点。由一个解向量求出另一个新的解向量向量是由方向和长度确定的,所以即求解和,选择和的原则是使目标函数在点阵上的值逐步减小,即检验是否收敛与最优解,及对于给定的精度,是否。,常常用到一维搜索,即沿某一已知方向求目标函数的极小点。一维搜索的方法很多,常用的有:(1)试探法(“成功—失败”,斐波那契法,);(2)插值法(抛物线插值法,三次插值法等);(3)微积分中的求根法(切线法,二分法等)。考虑一维极小化问题若是区间上的下单峰函数,我们介绍通过不断地缩短的长度,来搜索得的近似最优解的两个方法。通过缩短区间,。把在点的方向导数最小的方向作为搜索方向,:(1)选定初始点和给定的要求,;(2)若,则停止计算,,否则;(3)在处沿方向做一维搜索得,返回第二步,:,仅适用于正定二次函数的极小值问题:A为阶实对称正定阵从任意初始点和向量出发,由和可以得到——能够证明向量——是线性无关的,且关于A是两两共轭的。从而可得到——,则——为——的极小点。计算步骤:(1)对任意初始点和向量,取(2)若,即得到最优解,停止计算,否则求(3)令;返回(2):由则由最优条件当A为正定时,存在,,在点的局部有当正定时,也可用上面的牛顿法,这就是拟牛顿法。计算步骤:任取,(2)计算,若,则停止计算,否则计算,令;(3)令;返回(2),且对点有效约束的梯度线性无关,则必存在向量使下述条件成立:此条件为库恩-塔克条件(K-T条件),满足K-T条件的点也称为K-T点。K-T条件是非线性规划最重要的理论基础,是确定某点是否为最优解的必要条件,但不一定是充要条件。对于凸规划它一定是充要条件