数学建模
date
Sep 8, 2024
slug
mcm
status
Published
tags
ECNU
summary
type
Post
赛题类型
- 预测类
- 评价类
- 机理分析类
- 优化类
线性规划
可以通过加负号将≥变成≤号，将max变成min
整数规划
- 纯整数规划
- 混合整数规划
分支定界算法
割平面法
匈牙利算法
0-1变量
从下述 个约束条件中恰好选择个约束条件
指派问题
非线性规划
如果不考虑风险，求比值，否则求差值
二次规划
若某非线性规划的目标函数为自变量的二次函数，约束条件又全是线性的，就称这种规划为二次规划。
Matlab中二次规划的数学模型可表达如下：
这里是实对称矩阵，，， ， ，是列向量，，是相应维数的矩阵。
层次分析法
TOPSIS
理想解法亦称为TOPSIS法，是一种有效的多指标评价方法。这种方法通过构造评价问题的正理想解和负理想解，即各指标的最优解和最劣解，通过计算每个方案到理想方案的相对贴近度，即靠近正理想解和远离负理想解的程度，来对方案进行排序，从而选出最优方案。
设多属性决策方案集为，衡量方案优劣的属性变量为，这时方案集中的每个方案的个属性值构成的向量是，它作为维空间中的一个点，能唯一地表征方案。
正理想解是一个方案集中并不存在的虚拟的最佳方案，它的每个属性值都是决策矩阵中该属性的最优值；而负理想解则是虚拟的最差方案，它的每个属性值都是决策矩阵中该属性的最差值。在维空间中，将方案集中的各备选方案与正理想解和负理想解的距离进行比较，既靠近正理想解又远离负理想解的方案就是方案集中的最佳方案；并可以据此排定方案集中各备选方案的优先序。
TOPSIS法的具体算法如下
(1) 用向量规划化的方法来求得规范决策矩阵
设多属性决策问题的决策矩阵，规范化决策矩阵，其中
(2) 构成加权规范阵
设由决策人给定各属性的权重向量为，则
(3) 确定正理想解和负理想解
设正理想解的第个属性值为，负理想解第个属性值为，则
正理想解
负理想解
(4) 计算各方案到正理想解与负理想解的距离
备选方案到正理想解的距离为
备选方案到负理想解的距离为
(5) 计算各方案的排序指标值（即综合评价指数）
(6) 按由大到小排列方案的优劣次序。
在进行决策时要对属性值规范化：统一类型、非量纲化、归一化
常用的属性规范化方法有以下几种。
(1) 线性变换
原始的决策矩阵为，转换后的决策矩阵记为。设是决策矩阵第列中的最大值，是决策矩阵第列中的最小值。若为效益型属性，则
采用上述进行属性规范化时，经过转换的最差属性值不一定为 0，最佳属性值为 1。
若为成本型属性，则
采用上述进行属性规范化时，经过转换的最佳属性值不一定为 1，最差属性值为 0。
(2) 标准 0–1 变换
为了使每个属性变换后的最优值为 1 且最差值为 0，可以进行标准 0–1 变换。对效益型属性，令
对成本型属性，令
(3) 区间型属性的变换
有些属性既非效益型又非成本型，如生师比。显然这种属性不能采用前面介绍的两种方法处理。
设给定的最优属性区间为，为无法容忍下限，为无法容忍上限，则
(4) 向量规范化
无论成本型属性还是效益型属性，向量规范化均用下式进行变换
(5) 标准化处理
在实际问题中，不同变量的测量单位往往是不一样的。为了消除变量的量纲效应，使每个变量都具有同等的表现力，数据分析中常对数据进行标准化处理，即
其中
聚类分析
聚类(Clustering)：聚类是一个将数据集划分为若干组（class）或类（cluster）的过程，并使得同一个组内的数据对象具有较高的相似度；而不同组中的数据对象是不相似的。相似或不相似是基于数据描述属性的取值来确定的，通常利用各数据对象间的距离来进行表示。聚类分析尤其适合用来探讨样本间的相互关联关系从而对一个样本结构做一个初步的评价。
聚类是一种无监督的学习方法。与分类不同，其不依赖于事先确定的数据类别，以及标有数据类别的学习训练样本集合。
聚类分析有两种：一种是对样品的分类，称为Q型，另一种是对变量（指标）的分类，称为R型。
样品间的相似度量：距离
一. 常用距离的定义
设有个样品的元观测数据：
这时，每个样品可看成元空间的一个点，每两个点之间的距离记为满足条件：
比较常用的是欧氏距离：
变量间的相似度量：相似系数
当对 p 个指标变量进行聚类时，用相似系数来衡量变量之间的相似程度（关联度），若用表示变量之间的相似系数，则应满足：
相似系数中最常用的是相关系数与夹角余弦。
- 夹角余弦
两变量的夹角余弦定义为:
- 相关系数
两变量的相关系数定义为:
类间距离
设表示两个样品之间的距离，分别表示两个类别，各自含有个样品。
(1) 最短距离
即用两类中样品之间的距离最短者作为两类间距离。
(2) 最长距离
即用两类中样品之间的距离最长者作为两类间距离。
(3) 类平均距离
即用两类中所有两两样品之间距离的平均作为两类间距离。
(4) 重心距离
其中分别是的重心，这是用两类的重心之间的欧氏距离作为两类间的距离。
(5) 离差平方和距离 (ward)
显然，离差平方和距离与重心距离的平方成正比。
谱系聚类法
- 选择样本间距离的定义及类间距离的定义
- 计算n个样本两两之间的距离，得到距离矩阵
- 构造个类，每类只含有一个样本
- 合并符合类间距离定义要求的两类为一个新类
- 计算新类与当前各类的距离。若类的个数为1，则转到步骤6，否则回到步骤4
- 画出聚类图
- 决定类的个数和类。
K-means
- 随机的选择k个对象，每个对象初始的代表了一个簇的平均值
- 对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇
- 重新计算每个簇的平均值
- 这个过程不断重复，直到准则函数收敛
通常选择均方差作为收敛准则函数：
其中为数据库中所有对象的均方差之和；为代表对象的空间中的一个点；为聚类的均值（和均是多维的）。
这个准则试图使得生成的结果尽可能地紧凑和独立：当结果簇是密集的，且簇与簇之间区别明显时，算法的效果较好。
灰色系统理论与灰色关联分析模型
概念
灰色系统、白色系统和黑色系统
白色系统是指一个系统的内部特征是完全已知的，即系统的信息是完全充分的。
黑色系统是指一个系统的内部信息对外界来说是一无所知的，只能通过它与外界的联系来加以观测研究。
灰色系统内的一部分信息是已知的，另一部分信息是未知的，系统内各因素间有不确定的关系。
灰色预测
- 灰色预测法是一种对含有不确定因素的系统进行预测的方法。
- 灰色预测是对既含有已知信息又含有不确定信息的系统进行预测，就是对在一定范围内变化的、与时间有关的灰色过程进行预测。
灰色预测法用等时距观测到的反映预测对象特征的一系列数量值构造灰色预测模型，预测未来某一时刻的特征量，或达到某一特征量的时间。
灰色关联度
一定是小样本
选取参考数列
设参考数列，其中表示时刻。
假设有个比较数列。
则称
注：这里会变的只有
为比较数列对参考数列在时刻的关联系数，其中为分辨系数。一般来说，分辨系数，由 (1) 容易看出，越大，分辨率越大；越小，分辨率越小。
式 (1) 定义的关联系数是描述比较数列与参考数列在某时刻关联程度的一种指标，由于各个时刻都有一个关联系数，因此信息显得过于分散，不便于比较，为此我们给出：
为比较数列对参考数列的关联度。
应指出的是，公式 (1) 中的不能区别因素关联是正关联还是负关联，可采取下面办法解决这个问题。记
则当
则和为正关联；当
则和为负关联
灰色生成数列
累加生成
把数列各项（时刻）数据依次累加的过程称为累加生成过程。由累加生成过程所得到的数列称为累加生成数列。设原始数列为
令
称所得的新数列为数列的1次累加生成数列。类似地有
称为的次累加生成数列。
累减生成
对于原始数据列依次做前后相邻的两个数据相减的运算过程称为累减生成过程IAGO。如果原始数据列为
令
称所得的数列为的1次累减生成数列。
注：从这里的记号也可以看到，从原始数列，得到新数列，再通过累减生成可以还原出原始数列。在实际运用中在数列的基础上预测出，通过累减生成得到预测数列。
加权累加
设原始数列为
称为数列的任意一对邻值。称为后邻值，为前邻值，对于常数，令
由此得到的数列称为数列在权下的邻值生成数，权也称为生成系数。
特别地，当生成系数时，则称
为均值生成数，也称等权邻值生成数。
GM(1,1)
推导过程
设为原始数列，其1次累加生成数列为，其中
定义的灰导数为
令 为数列的邻值生成数列，即
于是定义 GM(1,1) 的灰微分方程模型为
即
在式 (1) 中，称为灰导数，称为发展系数，称为白化背景值，称为灰作用量。
将时刻表代入 (1) 式有
引入矩阵向量记号：
于是 GM(1,1) 模型可表示为。
现在问题归结为求的值。用一元线性回归，即最小二乘法求它们的估计值为
注意: 实际上回归分析中求估计值是用软件计算的，有标准程序求解，如 MATLAB 等。
GM(1,1) 的白化型
对于 GM(1,1) 的灰微分方程 (1)，如果将灰导数的时刻视为连续变量，则视为时间函数，于是对应于导数量级，白化背景值对应于导数。于是 GM(1,1) 的灰微分方程对应的白微分方程为
GM (1, 1) 灰色预测的步骤
- 数据的检验与处理 为了保证 GM (1, 1) 建模方法的可行性，需要对已知数据做必要的检验处理。
设原始数据列为，计算数列的级比
如果所有的级比都落在可容覆盖区间内，则数据列可以建立 GM (1, 1) 模型且可以进行灰色预测。否则对数据做适当的变换处理，如平移变换：
取 C 使得数据列的级比都落在可容覆盖区内。
- 建立 GM (1, 1) 模型
不妨设满足上面的要求，以它为数据列建立 GM (1, 1) 模型
用回归分析求得 a, b 的估计值，于是相应的白化模型为
解为
于是得到预测值
从而相应地得到预测值：
- 检验预测值
(1) 残差检验：计算相对残差
如果对所有的，则认为达到较高的要求；否则，若对所有的，则认为达到一般要求。
(2) 级比偏差值检验：计算
如果对所有的，则认为达到较高的要求；否则，若对所有的，则认为达到一般要求。
数据预处理
噪声数据：数据中存在着错误或异常，例如身高为0
对国赛来说不会占太多
- 数据清洗：去掉噪声，纠正不一致
- 数据集成：将多个数据源合并成一致的数据存储，构成一个完整的数据集
- 数据归约：通过聚集、删除冗余属性或聚类等方法来压缩数据
- 数据变换：例如简单的函数变换、归一化（将数据压缩到一个特定的区域内）
- 缺失值处理：删除记录、数据插补（均值/中位数/众数、固定值、最近临插补、回归、插值法（拉格朗日、牛顿））、不处理
- 异常值处理：删除、视为缺失值、平均值修正、不处理
异常值处理法一
异常值处理法二
计算维数据集中所有样本间的测量距离，如果样本中至少有一部分数量为的样本到的距离比大，那么样本是数据集中的一个噪声数据。
例子：
所以S1、S4、S6为噪声数据。
特征工程
特征工程的处理流程为首先去掉无用特征，接着去除冗余的特征，如共线特征，并利用存在的特征、转换特征、内容中的特征以及其他数据源生成新特征，然后对特征进行转换（数值化、类别转换、归一化等)，最后对特征进行处理（异常值、最大值、最小值，缺失值等)，以符合模型的使用。简单来说，特征工程的处理一般包括数据预处理、特征处理、特征选择等工作，而特征选择视情况而定，如果特征数量较多，则可以进行特征选择等操作。
国赛中不会遇到嵌入法，几乎不会用包装法，考虑过滤法就行
上图中删去x2或者x3几乎没有任何损失
主成分分析：
对降维之后的主成分需要进行解释，每个主成分反映了什么
例子如下
插值与拟合
插值
上述问题可归结为“已知函数在某区间(域)内若干点处的值，求函数在该区间(域)内其它点处的值”，这种问题适宜用插值方法解决。
一维插值问题可描述为：已知函数在处的值，求简单函数，使。
通常取为多项式。
拉格朗日插值法
对于给定的个点：，拉格朗日插值法的思路是找到一个在一点取值为1，而在其他点取值都是0的多项式。这样，多项式在点取值为，而在其他点取值都是0。而多项式就可以满足
在其它点取值为0的多项式容易找到，例如：
它在点取值为：。由于已经假定两两互不相同，因此上面的取值不等于0。于是，将多项式除以这个取值，就得到一个满足“在取值为1，而在其他点取值都是0的多项式”：
这就是拉格朗日基本多项式。
在研究插值问题的初期，所有人都想当然地认为插值多项式的次数越高，插值精度越高。 Runge 通过对一个例子的研究发现，上述结论仅仅在插值多项式的次数不超过七时成立；插值多项式的次数超过七时，插值多项式会出现严重的振荡现象，称之为Runge现象。
因此，在实际中不应使用七次以上的插值。 避免Runge现象的常用方法是：将插值区间分成若干小区间，在小区间内用低次(二次，三次)插值，即分段低次插值，如样条函数插值。
拟合
用插值函数外推插值区间外的数据会产生较大误差，即Runge现象，此时需要用拟合。
拟合问题与插值问题的区别在于：
(1) 插值函数过已知点，而拟合函数不一定过已知点；
(2) 插值主要用于求函数值，而拟合的主要目的是求函数关系，从而进行预测等进一步的分析。当然，某些特定问题既可以用插值也可以用拟合。
曲线拟合需解决如下两个问题：(1) 线型的选择；(2) 线型中参数的计算。线型的选择是拟合计算的关键和难点。通常主要根据专业知识和散点图确定线型。线性拟合中参数的计算可采用最小二乘法，而非线性拟合参数的计算则要应用Gauss-Newton迭代法。
Matlab中可以使用拟合工具箱（cftool）
主成分分析
研究如何通过少数几个主成分(principal component)来解释多个变量间的内部结构。即从原始变量中导出少数几个主分量，使它们尽可能多地保留原始变量的信息，且彼此间互不相关。
主成分分析的目的：数据的压缩；数据的解释
常被用来寻找判断事物或现象的综合指标，并对综合指标所包含的信息进行适当的解释
基本思想
主成分分析就是设法将原来众多具有一定相关性的变量(如p个变量)，重新组合成一组新的相互无关的综合变量来代替原来变量。通常数学上的处理就是将原来p个变量作线性组合作为新的综合变量。将选取的第一个线性组合即第一个综合变量记为F1，希望F1尽可能多的反映原来变量的信息。最经典的方法就是用方差来表达，即var(F1)越大，表示F1包含的信息越多。因此在所有的线性组合中所选取的F1应该是方差最大的，故称之为第一主成分（principal component I）。
如果第一主成分不足以代表原来p个变量的信息，再考虑选取F2即第二个线性组合。F2称为第二主成分（principal component II）。 为了有效地反映原来信息，F1已有的信息就不再出现在F2中，即cov（F1,F2)＝0。依此类推，可以获得p个主成分。因此，这些主成分之间是互不相关的，而且方差依次递减。在实际中，挑选前几个最大主成分来表征。各主成分的累积方差贡献率>80%或特征根>1。
数学模型
要从原来的所有变量得到新的综合变量，一种较为简单的方法是作线性变换，使新的综合变量为原变量的线性组合。
在进行主成分分析之前需要先进行检验：KMO >0.5 or Bartlett <0.05
通过推导可知，的主成分就是以协方差阵的特征向量为系数的线性组合，它们互不相关，其方差为的特征根。
解决实际问题时，一般不是取全部p个主成分，而是取前k个。
方法之一是取特征根大于1的主成分
方法之二是根据累计贡献率来取主成分
称为第一主成分的贡献率
因此第一主成分的贡献率越大，表明其综合信息的能力就越强。
称为前k个主成分的累计贡献率
如果前k个主成分的累计贡献率达到85％，则表明取前k个主成分基本包含了全部测量指标所具有的信息，从而达到了变量降维的目的。
SPSS例子：
模糊数学及模糊综合评价
现实中的许多现象及关系比较模糊。如高与矮，长与短，大与小，多与少，穷与富，好与差，年轻与年老等。 这类现象不满足“非此即彼”的排中律，而具有“亦此亦彼”的模糊性。
模糊集
模糊集运算
隶属函数
模糊综合评价
评价是人类社会中经常性的、极为重要的认识活动。对一个事物的评价通常要涉及多个因素或多个指标，评价是在多因素相互作用下的一种综合评判。
例子：
其中为的权重，
变异系数法
变异系数法的设计原理是：若某项指标的数值差异较大，能明确区分开各被评价对象，说明该指标的分辨信息丰富，因而应给该指标以较大的权重；反之，若各个被评价对象在某项指标上的数值差异较小，那么这项指标区分各评价对象的能力较弱，因而应给该指标较小的权重。
将指标的分辨能力定义为：
需要指出的是，用变异系数法求出的某指标的权重与该指标在评价体系中的重要性是两个概念。变异系数法的作用只是提高指标的分辨能力，利于排序。
使用变异系数法的前提恰恰是所有指标在评价体系中的重要性相当。
模糊合成
对评价矩阵R和权向量A进行某种适当的模糊运算,将两者合成为一个模糊向量
四种算子
把B称为模糊综合评价向量。分析处理B有两种常用方法：最大隶属度法和加权平均法
相对偏差模糊矩阵评价法
相对偏差模糊矩阵评价法与灰色关联分析有点类似。首先虚拟一个理想方案u，然后按照某种方法建立各方案与u的偏差矩阵R，再确定各评价指标的权重A，最后用A对R加权平均得各方案与u的综合距离F, 则根据F即可对方案进行排序。
Step1 虚拟理想方案
Step2 建立相对偏差模糊矩阵R（n个方案，m个指标）
Step3 确定各评价指标权重（变异系数法）
Step4 对各方案的偏差加权平均
根据值进行综合评价，若，则第个方案排在第个方案之前。
相对优属度模糊矩阵评价法
相对偏差法的评价依据是各方案与理想方案的偏差，而相对优属度评价法的基本思想是：首先用适当的方法将所有指标(效益型、成本型、固定型)转化为效益型(成本型)，得到优属度矩阵R，再确定各评价指标的权重A,最后用A对R加权平均得各方案的综合优属度F, 则根据F即可对方案进行排序。
Step1 建立模糊效益矩阵
Step2 确定各评价指标权重
Step3 对各方案的优属度加权平均
Step4 根据值进行综合评价，若，则第个方案排在第个方案之前。
相关性分析
定类变量：根据定性的原则区分总体各个案类别的变量
案例：性别，民族、婚姻状况
定序变量：区别同一类别个案中等级次序的变量
案例：文化程度、工厂规模、年龄大小
定距变量：区别同一类别个案中等级次序及其距离的变量（可以量化差距）
案例：摄氏温度、比率、智力水平
定比变量：也是区别同一类别个案中等级次序及其距离的变量（有零点）
案例：收入、价格、市场占有率
两变量相关性
Pearson相关系数：适用于定距、定比类型的变量。是运用最广的一种相关程度统计量。检验用t统计量：其中统计量t服从自由度(n-2)的分布。
适用条件
1、两变量均应由测量得到的连续变量。
2、两变量所来自的总体都应是正态分布，或接近正态的单峰对称分布。
3、变量必须是成对的数据。
4、两变量间为线性关系。
Spearman 等级相关系数：适用于度量定序变量与定序变量之间的相关。
- 只要有一个定距就可以用Pearson
- Eta对定序和定序偏差比较大
- 若Eta>Pearson，说明是非线性关系
偏相关
偏相关分析是指在对其他变量的影响进行控制的条件下，分析多个变量中某两个变量之间的线性相关程度，计算偏相关系数。
假定有这3个变量，要求计算剔除变量的影响后变量之间的偏相关系数，记为。其中为可控变量。
偏相关系数的显著性检验公式为：
BP神经网络
- 神经元模型
- 激活函数
- 网络结构
- 工作状态
- 学习方式
神经元模型和激活函数
多输入单输出非线性系统
激活函数是对净激活量与输出进行映射的函数。一些常用的激活函数,由于输入数据与期望值之间可能并不是量级一样，所以需要激活。
S形和双极S形函数的导函数均为连续函数。
网络模型
根据网络中神经元的互联方式的不同，网络模型分为：
前馈神经网络
只在训练过程会有反馈信号，而在分类过程中数据只能向前传送，直到到达输出层，层间没有向后的反馈信号
反馈神经网络
从输出到输入具有反馈连接的神经网络，其结构比前馈网络要复杂得多
自组织网络
通过自动寻找样本中的内在规律和本质属性，自组织、自适应地改变网络参数与结构。
学习：利用学习算法来调整神经元间的连接权重
监督学习
无监督学习
BP神经网络
用BP学习算法的前馈神经网络称为BP神经网络
利用输出后的误差来估计输出层的直接前导层的误差，再用这个误差估计更前一层的误差，如此一层一层的反传下去，就获得了所有其他各层的误差估计
先正向传播，判断是否转入反向传播阶段：若输出层的实际输出与期望的输出不符则进行误差反传：误差以某种形式在各层表示。修正各层单元的值，网络输出的误差减少到可接受的程度进行到预先设定的学习次数为止
假设输入层有个神经元，隐含层有个神经元，输出层有个神经元
符号定义
输入向量：
隐含层输入向量：
隐含层输出向量：
输出层输入向量：
输出层输出向量：
期望输出向量：
误差函数：
首先，计算各层神经元的输入和输出
第二步利用网络期望输出和实际输出，计算误差函数对输出层的各神经元的偏导数
第三步：利用隐含层到输出层的连接权值、输出层的和隐含层的输出计算误差函数对隐含层各神经元的偏导数
第四步，利用输出层各神经元的和隐含层各神经元的输出来修正连接权值
第五步，利用隐含层各神经元的和输入层各神经元的输入修正连接权
第六步，计算全局误差
第七步，判断网络误差是否满足要求。当误差达到预设精度或学习次数大于设定的最大次数，则结束算法。否则，选取下一个学习样本及对应的期望输出，返回进入下一轮学习
Matlab
参考：
元胞自动机
元胞自动机（Cellular Automata，CA）是一种时空离散的局部动力学模型，是研究复杂系统的一种典型方法，特别适合用于空间复杂系统的时空动态模拟研究。
元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总称，或者说是一个方法框架。
在CA模型中，散布在规则格网 (Lattice Grid)中的每一元胞(Cell)取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。
CA模型的特点：时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。
组成
元胞、元胞空间、邻居及规则
- 元胞：元胞自动机的最基本组成部分。它分布在离散的一维、二维或多维欧几里德空间的晶格点上。
- 状态：状态可以是{0,1}的二进制形式，或是{s0,s1,s2,…，si}整数形式的离散集。严格意义上，元胞只能有一个状态变量，但在实际应用中，往往将其进行扩展。
- 元胞空间：元胞所分布在的空间网点集合就是元胞空间
- 元胞空间的几何划分：任意维数的欧几里德空间规则划分。对于一维元胞自动机，元胞空间划分只有一种。而高维的元胞自动机，元胞空间的划分则可能有多种形式。对于常见的二维自动机，元胞空间通常可按三角形、四边形或六边形三种网格排列。
- 边界条件：理论上，元胞空间在各个维向上是无限延展的。实际应用过程中，无法在计算机上实现这一理想条件。
- 构形：在某个时刻，在元胞空间上所有元胞状态的空间分布组合。在数学上，它通常可以表示为一个多维的整数矩阵。
- 邻居：一维元胞自动机中，通常以半径r来确定邻居，距离一个元胞r内的所有元胞都属于该元胞的邻居。二维元胞自动机的邻居定义较为复杂，但通常有以下几种（以正方形网格为例 ）
- 状态转移函数：根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数
自底向上的研究方法
初等元胞自动机
初等元胞自动机是状态集S只有两个元素{s1，s2}，即状态个数k=2，邻居半径r=1的一维元胞自动机。由于在S中具体采用什么符号并不重要，它可取 {0，1}，{-1，1}，{静止，运动} 等等，重要的是S所含的符号个数，通常我们将其记为 {0，1}。此时，邻居集N的个数2·r=2，局部映射f：S3→S可记为:
二维元胞自动机
生命游戏
构成及规则：
(1)元胞分布在规则划分的网格上；
(2)元胞具有0，1两种状态，0代表“死”，1代表“生”；
(3)元胞以相邻的8个元胞为邻居。即Moore邻居形式；
(4)一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态 (确切讲是状态的和)决定：在当前时刻，如果一个元胞状态为“生”，且八个相邻元胞中有两个或三个的状态为“生”，则在下一时刻该元胞继续保持为“生”，否则“死”去；在当前时刻，如果一个元胞状态为“死”，且八个相邻元胞中正好有三个为“生”，则该元胞在下一时刻 "复活"。否则保持为"死"。
演化行为的统计特征
平稳型（homogeneous）：自任何初始状态开始，经过一定时间演化后，经过若干步运算便停留在一个固定的状态。
周期型(periodic)：经过一定时间演化后，在几种状态之间周期循环。
混沌型(chaos)：自任何初始状态开始，经过一定时间演化后，处于一种完全无序随机的状态，几乎找不到任何规律。
复杂型(edge of chaos)：在演化的过程中可能产生复杂的结构，这种结构既不是完全的随机混乱，又没有固定的周期和状态。
马尔科夫预测
随机过程
设是一族随机变量，T是一个实数集合，若对任意实数，是一个随机变量，则称随机过程。
T为参数集合，参数t可以看作时间。的每一个可能取值所构成的集合称为状态空间，记为E。当参数T为非负整数集时，随机过程又称为随机序列。我们要介绍的马尔可夫（Markov）链就是一类特殊的随机序列。
例如投篮命中率事50%，这次不中不代表下次就会中，下次命中率还是50%。
在随机过程中有很多这样的现象：某一系统在已知现在的情况下，系统未来时刻的情况只与现在有关，而与过去的历史无直接关系。
马尔科夫链
设是一个随机序列，状态空间为有限或可列集，对于任意的正整数，若，有
则称为一个马尔可夫链（马氏链）。
设是一个马氏链，如果等式（1）右边的条件概率与n无关，即
则称为时齐的马氏链。
称为系统由状态经过个时间间隔（或步）转移到状态的概率。
（2）式称为时齐性。它的含义是：系统由状态到状态的转移概率只依赖与时间间隔的长短，与起始的时刻无关。
转移概率矩阵
对于一个马尔可夫链，称以步转移概率为元素的矩阵为马尔可夫链的步转移矩阵。
当时，记为马氏链的一步转移矩阵，或简称转移矩阵。它们具有三个基本性质：
- 对一切，;
- 对一切，;
- 对一切，
设是转移矩阵（概率向量为行向量），是初始的概率分布。则第n步的概率分布为
若是正则的，转移概率存在与无关的极限，则称此马尔可夫链具有遍历性。在此基础上，若，则称为马尔可夫链的极限分布，同时它也是的唯一解
两个重要类型
正则链：从任一状态出发经有限次转移能以正概率到达另外任一状态
w为稳态概率
吸收链：存在吸收状态（一旦到达就不会离开的状态i, ）,且从任一非吸收状态出发经有限次转移能以正概率到达吸收状态
写作
作品组成
竞赛论文电子版：摘要页、正文、参考文献、附录
支撑材料：源程序代码及调用说明、中间结果、支撑数据等
论文基本构成
首页：论文题目、摘要、关键词
论文正文:
1.问题重述
2 问题分析
3 模型假设
4 符号说明
5 模型建立与求解
6.模型检验/模型改进与推广
7.模型优缺点评价
参考文献
附录
论文格式
论文题目---黑体3号，居中
摘要标题---黑体4号，居中
摘要内容---宋体，小4号
关键词:---黑体小4号
正文一级标题：黑体4号，居中
正文二三级标题：黑体小4号，居左
正文：宋体，小四号
数字、字母等：Times NewRoman
页边距：上下左右各2.5厘米
论文页数：正文尽量20页以内
行距：灵活调整
首页：论文题目、摘要、关键词
论文题目
应尽量涵盖论文研究的主要对象或研究内容，所采用的主要研究方法
要求:简短、精炼，一目了然; 一般独自占一行，居中排版
常见方式：
第一种：基于XXX模型/方法/理论的XXX问题研究（普遍选择）
第二种：直接对问题进行简化作为题目（大神选择（模型复杂，无法简化在题目中））
关键词
一般为3-5个，尽可能涵盖，主要包括五部分内容
- 研究对象或研究内容
- 研究目的
- 主要模型
- 求解算法
- 验证方法
不要写模糊综合、层次分析和灰色预测
摘要内容
摘要是现代科技论文的一个导读部分。摘要应具有独立性和代表性，即拥有与文献同等量的主要信息，即不阅读全文，就能获得必要的信息，它是解决读者在短时间内了解论文内容和方法的有效手段。主要包括
- 背景和问题:应简要叙述研究的对象和研究内容、研究目的;
- 问题分析:依据题目给出的数据或自行收集了哪些数据或信息;
- 关键假设:对所研究的问题、数据做了哪些机理分析或数据观察,据此做出了什么样的关键假设;
- 模型结构:采用了何种建模方法，建立了何种数学模型;
- 求解算法:对模型采用了什么样的方法、算法或软件求解;
- 结果、检验、结论:主要结果或结论是什么，或对假设、模型或结果做了何种验证或假设检验等
第一部分摘要前言
主要起到总结概括的作用，在撰写时主要包括三部分：研究问题的背景或意义，主要的研究思路或方法，取得的成果或解决的主要问题等一般2—3句话即可，以上三个模块可全部包括也可包括其中两项
第二部分摘要正文
该部分主要是简述各问题的建模过程及结果分析对于问题较多的情况，在描述时（题目大于2道）：针对问题一
针对问题二
针对问题三
对于问题较少的情况（题目小于2道），直接采用连词：首先，然后，最后
该部分为摘要的关键部分，对于每个问题主要包括四部分内容，分别是：简述问题；建模思路；模型求解和结果分析
简述问题
第一直接归纳：如针对第一问，主要分析相关拍照赚钱任务未完成的原因；针对问题一，主要给出团队的最佳协作策略及对应的颠球高度
第二种将其分类：如针对问题一，这是一道典型的动态规划赛题；针对问题二，可以将其定性为评价类问题；
建模思路
建模思路一般没有固定的模式，该部分主要包括对问题的分析或数据的获取与处理、采用了什么数学方法或进行了哪些分析，建立了什么样的数学模型等；例如
针对任务一中情况 1，本题仅需考虑一个班次中单工序加工的单RGV 动态调度模型。本文以RGV 的调度路径为决策变量，以获得最多成料为目标函数，约束条件为每次调度单RGV仅能对一台 CNC 进行作业、每班次 RGV 工作时长不超过 8 小时、RGV 下轮作业移动起点为上轮作业终点、每台 CNC 每次作业仅能加工一个物料，根据 0-1 规划的思想建立单目标规划模型，最终得到 CNC 无故障下加工单工序物料的所获成料最多模型。
模型求解
指的是采用了基于XXX数据，采用了什么方法/软件/平台等对模型进行求解
结果分析
主要是利用模型计算结果回答题目给出的问题。其中根据问题的不同又分为计算性问题和开放性问题
计算型问题指的是需要对某个参数进行准确的计算，一般适用于物理数学类赛题，结果的正确性往往能直接影响到论文的质量，在作答时需给出题目中要求我们计算的所有量，注意字体加深并注明单位
指的是题目让我们给出影响、后果、策略、评价等类型的赛题，这类问题在进行结果分析时，应尽可能将关键性的结果或结论进行简述，有数值支撑最好，实在无法简述则阐明该问题得到了解决即可，例如
运用灰色关联矩阵定量分析四个影响因子与定价的相关度，分别为0.9710,0.9671,0.9633,0.9390。得出所定义的指标对定价相关性很高，能较好描述定价规律。最后通过比较未完成任务与已完成任务的相关度矩阵得出距离对任务的完成的影响是最显著的。
第三部分摘要结尾
该部分主要是对整个建模过程的总结和升华，常见的是进行优缺点评价、模型的创新性评价、模型的推广等
最后我们对模型的鲁棒性和灵敏度进行了检验，发现模型具有较好的鲁棒性。同时我们也对模型的优缺点进行了评价。
论文正文部分撰写
问题重述
（看得很少）
千万不能直接照抄原题，避免查重扣分
在撰写中一般包括两部分内容，其一是背景描述；其二是问题阐述
问题重述的关键是：改写
数值计算类可以直接改写（需要将关键的参数或条件进行描述），开放类需要扩充或者简化
问题分析
每一问单独一段，不需要结论、结果，只需要对问题进行解题思路的简单描述，可以用流程图，不需要具体说明建立什么模型（例如灰色预测），只需要说建立什么类型的模型（例如小样本预测），不需要说明用什么方法求解，但需要指出需要哪些参数，有哪些参数
模型假设
要以严格、确切的数学语言来表达
是建立模型所必需的
假设应验证其合理性（常识、文献……）
①对题目中已知条件或参数做出保真性假设（题目中给出的数据准确）
② 仅考虑题目中涉及的主要条件，对其他情况不考虑或进行强制规定（不考虑无关条件）
③ 对题目中涉及的主要条件进行平稳性规定（未来不会变）
④ 为使研究更简便、或从常识性角度做出的假设
⑤ 对模型中相关参数做出规定
符号说明
是对建模过程中涉及到的主要变量提前在论文中进行描述，以方便评审老师阅读论文
一般符号说明是以三线表的形式给出，主要包括：符号、含义和单位
只需要写主要的全局变量即可，对于临时变量不需要写
用希腊字幕，尽量不要用中文字符或英文字母
即使在符号说明里对有关符号进行了解释，但在下文首次提到时仍需要再次解释
模型建立与求解
如果模型较为复杂，可以用流程图说明关键步骤
评价类赛题
建立评价体系
对指标规范化处理
确定指标体系对应权重系数
选择或构造综合评价模型
计算评价值给出结果
预测类
数据预处理
选择模型
误差分析
预测结果
对原模型改进
用伪代码或者流程图进行改进
常见赛题种类及结果展现形式：
① 数学物理类等需要计算具体参数或结果的赛题
求解结果：务必根据赛题要求给出具体的结果，注意单位
② 对于评价或预测等类型的赛题
求解结果：往往需要结合图表进行表现，注意图表格式和简单美化
③ 对于需要解释原因、给出意见或建议等开放类赛题
求解结果：能够结合模拟结果进行分条撰写，文笔简练、有理有据
模型检验
敏感性和稳定性
统计检验和误差分析
模型优缺点评价
常见的优点表述形式
① 模型或思路设计的简洁实用，效率高
② 本文建立的模型具有很强的创新性
③ 模型的计算结果准确，精度高
④ 模型考虑的系统全面，有很强的实用性
⑤ 对模型进行了各类检验、稳定性高
⑥ 模型本身具有的优点
常见的缺点表述形式
① 受XX因素限制，未考虑XX情况，影响精度
② 本文考虑的因素较为理想，降低了模型的普适性和推广能力
③ 由于系统考虑了XXX等因素，导致模型较为复杂，计算时间长，效率低
④ 模型本身具有的缺点
参考文献
注意格式