搜索
数数学建模常用算法学建模常用算法杨蕾杨蕾数学建模常用算法数学建模常用算法//方法方法1、数据拟合与插值2、回归分析法3、规划/优化问题（线性规划，非线性规划，整数规划，动态规划，目标规划）4、图论法5、聚类分析、判别分析6、模糊数学相关问题评判方法7、时间序列方法8、灰色理论方法9、先进优化算法（遗传算法，神经网络）11、数据拟合与插值方法、数据拟合与插值方法¾问题—给定一批数据点（输入变量与输出变量的数据），需确定满足特定要求的曲线或曲面¾插值问题—要求所求曲线（面）通过所给所有数据点¾数据拟合—不要求曲线（面）通过所有数据点，而是要求它反映对象整体的变化趋势数据拟合数据拟合¾一元函数拟合¾多项式拟合¾非线性函数拟合¾多元函数拟合（回归分析）¾MATLAB实现(拟合工具箱cftool)¾确定出拟合函数，进而计算任一点的函数值，可以用于预测插值方法插值方法¾一维插值的定义—已知n个节点，求任意点处的函数值。¾分段线性插值¾多项式插值¾样条插值¾y=interp1(x0,y0,x,'method')¾二维插值—节点为网格节点¾z=interp2(x0,y0,z0,x,y,'method')¾pp=csape({x0,y0},z0,conds,valconds)¾二维插值—节点为散点¾z1=griddata(x,y,z,x1,y1)22、回归分析、回归分析¾回归分析—对具有相关关系的现象，根据其关系形态，选择一个合适的数学模型，用来近似地表示变量间的平均变化关系的一种统计方法（一元线性回归、多元线性回归、非线性回归）¾回归分析在一组数据的基础上研究这样几个问题：¾建立因变量与自变量之间的回归模型（经验公式）¾对回归模型的可信度进行检验¾判断每个自变量对因变量的影响是否显著¾判断回归模型是否适合这组数据¾利用回归模型对进行预报或控制¾[b,bint,r,rint,stats]=regress(Y,X,alpha)（线性回归）¾rstool（x，y，’model’,alpha）（多元二项式回归）¾[beta,r,J]=nlinfit（x，y，’model’,beta0）（非线性回归）逐步回归分析逐步回归分析¾逐步回归分析—从一个自变量开始，视自变量作用的显著程度，从大到地依次逐个引入回归方程¾当引入的自变量由于后面变量的引入而变得不显著时，要将其剔除掉¾引入一个自变量或从回归方程中剔除一个自变量，为逐步回归的一步¾对于每一步都要进行值检验，以确保每次引入新的显著性变量前回归方程中只包含对作用显著的变量¾这个过程反复进行，直至既无不显著的变量从回归方程中剔除，又无显著变量可引入回归方程时为止¾stepwise(x,y,inmodel,alpha)¾SPSS,SAS33、规划、规划//优化模型分类优化模型分类¾线性规划模型（目标函数和约束条件都是线性函数的优化问题）¾非线性规划模型（目标函数或者约束条件是非线性的函数）¾整数规划（决策变量是整数值得规划问题）¾多目标规划（具有多个目标函数的规划问题）¾动态规划（求解多阶段决策问题的最优化方法）规划规划//优化优化模型四要素模型四要素¾决策变量¾目标函数（建模的核心，尽量简单、光滑）¾约束条件（建模的关键部分）¾求解方法（MATLAB,LINDO）规划规划//优化模型求解优化模型求解((matlabmatlab))¾无约束规划¾fminsearch¾fminbnd¾线性规划¾linprog¾非线性规划¾fmincon¾多目标规划（计算有效解）¾目标加权、效用函数¾动态规划（倒向、正向）¾整数规划（分支定界法、枚举法、Lingo、Lindo）44、图论方法、图论方法¾最短路问题¾两个指定顶点之间的最短路径—给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线（Dijkstra算法）¾每对顶点之间的最短路径（Dijkstra算法、Floyd算法）¾最小生成树问题¾连线问题—欲修筑连接多个城市的铁路设计一个线路图，使总造价最低（prim算法、Kruskal算法）¾图的匹配问题¾人员分派问题：n个工作人员去做件n份工作，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？(匈牙利算法)图论方法图论方法¾遍历性问题¾中国邮递员问题—邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线—旅行商问题¾最大流问题¾运输问题¾最小费用最大流问题¾在运输问题中，人们总是希望在完成运输任务的同时，寻求一个使总的运输费用最小的运输方案55、聚类分析、聚类分析¾聚类分析—所研究的样本或者变量之间存在程度不同的相似性，要求设法找出一些能够度量它们之间相似程度的统计量作为分类的依据，再利用这些量将样本或者变量进行分类¾系统聚类分析—将n个样本或者n个指标看成n类，一类包括一个样本或者指标，然后将性质最接近的两类合并成为一个新类，依此类推。最终可以按照需要来决定分多少类，每类有多少样本（指标）系统聚类分析步骤系统聚类分析步骤系统聚类方法步骤：1.计算n个样本两两之间的距离2.构成n个类，每类只包含一个样品3.合并距离最近的两类为一个新类4.计算新类与当前各类的距离（新类与当前类的距离等于当前类与组合类中包含的类的距离最小值），若类的个数等于1，转5，否则转35.画聚类图6.决定类的个数和类。分解聚类分解聚类z分解聚类：把全部样本作为一类，然后根据相似性、相邻性分解。z目标函数两类均值方差)()(212121xxxxTNNNE−−=N：总样本数，：ω1类样本数：ω2类样本数，两类均值:,21xx1N2N分解聚类框图：分解聚类框图：初始分类调整分类方案最终结果目标函数达到最优先？NYK-均值聚类分析K-meansCluster又称为快速样本聚类法，是非系统聚类中最常用的聚类法。优点：是占内存少、计算量小、处理速度快，特别适合大样本的聚类分析。缺点：应用范围有限，要求用户制定分类数目(要告知)，只能对观测量（样本）聚类基本原理具体做法1、按照指定的分类数目n，按某种方法选择某些观测量，设为{Z1，Z2，…Zn}，作为初始聚心。2、计算每个观测量到各个聚心的欧氏距离。即按就近原则将每个观测量选入一个类中，然后计算各个类的中心位置，即均值，作为新的聚心。3、使用计算出来的新聚心重新进行分类，分类完毕后继续计算各类的中心位置，作为新的聚心，如此反复操作，直到两次迭代计算的聚心之间距离的最大改变量小于初始聚类心间最小距离的倍数时，或者到达迭代次数的上限时，停止迭代。()2112⎥⎦⎤⎢⎣⎡−=−=∑=mkjkikjiijxxzxd判别分析判别分析¾判别分析—在已知研究对象分成若干类型，并已取得各种类型的一批已知样品的观测数据，在此基础上根据某些准则建立判别式，然后对未知类型的样品进行判别分类。¾距离判别法—首先根据已知分类的数据，分别计算各类的重心，计算新个体到每类的距离，确定最短的距离（欧氏距离、马氏距离）¾Fisher判别法—利用已知类别个体的指标构造判别式（同类差别较小、不同类差别较大），按照判别式的值判断新个体的类别¾Bayes判别法—计算新给样品属于各总体的条件概率，比较概率的大小，然后将新样品判归为来自概率最大的总体66、模糊数学相关的问题、模糊数学相关的问题¾模糊数学—研究和处理模糊性现象的数学（概念与其对立面之间没有一条明确的分界线）66、模糊数学相关的问题、模糊数学相关的问题¾模糊聚类分析—根据研究对象本身的属性构造模糊矩阵，在此基础上根据一定的隶属度来确定其分类关系¾模糊层次分析法—两两比较指标的确定¾模糊综合评判—综合评判就是对受到多个因素制约的事物或对象作出一个总的评价，如产品质量评定、科技成果鉴定、某种作物种植适应性的评价等，都属于综合评判问题。由于从多方面对事物进行评价难免带有模糊性和主观性，采用模糊数学的方法进行综合评判将使结果尽量客观从而取得更好的实际效果77、时间序列分析建模、时间序列分析建模¾时间序列是按时间顺序排列的、随时间变化且相互关联的数据序列—通过对预测目标自身时间序列的处理，来研究其变化趋势（长期趋势变动、季节变动、循环变动、不规则变动）¾自回归模型¾一般自回归模型AR(n)—系统在时刻t的响应X(t)仅与其以前时刻的响应X(t-1),…，X(t-n)有关，而与其以前时刻进入系统的扰动无关¾移动平均模型MA(m)—系统在时刻t的响应X(t)，与其以前任何时刻的响应无关，而与其以前时刻进入系统的扰动a(t-1),…,a(t-m)存在着一定的相关关系¾自回归移动平均模型ARMA(n,m)—系统在时刻t的响应X(t)，不仅与其前n个时刻的自身值有关，而且还与其前m个时刻进入系统的扰动存在一定的依存关系时间序列建模的基本步骤时间序列建模的基本步骤（（11））1.数据的预处理：数据的剔取及提取趋势项2.取n=1，拟合ARMA(2n,2n-1)（即ARMA(2,1)）模型3.n=n+1，拟合ARMA(2n,2n-1)模型4.用F准则检验模型的适用性。若检验显著，则转入第2步。若检验不显著，转入第5步。5.检查远端时刻的系数值的值是否很小，其置信区间是否包含零。若不是，则适用的模型就是ARMA(2n,2n-1)。若很小，且其置信区间包含零，则拟合ARMA(2n-1,2n-2)。时间序列建模的基本步骤时间序列建模的基本步骤（（22））6.利用F准则检验模型ARMA(2n,2n-1)和ARMA(2n-1,2n-2)，若F值不显著，转入第7步；若F值显著，转入第8步。7.舍弃小的MA参数，拟合m2n-2的模型ARMA(2n-1,m)，并用F准则进行检验。重复这一过程，直到得出具有最小参数的适用模型为止8.舍弃小的MA参数，拟合m2n-1的模型ARMA(2n,m)，并用F准则进行检验。重复这一过程，直到得出具有最小参数的适用模型为止。88、灰色理论、灰色理论1982年我国学者邓聚龙创立了灰色系统理论，模糊数学着重研究“认知不确定”问题，概率统计研究的是“随机不确定”现象的历史统计规律。灰色系统研究的是“部分信息明确，部分信息未知”的“小样本，贫信息”不确定性系统，它通过对已知“部分”信息的生成去开发了解、认识现实世界。¾¾灰色预测模型灰色预测模型(0)(0)(0)(0)((1),(2),,())Xxxxn=LGM(1,1)预测模型步骤：1、对于原始数列，做一次累加得，其中2、计算并得到(1)(1)(1)(1)((1),(2),,())Xxxxn=L(1)(0)1()(),1,2,,;kixkxikn===∑L))1()((21)()1()1()1(−+=kkkxxznk,3,2Λ=⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡=)()3()2()0()0()0(nY，xxxΜ⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡−−−=1)(1)3(1)2()1()1()1(nBzzzΜΜ3、计算参数向量4、将参数a,b代入响应函数，得到累加序列预测值5、由累加序列得到原始序列预测值YBBBaTTTba1)(ˆ),(−==ababkexxak+−=+−))1(()1()0()1(ˆexexxxakaabkkk−−−=−+=+))1()(1()()1()1()0()1()1()0(ˆˆˆGM(1,1)主要用于单调序列，灰色预测模型除GM(1,1)之外，还有:¾残差GM(1,1)模型¾对于非单调的摆动发展序列或有饱和的S形序列，可建立GM(2,1)，DGM和Verhulst模型¾区间预测¾灰色灾变预测(波形预测)¾系统预测灰色理论除了用于预测之外，还包含:¾灰色决策¾灰色人工神经网络模型¾灰色动态规划¾灰色控制¾灰色聚类评估99、先进优化算法、先进优化算法¾遗传算法¾神经网络¾微粒群算法PSO¾模拟退火算法遗传算法传统的优化方法（局部优化）共轭梯度法、拟牛顿法、单纯形方法全局优化方法漫步法（RandomWalk）、模拟退火法、GA比较：传统的优化方法关于优化问题1）依赖于初始条件。2）与求解空间有紧密关系