Mengzelev's Blog

数学建模几种常用算法

Word count: 1,651 / Reading time: 7 min
2019/01/19 Share

数据拟合

多项式拟合

1
2
3
4
5
6
x = [...];
y = [...];
P = polyfit(x,y,n); % n是多项式的次数
xi = 0: .2 :10;
yi = polyval(P, xi);
plot(xi, yi, x, y, 'r*');

规划

线性规划

标准型$$\min~c^Tx s.t. Ax\le b$$

1
[x,y] = linprog(c, -a, -b, [], [], zeros(3,1))

非线性规划

1
2
3
4
5
6
[x,y] = fmincon(fun, x0, A, B, Aeq, Beq, LB, UB, [c,ceq], OPTIONS)
% fun:目标函数
% x0:x的初始条件
% A,B,Aeq,Beq:线性约束条件
% LB,UB:上下界
% [c,ceq]:.m文件定义的非线性约束条件,分别为不等式与等式约束

二次规划

1
[x, fval] = quadprog(H, f, A, b, Aeq, Beq, LB, UB, X0, OPTIONS)

整数规划

  • 隐枚举法
  • 随机算法(蒙特卡洛)
  • 分枝定界法

其他求解约束最优化问题的函数

  • fminbnd:单变量非线性函数在区间上的极小值
  • fseminf
  • fminimax:函数族的极大极小值

灰色预测

GM(1,1)模型适用于具有较强指数规律的序列,只能描述单调的变化过程,而Verhulst模型则适用于非单调的摆动发展序列或具有饱和状态的S形序列。
原始数列$x^{(0)}$,AGO累加生成数列$x^{(1)}$,加权均值数列$z^{(0)}$

关联分析和优势分析

  • 根据bigger is better和smaller is better标准将数据分类进行初始化
  • 根据公式算关联系数
  • 根据关联系数计算关联度

灰色预测步骤

  • 数据的检验与处理:计算级比,视情况进行必要的变换处理,使其落入可容覆盖内
  • 建立模型 $x^{(1)}=…$可以得到预测值
  • 残差检验
  • 级比偏差检验
  • 预测预报
  • 另:灾变预测可以构造灾变数列

遗传算法

  • 求解多约束复杂非线性规划问题
  • 直接调库吧,不可能看懂的

层次分析法(Analytic Hierarchy Process)

  • 用于解决较为复杂、模糊、难于定量分析的问题
  • 当影响决策的因素较多且较主观时
  • 分层、构造矩阵、检验一致性

因为基本上做E或F题都会用到,所以详细展开一下

基本步骤

  • 建立递阶层次结构模型;
  • 构造出各层次中的所有判断矩阵;
  • 层次单排序及一致性检验;
  • 层次总排序及一致性检验。

层次结构的建立

构造判断矩阵

层次单排序一致性检验

  • 判断矩阵$A$对应于最大特征值$\lambda_{max}$的特征向量$W$ ,经归一化后即为同一层次相应因素对于上一层次某因素相对重要性的排序权值,这一过程称为层次单排序
  • 如果比较结果是前后完全一致的,则矩阵$A$的元素还应当满足$a_{ij}a_{jk}=a_{ik}$,此时矩阵$A$成为一致矩阵
  • $n$阶正互反矩阵$A$为一致矩阵当且仅当其最大特征根$\lambda_{max}=n$,且当正互反矩阵$A$非一致时,必有$\lambda_{max}>n$
  • 一致性检验步骤
    • 计算一致性指标$CI=\frac{\lambda_{max}-n}{n-1}$
    • 查找相应的平均随机一致性指标$RI$
    • 计算一致性比例$CR=\frac{CR}{CI}$
    • $CR<0.10$时,认为判断矩阵的一致性是可以接受的,否则应对判断矩阵作适当修正

层次总排序一致性检验

