数学建模学习（2）：数学建模各类常用的算法全解析

一、评价类算法

常见的评价算法

 1.层次分析法

基本思想

        是定性与定量相结合的多准则决策、评价方法。将决策的有关元素分解成目标层、准则层和方案层，并通过人们的 判断对决策方案的优劣进行排序，在此基础上进行定性和定量分析。它把人的思维过程层次化、数量化，并用数学 为分析、决策、评价、预报和控制提供定量的依据。基本步骤        构建层次结构模型；构建成对比较矩阵；层次单排序及一致性检验（即判断主观构建的成对比较矩阵在整体上是否 有较好的一致性）；层次总排序及一致性检验（检验层次之间的一致性）。优点        它完全依靠主观评价做出方案的优劣排序，所需数据量少，决策花费的时间很短。从整体上看，AHP在复杂决策过 程中引入定量分析，并充分利用决策者在两两比较中给出的偏好信息进行分析与决策支持，既有效地吸收了定性分 析的结果，又发挥了定量分析的优势，从而使决策过程具有很强的条理性和科学性，特别适合在社会经济系统的决 策分析中使用。缺点        用AHP进行决策主观成分很大。当决策者的判断过多地受其主观偏好影响，而产生某种对客观规律的歪曲时，AHP 的结果显然就靠不住了。适用范围        尤其适合于人的定性判断起重要作用的、对决策结果难于直接准确计量的场合。要使AHP的决策结论尽可能符合客 观规律，决策者必须对所面临的问题有比较深入和全面的认识。另外，当遇到因素众多，规模较大的评价问题时， 该模型容易出现问题，它要求评价者对问题的本质、包含的要素及其相互之间的逻辑关系能掌握得十分透彻，否则 评价结果就不可靠和准确。改进方法(1)成对比较矩阵可以采用德尔菲法获得。 (2)如果评价指标个数过多（一般超过9个），利用层次分析法所得到的权重就有一定的偏差，继而组合评价模型 的结果就不再可靠。可以根据评价对象的实际情况和特点，利用一定的方法，将各原始指标分层和归类，使得每层各类中的指标数少于9个。 2.灰色综合评价法（灰色关联分析）

属于灰箱模型

基本思想

        灰色关联分析的实质就是，可利用各方案与最优方案之间关联度大小对评价象进行比较、排序。关联度越大，说明比较序列与参考序列变化的态势越一致，反之，变化态势则相悖。由此可得出评价结果。基本步骤        建立原始指标矩阵；确定最优指标序列；进行指标标准化或无量纲化处理；求差序列、最大差和最小差；计算关联系数；计算关联度。优点

        是一种评价具有大量未知信息的系统的有效模型，是定性分析和定量分析相结合的综合评价模型，该模型可以较好地解决评价指标难以准确量化和统计的问题，可以排除人为因素带来的影响，使评价结果更加客观准确。整个计算 过程简单，通俗易懂，易于为人们所掌握;数据不必进行归一化处理，可用原始数据进行直接计算，可靠性强；评价指标体系可以根据具体情况增减；无需大量样本，只要有代表性的少量样本即可。

缺点               要求样本数据且具有时间序列特性；只是对评判对象的优劣做出鉴别，并不反映绝对水平，故基于灰色关联分析综合评价具有“相对评价”的全部缺点。适用范围        对样本量没有严格要求，不要求服从任何分布，适合只有少量观测数据的问题；应用该种方法进 行评价时，指标体系及权重分配是一个关键的题，选择的恰当与否直接影响最终评价结果。改进方法(1)采用组合赋权法：根据客观赋权法和主观赋权法综合而得权系数。 (2)结合TOPSIS法：不仅关注序列与正理想序列的关联度，而且关注序列与负理想序列的关联度， 依据公式计算最后的关联度。

3.TOPSIS综合评价模型

基本思想

        TOPSIS模型是根据评价对象与理想化目标的接近程度进行排序的方法，是一种距离综合评价方法。基本思路是通过假定正、负理想解，测算各样本与正、负理想解的距离，得到其与理想方案的相对贴近度基本步骤            指标同向化、标准化并得到权重；得到加权后的规范化矩阵；确定正、负理想解；计算各样本距离正、负理想解的距离；计算各评价对象与最优方案的贴近程度优点

        避免了数据的主观性，不需要目标函数，不用通过检验，而且能够很好的刻画多个影响指标的综合影响力度。对于数据分布及样本量、指标多少无严格限制，既适于小样本资料，也适于多评价单元、多指标的大系统,较为灵 活、方便。缺点              需要的每个指标的数据，对应的量化指标选取会有一定难度。不确定指标的选取个数为多少适宜，才能够去很好刻画指标的影响力度。必须有两个以上的研究对象才可以进行使用适用范围        Topsis法被广泛用于企业管理、市场营销、投资决策等领域。主要适用于评价指标相对较多，指标间相互独立。改进方法       在 TOPSIS 当中，默认了各个评价指标所占的权重相同，但在实际的评价过程当中由于各种主观客观因素的影响， 导致每一个评价指标所占的权重是有差异的; 1. 主观权重——层次分析法（AHP)2. 客观权重——熵权法 4.BP神经网络综合评价法

