非线性规划模型.docx

非线性规划模型.docx非线性规划模型在上一次作业中,我们对线性规划模型进行了相应的介绍及优缺点,然而在实际问题中并不是所有的问题都可以利用线性规划模型求解。实际问题中许多都可以归结为一个非线性规划问题,即如果目标函数和约束条件中包含有非线性函数,则这样的问题称为非线性规划问题。一般来说,解决非线性的问题要比线性的问题难得多,不像线性规划有适用于一般情况的单纯形法。对于线性规划来说,其可行域一般是一个凸集,只要存在最优解,则其最优解一定在可行域的边界上达到;对于非线性规划,即使是存在最优解,却是可以在可行域的任一点达到,因此,对于非线性规划模型,迄今为止还没有一种适用于一般情况的求解方法,我们在本文中也只是介绍了几个比较常用的几个求解方法。一、非线性规划的分类无约束的非线性规划当问题没有约束条件时,即求多元函数的极值问题,一般模型为minf Xx RX 。对于问题xRX0给出f(x)的极小点的初始值X(0),按某种规律计算出一系列的X(k)(k1,2,),希望点阵{X(k)}的极限X就是f(x)的一个极小点。由一个解向量X(k)X(k1)求出另一个新的解向量向量是由方向和长度确定的,所以X(k1)XkkPk(k1,2,)即求解k和Pk,选择k和Pk的原则是使目标函数在点阵上的值逐步减小,即f(X0)f(X1)f(Xk).检验{X(k)}是否收敛与最优解,及对于给定的精度0,是否||f(Xk1)||。,常常用到一维搜索,即沿某一已知方向求目标函数的极小点。一维搜索的方法很多,常用的有:1)试探法(“成功—失败”,斐波那契法,);2)插值法(抛物线插值法,三次插值法等);3)微积分中的求根法(切线法,二分法等)。考虑一维极小化问题minf(t)a t b若f(t)是[a,b]区间上的下单峰函数,我们介绍通过不断地缩短[a,b]的长度,来搜索得minf(t)的近似最优解的两个方法。通过缩短区间[a,b],逐步搜索得atbminf(t)的最优解t*。把f(x)在X(k)点的方向导数最小的方向作为搜索方向,即令Pkf(Xk).计算步骤:(1)选定初始点X0和给定的要求0,k0;(2)若||f(Xk)||,则停止计算,X*Xk,否则P(k)f(Xk);(3)在X(k)处沿方向P(k)做一维搜索得X(k1)XkkPk,令kk1,返回第二步,:kf(X(k))Tf(X(k))(k).f(X(k)TH(X(k)))f(X)(k)f(X(k))f(X(k))f(X(k))Tf(X)(,,,),x1x2xnf(X(k)),f(X(k)),,f(X(k))x1x2xnH(X(k))f(X(k)),f(X(k)),,f(X(k))x2x1x2x2x2xnf(X(k)),f(X(k)),,f(X(k)),仅适用于正定二次函数的极小值问题:minf(X)1XTAXBTXc2A为n n阶实对称正定阵 X,B En,c为常数从任意初始点 X(1)和向量P(1) f(X(1))出发,由X(k1)