数学建模常用算法思路

Author Avatar
Brian Lee 2月 28, 2018
  • 在其它设备中阅读本文章

前不久刚刚参加了美国大学生数学建模竞赛,以下内容是我在准备过程中的笔记,主要记录了一些常用算法的适用情况以及建模思路。


评价模型

层次分析法

Analytic Hierarchy Process(AHP)

适用情况

对较为复杂、较为模糊的问题作出决策,适用于难以完全定量分析的问题

步骤

  1. 建立递阶层次结构模型
    • 目标层、准则层、措施层
  2. 构造出各层次中的所有判断矩阵
    • 以数字1-9作为标度,构建的判断矩阵为正互反矩阵
    • 两组判断矩阵,一组(个)准则层的判断矩阵,一组方案层的判断矩阵
  3. 层次单排序及一致性检验
    • 判断矩阵 $A$对应于最大特征值 $λ_{max}$ 的特征向量 $W$ ,经归一化后即为同一层次相应因素对于上一层次某因素相对重要性的排序权值
    • 一致性检验:计算一致性指标CI、查找相应的平均随机一致性指标RI、计算一致性比例CR
    • 当 $CR<0.10$ 时,判断矩阵一致性可接受,否则对判断矩阵作适当修正
    • 最终得到一组元素对其上一层中某元素的权重向量
  4. 层次总排序及一致性检验
    • 要得到最底层中各方案对于目标的排序权重,总排序权重要自上而下地将单准则下的权重进行合成
    • 一致性检验由高层向低层逐层进行
    • 当 $CR<0.10$ 时,认为层次总排序结果具有较满意的一致性

主成分分析

PCA

适用情况

PCA是一种数学降维方法,将多个相关变量组合为一组新的数量较少的相互无关的综合变量

步骤

  1. 分别求x和y的平均值,然后对于所有样例,都减去对应的均值
  2. 求特征方差矩阵
  3. 求协方差的特征值和特征向量
  4. 将特征值按照从大到小的顺序排序,选择其中最大的k个,然后将其对应的k个特征向量分别作为列向量组成特征向量矩阵。
  5. 将样本点投影到选取的特征向量上

熵权法

适用情况

熵权法是一种客观赋权方法,根据各指标的变异程度,利用信息熵计算出各指标的权重

步骤

  1. 数据标准化
  2. 计算第$j$个指标下第$i$个项目的指标值的比重 $p_{ij}$
  3. 计算第$j$个指标的熵值$e_j$
  4. 计算第$j$个指标的熵权$w_j$
  5. 计算各样本的综合得分

预测模型

马氏链模型

适用情况

根据某些变量现在的情况及其变动趋向,预测它在未来某特定区间可能产生的变动,作为提供某种决策的依据

步骤

  1. 确定元素及元素间相互转移的概率
  2. 构建转移矩阵
  3. 求解方程组
  4. 求解得极限概率

灰色预测模型

适用情况

不需要很多数据就能解决历史数据少、序列的完整性及可靠性低的问题;能利用微分方程来充分挖掘系统的本质,精度高;只适用于中短期预测。

步骤

  1. 数据的检验与处理
  2. 建立模型
  3. 检验预测值
  4. 残差检验
  5. 级比偏差值检验

微分方程建模

适用情况

把实际问题化为微分方程的定解问题

步骤

  1. 根据实际要求确定要研究的量(自变量、未知函数、必要的参数等),并确定坐标系
  2. 找出这些量所满足的基本规律(物理的、几何的、化学的或生物的)
  3. 运用这些规律列出方程和定解条件
    • 按规律直接列方程
    • 微元分析法与任意区域上取积分的方法
    • 模拟近似法
  4. 求解方程

灰色关联分析

适用情况

对于两个系统之间的因素,其随时间或不同对象而变化的关联性大小的量度称为关联性。衡量因素间关联程度的一种方法,若样本数据反映出的两因素变化的态势(方向、大小和速度等)基本一致,则它们之间的关联度较大;反之,关联度较小。

步骤

  1. 求初值项
  2. 求差序列
  3. 求两极差
  4. 计算关联系数
  5. 求灰色关联度
  6. 关联度排序

优化模型

线性规划

适用情况

利用现有资源来安排生产,以取得最大经济效益

步骤

  1. 根据问题中提及变量确定决策变量
  2. 基本假设
  3. 根据所要求得的结果确定目标函数
  4. 根据题目中条件确定约束条件
  5. 模型求解(也可使用图解法)

整数规划

适用情况

规划中的变量(部分或全部)限制为整数时,一般指整数线性规划

步骤

  • 分枝定界法
    对有约束条件的最优化问题的所有可行解空间恰当地进行系统搜索
    1. 设有最大化的整数规划问题$A$
    2. 先不考虑整数限制,求得相应的线性规划,求得最优解$z$
    3. 若最优解不符合整数条件,此时z为最优目标函数值$z^b$的上界,$A$的任意可行解的目标函数值为$z^b$的一个下界
    4. 重复分枝、定界,直到求得整数最优解
  • 0-1型整数规划
    变量$x_j$仅取0或1
    1. 试探性求一个可行解
    2. 增加约束条件
    3. 改进过滤条件
    4. 优先计算目标值$z$大的组合
  • 蒙特卡洛法
    用于解决非线性整数规划

非线性规划

适用情况

目标函数或约束条件中包含非线性函数

步骤

  1. 确定供选方案,并用一组变量表示它们
  2. 提出追求目标,并表示为数学关系式
  3. 给出价值标准,并以某种数量形式来描述它
  4. 寻求限制条件,并用变量之间一些不等式或等式表示
  5. 求解,有多种方法,有其特定的适用范围

分类模型

K-Means聚类算法

适用情况

在数据中发现数据对象之间的关系,将数据进行分组,组内相似性越大,组间差别很大,则聚类效果越好。

步骤

选择k个点作为初始质心
repeat
    将每个点指派到最近的质心,形成k个簇
    重新计算每个簇的质心
until 簇不发生变化或达到最大迭代次数

本博客采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!
本文链接:http://brianleelxt.top/2018/02/28/math-model/