《数学建模》PPT课件.ppt

《《数学建模》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数学建模》PPT课件.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学模型数学模型Mathematical ModelMathematical Model（7）优化模型优化模型 人们在解决实际问题时往往会提出若干方案，通过各人们在解决实际问题时往往会提出若干方案，通过各方面的信息论证，从中提取最佳方案。我们关心的是如方面的信息论证，从中提取最佳方案。我们关心的是如何从多个方案中科学合理地提取出最佳方案。优化问题何从多个方案中科学合理地提取出最佳方案。优化问题无所不在，它包含两个方面的内容：无所不在，它包含两个方面的内容：（1）建立数学模型。模型中的数学关系式反映了最优）建立数学模型。模型中的数学关系式反映了最优化问题所要达到的目标和各种约束条件。化问题所要达

2、到的目标和各种约束条件。（2）求解。数学模型建好以后，选择合理的最优化方）求解。数学模型建好以后，选择合理的最优化方法进行求解。法进行求解。优化问题包含有多个分支，如线性规划、整数规划、优化问题包含有多个分支，如线性规划、整数规划、非线性规划、动态规划、多目标规划等。非线性规划、动态规划、多目标规划等。按变量的多少可分为单变量和多变量优化问题按变量的多少可分为单变量和多变量优化问题优化模型优化模型一、单变量优化问题一、单变量优化问题 只有一个变量的最小只有一个变量的最小(大大)化问题，即一维搜索问题。化问题，即一维搜索问题。该问题在某些情况下可以直接用于求解实际问题，但大该问题在某些情况下可以

3、直接用于求解实际问题，但大多数情况下它是作为多变量最优化方法的基础在应用，多数情况下它是作为多变量最优化方法的基础在应用，因为进行多变量最优化要用到一维搜索法。因为进行多变量最优化要用到一维搜索法。该问题的数学模型为：该问题的数学模型为：其中，其中，x、x1和和x2为标量，为标量，f(x)为函数，返回标量。为函数，返回标量。优化模型优化模型 该问题的搜索过程为：该问题的搜索过程为：其中其中xk为本次迭代的值，为本次迭代的值，d为搜索方向，为搜索方向，为搜索方向为搜索方向上的步长参数。所以一维搜索就是要利用本次迭代的信上的步长参数。所以一维搜索就是要利用本次迭代的信息来构造下次迭代的条件。息来构

4、造下次迭代的条件。求解单变量最优化问题的方法有很多种，根据目标函求解单变量最优化问题的方法有很多种，根据目标函数是否需要求导，可以分为两类，即直接法和间接法。数是否需要求导，可以分为两类，即直接法和间接法。直接法不需要对目标函数进行求导，而间接法则需要用直接法不需要对目标函数进行求导，而间接法则需要用到目标函数的导数。到目标函数的导数。优化模型优化模型1、直接法、直接法 常用的一维直接法主要有消去法和近似法两种：常用的一维直接法主要有消去法和近似法两种：（1）消去法）消去法 该法利用单峰函数具有的消去性质进行该法利用单峰函数具有的消去性质进行反复迭代，逐渐消去不包含极小点的区间，缩小搜索区反复

