数学建模(7)

数学模型MathematicalModel（7）优化模型人们在解决实际问题时往往会提出若干方案，通过各方面的信息论证，从中提取最佳方案。我们关心的是如何从多个方案中科学合理地提取出最佳方案。优化问题无所不在，它包含两个方面的内容：（1）建立数学模型。模型中的数学关系式反映了最优化问题所要达到的目标和各种约束条件。（2）求解。数学模型建好以后，选择合理的最优化方法进行求解。优化问题包含有多个分支，如线性规划、整数规划、非线性规划、动态规划、多目标规划等。按变量的多少可分为单变量和多变量优化问题优化模型一、单变量优化问题只有一个变量的最小(大)化问题，即一维搜索问题。该问题在某些情况下可以直接用于求解实际问题，但大多数情况下它是作为多变量最优化方法的基础在应用，因为进行多变量最优化要用到一维搜索法。该问题的数学模型为：其中，x、x1和x2为标量，f(x)为函数，返回标量。21)(minxxxxfx优化模型该问题的搜索过程为：其中xk为本次迭代的值，d为搜索方向，α为搜索方向上的步长参数。所以一维搜索就是要利用本次迭代的信息来构造下次迭代的条件。求解单变量最优化问题的方法有很多种，根据目标函数是否需要求导，可以分为两类，即直接法和间接法。直接法不需要对目标函数进行求导，而间接法则需要用到目标函数的导数。dxxkk1优化模型1、直接法常用的一维直接法主要有消去法和近似法两种：（1）消去法该法利用单峰函数具有的消去性质进行反复迭代，逐渐消去不包含极小点的区间，缩小搜索区间，直到搜索区间缩小到给定允许精度为止。一种典型的消去法为黄金分割法(GoldenSectionSearch）。黄金分割法的基本思想是在单峰区间内适当插入两点，将区间分为三段，然后通过比较这两点函数值的大小来确定是删去最左段还是最右段，或同时删去左右两段保留中间段。重复该过程使区间无限缩小。插入点的位置放在区间的黄金分割点及其对称点上，所以该法称为黄金分割法。该法的优点是算法简单，效率较高，稳定性好。优化模型（2）多项式近似法该法用于目标函数比较复杂的情况。此时寻找一个与它近似的函数代替目标函数，并用近似函数的极小点作为原函数极小点的近似。常用的近似函数为二次和三次多项式。二次内插涉及到形如下式的二次函数数据拟合问题：其中步长极值为：cbamq2)(ab2优化模型然后只要利用三个梯度或函数方程组就可以确定系数a和b，从而可以确定α*。得到该值以后，进行搜索区间的收缩。在缩短的新区间中，重新安排三点求出下一次的近似极小点α*，如此迭代下去，直到满足终止准则为止。其迭代公式为：其中)()()()()()(213122311233122311231xfxfxfxfxfxfxk22jiijxxjiijxx优化模型2、间接法间接法需要计算目标函数的导数，优点是计算速度很快。常见的间接法包括牛顿切线法、对分法、割线法和三次插值多项式近似法等。用得较多的是三次插值法。三次插值的基本思想与二次插值的一致，是用四个已知点构造一个三次多项式P3(x)，用它逼近函数f(x)，以P3(x)的极小点作为f(x)的近似极小点。一般讲，三次插值法比二次插值法的收敛速度要快些，但每次迭代需要计算两个导数值。优化模型三次插值法的迭代公式为其中如函数的导数容易求得，一般首先考虑使用三次插值法，因为它具有较高效率。对于只需要计算函数值的方法中，二次插值法是一个很好的方法，它的收敛速度较快，尤其在极小点所在区间较小时尤其如此。黄金分割法则是一种十分稳定的方法，并且计算简单。21212212212)()()()(xfxfxfxxxxk2121211)()(3)()(xxxfxfxfxf2/121212))()((xfxf优化模型3、单变量优化的Matlab实现fminbnd返回固定区间内单变量函数的最小值x=fminbnd(fun,x1,x2)返回区间{x1，x2}上fun参数描述的标量函数的最小值xx=fminbnd(fun,x1,x2,options)用options参数指定的优化参数进行最小化x=fminbnd(fun,x1,x2,options,P1,P2,...)提供另外参数P1,P2等,传输给目标函数fun。如果没有设置options选项，则令options=[]优化模型注(1)Fun：需要最小化的目标函数。fun函数需要输入自变量x，返回x处的目标函数值f。如x=fminbnd(@sin,0,5)同样，fun参数可以是一个包含函数名的字符串。对应的函数可以是M文件、内部函数或MEX文件。上述问题最小值情况可以图形化说明x=0:pi/100:5;y=sin(x);plot(x,y)优化模型注(2)Options：优化参数选项。可以用optimset函数设置或改变这些参数的值。options参数有以下几个选项：Display–显示的水平。选择‘off’，不显示输出；选择‘iter’，显示每一步迭代过程的输出；选择‘final’，显示最终结果。MaxFunEvals–函数评价的最大允许次数。MaxIter–最大允许迭代次数。TolX–x处的终止容限。优化模型例：对边长为3m的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？优化模型二、多变量优化模型1、线性规划(LinearProgramming)模型（1）线性规划模型的一般形式是：0,...,,),(.........),(...),(......max(min)21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcz＝＝＝优化模型（2）线性规划模型的压缩形式是：njxmibxaxczjinjjijnjjj,...,2,1,0,...,2,1,),(max(min)11＝优化模型（3）线性规划模型的矩阵形式是：其中0X)b,(AXCXmax(min)＝z),...,,(C21ncccnjxxx...X21mjjjjaaa...A21mbbb...b21mnmmnnnaaaaaaaaaAAA............),...,,(A21222211121121优化模型（4）线性规划问题的标准形式是：或矩阵形式为：0,,,max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcznjxmibxaxczjnjijijnjjj,...,2,1,0,...,2,1,max110maxXbAXCXz优化模型（5）线性规划模型的一般解法图解法单纯形法对偶单纯形法表上作业法动态规划法等等优化模型（6）解法的Matlab实现x=linprog(c,A,b)求解问题minc*x，约束条件为A*x=bx=linprog(c,A,b,Aeq,beq)求解上面的问题，增加等式约束，即Aeq*x=beq。若没有不等式存在，则令A=[]、b=[]。x=linprog(c,A,b,Aeq,beq,lb,ub)定义设计变量x的下界lb和上界ub，使得x始终在该范围内。若没有等式约束，令Aeq=[]、beq=[]。x=linprog(f,A,b,Aeq,beq,lb,ub,x0)设置初值为x0。该选项只适用于中型问题，缺省时大型算法将忽略初值。优化模型x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)用options指定的优化参数进行最小化。[x,fval]=linprog(...)返回解x处的目标函数值fval。[x,lambda,exitflag]=linprog(...)返回exitflag值，描述函数计算的退出条件。[x,lambda,exitflag,output]=linprog(...)返回包含优化信息的输出变量output。[x,fval,exitflag,output,lambda]=linprog(...)将解x处的拉格朗日乘子返回到lambda参数中。优化模型例子：某厂生产甲乙两种产品，制成一吨产品甲需用资源A3吨，资源B4m3；制成一吨产品乙需用资源A2吨，资源B6m3，资源C7个单位。若一吨产品甲和乙的经济价值分别为7万元和5万元，三种资源限制量分别为90吨、200m3和210个单位，试决定应生产这两种产品各多少吨才能使创造的总经济价值最高？令生产产品甲的数量为x1，生产产品乙的数量为x2。由题意可以建立下面的模型：该模型中要求目标函数最大化，需要按照Matlab的要求进行转换，即目标函数为优化模型0,0210720064902357max212212121xxxxxxxxxz2157maxxxz优化模型首先输入下列系数：f=[-7;-5];A=[32；46；07];b=[90;200;210];lb=zeros(2,1);然后调用linprog函数：[x,fval,exitflag,output,lambda]=linprog(f,A,b,[],[],lb)优化模型Optimizationterminatedsuccessfully.x=14.000024.0000fval=-218.0000exitflag=1output=iterations:5cgiterations:0algorithm:'lipsol'lambda=ineqlin:[3x1double]eqlin:[0x1double]upper:[2x1double]lower:[2x1double]优化模型由上可知，生产甲种产品14吨、乙种产品24吨可使创建的总经济价值最高。最高经济价值为218万元。exitflag=1表示过程正常收敛于解x处。练习1练习2练习3优化模型2、整数规划(IntegerProgramming)模型一般来说，所谓整数规划即整数线性规划，也就是要求全部或部分变量取值为整数这一特殊条件。模型为且为整数0,X)b,(AXCXmax(min)＝z优化模型3、非线性规划模型所谓非线性规划也就是在目标函数或约束条件中含有自变量的非线性函数。求解这类问题的方法一般有两类:直接搜索法(Searchmethod)和梯度法(Gradientmethod)。直接搜索法适用于目标函数高度非线性，没有导数或导数很难计算的情况，由于实际工程中很多问题都是非线性的，直接搜索法不失为一种有效的解决办法。常用的有Hooke-Jeeves搜索法、Pavell共轭方向法等，其缺点是收敛速度慢。优化模型在函数的导数可求的情况下，梯度法是一种更优的方法，该法利用函数的梯度(一阶导数)和Hessian矩阵(二阶导数)构造算法，可以获得更快的收敛速度。函数f(x)的负梯度方向－▽f(x)即反映了函数的最大下降方向。当搜索方向取为负梯度方向时称为最速下降法。常见的梯度法有最速下降法、Newton法、Marquart法、共轭梯度法和拟牛顿法（Quasi-Newtonmethod）等。在所有这些方法中用得最多的是拟牛顿法，这些方法在每次迭代过程中建立曲率信息，构成下式得二次模型问题优化模型其中，Hessian矩阵H为一正定对称矩阵，C为常数向量，b为常数。对x求偏导数可以获得问题的最优解解x*可写作：bXCHXX21TTXmin0CHx)f(x**CHx1*优化模型解法的Matlab实现x=fminunc(