数学建模中的算法

A. 【数学建模算法】(28)插值和拟合：最小二乘优化

在无约束最优化问题中，有些重要的特殊情形，比如目标函数由若干个函数的平方和构成。这类函数一般可以写携含成：

其中 ，一般假设 。我们把极小化这类函数的问题：

称为最小二乘优化问题。

求解
s.t.
其中 为矩阵， 为向量。
Matlab函数为：
x=lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0)

解：程序如下：

给定输入输出数列 ，求参量 使得

Matlab中的函数为：
X=lsqcurvefit(FUN,X0,XDATA,YDATA,LB,UB,OPTIONS)
其中FUN是定义函数 的N文件。

解：这个问题即解最优化问题：

解这个问题要分知芦两步：
首先编写待求函数：

已知函数向量 ，求 使得：

Matlab中的函数为：

用该函数求解例2：
首先编写含有待求参数的函数：

之后调用函数lsqnonlin，编写如下程序：

求解 非负 的 ，使得满足
Matlab中的搭隐带函数为：

编写程序如下：

B. 【数学建模算法】(16)排队论：常用的几种概率分布及产生

区间 内的 均匀分布 记做 。服从 分布的随机变量又称为随机数，它是产生其他随机变量的基础。如若 为 分布，则 服从 。

以 为期望， 为方差的 正态分布 记做 。正态分布的应用十分广泛。正态分布还可以作为二项分布一定条件下的近似。

指数分布 是单参数 的非对称分布，记做 ，概率密度函数为：

数学期望为 ，方差为 。指数分布是唯一具有无记忆性的连续型随机变量，既有 ，在排队论，可靠性分析中有广泛应用。

Gamma分布是双参数 的非对称分布，记做 ，期望是 。 时退化为指数分布。 个相互独立，同分布（参数 ）的指数分布之和是Gamma分布 。Gamma分布可用于服务时间，零件寿命等。
Gamma分布又称为埃尔朗分布。

Weibull分布是双参数 的非对称分布，记做 。 时退化为指数分布。作为设备，零件的寿命分布在可靠性分析中有非常广泛的应用。

Beta分布是区间 内的双参数，非均匀分布，记做 。

伯努利分布是 处取值的概率分别是 和 的两点分布，记做 。用于基本的离散模型。

泊松分布与指数分布有密切的关系。当顾客平均到达率为常数 的到达间隔服从指数分布时，单位时间内到达的顾客数 服从泊松分布，即单位时间内到达 位顾客的概率为：

记做 。泊松分布在排队服务，产品检验，生物与医学统计，天文，物理等领域都有广泛应用。

在独立进行的每次试验中，某事件发生的概率为 ，则 次实验中该事件发生的次数 服从二项分布，即发生 次的概率为：

记做 。二项分布是 个独立的伯努利分布之和。它在产品检验，保险，生物和医学统计等领域有着广泛的应用。
当 很大时， 近似于正态分布 ；当 很大， 很小，且 约为常数 时， 近似于

C. 数学建模应用的数学建模十大算法

1、蒙特卡罗算法,该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性。
2、数据拟合、参数估计、插值等数据处理算法，通常使用Matlab作为工具。
3、线性规划、整数规划、多元规划、二次规划等规划类问题，通常使用Lindo、Lingo软件实现。
4、图论算法，这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决。
5、动态规划、回溯搜索、分治算法、分支定界等计算机算法。
6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用）
7、网格算法和穷举法，网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。
8、一些连续离散化方法，很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要。
9、数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用）。
10、图象处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理）。

D. 参加数学建模有哪些必学的算法

1. 蒙特卡洛方法：
又称计算机随机性模拟方法，也称统计实验方法。可以通过模拟来检验自己模型的正确性。

2. 数据拟合、参数估计、插值等数据处理
比赛中常遇到大量的数据需要处理，而处理的数据的关键就在于这些方法，通常使用matlab辅助，与图形结合时还可处理很多有关拟合的问题。

3. 规划类问题算法：
包括线性规划、整数规划、多元规划、二次规划等；竞赛中又很多问题都和规划有关，可以说不少的模型都可以归结为一组不等式作为约束条件，几个函数表达式作为目标函数的问题，这类问题，求解是关键。
这类问题一般用lingo软件就能求解。

4. 图论问题：
主要是考察这类问题的算法，包括：Dijkstra、Floyd、Prime、Bellman-Ford，最大流、二分匹配等。熟悉ACM的人来说，应该都不难。

5. 计算机算法设计中的问题：
算法设计包括：动态规划、回溯搜索、分治、分支定界法（求解整数解）等。

6. 最优化理论的三大非经典算法：
a) 模拟退火法（SA）
b) 神经网络（NN）
c) 遗传算法（GA）

7. 网格算法和穷举算法

8. 连续问题离散化的方法
因为计算机只能处理离散化的问题，但是实际中数据大多是连续的，因此需要将连续问题离散化之后再用计算机求解。
如：差分代替微分、求和代替积分等思想都是把连续问题离散化的常用方法。

