数学建模常用方法整理-常培-2013-01-16

1、1数学建模常用方法整理数学建模常用方法整理数学建模工作室数学建模工作室常培常培2013-01-162013-01-162 数学建模就是用数学语言描述实际现象的过程。这里的实际现象既包涵具体的自然现象比如自由落体现象，也包涵抽象的现象比如顾客对某种商品所取的价值倾向。什么是数学建模？什么是数学建模？3常见的数学建模方法常见的数学建模方法 最优化理论之多目标规划最优化理论之多目标规划 动态规划动态规划 图论图论 层次分析层次分析 灰色关联度分析灰色关联度分析 微分方程微分方程 41.最优化理论l最短路径优化l最省时间优化l管理科学优化l工程设计优化l市场调度优化l城市建设优化生活中的优化无处不在5

2、1.最优化理论建模真题之优化问题l 1994年全国赛A题：逢山开路l 1996年全国赛A题：最优捕鱼策略l 2001年全国赛B题：公交车优化调度l 2010年东三省A题：企业的营销管理问题l 2010年东三省B题：周游全中国据统计，19922005年全国赛28个赛题中有关优化问题有19个，最优化方法是用的最多的方法之一。61.最优化理论最优化问题的定义最优化问题的定义 最优化问题就是在给定条件下寻找最佳方案的问题 即在资源给定时寻找最好的目标，或在目标确定时使用最少的资源71.最优化理论最优化问题的分类最优化问题的分类动态规划非线性规划目标规划规划整数规划线性规划数学规划1081.最优化理论解

3、最优化问题的方法解最优化问题的方法最优化问题的求解方法一般可以分成解析法、直接法、数值计算法和其他方法 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法 91.最优化理论最优化模型基本要素最优化模型基本要素决策变量、目标函数和约束条件（1）决策变量是问题中有待确定的未知因素。（2）目标函数是指对问题所追求的目标的数学描述。（3）约束条件是指实现问题目标的限制因素。101.1.最优化理论之多目标规划最优化理论之多目标规划多目标规划多目标规划 111.1.最优化理论之多目标规划最优化理论之多目标规划基本方法基本方法一、将多目标转化为单目标一、将多目标转化为单目标 优选法优选法 线形

4、加权法线形加权法 平方和加权法平方和加权法 乘除法乘除法 分层序列法分层序列法二、直接用数学方法求非劣解二、直接用数学方法求非劣解121.1.最优化理论之多目标规划最优化理论之多目标规划1.优选法优选法（使主要目标优化兼顾其它目标）（使主要目标优化兼顾其它目标） 如果其中一个目标比较关键，如果希望它取极（小）值，将其他目标分别给一希望值后，加到约束里（即其他目标满足一定希望值）而把问题转化为单目标规划问题。 xf1minRx RxpifxffRii , 2,1 iiifxff pi, 2 适合解决目标函数主次明显的问题131.1.最优化理论之多目标规划最优化理论之多目标规划 当 个目标 都要求

5、最小时，可以给每个目标相应的权系数 且 , 构成新的目标函数 p xfxfxfp,210i11pii xfxFipii1然后使这个新的目标函数取极小值。这里的权系数大小根据每个目标函数的相对重要性来确定。2.线性加权法线性加权法141.1.最优化理论之多目标规划最优化理论之多目标规划3.平方和加权法平方和加权法 首先确定各个目标 的希望目标值 ， 要求所有的目标值和相应的希望目标值尽可能接近。此时采用下列评价函数：然后求 。 xfi*if 21*piiifxfxF xFmin151.1.最优化理论之多目标规划最优化理论之多目标规划 如果对其中不同的目标重视程度不同，则可采用加权的平方和作为评价

6、函数，即求： 2*1miniipiiRxfxfxF式中， 为加权系数，可按各目标被重视的程度给出。i161.1.最优化理论之多目标规划最优化理论之多目标规划4.乘除法乘除法 设有 个目标 。式中，有 个要求极小值，例如设 ，而余下 的要求其极大值，并假定 。这时，采用以下评价函数：p xfxfxfp,21 xfxfxfk,21 xfxfxfpkk,21 0,21xfxfxfpkkk xfxfxfxfxfxfxFpkkk2121作为单目标问题求极小值。17 5.分层序列法分层序列法 将目标按重要性的次序分成最重要目标、次重要目标，如 。然后按顺序将一个多目标规划问题转化为一系列单目标优化问题来求

