数学建模中十大算法实现步骤与代码

杨利霞

数学建模中十大算法实现步骤与代码
) J7 E0 }0 I: x/ F# `1 s步骤

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

这些方法可以解一些模型：优化模型、微分方程模型、统计模型、概率模型、图论模型、决策模型。

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

在优化方法中，决策变量、目标函数（尽量简单、光滑）、约束条件、求解方法是四个关键因素。其中包括无约束规则（用fminserch、fminbnd实现）线性规则（用linprog实现）非线性规则、（ 用fmincon实现）多目标规划（有目标加权、效用函数）动态规划、整数规划。
4 C) v* t% J; E2 M0 o+ s
8 {# N  a- U& V; b) H: `/ v回归分析：对具有相关关系的现象，根据其关系形态，选择一个合适的数学模型，用来近似地表示变量间的平均变化关系的一种统计方法 （一元线性回归、多元线性回归、非线性回归），回归分析在一组数据的基础上研究这样几个问题：建立因变量与自变量之间的回归模型（经验公式）；对回归模型的可信度进行检验；判断每个自变量对因变量的影响是否显著；判断回归模型是否适合这组数据；利用回归模型对进行预报或控制。相对应的有 线性回归、多元二项式回归、非线性回归。

0 q/ D: |- t; Q+ y6 H逐步回归分析：从一个自变量开始，视自变量作用的显著程度，从大到地依次逐个引入回归方程：当引入的自变量由于后面变量的引入而变得不显著时，要将其剔除掉；引入一个自变量或从回归方程中剔除一个自变量，为逐步回归的一步；对于每一步都要进行值检验，以确保每次引入新的显著性变量前回归方程中只包含对作用显著的变量；这个过程反复进行，直至既无不显著的变量从回归方程中剔除，又无显著变量可引入回归方程时为止。（主要用SAS来实现，也可以用matlab软件来实现）。
! W+ L/ p% w1 r' c& C; I5 a* F
) d3 t+ v2 t% G聚类分析：所研究的样本或者变量之间存在程度不同的相似性，要求设法找出一些能够度量它们之间相似程度的统计量作为分类的依据，再利用这些量将样本或者变量进行分类。
% F) W' K- w( k9 b  Q% _
系统聚类分析—将n个样本或者n个指标看成n类，一类包括一个样本或者指标，然后将性质最接近的两类合并成为一个新类，依此类推。最终可以按照需要来决定分多少类，每类有多少样本（指标）。

! i4 W: p$ y" w& K* D. B系统聚类方法步骤：
  W% J% d1 F% g+ k7 z( V$ Q0 X1. 计算n个样本两两之间的距离
2. 构成n个类，每类只包含一个样品
3. 合并距离最近的两类为一个新类
9 S1 n: ~3 M; I; R4. 计算新类与当前各类的距离（新类与当前类的距离等于当前类与组合类中包含的类的距离最小值），若类的个数等于1，转5，否则转3
) f. _6 x! Z0 P2 M5. 画聚类图
6. 决定类的个数和类。
7.
" }; X3 D( i+ C! j9 ~
判别分析：
/ V: g& }& x% C  @
在已知研究对象分成若干类型，并已取得各种类型的一批已知样品的观测数据，在此基础上根据某些准则建立判别式，然后对未知类型的样品进行判别分类。
距离判别法—首先根据已知分类的数据，分别计算各类的重心，计算新个体到每类的距离，确定最短的距离（欧氏距离、马氏距离）。
/ N+ }' s$ w+ m$ T
Fisher判别法
3 Y/ {4 F  K  ?: V
9 F* e& \9 W# x( X6 N; z9 C—利用已知类别个体的指标构造判别式（同类差别较小、不同类差别较大），按照判别式的值判断新个体的类别。
; p" `! ?- w* U. X
Bayes判别法

1 _4 u) W# h! W9 t: V—计算新给样品属于各总体的条件概率，比较概率的大小，然后将新样品判归为来自概率最大的总体。

模糊数学：

: n% |% v* s% A5 B* K: H研究和处理模糊性现象的数学 （概念与其对立面之间没有一条明确的分界线）与模糊数学相关的问题：模糊分类问题—已知若干个相互之间不分明的模糊概念，需要判断某个确定事物用哪一个模糊概念来反映更合理准确；

模糊相似选择 —按某种性质对一组事物或对象排序是一类常见的问题，但是用来比较的性质具有边界不分明的模糊性；
: y5 k0 j8 g% f  X6 Z
模糊聚类分析—根据研究对象本身的属性构造模糊矩阵，在此基础上根据一定的隶属度来确定其分类关系 ；模糊层次分析法—两两比较指标的确定；模糊综合评判—综合评判就是对受到多个因素制约的事物或对象作出一个总的评价，如产品质量评定、科技成果鉴定、某种作物种植适应性的评价等，都属于综合评判问题。由于从多方面对事物进行评价难免带有模糊性和主观性，采用模糊数学的方法进行综合评判将使结果尽量客观从而取得更好的实际效果 。
: l, u) S- u* p7 w9 H7 P
; o7 \' ?3 d4 h时间序列–我的拿手好菜~-~