9. 数值分析方法
主要研究各种求解数学问题的数值计算方法，特别是适用于计算机实现的方法与算法。
包括：函数的数值逼近、数值微分与数值积分、非线性返程的数值解法、数值代数、常微分方程数值解等。
主要应用matlab进行求解。

10. 图像处理算法
这部分主要是使用matlab进行图像处理。
包括展示图片，进行问题解决说明等。

E. 数学建模中的数学模型和算法有什么关系，怎样理解它们之间的联系和区别

模型是将实际问题转换为数学问题，算法是求解模型的方法。

F. 数学建模算法总结

无总结反省则无进步

写这篇文章，一是为了总结之前为了准备美赛而学的算法，而是将算法罗列并有几句话解释方便以后自己需要时来查找。

数学建模问题总共分为四类：

1. 分类问题 2. 优化问题 3. 评价问题 4. 预测问题

我所写的都是基于数学建模算法与应用这本书

一 优化问题

线性规划与非线性规划方法是最基本经典的：目标函数与约束函数的思想

现代优化算法：禁忌搜索；模拟退火；遗传算法；人工神经网络

模拟退火算法：

简介：材料统计力学的研究成果。统计力学表明材料中不同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温（此过程称为退火），粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形成处于低能状态的晶体。

思想可用于数学问题的解决 在寻找解的过程中，每一次以一种方法变换新解，再用退火过程的思想，以概率接受该状态（新解） 退火过程：概率转化，概率为自然底数的能量/KT次方

遗传算法： 遗传算法是一种基于自然选择原理和自然遗传机制的搜索算法。模拟自然界中的生命进化机制，在人工系统中实现特定目标的优化。

遗传算法的实质是通过群体搜索技术（？），根据适者生存的原则逐代进化，最终得到最优解或准最优解。

具体实现过程（P329~331）

* 编码

* 确定适应度函数（即目标函数）

* 确定进化参数：群体规模M，交叉概率Pc，变异概率Pm，进化终止条件

* 编码

* 确定初始种群，使用经典的改良圈算法

* 目标函数

* 交叉操作

* 变异操作

* 选择

改良的遗传算法

两点改进 ：交叉操作变为了以“门当户对”原则配对，以混乱序列确定较差点位置 变异操作从交叉操作中分离出来

二 分类问题（以及一些多元分析方法）

* 支持向量机SVM

* 聚类分析

* 主成分分析

* 判别分析

* 典型相关分析

支持向量机SVM： 主要思想：找到一个超平面，使得它能够尽可能多地将两类数据点正确分开，同时使分开的两类数据点距离分类面最远

聚类分析（极其经典的一种算法）： 对样本进行分类称为Q型聚类分析 对指标进行分类称为R型聚类分析

基础：样品相似度的度量——数量化，距离——如闵氏距离

主成分分析法： 其主要目的是希望用较少的变量去解释原来资料中的大部分变异，将掌握的许多相关性很高的变量转化成彼此相互独立或不相关的变量。通常是选出比原始变量个数少，能解释大部分资料中的变异的几个新变量，及主成分。实质是一种降维方法

判别分析： 是根据所研究的个体的观测指标来推断个体所属类型的一种统计方法。判别准则在某种意义下是最优的，如错判概率最小或错判损失最小。这一方法像是分类方法统称。 如距离判别，贝叶斯判别和FISHER判别

典型相关分析： 研究两组变量的相关关系 相对于计算全部相关系数，采用类似主成分的思想，分别找出两组变量的各自的某个线性组合，讨论线性组合之间的相关关系

三 评价与决策问题

评价方法分为两大类，区别在于确定权重上：一类是主观赋权：综合资讯评价定权；另一类为客观赋权：根据各指标相关关系或各指标值变异程度来确定权数

* 理想解法

* 模糊综合评判法

* 数据包络分析法

* 灰色关联分析法

* 主成分分析法（略）

* 秩和比综合评价法 理想解法

思想：与最优解（理想解）的距离作为评价样本的标准

模糊综合评判法 用于人事考核这类模糊性问题上。有多层次模糊综合评判法。

数据包络分析法 是评价具有多指标输入和多指标输出系统的较为有效的方法。是以相对效率为概念基础的。

灰色关联分析法 思想：计算所有待评价对象与理想对象的灰色加权关联度，与TOPSIS方法类似

主成分分析法（略）

秩和比综合评价法 样本秩的概念： 效益型指标从小到大排序的排名 成本型指标从大到小排序的排名 再计算秩和比，最后统计回归

四 预测问题

* 微分方程模型

* 灰色预测模型

* 马尔科夫预测

* 时间序列（略）

* 插值与拟合（略）

* 神经网络

微分方程模型 Lanchester战争预测模型。。

灰色预测模型 主要特点：使用的不是原始数据序列，而是生成的数据序列 优点：不需要很多数据·，能利用微分方程来充分挖掘系统的本质，精度高。能将无规律的原始数据进行生成得到规律性较强的生成序列。 缺点：只适用于中短期预测，只适合指数增长的预测

马尔科夫预测 某一系统未来时刻情况只与现在状态有关，与过去无关。

马尔科夫链

时齐性的马尔科夫链

时间序列（略）

插值与拟合（略）

神经网络（略）