5、迭代，逐渐消去不包含极小点的区间，缩小搜索区间，直到搜索区间缩小到给定允许精度为止。一种典型间，直到搜索区间缩小到给定允许精度为止。一种典型的消去法为黄金分割法的消去法为黄金分割法(Golden Section Search）。黄金）。黄金分割法的基本思想是在单峰区间内适当插入两点，将区分割法的基本思想是在单峰区间内适当插入两点，将区间分为三段，然后通过比较这两点函数值的大小来确定间分为三段，然后通过比较这两点函数值的大小来确定是删去最左段还是最右段，或同时删去左右两段保留中是删去最左段还是最右段，或同时删去左右两段保留中间段。重复该过程使区间无限缩小。插入点的位置放在间段。重复该过程使区间无

6、限缩小。插入点的位置放在区间的黄金分割点及其对称点上，所以该法称为黄金分区间的黄金分割点及其对称点上，所以该法称为黄金分割法。该法的优点是算法简单，效率较高，稳定性好。割法。该法的优点是算法简单，效率较高，稳定性好。优化模型优化模型 （2）多项式近似法）多项式近似法 该法用于目标函数比较复杂的情该法用于目标函数比较复杂的情况。此时寻找一个与它近似的函数代替目标函数，并用况。此时寻找一个与它近似的函数代替目标函数，并用近似函数的极小点作为原函数极小点的近似。常用的近近似函数的极小点作为原函数极小点的近似。常用的近似函数为二次和三次多项式。似函数为二次和三次多项式。二次内插涉及到形如下式的二次函数

7、数据拟合问题：二次内插涉及到形如下式的二次函数数据拟合问题：其中步长极值为：其中步长极值为：优化模型优化模型 然后只要利用三个梯度或函数方程组就可以确定系数然后只要利用三个梯度或函数方程组就可以确定系数a和和b，从而可以确定，从而可以确定*。得到该值以后，进行搜索区间。得到该值以后，进行搜索区间的收缩。在缩短的新区间中，重新安排三点求出下一次的收缩。在缩短的新区间中，重新安排三点求出下一次的近似极小点的近似极小点*，如此迭代下去，直到满足终止准则为，如此迭代下去，直到满足终止准则为止。其迭代公式为：止。其迭代公式为：其中其中优化模型优化模型2、间接法、间接法 间接法需要计算目标函数的导数，优点

8、是计算速度很间接法需要计算目标函数的导数，优点是计算速度很快。常见的间接法包括牛顿切线法、对分法、割线法和快。常见的间接法包括牛顿切线法、对分法、割线法和三次插值多项式近似法等。用得较多的是三次插值法。三次插值多项式近似法等。用得较多的是三次插值法。三次插值的基本思想与二次插值的一致，是用四个已三次插值的基本思想与二次插值的一致，是用四个已知点构造一个三次多项式知点构造一个三次多项式P3(x)，用它逼近函数，用它逼近函数f(x)，以，以P3(x)的极小点作为的极小点作为f(x)的近似极小点。一般讲，三次插的近似极小点。一般讲，三次插值法比二次插值法的收敛速度要快些，但每次迭代需要值法比二次插值

9、法的收敛速度要快些，但每次迭代需要计算两个导数值。计算两个导数值。优化模型优化模型 三次插值法的迭代公式为三次插值法的迭代公式为 其中其中 如函数的导数容易求得，一般首先考虑使用三次插值如函数的导数容易求得，一般首先考虑使用三次插值法，因为它具有较高效率。对于只需要计算函数值的方法，因为它具有较高效率。对于只需要计算函数值的方法中，二次插值法是一个很好的方法，它的收敛速度较法中，二次插值法是一个很好的方法，它的收敛速度较快，尤其在极小点所在区间较小时尤其如此。黄金分割快，尤其在极小点所在区间较小时尤其如此。黄金分割法则是一种十分稳定的方法，并且计算简单。法则是一种十分稳定的方法，并且计算简单。

10、优化模型优化模型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,.)提供另外参数提供另外参数P1,P2等等,传输给目标函数传输给目标函数fun。如果没有。如果没有设置设置option

11、s选项，则令选项，则令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：优化参数选项。可

12、以用优化参数选项。可以用optimset函数设置或改变这些函数设置或改变这些参数的值。参数的值。options参数有以下几个选项：参数有以下几个选项：Display 显示的水平。显示的水平。选择选择off，不显示输出；选择，不显示输出；选择iter，显示每，显示每一步迭代过程的输出；选择一步迭代过程的输出；选择final，显示最终结果。，显示最终结果。MaxFunEvals 函数评价的最大允许次数。函数评价的最大允许次数。MaxIter 最大允许迭代次数。最大允许迭代次数。TolX x处的终止容限。处的终止容限。优化模型优化模型例：对边长为例：对边长为3m的正方形铁板，在四个角处剪去相等的的正

13、方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？最大？优化模型优化模型二、多变量优化模型二、多变量优化模型1、线性规划、线性规划(Linear Programming)模型模型 （1）线性规划模型的一般形式是：线性规划模型的一般形式是：优化模型优化模型 （2）线性规划模型的压缩形式是：）线性规划模型的压缩形式是：优化模型优化模型 （3）线性规划模型的矩阵形式是：）线性规划模型的矩阵形式是：其中其中优化模型优化模型 （4）线性规划问题的标准形式是：）线性规划问题的标准形式是：或或 矩阵形式为：矩阵形式为：优化模型

14、优化模型 （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)定义设计变量定义

15、设计变量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,l

16、ambda,exitflag=linprog(.)返回返回exitflag值，描述函数计算的退出条件。值，描述函数计算的退出条件。x,lambda,exitflag,output=linprog(.)返回包含优化信息的输出变量返回包含优化信息的输出变量output。x,fval,exitflag,output,lambda=linprog(.)将解将解x处的拉格朗日乘子返回到处的拉格朗日乘子返回到lambda参数中。参数中。优化模型优化模型例子：例子：某厂生产甲乙两种产品，制成一吨产品甲需用资源某厂生产甲乙两种产品，制成一吨产品甲需用资源A 3吨，资源吨，资源B 4m3；制成一吨产品乙需用资源