2 z) V0 K2 Q( l* _+ E$ k4 Y. H是按时间顺序排列的、随时间变化且相互关联的数据序列—通过对预测目标自身时间序列的处理，来研究其变化趋势（长期趋势变动、季节变动、循环变动、不规则变动）

# z3 x; w2 F0 H" P# J0 j自回归模型：
* O' z8 o$ p+ e
1 S. ]* d+ P( B. n7 H一般自回归模型AR(n)—系统在时刻t的响应X(t)仅与其以前时刻的响应X(t-1),…， X(t-n)有关，而与其以前时刻进入系统的扰动无关 ；
9 z; I2 H$ \& D+ O9 Q( d5 Q
) W! @# g0 x7 r# Y) z移动平均模型MA(m)—系统在时刻t的响应X(t) ，与其以前任何时刻的响应无关，而与其以前时刻进入系统的扰动a(t-1),…,a(t-m)存在着一定的相关关系 ；
3 ~7 B5 J: v% \9 t( u3 i, ~* V
4 F2 `; W; S3 d5 t( k0 L- [自回归移动平均模型 ARMA(n,m)—系统在时刻t的响应X(t)，不仅与其前n个时刻的自身值有关，而且还与其前m个时刻进入系统的扰动存在一定的依存关系 。
. n( Q/ [& Q- h$ S2 u7 |/ g+ Y
9 ^! o9 j9 D# Q$ s时间序列建模的基本步骤
1. 数据的预处理：数据的剔取及提取趋势项
3 k2 b- {/ j$ \/ S% @2. 取n=1，拟合ARMA(2n,2n-1)（即ARMA(2,1)）模型
5 G- F( l, K, G3. n=n+1，拟合ARMA(2n,2n-1)模型
" L- w* g) B9 s4. 用F准则检验模型的适用性。若检验显著，则转入第2步。若检验不显著，转入第5步。
, v" ~7 b9 t0 c' W  r: p% ]4 l3 C5. 检查远端时刻的系数值的值是否很小，其置信区间是否包含零。若不是，则适用的模型就是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准则进行检验。重复这一过程，直到得出具有最小参数的适用模型为止。
$ S7 g$ o4 s: _" e
图论方法：
. `2 A( X* _4 Q6 a/ o4 r/ m
- q- J9 L0 f6 i. C5 O6 i  Q4 ?9 X最短路问题：
( }7 ?0 b. r. W6 F) O
2 l- D. u9 p$ m两个指定顶点之间的最短路径—给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线 （Dijkstra算法 ）每对顶点之间的最短路径 （Dijkstra算法、Floyd算法 ）。

最小生成树问题：

连线问题

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

2 b$ }  \) q. d8 S3 l  k5 }2 I图的匹配问题：
7 R4 k7 ~$ l. d
2 z; l0 k, ^* J. Q2 @' @( E8 B人员分派问题：n个工作人员去做件n份工作，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？(匈牙利算法)。

9 v2 V( `6 B/ O# _2 j遍历性问题：

; b) V  j: c' _' {中国邮递员问题—邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线
最大流问题。
7 _5 I$ Z3 W  Z' `
0 w6 b. S. d  W, \运输问题：

. u( `, O( S+ N$ {9 e7 S最小费用最大流问题：在运输问题中，人们总是希望在完成运输任务的同时，寻求一个使总的运输费用最小的运输方案
1 i) P5 Q) }/ k% k( s9 W在数学建模中常用的算法：
7 S4 A+ \. {+ q+ W; I* L; r. M" u1：蒙特卡罗算法；
1 Y) T9 Q$ T! D2 \( w2：数据拟合、参数估计、插值等数据处理算法（常用matlab实现）；
3：线性规划、整数规划、多元规划、二次规划(用lingo、lingdo、matlab即可实现)；
" S0 q2 L8 K5 _/ V) q4：图论算法（包括最短路、网络流、二分图）；
( v+ h, R7 D8 h* Q  Z5：动态规划、回溯搜索、分治算法、分支界定；
  W) g. @( R! l+ D6：最优化理论的三大经典算法（模拟退火算法、神经网络算法、遗传算法）；
1 S+ \/ L/ i" b& C" K7：网格算法和穷举法；
7 ~$ D' d$ o7 D4 s& ~8：连续数据离散化；
! ?% [9 |4 {- e8 `: J7 s3 Q0 Q9：数值分析算法；
10：图象处理算法（常用matlab来实现）。
1 u8 `: o1 H8 `5 _


---------------------