基本思想

        是一种交互式的评价方法，它可以根据用户期望的输出不断修改指标的权值，直到用户满意为止。因此，一般来说，人工 神经网络评价方法得到的结果会更符合实际情况。

优点

        
神经网络具有自适应能力，能对多指标综合评价问题给出一个客观评价，这对于弱化权重确定中的人为因素是十分有益的。在以前的评价方法中，传统的权重设计带有很大的模糊性，同时权重确定中人为因素影响也很大。随着时间、空间的推移， 各指标对其对应题的影响程度也可能发生变化，确定的初始权重不一定符合实际情况。再者，考虑到整个分析评价是一个 复杂的非线性大系统，必须建立权重的学习机制，这些方面正是人工神经网络的优势所在。针对综合评价建模过程中变量 选取方法的局限性，采用神经网络原理可对变量进行贡献分析，进而剔除影响不显著和不重要的因素，以建立简化模型， 可以避免主观因素对变量选取的干扰。缺点                 ANN在应用中遇到的最大问题是不能提供解析表达式，权值不能解释为一种回归系数，也不能用来分析因果关系，目前还不能从理论上或从实际出发来解释ANN的权值的意义。需要大量的训练样本，精度不高，应用范围是有限的。最大的应用 障碍是评价算法的复杂性，人们只能借助计算机进行处理，而这方面的商品化软件还不够成熟。适用范围        神经网络评价模型具有自适应能力、可容错性，能够处理非线性、非局域性的大型复杂系统。在对学习样本训练中，无需 考虑输入因子之间的权系数，ANN通过输入值与期望值之间的误差比较，沿原连接权自动地进行调节和适应，因此该方法 体现了因子之间的相互作用。
 

改进方法        采用组合评价法：对用其它评价方法得出的结果，选取一部分作为训练样本，一部分作为待测样本进行检验，如此对 神经网络进行训练，知道满足要求为止，可得到更好的效果。

3.TOPSIS综合评价模型

基本思想

        TOPSIS模型是根据评价对象与理想化目标的接近程度进行排序的方法，是一种距离综合评价方法。基本思路是通过假定正、负理想解，测算各样本与正、负理想解的距离，得到其与理想方案的相对贴近度

优点        缺点              需要的每个指标的数据，对应的量化指标选取会有一定难度。不确定指标的选取个数为多少适宜，才能够去很好刻画指标的影响力度。必须有两个以上的研究对象才可以进行使用适用范围        Topsis法被广泛用于企业管理、市场营销、投资决策等领域。主要适用于评价指标相对较多，指标间相互独立。改进方法       在 TOPSIS 当中，默认了各个评价指标所占的权重相同，但在实际的评价过程当中由于各种主观客观因素的影响， 导致每一个评价指标所占的权重是有差异的; 1. 主观权重——层次分析法（AHP)2. 客观权重——熵权法

 二、预测类算法

常见的预测算法

 1.灰色预测模型

基本思想   

        灰色预测是一种对含有不确定因素的系统进行预测的方法。灰色预测通过鉴别系统因素之间发展趋势 的相异程度，即进行关联分析，并对原始数据进行生成处理来寻找系统变动的规律，生成有较强规律 性的数据序列，然后建立相应的微分方程模型，从而预测事物未来发展趋势的状况。其用等时距观测 到的反映预测对象特征的一系列数量值构造灰色预测模型，预测未来某一时刻的特征量，或达到某一 特征量的时间。基本步骤        1）数据检验与处理，判断数据列的级比是否都落在可容覆盖内，从而判断已知该数据列是否可进行灰色预测；2）根据预测算法建立灰色模型得到预测值；3）检验预测值—-残差检验、级比偏差值检验；4）给出预测预报即结论。优点

        在处理较少的特征值数据，不需要数据的样本空间足够大，就能解诀历史数据少、序列的完 整性以及可靠性低的问题，能将无规律的原始数据进行生成得到规律较强的生成序列。缺点        只适用于中短期的预测，只适合近似于指数增长的预测。适用范围

        该模型使用的不是原始数据的序列，而是生成的数据序列。核心体系是Grey Model.即对原 始数据作累加生成(或其他处理生成)得到近似的指数规律再进行建模的方法。改进方法(1)成对比较矩阵可以采用德尔菲法获得。 (2)如果评价指标个数过多（一般超过9个），利用层次分析法所得到的权重就有一定的偏差，继而组合评价模型 的结果就不再可靠。可以根据评价对象的实际情况和特点，利用一定的方法，将各原始指标分层和归类，使得每层各类中的指标数少于9个。 2.回归预测方法

