实验一工业生产的产量问题

1、实验七 生产计划中的产量问题实验目的】1介绍无约束最优化方法的一些基本概念。2了解几种常见的无约束优化问题的求解方法，如迭代算法、最速下降法(梯度法)、牛顿法(Newt on)、拟牛顿法。3学习掌握用MATLAB优化工具箱中的命令来求解无约束优化问题。实验内容】某公司生产一种产品有甲、 乙两个品牌， 试讨论产销平衡下的最大利润。 所谓产销平衡 指公司的产量等于市场上的销量。 利润既取决于销量和单件价格， 也依赖于产量和单件成本。按照市场规律，甲种品牌的价格 pi固然会随其销量Xi的增长而降低；同时乙品牌销量X2的 增长也会使甲的价格有稍微下降，根据实际情况，可以确定价格与销量成线性关系，即p1

2、 = 300 2.35 x1 0.09 x2乙的价格卩2遵循同样的规律，有p2 = 480 0.14 x1 2.98 x2甲品牌的成本会随着其产量的增长而降低，按实际情况可假设为负指数关系，即有q1 = 38 e 0.023X1 + 1 16乙品牌的成本q2遵循同样的规律，有0.018 x2q2 = 94 e2 + 145试确定甲、乙两种品牌的产量，使公司获得的总利润最大。【实验准备】 无约束最优化方法是指在没有约束条件限制下， 求多变量实值函数极值的方法。 无约束 最优化问题的数学表达式为min f (x) , x =( x1, x2，Xn) Rn(1)一般f为非线性函数，x是n维实变量，实

3、际上这是一个多元函数无条件极值 问题。由于一个求极大值问题， 可以添加负号的方式转化为求极小值问题， 因此通常只讨论求极小 值问题。应该注意的是，极值问题的解，即极值点，都是 局部最优解 ，全局最优解 只能从局 部最优解的比较中得到。如何求解无约束最优化问题( 1)的最优解呢？一般是采用迭代方法，即先选择一个初 始点， 再寻找该点处的下降方向，我们称为搜索方向。在该方向上求极小点，得到一个新的 点。这个新的点要优于原来的点， 即新点处的目标函数值小于原来点处的目标函数值。然后在新点处再寻找下降方向和该方向上求极小点，如此下去，最终得到最优点。因此， 求解无约束最优化问题需解决两个问题： 一是在