7、解。 xfxfxfp,211.1.最优化理论之多目标规划最优化理论之多目标规划182.2.最优化理论之动态规划最优化理论之动态规划 动态规划是解决多阶段决策过程最优化问题的一种方法。由美国数学家贝尔曼（Ballman）等人在20世纪50年代提出。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理 、 工程技术等方面的许多实际问题。192.2.最优化理论之动态规划最优化理论之动态规划动态规划模型的分类：（时间角度）离散型和连续型；（信息确定与否）确定型和随机型；（目标函数个数）单目标型和多目标型。基本原理基本原理：202.2.最优化理论之动态规划最优化理论之

8、动态规划 动态规划可用于最优路径问题、资源分配问题、生产计划和库存问题、投资问题、装载问题、排序问题及生产过程的最优控制等。212.2.最优化理论之动态规划最优化理论之动态规划按时间或空间特征分解成若干个相互联系的阶段，常用K表示以便按次序去求每阶段的解描述各阶段状态的变量称为状态变量，常用sk表示第k阶段的状态变量222.2.最优化理论之动态规划最优化理论之动态规划依据各段的状态做出不同的决定从而确定下一阶段的状态用dk(Sk)表示动态规划中本阶段的状态往往是上一阶段的决策结果用于衡量所选定策略优劣的数量指标称为指标函数。232.2.最优化理论之动态规划最优化理论之动态规划（路径类）动态规划

9、的解题思路：（路径类）动态规划的解题思路：从过程的最后一段开始，用从过程的最后一段开始，用逆序递推方法逆序递推方法求求解，逐步求出各段各点到终点解，逐步求出各段各点到终点的的最短路线，最短路线，最后求出最后求出总的总的最短路线。最短路线。242.2.最优化理论之动态规划最优化理论之动态规划如图是一个五座城市的如图是一个五座城市的及其相连道路的交通图，线及其相连道路的交通图，线上的数字是对应的路长。问：上的数字是对应的路长。问：应如何选择行驶路线，才能应如何选择行驶路线，才能使从使从A市经过市经过B、C、D各城各城市市（无顺序要求）（无顺序要求）到到E城市城市的行驶路程最短？的行驶路程最短？25

10、2.2.最优化理论之动态规划最优化理论之动态规划于是从于是从A城市到达城市到达E城市的阶段数有下城市的阶段数有下列四种情形：列四种情形：1.从A城市直达E城市，一个阶段。2.从A城市通过其他B、C、D三城市之一到E城市，二个阶段。3.从A城市通过其他B、C、D三城市之二到E城市，三个阶段。4.从A城市通过其他B、C、D三城市各一次到E城市，四个阶段。262.2.最优化理论之动态规划最优化理论之动态规划可把一个可把一个N维优化问题化成维优化问题化成N个一维优个一维优化问题求解。化问题求解。DP方程中附加某些约束条件，可使求方程中附加某些约束条件，可使求解更加容易。解更加容易。求得最优解以后，可得

11、所有子问题的最求得最优解以后，可得所有子问题的最优解。优解。但是但是,状态变量维数不能太高，一般要求小状态变量维数不能太高，一般要求小于于6。273.3.图论图论 图并不是几何学中的图并不是几何学中的图形图形, ,而是客观世界中某而是客观世界中某些事物间联系的一个数些事物间联系的一个数学抽象学抽象, ,用用顶点代表事物顶点代表事物, ,用边表示各事物间的关用边表示各事物间的关系系, ,如果所讨论的事物之如果所讨论的事物之间有关系间有关系, ,就把相应的顶就把相应的顶点连成一条边点连成一条边. .这种由顶这种由顶点及边所组成的图点及边所组成的图, ,就是就是图论中研究的图图论中研究的图. .用图