17、；制成一吨产品乙需用资源A 2吨，资吨，资源源B 6m3，资源，资源C 7个单位。若一吨产品甲和乙的经济价个单位。若一吨产品甲和乙的经济价值分别为值分别为7万元和万元和5万元，三种资源限制量分别为万元，三种资源限制量分别为90吨、吨、200m3和和210个单位，试决定应生产这两种产品各多少吨个单位，试决定应生产这两种产品各多少吨才能使创造的总经济价值最高？才能使创造的总经济价值最高？令生产产品甲的数量为令生产产品甲的数量为x1，生产产品乙的数量为，生产产品乙的数量为x2。由题意可以建立下面的模型：由题意可以建立下面的模型：该模型中要求目标函数最大化，需要按照该模型中要求目标函数最大化，需要按照

18、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=fval=exitflag=1output=iterations:5cgiterations:0algorithm:lipsollam

19、bda=ineqlin:3x1 doubleeqlin:0 x1 doubleupper:2x1 doublelower:2x1 double优化模型优化模型 由由上上可可知知，生生产产甲甲种种产产品品14吨吨、乙乙种种产产品品24吨吨可可使使创创建的总经济价值最高。建的总经济价值最高。最高经济价值为最高经济价值为218万元。万元。exitflag=1表示过程正常收敛于解表示过程正常收敛于解x处。处。练习练习1练习练习2练习练习3优化模型优化模型2、整数规划、整数规划(Integer Programming)模型模型 一般来说，所谓整数规划即整数线性规划，也就是要一般来说，所谓整数规划即整数线

20、性规划，也就是要求全部或部分变量取值为整数这一特殊条件。模型为求全部或部分变量取值为整数这一特殊条件。模型为优化模型优化模型3、非线性规划模型、非线性规划模型 所谓非线性规划也就是在目标函数或约束条件中含有所谓非线性规划也就是在目标函数或约束条件中含有自变量的非线性函数。自变量的非线性函数。求解这类问题的方法一般有两类求解这类问题的方法一般有两类:直接搜索法直接搜索法(Search method)和梯度法和梯度法(Gradient method)。直接搜索法适用于目标函数高度非线性，没有导数或直接搜索法适用于目标函数高度非线性，没有导数或导数很难计算的情况，由于实际工程中很多问题都是非导数很难

21、计算的情况，由于实际工程中很多问题都是非线性的，直接搜索法不失为一种有效的解决办法。常用线性的，直接搜索法不失为一种有效的解决办法。常用的有的有Hooke-Jeeves搜索法、搜索法、Pavell共轭方向法等，其缺共轭方向法等，其缺点是收敛速度慢。点是收敛速度慢。优化模型优化模型 在函数的导数可求的情况下，梯度法是一种更优的方在函数的导数可求的情况下，梯度法是一种更优的方法，该法利用函数的梯度法，该法利用函数的梯度(一阶导数一阶导数)和和Hessian矩阵矩阵(二阶二阶导数导数)构造算法，可以获得更快的收敛速度。函数构造算法，可以获得更快的收敛速度。函数f(x)的的负梯度方向负梯度方向f(x)

22、即反映了函数的最大下降方向。当即反映了函数的最大下降方向。当搜索方向取为负梯度方向时称为最速下降法。常见的梯搜索方向取为负梯度方向时称为最速下降法。常见的梯度法有最速下降法、度法有最速下降法、Newton法、法、Marquart法、共轭梯法、共轭梯度法和拟牛顿法（度法和拟牛顿法（Quasi-Newton method）等。）等。在所有这些方法中用得最多的是拟牛顿法，这些方法在所有这些方法中用得最多的是拟牛顿法，这些方法在每次迭代过程中建立曲率信息，构成下式得二次模型在每次迭代过程中建立曲率信息，构成下式得二次模型问题问题优化模型优化模型 其中，其中，Hessian矩阵矩阵H为一正定对称矩阵，为

23、一正定对称矩阵，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等直接输给目标函数

24、等直接输给目标函数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

25、函数的梯度值返回到函数的梯度值返回到grad参数中。参数中。x,fval,exitflag,output,grad,hessian=fminunc(.)将解将解x处目标函数的处目标函数的Hessian矩阵信息返回到矩阵信息返回到hessian参数中。参数中。优化模型优化模型三、特殊优化算法三、特殊优化算法1、模拟退火算法、模拟退火算法(Simulated Annealing,简称简称SA算法算法)2、遗传算法（、遗传算法（Genetic Algorithm,简称简称GA算法）算法）优化模型优化模型模拟退火算法模拟退火算法 模拟退火算法模拟退火算法(Simulated Annealing,简称简

26、称SA算法算法)是模是模拟加热熔化的金属的退火过程，来寻找全局最优解的有拟加热熔化的金属的退火过程，来寻找全局最优解的有效方法之一。效方法之一。模拟退火的基本思想和步骤如下：模拟退火的基本思想和步骤如下：设设Ss1,s2,sn为所有可能的状态所构成的集合，为所有可能的状态所构成的集合，f：SR为非负代价函数，即优化问题抽象如下：为非负代价函数，即优化问题抽象如下：寻找寻找s*S，使得，使得f(s*)min f(si)任意任意siS 优化模型优化模型（1）给定一较高初始温度）给定一较高初始温度T，随机产生初始状态，随机产生初始状态S（2）按一定方式，对当前状态作随机扰动，产生一个）按一定方式，对

