数学建模算法与应用算法分类与总结
模型建立方法以及流程
问题分析
简述问题的意思,明确问题处理的思路
模型假设
通常为8-10条,给出模型在什么条件下成立
符号说明
模型建立
给出一定的公式,推到出相应的最终表达式
模型求解
灵敏度分析
已经假设固定的变量,实际上并不是固定的,要给定其一定的上下波动范围来对其进行求解
结果分析以及得出结论
规划类
线性规划
线性规划模型通常在题目中表现会比较明显,不过多赘述(书本$P_1$)
可转为线性规划的形式(书本$P_8$)
$$ \min \lvert x_1 \rvert + \lvert x_2 \rvert +\lvert x_3 \rvert + … + \lvert x_n \rvert \
s.t. Ax \leq b
$$带有绝对值的min max类非线性规划,可以使用手工线性化之后使用软件求解(书本$P_9$)
线性求解参考代码$P_{14}$
整数规划
适宜解决的问题
符合线性规划的形式且带整数约束的规划问题
要么是1要么是0的0-1规划问题(使用或不使用)
路线规划问题(也用于图论),即进入一个地方则$x_{ij}=1$,否则$x_{ij}=0$ ($P_{20}$)
引入充分大的数构成约束来达到选择的效果($P_{21}$)
混合整数规划问题,比如如果不采用a方案,那么a方案的产出$x_a=0$,这时候可以使用($P_{22}$)
代码参考$P_{26}$
利用蒙卡特洛方法可以很好地对非线性整数规划问题进行求解($P_{27}$)
非线性规划
无约束非线性优化的求解($P_{38}$),利用海塞尔矩阵求解
带约束非线性优化的求解思路,通常是线性化为非线性,带约束化为无约束
只有等式约束的时候,可以采用拉格朗日乘数法($P_{39}$)
当同时含有等式约束和不等式约束时,可以采用罚函数法($P_{39}$)
凸规划($P_{40}$)
凸规划是求解式子为凸函数,不等式约束为凸函数,等式约束为线性函数的规划,线性规划是特殊的凸规划,凸规划局部最优解即为全局最优解
KT条件用来判断凸规划的解x是否是全局最优解
例子($P_{42} , P_{56}$)
二次规划
- 决策变量为二次函数,而约束条件为线性函数的模型(P_{48})
非线性规划代码介绍($P_{49}$)
图论
Matlab生成图($P_{65}$)
典型的寻路算法(Dijkstra,Floyd)($P_{67}$)
最短路问题的0-1整数规划模型,见整数规划($P_{74}$)
最小生成树算法($P_{75}$)Prim,Kruskal算法,最小生成树的整数规划模型($P_{78}$)
最大流算法:所谓最大流算法指的是在流进等于流出的条件之下,整个图允许通过的最大容量(不包含始末),最大流算法可以写作整数规划模型来求解($P_{82}$),也可以使用标号法Ford-Fulkerson算法来实现($P_{83}$)
最小费用流算法:考虑到达终点所需要的最小花费的算法,一般和最大流算法一起使用,一般转化为线性规划来求解,也可以使用迭代法来求解($P_{84}$)
改良圈算法:即不重复经过同一个节点,且使得总路程最短的解算算法($P_{88}$),这个问题也可以用整数规划模型来解决
关键路径求解:可以将关键路径看成最长路径来进行求解$P_{96}$,也可以根据最早开工时间和最晚开工时间迭代求解$P_{97}$
实际上工作时间可能会随着客观因素而变动,利用$P_{100}$的算法来计算能够按时完成任务的概率
插值
特性:插值可以对区间之外的部分作出短期预测,长期预测可能失效较为严重
多项式插值($P_{114}$)
待定系数法,用于观测点数目和约束方程数量一致的情况($P_{114}$)
拉格朗日插值法,一般实际应用意义不是很大($P_{115}$)
牛顿插值法,一般实际应用意义不大($P_{116}$)
分段线性化方法插值,多项式高次插值导致产生龙格震荡现象,故利用分段线性化可以更好地拟合出真正地曲线($P_{119}$)
三次样条插值:分段线性化的插值会导致取样点处的导数不存在,三次插值实际上是利用节点处的一阶和二阶导数相等来待定系数求解($P_{119}$)
二次插值
网格节点插值法($P_{121}$)
最临近点插值,即某一点与这一点所处于的区间最接近的有值的一点函数值相同
分片线性插值
双线性插值
散乱数据插值方法,对一群离散点进行插值($P_{122}$)
拟合
最小二乘法拟合(线性与非线性)($P_{132}$)
拟合函数选择($P_{133}$)
拟合可以使用Matlab工具箱,参考($P_{133}$)
曲线与曲面拟合($P_{141}$)
拟合或统计的判断方法($P_{143}$)
函数逼近($P_{143}$)
微分方程
用途:可用于每一时刻的状态变化和下一时刻状态变化密切相关的场合,比如传染病模型,传染人数和感染人数相关
传播可以采用指数传播模型($P_{153}$)
三种典型的传染病模型($P_{154}$)
SI模型,不考虑治愈以及免疫
SIS模型考虑病人治愈
SIR模型考虑治愈以及免疫之后退出感染系统
微分方程求解($P_{159}$)
Lorenz模型的混沌效应:具有初值敏感性(不知道有什么用)($P_{161}$)
边值问题求解($P_{166}$)
人口预测模型
Malthus模型,人口预测模型,假设人口的增长率不变($P_{170}$)
Logistic模型,人口的增长率是与人口数量有关($P_{171}$)
种群相互作用模型
种群竞争模型($P_{173}$)
弱肉强食模型($P_{174}$)
数理统计
区间估计:即估计在某一区间内的数占总量的百分之几,注意均值和方差是否已知($P_{182}$)
双变量联合分布求置信区间示例($P_{184}$)
经验分布函数的使用($P_{184}$)
Q-Q图检验拟合优度,即检验某个随机变量是否符合你所预估的分布($P_{185}$)
非参数检验
卡方拟合优度检验:检验总体X是否满足某个概率密度($P_{187}$)
柯尔莫哥洛夫检验:基于经验分布函数检验理论分布函数与样本分布函数的拟合优度($P_{191}$)
秩和检验:检验两个分布总体分布是否有明显差异($P_{192}$)
Bootstrap方法:抽取很多个样本,利用样本对总体进行统计推断
标准误差的Bootstrap估计($P_{194}$)
均方误差的Bootstrap估计($P_{196}$)
Bootstrap求解置信区间($P_{197}$)
分布函数形式已知,但部分参数未知,可以利用Bootstrap进行参数估计($P_{198}$)
均值检验:比较两个总体的均值($P_{201}$),不用于多于两个总体
单因素方差分析:仅仅考虑一个因素,其它因素不变,用来判断该因素对总体的影响($P_{202}$)
双因素方差分析:考虑两个因素对总体的影响,包括无交互影响的双因素方差分析($P_{207}$)和有交互影响的方差分析($P_{208}$)
回归分析
多元线性回归
参数估计($P_{211}$)
对统计变量的残差,期望,方差进行分析($P_{212}$)
回归模型的假设检验,检验变量是否符合该多元线性关系,排除多出维度参数的可能($P_{213}$)
回归系数的假设检验和区间估计,即排除部分维度,找出拟合最好的维度,舍去贡献度很小的维度($P_{213}$)
回归模型预测($P_{214}$)
多元二次项回归($P_{214}$)
非线性回归($P_{218}$)
逐步回归:多因素,使用关联性强的因素选入模型进行回归,舍去关联性不强的因素
前进法,每次增加一个因素,然后使用显著性P值来检验新因素的影响($P_{220}$)
后退法,每次减少一个因素,然后使用显著性P值来检验新因素的影响($P_{221}$)
逐步回归法,每增加一个因素,就要对所有因素进行一次检验,解得的集合为最优回归子集($P_{221}$)
灰色模型和Bootstrap理论
用途:小样本,数据预测,统计推断,对分布参数进行较为精确的区间估计,不需要知道原有数据的分布($P_{222}$)
灰色模型建立($P_{223}$)
Bootstrap分析:重发取样,求得统计量的经验分布并进行区间估计($P_{224}$)
差分方程
特点:通过递推关系求得状态之间的关联
差分方程建模($P_{231}$)
Leslie种群模型:求年龄分布和种群增长的规律,有明显的递推关系特征
分类问题
支持向量机($P_{248}$)
Q型据类分析($P_{262}$),对样本进行分类
多元分析
聚类分析
Q型聚类分析,样本分类
R型聚类,用于变量分类,便于理清变量之间的关系,然后通过这个关系来选择关键因素进行模型建立($P_{269}$)
主成分分析($P_{279}$)
特点:是一种降维方法,去除很多无关的变量,提取主要变量
主成分回归分析:将回归自变量变换到另一组变量,提取主成分之后再进行逆变换之后得出参数估计
因子分析:和主成分分析的目的相同,都是特征降维($P_{285}$)
因子分析与主成分分析对比($P_{296}$)
判别分析:使用研究个体的观察指标来判断个体的类型($P_{303}$)
距离判断($P_{304}$)
Fisher判别($P_{306}$)
Bayes判别($P_{307}$)
典型相关分析:用来研究两组变量的相关关系($P_{313}$)
对应分析:再因子分析的基础之上,解决因子分析求解速度很慢的问题($P_{328}$)
多维标度法:n个指标反映的东西是模糊的,通过这几个指标的距离,反映他们之间的关系($P_{344}$)
偏最小二乘回归分析
- 通过从自变量和因变量中提取成分来求解多对多的回归建模($P_{355}$)
现代优化算法
模拟退火算法($P_{367}$)
遗传算法($P_{373}$)
综合评价和决策方法
确定多属性的权值算法
TOPSIS算法:通过距离正理想解和负理想解的距离来判断($P_{411}$)
模糊综合方法:不受主观因素影响,可用于人才资源评测($P_{416}$)
数据包络分析:对多指标输入和多指标输出有效($P_{410}$)
灰色关联分析($P_{424}$)
主成分分析($P_{427}$)
秩和比综合评价($P_{430}$)
熵权法评价($P_{432}$)
PageRank算法:搜索引擎检测结果排序算法($P_{434}$)
预测方法
根据已有数据对未来一段时间的数据进行预测
微分方程模型($P_{448}$)
灰色预测模型($P_{450}$)
马尔可夫预测模型:下一步发生的概率与历史的数据无关,仅仅与当前位置有关($P_{460}$)
时间序列
- 检验时间序列是否平稳的Daniel算法($P_{466}$)
插值与拟合($P_{469}$)
神经网络($P_{473}$)
通过元胞自动机来模拟传播并且进行预测
多目标规划
- 即有多个目标函数,求解对于所有目标函数最小或者最大的最优解问题