12、来解决问题的理论即为图论28图论最基本的概念图论最基本的概念 图：由点及连接线所构成的图形， 用G=(V,E) 表示。 点(vertex)：代表事物。 线(edge)：两个事物间具有的关系。,)(21nvvvGV,)(21neeeGE),(jikvve 293.3.图论图论度的概念度（次）：节点v相连的边的数目， 表示为d（v）。 奇数度节点：节点的度的数目为奇数的点； 偶数度节点：节点的度的数目为偶数的点。303.3.图论图论路 通路：点 到点 中任意的两点都连通. 回路：起点和终点是同一个点的路,即 ivjv,1211jljikikivevvevevTjivv 31常见的图论算法常见的图论

13、算法 TSP （旅行商问题-寻找回路的最短路径）； Dijkstra （ 迪杰斯特拉算法-求单源最短路径 ）； Kruskal； 匈牙利算法。323.3.图论图论欧拉通路：走遍图G每一条边一次仅且一次的通路。欧拉回路：走遍图G每一条边一次仅且一次的回路。汉密尔顿通路：走遍图G每个顶点一次且仅一次的通路。汉密尔顿回路：走遍图G每个顶点一次仅且一次的回路。333.3.图论图论定理1. 图G 具有欧拉通路的判别条件：当且仅当G 是连通的且仅有零个或两个奇数度顶点。若无奇数度顶点，则通路为回路；若有两个奇数度顶点，则它们是每条欧拉通路的端点。343.3.图论图论定理2. 图G 具有汉密尔顿通路的判别条

14、件：充分条件：图充分条件：图G中任意两点的度数之和大于等中任意两点的度数之和大于等于顶点数于顶点数注意：目前没有充分必要要条件来判断任注意：目前没有充分必要要条件来判断任意一图是否为意一图是否为Hamilton图图35哥尼斯堡七桥哥尼斯堡七桥问题问题 能否从一点出发，走遍能否从一点出发，走遍7 7座桥，且通过每座座桥，且通过每座桥恰好一次，最后仍回到起始点桥恰好一次，最后仍回到起始点？363.3.图论图论各个点都与奇数条边各个点都与奇数条边相连所以不能实现相连所以不能实现七桥路径图373.3.图论图论欲建设一个连接欲建设一个连接7个城市的光纤通信网络。个城市的光纤通信网络。各城市间线路的造价如

15、图所示，求一个使总造各城市间线路的造价如图所示，求一个使总造价最少的线路建设方案。价最少的线路建设方案。 各线路的造价图383.3.图论图论 避圈法步骤：避圈法步骤： 1. 1. 在所有各边中找到边权最小的一条，将其作为第一在所有各边中找到边权最小的一条，将其作为第一边；在剩余的边中，仍然找到边权最小的作为第二条边；边；在剩余的边中，仍然找到边权最小的作为第二条边； 2. 2. 在剩余的边中，找到边权最小的边，查看其是否与在剩余的边中，找到边权最小的边，查看其是否与前面的边形成圈，如果没有，则在最小部分树中添加该边，前面的边形成圈，如果没有，则在最小部分树中添加该边，如果形成了圈，则不再考虑该

16、边；如果形成了圈，则不再考虑该边； 3. 3. 重复进行第二步，直到找到第重复进行第二步，直到找到第 n n-1 -1 条边为止。条边为止。39结果为结果为143.3.图论图论休息一下吧休息一下吧404.4.层次分析层次分析一、基本概述一、基本概述 层次分析是一种多层次权重解析方法。层次分析是一种多层次权重解析方法。AHPAHP是分析是分析多目标、多准则的复杂大系统的有力工具。多目标、多准则的复杂大系统的有力工具。 它最适宜于解决那些难以完全用定量方法进行分它最适宜于解决那些难以完全用定量方法进行分析的评价决策问题。析的评价决策问题。 它具有思路清晰、方法简单、实用面广、系统性它具有思路清晰、

17、方法简单、实用面广、系统性强等特点，便于普及推广。强等特点，便于普及推广。 41二、模型建立的基本步骤二、模型建立的基本步骤第一步：建立层次结构模型（第一步：建立层次结构模型（解决问题的关键解决问题的关键）第二步：构造判断矩阵第二步：构造判断矩阵第三步：层次单排序及其一致性检验第三步：层次单排序及其一致性检验第四步：层次总排序第四步：层次总排序第五步：层次总排序的一致性检验第五步：层次总排序的一致性检验4.4.层次分析层次分析42层次分析的结构层次分析的结构目标层目标层决策层决策层方案层方案层43ijaicicicicicjcjcjcjcjcicjcicjc比较尺度比较尺度 ：不同性质的因素

18、和 对上一层因素的影响之比jcicija44 假期旅游，假如有假期旅游，假如有3个旅游胜地供你选择，从景个旅游胜地供你选择，从景色、费用、居住、饮食和旅途五个方面出发，选出色、费用、居住、饮食和旅途五个方面出发，选出你认为的最佳旅游胜地。你认为的最佳旅游胜地。 选择旅游地选择旅游地居住居住景色景色旅途旅途费用费用饮食饮食P3P2 P1决策层决策层目标层目标层方案层方案层45一致性的概念一致性的概念2: 1:21CC1 : 4:32CC?:31CC2:31CC2:31CC矩阵为一致性的矩阵为一致性的矩阵为非一致性的矩阵为非一致性的46最大特征根的求解最大特征根的求解141614121621Aw0

19、91. 0077. 01 . 0364. 0308. 03 . 0545. 0645. 06 . 0268. 0972. 0760. 1089. 0324. 0587. 0268. 0974. 0769. 1Aw009. 3089. 0268. 0324. 0974. 0587. 0769. 131按行按行求和求和列的归列的归一化一化归一化归一化特征向量特征向量最大特征根：最大特征根：47层次单排序及其一致性检验层次单排序及其一致性检验最大特征根最大特征根maxmax的求解：的求解：1maxnnCI一致性指标：一致性指标：随机性比率：随机性比率：1-9阶矩阵的平均随机一致性指标阶矩阵的平均随机

20、一致性指标10. 0RICICR运用运用Matlab求解求解 V，D=eig(A)若若一致性检验通过一致性检验通过，则特征向量，则特征向量可作为权向量可作为权向量 48CA11/2433217551/41/711/21/31/31/52111/31/5311C C1 1C C3 3C C2 2C C1 1C C5 5C C4 4C C2 2C C3 3C C4 4C C5 5第二步：构造判断矩阵第二步：构造判断矩阵491215121215211PC1383113813112PC131313113113PC114111314314PC144411141115PCP3P1P2P3P2P1Ci-P矩

21、阵中的任意元素矩阵中的任意元素amn表示方案表示方案 Pm和方案和方案Pn对于准对于准则则Ci的重要程度的重要程度50 3kkkCIk由第3层的成对比较阵 计算出权向量 ，最大特征根 和一致性指标 结果如下：kC 3kkkCI58. 0RIkCIn=3时随机一致性指标 ，所以上面的 均可以通过一致性检验51组合组合方案方案 在目标层中的组合权重应为它们相应在目标层中的组合权重应为它们相应项的两两乘积之和，即项的两两乘积之和，即1P300. 0110. 0166. 0099. 0633. 0055. 0429. 0475. 0082. 0263. 0595. 02P3PT456. 0 ,246.

22、 0 ,300. 0)3(同样可计算出 、 在目标层中的权重为0.246和0.456结果表明：结果表明：方案方案P3在旅游地选择中占的权重近于在旅游地选择中占的权重近于 1/2，远大于，远大于P1、P2，P3应作为第一选择地点。应作为第一选择地点。525.5.灰色关联度之因素分析灰色关联度之因素分析u灰色系统灰色系统 u关联度关联度 是指部分信息已知而部分信息未知的系统，灰色系统理论所要考察和研究的是对信息不完备的系统，通过已知信息来研究和预测未知领域从而达到了解整个系统的目的。关联度是事物之间、因素之间关联性大小的量度。它定量地描述了事物或因素之间相互变化的情况，即变化的大小、方向与速度等的

23、相对性。如果事物或因素变化的态势基本一致，则可以认为它们之间的关联度较大，反之，关联度较小。535.5.灰色关联度之因素分析灰色关联度之因素分析 在预测分析中，最基本的预测模型为线性回归方程，针对一些规律性较强的数据，该模型能作出精确的预测，但在实际中，我们得到的常是一些离散的，规律性不强的数据，为解决此类问题，线性的方法就不适用了，此时，就需要采用灰色预测的方法。545.5.灰色关联度之因素分析灰色关联度之因素分析分析研究某公路施工企业年收入的主要影响因素分析研究某公路施工企业年收入的主要影响因素555.5.灰色关联度之因素分析灰色关联度之因素分析 确定参考数列 处理原始数据 计算关联系数

24、关联度的计算与比较565.5.灰色关联度之因素分析灰色关联度之因素分析由于各因素各有不同的计量单位，因而原始数据存在量纲和数量级上的差异，不同的量纲和数量级不便于比较，或者比较时难以得出正确结论。因此，在计算关联度之前，通常要对原始数据进行无量纲化处理。原始数据的处理原始数据的处理57 设 为因素 的行为序列)(,),2(),1 (nxxxXniiiiXu初值化初值化),(),.,2(),1 () 1 (nxxxxXXiiiiiimixi,.,2 , 1 , 0, 0) 1 (初值化方法适用于较稳定的社会经济现象的无量纲化，这样的数初值化方法适用于较稳定的社会经济现象的无量纲化，这样的数列多数

25、呈稳定增长趋势，通过初值化处理，可列多数呈稳定增长趋势，通过初值化处理，可使增长趋势更加明使增长趋势更加明显显。u均值化均值化均值化方法比较均值化方法比较适合于没有明显升降趋势现象适合于没有明显升降趋势现象的数据处理。的数据处理。585.5.灰色关联度之因素分析灰色关联度之因素分析u区间化区间化可以将各可以将各变量取值范围变量取值范围限制在限制在01之间之间59若系统 因素 与系统主行为 呈负相关关系，我们可以将其逆化或倒数化后进行计算。iX0Xu倒数化u逆化60对例对例题题中数据做均值化处理中数据做均值化处理61关联系数的计算关联系数的计算设经过数据处理后的参考数列为：比较数列为：62从几何

26、角度看，关联程度实质上是参考数列与比较数列曲线形状的相似程度。因此，可用曲线间的差值大小作为关联度的衡量标准。则：两极最大差与最小差：63关联系数：关联系数：式中 分辩系数（常取0.2或0.5），用来削弱(max)过大而使关联系数失真的影响。人为引入这个系数是为了提高关联系数之间的差异显著性。) 1 , 0(64例例题题中各比较数列同参考数列在同一时期的绝对中各比较数列同参考数列在同一时期的绝对差差65第三步第三步 找出两极最大差与最小差找出两极最大差与最小差第四步第四步 计算关联系数，取分辨系数计算关联系数，取分辨系数 ，则计算公式为：，则计算公式为：66关联度的计算与比较关联度的计算与比较

27、有必要对关联信息作集中处理。而求平均值便是一种信息集中的方式。即用比较数列与参考数列各个时期的关联系数之平均值来定量反映这两个数列的关联程度：67计算关联度计算关联度利用表4，分别求各个数列每个时期的关联系数的平均值即得关联度：68 由关联度数值可看出，r03r01r02。这表明，三种工资对工资总额的关联程度的排列顺序为：承包工资、计时工资、档案工资。即该公路施工企业的工资发展方向是以承包工资为主导，计时工资和档案工资对工资总额的影响属于同一水平。相关排序相关排序696.6.微分方程微分方程 在研究实际问题时，常常会联系到某些变量的变化率或导数，这样所得到变量之间的关系式就是微分方模型。微分方

28、程模型反映的是变量之间的间接关系，因此，要得到直接关系，就得求微分方程。求解微分方程有三种方法： 1）求精确解；2）求数值解（近似解）；3）定性理论方法。70r模型模型1：马尔萨斯（：马尔萨斯（Malthus）模型）模型t)(tNtttttrNtNttN)()()(设时刻设时刻 的人口总数为的人口总数为 ，时间从，时间从 到到 人口增长量为：人口增长量为： 马尔萨斯通过对大量的人口数据进行分析，做马尔萨斯通过对大量的人口数据进行分析，做出了如下假设：单位时间内人口增长量与人口总出了如下假设：单位时间内人口增长量与人口总数成正比，即人口净增长率数成正比，即人口净增长率 基本上是一常基本上是一常数数 ， , 为出生率，为出生率， 为死亡率。为死亡率。rdbrbd71)()()(trNttNttN等式两边同时除以等式两边同时除以 ，有，有t再运用极限的思想，令再运用极限的思想，令 有有 0t)()(trNdttdN由初始条件由初始条件 ，即为初始时刻的，即为初始时刻的人口数，故解方程得人口数，故解方程得)(00tNN )(00)(ttreNtN7219502000205021002150220000.511.522.533.5x 1011t/年N/人马 尔 萨 斯