27、当前状态作随机扰动，产生一个新的状态新的状态SSSsign().其中其中为给定的步长，为给定的步长，为为1,1的随机数的随机数 计算计算f(S)f(S)（3）若）若0，则令，则令SS，转第，转第(5)步步（4）若）若0，则以概率，则以概率exp(/T)接受接受S，即，即SS优化模型优化模型 具体操作：产生一个在具体操作：产生一个在0，1上服从均匀分布的随机上服从均匀分布的随机数数x，若，若xexp(/T)，则，则SS 否则否则S保持不变保持不变(5)按一定方式降温，使按一定方式降温，使TTi1，Ti1 Ti，如：如：Ti1Ti，习惯上取，习惯上取，0.9999)(6)检查退火是否结束检查退火是

28、否结束 是是转向第转向第(7)步步 否否转向第转向第(2)步步优化模型优化模型(7)以当前以当前Si作为最优解输出作为最优解输出注：注：1、结束标志：温度是否小于某一阀值、结束标志：温度是否小于某一阀值(循环次数循环次数)f的值变化是否明显的值变化是否明显 2、初始温度的高低：下降是否充分慢对结果有影响、初始温度的高低：下降是否充分慢对结果有影响Sin(x)在在x处处取得极小取得极小优化模型优化模型练习练习1 投资问题投资问题 某单位有一批资金用于四个工程项目的投资，用于各某单位有一批资金用于四个工程项目的投资，用于各工程项目时所得到得净收益（投入资金的百分比）如下工程项目时所得到得净收益（投

29、入资金的百分比）如下表所示表所示，由于某种原因，决定用于项目，由于某种原因，决定用于项目A的投资不大于的投资不大于其它各项投资之和；而用于项目其它各项投资之和；而用于项目B和和C的投资要大于项的投资要大于项目目D的投资。试确定该单位收益最大的投资分配方案。的投资。试确定该单位收益最大的投资分配方案。工工工工 程程程程 项项项项 目目目目A AB BC CD D收益（收益（收益（收益（%）151510108 81212优化模型优化模型练习练习2 2 工件加工任务分配问题工件加工任务分配问题 某车间有两台机床甲和乙，可用于加工三种工件。假定这两台某车间有两台机床甲和乙，可用于加工三种工件。假定这两

30、台机床的可用台时数分别为机床的可用台时数分别为700和和800，三种工件的数量分别为，三种工件的数量分别为300、500和和400，且已知用三种不同机床加工单位数量的不同工件所，且已知用三种不同机床加工单位数量的不同工件所需的台时数和加工费用（如表所示），问怎样分配机床的加工任需的台时数和加工费用（如表所示），问怎样分配机床的加工任务，才能既满足加工工件的要求，又使总加工费用最低？务，才能既满足加工工件的要求，又使总加工费用最低？机床机床机床机床类型类型类型类型 单位工作所需加工台时数单位工作所需加工台时数单位工作所需加工台时数单位工作所需加工台时数 单位工作所需费用单位工作所需费用单位工作所

31、需费用单位工作所需费用可用可用可用可用台时数台时数台时数台时数 工件工件工件工件1 1工件工件工件工件2 2工件工件工件工件3 3工件工件工件工件1 1工件工件工件工件2 2工件工件工件工件3 3甲甲甲甲0.40.41.11.11.01.013139 91010700700乙乙乙乙0.50.51.21.21.31.3111112128 8800800优化模型优化模型练习练习3 3 裁料问题裁料问题 在某建筑工程施工中需要制作在某建筑工程施工中需要制作10000套钢筋，每套套钢筋，每套钢筋由、和三种不同长度的钢筋各一根组成，它们的钢筋由、和三种不同长度的钢筋各一根组成，它们的直径和材质相同。目前在市场上采购到的同类钢筋的直径和材质相同。目前在市场上采购到的同类钢筋的长度每根均为，问应购进多少根长的钢筋才能满足工长度每根均为，问应购进多少根长的钢筋才能满足工程的需要？程的需要？