设A层(上一层次)包含$A_1,…A_m$共$m$个因素,层次总排序权重分别为$a_1,…a_m$,又设其后的下一层次B层包含$n$个因素$B_1,…B_n$,它们关于$A_j$的层次单排序权重分别为$b_{1j},…b_{nj}$(当$B_i$与$A_j$无关时,$b_{ij}=0$)。现求$B$层中各因素关于总目标的权重,即求$B$层个因素的层次总排序权重$b_1,…,b_n$。
$B$层各因素的层次总排序权重$b_i=\sum\limits_{j=1}^{m}b_{ij}a_{j}$
B层总排序随机一致性比例$$CR=\frac{\sum\limits_{j=1}^{m}CI(j)a_j}{\sum\limits_{j=1}^{m}RI(j)a_j}$$
$CR<0.10$时认为层次总排序具有较满意的一致性并接受该分析结果

方差分析(ANOVA)

  • 又称F检验
  • 用数理统计分析试验结果、鉴别各因素对结果影响程度的方法

单因素方差分析

  • 任务:从试验结果推断某因素对指标有无显著影响
  • 单因素方差分析表
  • 方差分析命令anovalp = anoval(x,group)将算得的概率p\alpha进行比较

双因素方差分析

  • p = anova2(x,reps)

多因素方差分析

  • anovan
1
2
3
4
5
y = [31 54 38 53 49 42 57 62 64]; %试验结果
g1 = [1 2 3 1 2 3 1 2 3]; %正交表第一列
g2 = [1 1 1 2 2 2 3 3 3];
g3 = [2 1 3 1 3 2 3 2 1];
[p,t,st] = anovan(y,{g1,g2,g3})

回归分析

  • 用来检验拟合函数的准确度

  • 残差:实际观察值,估计值(拟合值)之间的差

  • $R^2$判定系数:可解释的变异占总变异的百分比

多元线性回归

1
2
3
4
5
6
[b,bint,r,rint,stats] = regress(y,x,alpha);
% b为回归系数估计值
% bint为置信区间
% r为残差,rint为残差的置信区间
% stats是用于检验回归模型的统计量[R^2,F,p,s^2]
% alpha显著性水平,缺省时为0.05

一元多项式回归

1
2
3
4
[p,s] =  polyfit(x0, y0, 2);
% s为用于计算函数值的数据结构,如
[y,delta] = polyconf(p,x0,s);y
%可以得到y的拟合值、置信区间半径delta

多元二项式回归

1
2
3
4
rstool(x,y,model,alpha)
% x:n×m维矩阵
% y:n维向量
%model:线性、纯二次、交叉、完全二次四选一

主成成分分析

  • 用较少的变量去解释原来资料中的大部分变异
  • 选出比原始变量个数少、能解释大部分资料中的变异的几个新变量

步骤

  • 对原始数据进行标准化处理
  • 计算相关系数矩阵$R$
  • 计算特征值和特征向量
  • 选择$p$个主成分,计算综合评价值
  • 计算综合得分

排队论

  • 有很多公式,用的时候再查吧
  • 优化:最优服务率,最优服务台数

灵敏度分析

  • 当模型的数据中有一个或几个发生变化时,最优解会有什么变化
  • 这些数据在什么范围内变化时,已求解的最优解不变
CATALOG
  1. 1. 数据拟合
    1. 1.1. 多项式拟合
  2. 2. 规划
    1. 2.1. 线性规划
    2. 2.2. 非线性规划
    3. 2.3. 二次规划
    4. 2.4. 整数规划
    5. 2.5. 其他求解约束最优化问题的函数
  3. 3. 灰色预测
    1. 3.1. 关联分析和优势分析
    2. 3.2. 灰色预测步骤
  4. 4. 遗传算法
  5. 5. 层次分析法(Analytic Hierarchy Process)
    1. 5.1. 基本步骤
    2. 5.2. 层次结构的建立
    3. 5.3. 构造判断矩阵
    4. 5.4. 层次单排序一致性检验
    5. 5.5. 层次总排序一致性检验
  6. 6. 方差分析(ANOVA)
    1. 6.1. 单因素方差分析
    2. 6.2. 双因素方差分析
    3. 6.3. 多因素方差分析
  7. 7. 回归分析
    1. 7.1. 多元线性回归
    2. 7.2. 一元多项式回归
    3. 7.3. 多元二项式回归
  8. 8. 主成成分分析
    1. 8.1. 步骤
  9. 9. 排队论
  10. 10. 灵敏度分析