基本思想

        回归预测方法是根据自变量和因变量之间的相关关系进行预测的。自变量的个数可以一个或多个，根据自变量的个数可分为一元回归预测和多元回归预测。同时根据自变量和因变量的相关关系，分为线性回归预测方法和非线性回归方法。回归 问题的学习等价于函数拟合：选择一条函数曲线使其很好的拟合已知数据且能很好的预测未知数据。优点

        1）回归分析法在分析多因素模型时，更加简单和方便; 2）运用回归模型，只要采用的模型和数据相同，通过标准的统计方法可以计算出唯一的结果,但在图和表的形式中,数据之间关系的解释往往因人而异,不同分析者画出的拟合曲线很可能 也是不一样的; 3）回归分析可以准确地计量各个因素之间的相关程度与回归拟合程度的高低，提高预测方程式的效果;缺点       有时候在回归分析中，选用何种因子和该因子采用何种表达式只是一种推测,这影响了因子的多样性和某些因子的不可测性，使得回归分析在某些情况下受到限制;适用范围        回归分析适合自变量和因变量之间具有一定的相关关系，并且该关系可以通过线性和非线性函数进行拟合改进方法(1)采用组合赋权法：根据客观赋权法和主观赋权法综合而得权系数。 (2)结合TOPSIS法：不仅关注序列与正理想序列的关联度，而且关注序列与负理想序列的关联度， 依据公式计算最后的关联度。

3.时间序列分析法

基本思想

        ARIMA模型的全称叫做自回归移动平均模型，全称是(ARIMA, Autoregressive Integrated Moving Average Model)。 也记作ARIMA(p,d,q)，是统计模型(statistic model)中最常见的一种用来进行时间序列 预测的模型。基本步骤          1）导入实验数据。2)确定ARMA模型阶数。3)残差检验。4)给出结果优点                一般用ARMA模型拟合时间序列，预测该时间序列未来值。Daniel检验平稳性。自动回归AR（Auto regressive）和 移动平均MA（Moving Average）预测模型，预测精度相对较高，适合中长期预测问题缺点              当遇到外界发生较大变化，往往会有较大偏差，时间序列预测法对于中短期预测的效果要比长期预测的效果好。 4.微分方程

基本思想   

        微分方程模型是我们在日常生活中比较常见并且比较重要的一种模型，我们在平时的课程中时经常会涉及到这种题型，像比如我们所遇到的牛顿第二定律就常遇到相关的问题。基本步骤        1）确定实际的量（所有要求的自变量、未知函数、必要参数）并确定坐标系。         2）找出这些量所存在的基本关系（物理、化学，生物、几何等关系）。         3）运用这些关系列出方程和定解条件。优点

        
是短、中、长期的预测都适合。如传染病的预测模型、经济增长(或人口)的预测模型、Lanchester战争预测模型。缺点                 反应事物内部规律及其内在关系，但由于方程的建立是以局部规律的独立性假定为基础，当作为长期预测时，误差较大，且微分方程的解比较难以得到适用范围             适用于基于相关原理的因果预测模型，大多是物理或几何方面的典型问题，假设条件，用数学符号表示规律,列出方程，求解的结果就是问题的答案。

 三、优化类算法

1、何谓最优化问题？ 

