数学建模中常用的思想、方法和软件

数学建模中常用的思想和方法

在数学建模中常用的方法：类比法、二分法、量纲分析法、差分法、变分法、图论法、层次分析法、数据拟合法、回归分析法、数学规划（线性规划，非线性规划，整数规划，动态规划，目标规划）、机理分析、排队方法、对策方法、决策方法、模糊评判方法、时间序列方法、灰色理论方法、现代优化算法（禁忌搜索算法，模拟退火算法，遗传算法，神经网络）。 用这些方法可以解下列一些模型：优化模型、微分方程模型、统计模型、概率模型、图论模型、决策模型。

拟合与插值方法（给出一批数据点，确定满足特定要求的曲线或者曲面，从而反映对象整体的变化趋势）： matlab可以实现一元函数，包括多项式和非线性函数的拟合以及多元函数的拟合，即回归分析，从而确定函数； 同时也可以用matlab实现分段线性、多项式、样条以及多维插值。

在优化方法中，决策变量、目标函数（尽量简单、光滑）、约束条件、求解方法是四个关键因素。其中包括无约束规则（用fminserch、fminbnd实现）线性规则（用linprog实现）非线性规则、（ 用fmincon实现）多目标规划（有目标加权、效用函数）动态规划（倒向和正向）整数规划。

回归分析：对具有相关关系的现象，根据其关系形态，选择一个合适的数学模型，用来近似地表示变量间的平均变化关系的一种统计方法 （一元线性回归、多元线性回归、非线性回归），回归分析在一组数据的基础上研究这样几个问题：建立因变量与自变量之间的回归模型（经验公式）；对回归模型的可信度进行检验；判断每个自变量对因变量的影响是否显著；判断回归模型是否适合这组数据；利用回归模型对进行预报或控制。相对应的有 线性回归、多元二项式回归、非线性回归。

逐步回归分析：从一个自变量开始，视自变量作用的显著程度，从大到地依次逐个引入回归方程：当引入的自变量由于后面变量的引入而变得不显著时，要将其剔除掉；引入一个自变量或从回归方程中剔除一个自变量，为逐步回归的一步；对于每一步都要进行值检验，以确保每次引入新的显著性变量前回归方程中只包含对作用显著的变量；这个过程反复进行，直至既无不显著的变量从回归方程中剔除，又无显著变量可引入回归方程时为止。（主要用SAS来实现，也可以用matlab软件来实现）。

聚类分析：所研究的样本或者变量之间存在程度不同的相似性，要求设法找出一些能够度量它们之间相似程度的统计量作为分类的依据，再利用这些量将样本或者变量进行分类。 系统聚类分析—将n个样本或者n个指标看成n类，一类包括一个样本或者指标，然后将性质最接近的两类合并成为一个新类，依此类推。最终可以按照需要来决定分多少类，每类有多少样本（指标）。

系统聚类方法步骤：

1. 计算n个样本两两之间的距离 2. 构成n个类，每类只包含一个样品 3. 合并距离最近的两类为一个新类

4. 计算新类与当前各类的距离（新类与当前类的距离等于当前类与组合类中包含的类的距离最小值），若类的个数等于1，转5，否则转3 5. 画聚类图

6. 决定类的个数和类。

判别分析：在已知研究对象分成若干类型，并已取得各种类型的一批已知样品的观测数据，在此基础上根据某些准则建立判别式，然后对未知类型的样品进行判别分类。

距离判别法—首先根据已知分类的数据，分别计算各类的重心，计算新个体到每类的距离，确定最短的距离（欧氏距离、马氏距离）

Fisher判别法—利用已知类别个体的指标构造判别式（同类差别较小、不同类差别较大），按照判别式的值判断新个体的类别

Bayes判别法—计算新给样品属于各总体的条件概率，比较概率的大小，然后将新样品判归为来自概率最大的总体

模糊数学：研究和处理模糊性现象的数学 （概念与其对立面之间没有一条明确的分界线）与模糊数学相关的问题：模糊分类问题—已知若干个相互之间不分明的模糊概念，需要判断某个确定事物用哪一个模糊概念来反映更合理准确；模糊相似选择 —按某种性质对一组事物或对象排序是一类常见的问题，但是用来比较的性质具有边界不分明的模糊性；模糊聚类分析—根据研究对象本身的属性构造模糊矩阵，在此基础上根据一定的隶属度来确定其分类关系 ；模糊层次分析法—两两比较指标的确定；模糊综合评判—综合评判就是对受到多个因素制约的事物或对象作出一个总的评价，如产品质量评定、科技成果鉴定、某种作物种植适应性的评价等，都属于综合评判问题。由于从多方面对事物进行评价难免带有模糊性和主观性，采用模糊数学的方法进行综合评判将使结果尽量客观从而取得更好的实际效果 。 时间序列是按时间顺序排列的、随时间变化且相互关联的数据序列—通过对预测目标自身时间序列的处理，来研究其变化趋势（长期趋势变动、季节变动、循环变动、不规则变动） 自回归模型：一般自回归模型AR(n)—系统在时刻t的响应X(t)仅与其以前时刻的响应

