《数学建模》PPT课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数学模型,Mathematical Model,（,7,）,优化模型,人们在解决实际问题时往往会提出若干方案，通过各方面的信息论证，从中提取最佳方案。我们关心的是如何从多个方案中科学合理地提取出最佳方案。优化问题无所不在，它包含两个方面的内容：,（,1,）建立数学模型。模型中的数学关系式反映了最优化问题所要达到的目标和各种约束条件。,（,2,）求解。数学模型建好以后，选择合理的最优化方法进行求解。,优化问题包含有多个分支，如线性规划、整数规划、非线性规划、动态规划、多目标规划等。,按变量的多少可分为单变量和多变量优化问题,优化模型,一、单变量优化问题,只有一个变量的最小,(,大,),化问题，即一维搜索问题。该问题在某些情况下可以直接用于求解实际问题，但大多数情况下它是作为多变量最优化方法的基础在应用，因为进行多变量最优化要用到一维搜索法。,该问题的数学模型为：,其中，,x,、,x,1,和,x,2,为标量，,f(x),为函数，返回标量。,优化模型,该问题的搜索过程为：,其中,x,k,为本次迭代的值，,d,为搜索方向，,为搜索方向上的步长参数。所以一维搜索就是要利用本次迭代的信息来构造下次迭代的条件。,求解单变量最优化问题的方法有很多种，根据目标函数是否需要求导，可以分为两类，即直接法和间接法。直接法不需要对目标函数进行求导，而间接法则需要用到目标函数的导数。,优化模型,1,、直接法,常用的一维直接法主要有消去法和近似法两种：,（,1,）消去法 该法利用单峰函数具有的消去性质进行反复迭代，逐渐消去不包含极小点的区间，缩小搜索区间，直到搜索区间缩小到给定允许精度为止。一种典型的消去法为黄金分割法,(Golden Section Search,）。黄金分割法的基本思想是在单峰区间内适当插入两点，将区间分为三段，然后通过比较这两点函数值的大小来确定是删去最左段还是最右段，或同时删去左右两段保留中间段。重复该过程使区间无限缩小。插入点的位置放在区间的黄金分割点及其对称点上，所以该法称为黄金分割法。该法的优点是算法简单，效率较高，稳定性好。,优化模型,（,2,）多项式近似法 该法用于目标函数比较复杂的情况。此时寻找一个与它近似的函数代替目标函数，并用近似函数的极小点作为原函数极小点的近似。常用的近似函数为二次和三次多项式。,二次内插涉及到形如下式的二次函数数据拟合问题：,其中步长极值为：,优化模型,然后只要利用三个梯度或函数方程组就可以确定系数,a,和,b,，从而可以确定,*,。得到该值以后，进行搜索区间的收缩。在缩短的新区间中，重新安排三点求出下一次的近似极小点,*,，如此迭代下去，直到满足终止准则为止。其迭代公式为：,其中,优化模型,2,、间接法,间接法需要计算目标函数的导数，优点是计算速度很快。常见的间接法包括牛顿切线法、对分法、割线法和三次插值多项式近似法等。用得较多的是三次插值法。,三次插值的基本思想与二次插值的一致，是用四个已知点构造一个三次多项式,P,3,(x),，用它逼近函数,f(x),，以,P,3,(x),的极小点作为,f(x),的近似极小点。一般讲，三次插值法比二次插值法的收敛速度要快些，但每次迭代需要计算两个导数值。,优化模型,三次插值法的迭代公式为,其中,如函数的导数容易求得，一般首先考虑使用三次插值法，因为它具有较高效率。对于只需要计算函数值的方法中，二次插值法是一个很好的方法，它的收敛速度较快，尤其在极小点所在区间较小时尤其如此。黄金分割法则是一种十分稳定的方法，并且计算简单。,优化模型,3,、单变量优化的,Matlab,实现,fminbnd,返回固定区间内单变量函数的最小值,x=fminbnd(fun,x1,x2),返回区间,x1,，,x2,上,fun,参数描述的标量函数的最小值,x,x=fminbnd(fun,x1,x2,options),用,options,参数指定的优化参数进行最小化,x=fminbnd(fun,x1,x2,options,P1,P2,.),提供另外参数,P,1,P,2,等,传输给目标函数,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,、线性规划,(Linear Programming),模型,（,1,）线性规划模型的一般形式是：,优化模型,（,2,）线性规划模型的压缩形式是：,优化模型,（,3,）线性规划模型的矩阵形式是：,其中,优化模型,（,4,）线性规划问题的标准形式是：,或,矩阵形式为：,优化模型,（,5,）线性规划模型的一般解法,图解法,单纯形法,对偶单纯形法,表上作业法,动态规划法,等等,优化模型,（,6,）解法的,Matlab,实现,x=linprog(c,A,b),求解问题,min c*x,，约束条件为,A*x=b,x=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,参数中。,优化模型,例子：,某厂生产甲乙两种产品，制成一吨产品甲需用资源,A 3,吨，资源,B 4m,3,；制成一吨产品乙需用资源,A 2,吨，资源,B 6m,3,，资源,C 7,个单位。若一吨产品甲和乙的经济价值分别为,7,万元和,5,万元，三种资源限制量分别为,90,吨、,200m,3,和,210,个单位，试决定应生产这两种产品各多少吨才能使创造的总经济价值最高？,令生产产品甲的数量为,x1,，生产产品乙的数量为,x2,。由题意可以建立下面的模型：,该模型中要求目标函数最大化，需要按照,Matlab,的要求进行转换，即目标函数为,优化模型,优化模型,首先输入下列系数：,f=-7;-5;,A=3 2,；,4 6,；,0 7;,b=90;200;210;,lb=zeros(2,1);,然后调用,linprog,函数：,x,fval,exitflag,output,lambda=linprog(f,A,b,lb),优化模型,Optimization terminated successfully.,x=,14.0000,24.0000,fval=,-218.0000,exitflag=,1,output=,iterations:5,cgiterations:0,algorithm:lipsol,lambda=,ineqlin:3x1 double,eqlin:0 x1 double,upper:2x1 double,lower:2x1 double,优化模型,由上可知，生产甲种产品,14,吨、乙种产品,24,吨可使创建的总经济价值最高。,最高经济价值为,218,万元。,exitflag=1,表示过程正常收敛于解,x,处。,练习,1,练习,2,练习,3,优化模型,2,、整数规划,(Integer Programming),模型,一般来说，所谓整数规划即整数线性规划，也就是要求全部或部分变量取值为整数这一特殊条件。模型为,优化模型,3,、非线性规划模型,所谓非线性规划也就是在目标函数或约束条件中含有自变量的非线性函数。,求解这类问题的方法一般有两类,:,直接搜索法,(Search method),和梯度法,(Gradient method),。,直接搜索法适用于目标函数高度非线性，没有导数或导数很难计算的情况，由于实际工程中很多问题都是非线性的，直接搜索法不失为一种有效的解决办法。常用的有,Hooke-Jeeves,搜索法、,Pavell,共轭方向法等，其缺点是收敛速度慢。,优化模型,在函数的导数可求的情况下，梯度法是一种更优的方法，该法利用函数的梯度,(,一阶导数,),和,Hessian,矩阵,(,二阶导数,),构造算法，可以获得更快的收敛速度。函数,f(x),的负梯度方向,f(x),即反映了函数的最大下降方向。当搜索方向取为负梯度方向时称为最速下降法。常见的梯度法有最速下降法、,Newton,法、,Marquart,法、共轭梯度法和拟牛顿法（,Quasi-Newton method,）等。,在所有这些方法中用得最多的是拟牛顿法，这些方法在每次迭代过程中建立曲率信息，构成下式得二次模型问题,优化模型,其中，,Hessian,矩阵,H,为一正定对称矩阵，,C,为常数向量，,b,为常数。对,x,求偏导数可以获得问题的最优解,解,x*,可写作：,优化模型,解法的,Matlab,实现,x=fminunc(fun,x0),给定初值,x0,，求,fun,函数的局部极小点,x,。,x0,可以是标量、向量或矩阵。,x=fminunc(fun,x0,options),用,options,参数中指定的优化参数进行最小化。,x=fminunc(fun,x0,options,P1,P2,.),将问题参数,p1,、,p2,等直接输给目标函数,fun,，将,options,参数设置为空矩阵，作为,options,参数的缺省值。,x,fval=fminunc(.),将解,x,处目标函数的值返回到,fval,参数中。,优化模型,x,fval,exitflag=fminunc(.),返回,exitflag,值，描述函数的输出条件。,x,fval,exitflag,output=fminunc(.),返回包含优化信息的结构输出。,x,fval,exitflag,output,grad=fminunc(.),将解,x,处,fun,函数的梯度值返回到,grad,参数中。,x,fval,exitflag,output,grad,hessian=fminunc(.),将解,x,处目标函数的,Hessian,矩阵信息返回到,hessian,参数中。,优