● 所谓最优化，即从所有可能方案中选择最合理的一种以达到最优目标的学科。在实 际生活当中，人们做任何事情，不管是分析问题，还是进行决策，都要用一种标准 衡量一下是否达到了最优（比如基金人投资）。在各种科学问题、工程问题、生产 管理、社会经济问题中，人们总是希望在有限的资源条件下，用尽可能小的代价， 获得最大的收获（比如保险）。 ● 在数学中，一个优化问题有三个要素：决策变量、目标函数、约束条件。优化问题 是指，在满足约束的情况下，调整决策变量，使得目标函数的值最小（或最大）。● 举个例子，假设你是一名大学生，怎么选择课程才能使期末的GPA最高？在这个问题中，决策变量是选择哪些课，目标函数为期末的GPA，约束条件为各门课 程的上课时间安排、学校的学分要求、每门课的难易程度和自身的学习时间。 ● 正常情况下，我们都会执行贪心的选课策略，在满足上课时间安排的情况下，选择 自己最擅长且学分较高的课程、然后选择自己擅长但学分不高的课程，最后选择剩 下的课程，直到满足学分要求。更多资料请关注公众号【数学建模老哥】课件或代码请公众号回复● 优化问题也分为单目标和多目标，在选课这个例子中，只有GPA一个目标函数，所以 为单目标优化问题，其目标函数即一个多变量单输出函数。用xi作为决策变量表示 是否选择第i门课程，用f(x)表示GPA计算函数。为什么我们会先选择擅长且学分高 的课程呢？因为将这些擅长且学分高的课程对应的决策变量xi设为1会使得 f(x) 有较大的提高，说明这些变量对函数值的影响较大，在数学上讲，这些变量表示了 目标函数的梯度方向。 ● 沿着梯度方向迭代，总能到达一个函数极值点。但是，极值点对应的决策变量不一 定满足约束条件。也许你挑中了所有最擅长的课，结果发现这些课的上课时间是重 叠的。或者你发现只选一门最最擅长的课可以得到最高的GPA，但却达不到学分要求。 这些约束限制着你的选课范围，也就是限制了优化方向，这就增加了优化问题的复 杂性。2、如何建立优化模型● 为了更直接地说明问题，我们先来看几个例子： ● 问题一：某工厂在计划期内要安排生产 I、II 两种产品，已知生产单位产品所需的 设备台时及A、B两种原材料的消耗，如下表所示 ● 该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元。问应如何安排计 划使该工厂获利最多？● 所谓最优化问题是指使得问题中某一项指标“最优”的方案， “最优”包括： “最 大” 、 “最小” 、 “最高” 、 “最低” 、 “最多”和“最少”等。 ● 解决优化问题第一步需要找到目标函数，也就是要找到“最优” ；第二步需要寻找 决策变量，也就是可以优化的变量，再通俗一点就是我们可以控制并使得目标函数 更优的变量；第三步就是确定约束条件，在建模过程中比较难把握的就是约束条件， 约束条件需要全面准确，否则会产生无穷多最优解或没有最优解，另外约束条件往 往是对现实条件的数学刻画，对约束条件的合理简化也是比赛时候需要重点关注的 地方● 在上面这个例子中，显然工厂利用就是目标函数，产品的生产计划就是决策变量， 约束条件为原材料消耗和生产设备的使用时长，因此，其数学模型可表示为：

其中，x1,x2表示产品1和产品2的生产数量。● 进一步，我们可以来总结一下优化问题的一般建模步骤： ● Step1：确定决策变量； ● Step2：用关于决策变量的函数表示目标，并确定是求极小还是极大； ● Step3：明确约束条件，并用关于决策变量的数学语言表示； ● Step4：根据变量的物理性质研究变量是否有非负性。

● 特别说明一下step4，这是建模过程中非常容易遗忘的一个点，像上文例子的第四条约束就反应了决 策变量的非负性，因为我们知道根据物理性质，产品生产个数不能为负，其实这条约束仍然不是很严 谨，产品个数不仅不能为负，同时还应该为整数，第四条约束应该为非负整数约束。3.MATLAB求解优化模型● 简单来说，约束条件和目标函数都是线性的，称之为线性规划，MATLAB求解线性规划的标准 形式表示为：

●线性规划的求解可以通过MATLAB中的linprog函数来进行求解。 ●当然，并不是所有优化模型都是线性规划，对于非线性无约束优化模型，在MATLAB中可以采用fminsearch函数和fminunc函数进行求解。 ●带约束条件的优化问题比无约束条件的优化问题要复杂的多，种类也比较多。对不同类型的优化问题，MATLAB提供了不同的优化方法。其中常用的是fmincon函数。4.优化模型的精确求解算法●在无约束优化模型中，如果其目标函数为凸函数且可导，我们可以考虑通过梯度下降法求解其精确解，随机设定初始解，每次都沿梯度方向进行迭代，直到导数取值足够小。

●因为梯度方向即为目标函数下降最快的方向，因此梯度下降算法求解速度很快，且精度很高，但容易陷入局部最优解，不能求解非凸问题。 ●牛顿迭代法利用了二阶导数信息，迭代速度比梯度下降算法更多，对于强凸函数一次迭代即可找到最优解，但每次迭代需要计算二阶Hesse矩阵，计算量相对较大。

5.
启发式搜索算法

 
●上文介绍了所有求解算法都是面向凸优化的问题，所谓凸优化问题是指目标函数为凸函数且可行域为凸集，通俗讲，就是目标函数在可行域范围内只有一个极值点，而非凸函数在可行域内存在无数个极值点，为了跳出局部最优 解，找到全局最优解，人们开始了对启发式搜索算法的研究。 ●粒子群优化算法（ParticleSwarmOptimization，简称PSO）,它源于对鸟群捕食行为的研究。粒子群优化算法的基本核心是利用群体中的个体对信息的共享，从而使得整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得问题的最优解。