4、某些方向上的一维极小点，我们也称为一维搜索； 另一个是寻找某些点处的下降方向， 这是无约束最优化方法中最重要的一 个问题。我们先了解第一个问题最常用的搜索方法。1. 求一维极小的二点二次插值方法设d(k)是点x(k)处的一个搜索方向，要在该方向上寻优问题，转化为求一维函数()=f ( x(k) + d(k)(2)的求极值问题。最常用的一维搜索方法是插值法，即用某些点的函数值(或导数值)构造插值函数，用插值函数的极小点来近似函数()的极小点。这里介绍一种有效的插值方法，称为二点二次插值方法，即用二点处的函数值和一个点处的导数值构造二次函数，反复用二次函数的极小点来逼近函数()的极小点。算法1二点

5、二次插值法(1) 取初始点 1 (如(如 =0.1 )，置精度要求(2)则置(3)(4)计算如果(5)计算(6)，则停止计算(1 = 0),初始步长 (如，并计算1 =( 1),;否则置 =2 = ( 2 )2 1 ),则置=21( 2 J'1 ( 2 1)作为极小点)；和步长缩减因子(1)，转(3)否则置(0, 1)= ，转2.最速下降法前面介绍了一维搜索的二点二次插值方法, 来看看两个概念。2)F面讨论如何选择搜索方向的问题,我们先定义1称n维向量(X1X2)T为函数f(x)在x处的梯度，记为 f(x)Xn f (X)=(X1定义2设d是任意的单位向量，若极限 limn 0Xnf

6、(X ")一空存在，则称该极限为(3)函数f (X)在X处沿方向d的一阶方向导数，简称为方向导数，记为f(X)，即d_f(x) = lim f(X ad) f(X)(4dn 0a最速下降法的基本思想：选取一点x1作为初始点，计算该点的梯度f(x)，求该点处的最速下降方向，即令 d1 = f (X1)，再沿d1方向前进，寻找该方向上的极小点，得 到点x2，再计算 f(x2)，令d2 = f(x2)，沿d2方向前进，得到点x3，如此下去 具体算法如下：算法2最速下降法(1) 取初始点x1，置精度要求为，置k = 1(2) 若| f (xk) | v ，则停止计算(xk为无约束问题的最优解

7、)；否则置dk = f (xk)(3) 一维搜索，求一维问题min (a) = f ( xk ad k)ak 1kk得 ak，置 x = x ad 。(4) 置k = k +1，转步骤(2)在算法中，为精度要求，即当梯度接近于0时，我们就认为达到极小点，终止计算。这样做的目的是避免算法产生死循环，算法中的一维搜索可用算法1来求解。最速下降法是一种最基本的算法，它在最优化方法中占有重要地位。其优点是工作量小， 存储变量较少，初始点要求不高；缺点是收敛慢，效率不高，有时达不到最优解。下面介绍一种简单而直观的方法 Newton法。3. 牛顿法22 f将f (x)的二阶导数记作f(X)=()是一个n

8、n矩阵，称黑塞(Hessian )XiXj矩阵(简记H(X)。当f (x)二阶偏导数连续时，H(X)是对称矩阵。Newton法的基本思想是用一个二次函数去近似目标函数f(x)，然后精确地求出这个二次函数的极小点，并把这个极小点作为所示函数的极小点x的近似值。k 1*k设x 是f(x)极小点x的第k 1次近似，将f (X)在x点作二阶Taylor展开，略去 高于二阶的项，用dk = xk 1 xk得到f (xk 1) = f (xk dk)f(xk) + f (xk) dk + 1 d 2 f (xk) d k(5)为了求dk使f(xk dk)最小，只需将(5)式右端对dk求导，并令其为零，可得

9、 f (xk) + 2 f(xk) d k = 0(6)称为牛顿方程。当黑塞矩阵2 f (xk)正定时，可解得dk 一 ( 2f(xk)-1 f(xk)( 7)称为牛顿方向。其迭代公式为k 1 k2 k -1kx = x - ( f(x ) f(x )(8)4. 拟牛顿法牛顿法的优点是在接近最优解时具有2阶收敛性，缺点是计算复杂，而且会出现病态、不正定等情况。为克服这些问题，同时又保持较快的收敛，禾U用第k和第k 1步得到的xk、k 1kk 1k 12kx 、 f(x ) . f (x )根据拟牛顿条件构造一正定矩阵G近似代替f(x )或H k 1近似代替(2 f (xk 1)-1，得到的迭代

10、算法称为拟牛顿法。其中有两个常用的著名的迭代公式为BFGS公式和DFP公式，可参见其他最优化方法书籍或MATLAB帮助。5. MATLAB求解无约束优化问题的主要命令(1) MATLAB5.2及以下版本使用的命令x = fmin( ' fun ' , x1 , x2 )求一元函数 y = f( x )在x1 , x2 内的极小值x = fmin( ' fun ' , x1 , x2 , optio ns )同上，参数 optio ns 的定义由表 1给出x , opti ons = fmin( .)同上，同时返回参数optio ns 的值fmin函数采用黄金分割

11、法和抛物线插值法，fun可直接用函数表达式表示，也可以是用M文件定义的函数名。建立函数形式的M-文件格式如下，文件名fun.m (般M函数文件名取函数名)function f = fun( x )f = f( x )x = fmins( ' fun ' , x0 )求多元函数(1)以x0为迭代初值的局部极小值x = fmins( ' fun ' , x0 , options )同上，参数 options 的定义由表 1 给出x , optio ns = fmin s(.)同上，同时返回参数 optio ns 的值fmins函数采用Nelder - Meade单纯

12、形搜索法，fun可直接用函数表达式表示，也 可以是用M文件定义的函数名。x = fminu( ' fun ' , xO )x = fminu( ' fun ' , x0 , opti ons )x , opti ons = fminu( ' fun ' , x0 ,.)的值fminu函数为无约束优化提供了三种算法，由 提供了二种算法，由optio ns (7)控制。这里,求多元函数(1)以x0为迭代初值的局部极小值同上，参数options 的定义由表1给出同时返回参数optio ns同上,opti ons (6) fminu必须先用控制，为步长一

13、维搜索 M-文件定义函数 fun。(2) MATLAB5.3以上版本使用的命令fminbnd替代fmin求解一元函数极值，使用格式、搜索算法与之相同，x , Fval =fminbnd( ' fun ' , x0 ,.)同时返回解x处的函数值，而不是参数options的返回值fminsearch替代fmins求解多元函数(1)极值，使用格式、搜索算法与之相同fminunc替代fminu求解多元函数(1)极值，使用格式、搜索算法与之相同有关上述命令的详细信息和使用方式可在帮助文件中了解，或在命令框里输入help“命令名”查阅。在MATLAB5.3以上的各种最新版本中fmin、fm

14、ins和fminu命令仍然有用，但在MATLAB勺未来版本将可能删除这些命令。(3) 命令中参数optio ns的有关定义在大多数MATLAB化命令函数中有一个控制参数options，它是一个有18个分量的向量，包含了在优化程序中要用到的参数，以便在计算最优值时控制精度要求、输出形式、搜索算法、迭代次数、步长等等是。在对优化命令函数的第一次调用时，向量options会自动使用缺省值；当然在调用前，可以对optio ns的某些分量进行赋值，以达到控制要求。表1 参数options各分量说明序号功能定义分量说明缺省值含义1输出形式options(1)=1 ，有中间结果输出 options(1)=

15、1,给出警告信息0，无中间结果输出2解x(k)的精度(k)options(2)设置x 的精度|x(k1)(k) xx(k)|< 1e 43函数f (k)的精度options(3)设置f (k)的精度1)f (k)f (k)-< 1e 44函数g(k)的精度options(4)设置g (k)的精度，由 命令 constr、minmax使用终止判 据g(k1) g(k)-W 彳a 7(k) g5主要算法options(5)=1 ，高斯-牛顿法0，LM方法6搜索方向算法options(6)=1 ,拟牛顿法DFP公式 options(6)=2，最速下降法0，拟牛顿法的BFGS公式7步长一维

16、搜索算法options=1，三次多项式插值0,混合的二次和三次多项式8函数值输岀options©)输出极值点处的函数 值9梯度检查options(9)=1，最初几步，梯度将与有限微分计算的结果比较0,不作检查10函数计算次数option(10)输出函数计算次数11梯度计算次数option(11)输出梯度计算次数12约束梯度计算次数option(12)输出约束梯度计算次 数13等式约束的个数option(13)确定等式约束数目0，等式约束个数为014最大迭代次数option(14)输入迭代的最大次数100 n，n为自变量个数200 n (fmins )500 n (fmin )15目标

17、优化由 attgoal 命令使用，option(15) 输入须达目的的目标个数016差分步长最小值用差分计算梯度时步长的下限1e 817差分步长最大值用差分计算梯度时步长的上限0.118步长参数，一般取1或更小【实验方法与步骤】1. MATLAB化工具箱中解无约束问题的命令和参数options的基本用法下面用例题来予以说明例 1 求解 min f(x) = ex 5 x , 1< x< 2输入命令：>> x=fmin( 'exp(x) - 5*x' , 1 , 2 ) , f=exp( x ) - 5*xx =1.6094f =-3.0472同时，该问题

18、可以用 fminbnd求解，得到的解答一样输入命令：>> x , fval=fmi nbn d( 'exp( x ) - 5*x' , 1 , 2 )x =1.6094fval =-3.0472例2用拟牛顿法的DFP公式求解min f (x) = 4x" + x； x3x2，初值为(1, 2)，要 求精度为1e 7,给出函数计算次数以及函数值首先建立M-文件，文件名取函数名fun.mfunction f = fun( x )f = 4 * x( 1 )A2 + x( 2 )A2 - x( 1 )A3 * x( 2 )输入命令：>> x0=1,2

19、;>> opt( 2 )=1e-6;%设置自变量要求的精度>> opt( 3 )=1e-6;%设置函数所要求的精度>> opt( 6 )=1;%搜索算法用拟牛顿法的DFP公式求解>> x, opt=fminu( ' fun ', x0, opt);%返回参数 options 的值给向量 opt可得到结果x =1.0e-008 *-0.34930.7566参数options的值返回给向量opt，全部元素略。>> n=opt( 10 );%函数计算次数赋值给nn =35>> y=opt( 8 );%在极值点处函

20、数值赋值给yy =1.0606e-0162. 引例问题的分析与求解由题设可知，甲品牌产品单件获利为p1 q1，乙品牌产品单件获利为P2 q2，由产 销平衡原理，所有产品的销量即为产量，则甲、乙两种产品总获利为Z(X1 ,X2)=( Pi qi) Xi +( P2 q2) x?容易看出，原问题实际上转化为求二元函数z(x1 ,X2)的极大值，为用MATLAB优化工具箱中的fminunc求解，需将其转化为求函数y(x1, x2) = z(x1, x2)的最小值。为确定初始值，先忽略成本，并令p1价格中x2项的较小系数0.09和p2中x1项较小的 系数0.14等于零(因为它们对价格的作用比较微弱，暂时可忽略不计)，则确定初值问题转化为求Z(Xi,X2)=( 300 2.35 Xi) Xi +( 480 2.98 X?) X：的极值，很容易可以求得xi =300 = 63.83 , x2 = 480= 80.54，我们用它作为原2 2.3522.98问