X(t-1),…， X(t-n)有关，而与其以前时刻进入系统的扰动无关 ；移动平均模型MA(m)—系统在时刻t的响应X(t) ，与其以前任何时刻的响应无关，而与其以前时刻进入系统的扰动a(t-1),…,a(t-m)存在着一定的相关关系 ；自回归移动平均模型 ARMA(n,m)—系统在时刻t的响应X(t)，不仅与其前n个时刻的自身值有关，而且还与其前m个时刻进入系统的扰动存在一定的依存关系 。 时间序列建模的基本步骤

1. 数据的预处理：数据的剔取及提取趋势项

2. 取n=1，拟合ARMA(2n,2n-1)（即ARMA(2,1)）模型 3. n=n+1，拟合ARMA(2n,2n-1)模型

4. 用F准则检验模型的适用性。若检验显著，则转入第2步。若检验不显著，转入第

5步。 5. 检查远端时刻的系数值的值是否很小，其置信区间是否包含零。若不是，则适用的

模型就是ARMA(2n,2n-1) 。若很小，且其置信区间包含零，则拟合

ARMA(2n-1,2n-2) 。

6. 利用F准则检验模型ARMA(2n,2n-1)和ARMA(2n-1,2n-2) ，若F值不显著，转入第

7步；若F值显著，转入第8步。

7. 舍弃小的MA参数，拟合m<2n-2的模型ARMA(2n-1,m) ，并用F准则进行检验。

重复这一过程，直到得出具有最小参数的适用模型为止

8. 舍弃小的MA参数，拟合m<2n-1的模型ARMA(2n,m) ，并用F准则进行检验。重

复这一过程，直到得出具有最小参数的适用模型为止。 图论方法：

最短路问题：两个指定顶点之间的最短路径—给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线 （Dijkstra算法 ）每对顶点之间的最短路径 （Dijkstra算法、Floyd算法 ）。

最小生成树问题：连线问题—欲修筑连接多个城市的铁路设计一个线路图，使总造价最低（prim算法、Kruskal算法 ）。

图的匹配问题：人员分派问题：n个工作人员去做件n份工作，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？(匈牙利算法)。 遍历性问题：中国邮递员问题—邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线 最大流问题。 运输问题：

最小费用最大流问题：在运输问题中，人们总是希望在完成运输任务的同时，寻求一个使总的运输费用最小的运输方案 在数学建模中常用的算法： 1：蒙特卡罗算法；

2：数据拟合、参数估计、插值等数据处理算法（常用matlab实现）；

3：线性规划、整数规划、多元规划、二次规划(用lingo、lingdo、matlab即可实现)； 4：图论算法（包括最短路、网络流、二分图）； 5：动态规划、回溯搜索、分治算法、分支界定；

6：最优化理论的三大经典算法（模拟退火算法、神经网络算法、遗传算法）； 7：网格算法和穷举法； 8：连续数据离散化； 9：数值分析算法；

10：图象处理算法（常用matlab来实现）。

数模十大常用算法及说明

(2010-06-22 18:54:54) 转载▼

标签： 分类： 数模

杂谈

1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用 MATLAB 作为工具。 3 . 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用 Lindo 、 Lingo 软件求解。

4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。

5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。

6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。

7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好

使用一些高级语言作为编程工具。

8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。

9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。

10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用 MATLAB 进行处理。

以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 2.1 蒙特卡罗算法 

大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。

举个例子就是 97 年的 A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和 108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年 y 的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。 2.2 数据拟合、参数估计、插值等算法

数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是 98 年美国赛 A 题，生物组织切片的三维插值处理， 94 年 A 题逢山开路，山体海拔高度的插值计算，还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法，观察数据的走向进行处理。此类问题在 MATLAB 中有很多现成的函数可以调用，熟悉 MATLAB ，这些方法都能游刃有余的用好。 2.3 规划类问题算法

竞赛中很多问题都和数学规划有关，可以说不少的模型都可以归结为一组不等式作为约束条件、几个函数表达式作为目标函数的问题，遇到这类问题，求解就是关键了，比如 98 年 B 题，用很多不等式完全可以把问题刻画清楚，因此列举出规划后用 Lindo 、 Lingo 等软件来进行解决比较方便，所以还需要熟悉这两个软件。

2.4 图论问题

98 年 B 题、 00 年 B 题、 95 年锁具装箱等问题体现了图论问题的重要性，这类问题算法有很多，包括： Dijkstra 、 Floyd 、 Prim 、 Bellman-Ford ，最大流，二分匹配等问题。每一个算法都应该实现一遍，否则到比赛时再写就晚了。

本文来源：https://www.bwwdw.com/article/po32.html