数学建模方法综述 PPT课件

1、数学建模方法综述,西南交通大学峨眉校区数学建模暑期培训 2014.8.21,2,确定葡萄酒质量时一般是通过聘请一批有资质的评酒员进行品评。每个评酒员在对葡萄酒进行品尝后对其分类指标打分，然后求和得到其总分，从而确定葡萄酒的质量。酿酒葡萄的好坏与所酿葡萄酒的质量有直接的关系，葡萄酒和酿酒葡萄检测的理化指标会在一定程度上反映葡萄酒和葡萄的质量。附件1给出了某一年份一些葡萄酒的评价结果，附件2和附件3分别给出了该年份这些葡萄酒的和酿酒葡萄的成分数据。请尝试建立数学模型讨论下列问题： 1. 分析附件1中两组评酒员的评价结果有无显著性差异，哪一组结果更可信？ 2. 根据酿酒葡萄的理化指标和葡萄酒的质量对

2、这些酿酒葡萄进行分级。 3. 分析酿酒葡萄与葡萄酒的理化指标之间的联系。 4分析酿酒葡萄和葡萄酒的理化指标对葡萄酒质量的影响，并论证能否用葡萄和葡萄酒的理化指标来评价葡萄酒的质量？ 附件1：葡萄酒品尝评分表（含4个表格） 附件2：葡萄和葡萄酒的理化指标（含2个表格） 附件3：葡萄和葡萄酒的芳香物质（含4个表格）,引例-1 2012年A题（葡萄酒的评价）,3,破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动

3、拼接技术，以提高拼接复原效率。请讨论以下问题： 1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。 2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 3.,引例-2 2013年B题(碎纸片的拼接复原

4、),4,数学建模常用方法介绍,1. 数学规划及其延伸内容,2. 插值,拟合,偏最小二乘法,3. 描述性统计与多元统计分析,4. 数据建模的综合评价方法,. 数据建模的预测方法,. 现代优化算法,5,例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000 元与3000 元。生产甲机床需用 A、B机器加工，加工时间分别为每台 2 小时和 1 小时；生产乙机床需用 A、B、C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A 机器10 小时、B 机器8 小时和C 机器7 小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？,1线性规划,一、数学规划,设该厂生产x台甲

5、机床和x乙机床时总利润最大,注：单纯形法，灵敏性分析（影子价格）,6,2整数规划,一、数学规划,求解方法：（1）分支定界法可求纯或混合整数线性规划； （2）割平面法可求纯或混合整数线性规划； （3）隐枚举法求解0-1整数规划； （4）匈牙利法求解0-1整数规划； （5）蒙特卡洛法求解各种类型规划。,30-1规划（指派问题）,7,4非线性规划（参考资料-1）,一、数学规划,求解方法：（1）罚函数法（外点法） ； （2）罚函数法（内点法或障碍函数法） ； （3）直接法（解析法） ； （4）间接法（如：最速下降法）； （5）蒙特卡洛法求解各种类型规划。,8,5动态规划（参考资料-2）,一、数学规划-

6、延伸知识,例2 生产计划问题 设某工厂有 1000 台机器，生产两种产品 A、B，若投入x台机器生产A产品，则纯收入为5x，若投入y台机器生产B种产品，则纯收入为4y，又知：生产A种产品机器的年折损率为20%，生产B产品机器的年折损率为10%，问在5 年内如何安排各年度的生产计划，才能使总收入最高？,优点：（1）能够得到全局最优解； （2）可以得到一族最优解； 缺点：（3）没有统一的标准模型； （4）维数灾变量过多取值过宽求解困难。,9,6目标规划,一、数学规划-延伸知识,求解方法： （1）加权系数法为每一个目标赋一个权系数； （2）优先等级法序贯算法。,10,7图与网络（参考资料-3）,一、

7、数学规划-延伸知识,7.1 最短路问题 现有A、B1、B2、C1、C2、C3、D共7个城市，点与点之间的连线表示城市间有道路相连。连线旁的数字表示道路的长度。求城市A到城市D的一条最短路。,求解算法： （1）Dijkstra算法 （2）Floyd算法 注：参考资料-4,11,7图与网络,一、数学规划-延伸知识,7.2 最小生成树 欲修建连接n个城市的铁路，已知i城与j城之间的铁路造价为cij设计一个线路图，使总造价最低？,求解算法： （1）prim算法 （2）Kruskal算法 注：参考资料-4,12,7图与网络,一、数学规划-延伸知识,7.3 网络最大流问题 现需要将城市s的石油通过管道运送

8、到城市t，中间有4个中转站，城市与中转站的连接以及管道的容量如图所示，求从城市s到城市t的最大流。,求解算法：标号法 注：参考资料-4,数学模型：,13,7图与网络,一、数学规划-延伸知识,7.4 最小费用最大流问题 对前面的问题考虑带有运费的网络，其中第1个数字是网络的容量，第2个数字是网络的单位运费。,注： 表示用线性规划模型求得的最大流的流量。 参考资料-4,数学模型：,14,7图与网络,一、数学规划-延伸知识,7.5 旅行商（TSP）问题 一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？,7.6

9、计划评审方法和关键路线法（统筹方法）,数学模型的一般形式：,15,8排队论（参考资料-5）,一、数学规划-延伸知识,例3 某维修中心在周末现只安排一名员工为顾客提供服务。新来的顾客到达后，若已有顾客正在服务，则需要排队等待，若排队的人数过多，势必会造成顾客抱怨，会影响到公司效益；若维修人员多，会增加维修中心的支出，如何调整两者的关系，使得系统到达最优。,分类： （1）等待制排队模型，如：M/M/S/ （2）损失制排队模型，如：M/M/S/S （3）混合制排队模型，如：M/M/S/K （4）闭合式排队模型，如：M/M/S/K/K,16,9对策论和存储论（参考资料-6,7）,一、数学规划-延伸知识

10、,例4（囚徒的困境）,例5 某商品单位成本为5 元，每天保管费为成本的0.1%，每次定购费为10 元。已知对该商品的需求是100 件/天，不允许缺货（允许缺货）。假设该商品的进货可以随时实现。问应怎样组织进货，才能最经济。,17,插值：求过已知有限个数据点的近似函数。,1插值,二、插值，拟合，偏最小二乘回归,拟合：已知有限个数据点，求近似函数，不要求过已知数据点，只要求在某种意义下它在这些点上的总偏差最小。,18,一维插值：,二、插值，拟合，偏最小二乘回归,拉格朗日插值，牛顿插值， Hermite插值， 分段线性插值，三次样条插值,19,二维插值：Shepard方法、反距离平均法、线性插值三角

11、网格法、Kriging方法 插值节点为网络节点interp2 插值节点为散乱节点griddata,二、插值，拟合，偏最小二乘回归,20,拟合：多项式拟合，非线性拟合 原则：一般是最小二乘法，活用cftool命定,2拟合,二、插值，拟合，偏最小二乘回归,21,传统的回归方法，一般是输入量多个，输出量一个；如果输入和输出量都是多个的情况，我们可以用偏最小二乘回归分析。,3偏最小二乘回归,二、插值，拟合，偏最小二乘回归,22,三、描述性统计与多元统计分析,数理统计研究的对象是受随机因素影响的数据，多元分析是多变量的统计分析方法，是数理统计中应用广泛的一个重要分支。,描述性统计就是搜集、整理、加工和分

12、析统计数据，使之系统化、条理化，以显示出数据资料的趋势、特征和数量关系。,算数平均数（简称均值）描述数据取值的平均位置 中位数将数据由小到大排序后位于中间位置的那个数值 标准差各个数据与均值偏离程度的度量，这种偏离不妨称为变异 方差标准差的平方 极差最大值与最小值之差 偏度和峰度分布形状的统计量,1. 统计量,23,三、描述性统计与多元统计分析,2.1.1 方差已知，关于均值的检验（Z检验）,2. 假设检验(参考资料-8),2.1 单个总体 均值 的检验,例如：某车间用一台包装机包装糖果。包得的袋装糖重是一个随机变量，它服从正态分布。当机器正常时，其均值为0.5 公斤，标准差为0.015 公斤

13、。某日开工后为检验包装机是否正常，随机地抽取它所包装的糖9 袋，称得净重为（公斤）：0.497 0.506 0.518 0.524 0.498 0.511 0.520 0.515 0.512问机器是否正常？,24,三、描述性统计与多元统计分析,2. 假设检验,2.2 两个正态总体均值差的检验（t 检验）,2.1.2 方差未知，关于均值的检验（t检验）,例如：某种电子元件的寿命x (以小时计)服从正态分布,均值，方差均未知.现得 16 只元件的寿命如下: 159 280 101 212 224 379 179 264 222 362 168 250 149 260 485 170 问是否有理由认

14、为元件的平均寿命大于225(小时)?,例如： 在平炉上进行一项试验以确定改变操作方法的建议是否会增加钢的得率,试验是在同一平炉上进行的。每炼一炉钢时除操作方法外,其它条件都可能做到相同。先用标准方法炼一炉,然后用建议的新方法炼一炉,以后交换进行,各炼了10 炉,其得率分别为 1标准方法 78.1 72.4 76.2 74.3 77.4 78.4 76.0 75.6 76.7 77.3 2新方法 79.1 81.0 77.3 79.1 80.0 79.1 79.1 77.3 80.2 82.1 设这两个样本相互独立且分别来自正态总体 均未知， 问建议的新方法能否提高得率?(取 = 0.05),注

15、：方差不相等的假设检验也可以做,25,三、描述性统计与多元统计分析,2.3 分布拟合检验(参考资料-9),26,三、描述性统计与多元统计分析,2.4 非参数检验,参数检验是在总体分布形式已知的情况下，对总体分布的参数如均值、方差等进行推断的方法。但是，在数据分析过程中，由于种种原因，人们往往无法对总体分布形态作简单假定，此时参数检验的方法就不再适用了。非参数检验正是一类基于这种考虑，在总体方差未知或知道甚少的情况下，利用样本数据对总体分布形态等进行推断的方法。由于非参数检验方法在推断过程中不涉及有关总体分布的参数，因而得名为“非参数”检验。,两独立样本的非参数检验: (1)曼-惠特尼U检验 (

16、2)K-S检验 (3)游程检验 (4)极端反应检验 多独立样本的非参数检验: (1)中位数检验 (2)Kruskal-Wallis检验 (3)Jonckheere-Terpstra检验,两配对样本的非参数检验: (1)McNemar检验 (2)符号检验 (3)Wilcoxon符号秩检验 多配对样本的非参数检验: (1)Friedman检验 (2)Cochran Q检验 (3)Kendall协同系数检验,27,三、描述性统计与多元统计分析,例 为考察5 名工人的劳动生产率是否相同，记录了每人4 天的产量，并算出其平均值，如下表。你能从这些数据推断出他们的生产率有无显著差别吗？,3. 方差分析,3

17、.1 单因素方差分析,28,三、描述性统计与多元统计分析,例 一种火箭使用了四种燃料、三种推进器，进行射程试验，对于每种燃料与每种推进器的组合作一次试验，得到试验数据如下表。问各种燃料之间及各种推进器之间有无显著差异？,3. 方差分析,3.2 双因素方差分析,29,三、描述性统计与多元统计分析,4. 聚类分析,样本的相似性度量： 绝对值距离、欧式距离、车比雪夫距离、马氏距离 变量相似性度量： 相关系数、夹角余弦 类与类间的相似性度量： 最短距离法、最长距离法、重心法、类平均法、离差平方和法,聚类分析又称为群分析，是对多个样本（或指标） 进行定量分类的一种多元统计分析方法。 Q型聚类分析对样本进

18、行分类 R型聚类分析对指标进行分类,30,三、描述性统计与多元统计分析,因子分析可以看成主成分分析的推广，它也是多元统计分析中常用的一种降维方式，因子分析所涉及的计算与主成分分析也很类似，但差别也是很明显的：1）主成分分析把方差划分为不同的正交成分，而因子分析则把方差划归为不同的起因因子；2）因子分析中特征值的计算只能从相关系数矩阵出发，且必须将主成分转换成因子。,5. 主成分分析（后面有介绍）,例如 诊断时，医生检测了病人的五个生理指标：收缩压、舒张压、心跳间隔、呼吸间隔和舌下温度，但依据生理学知识，这五个指标是受植物神经支配的，植物神经又分为交感神经和副交感神经，因此这五个指标可用交感神经

19、和副交感神经两个公共因子来确定，从而也构成了因子模型。 例如 Holjinger和Swineford在芝加哥郊区对145名七、八年级学生进行了24个心理测验，通过因子分析，这24个心理指标被归结为4个公共因子，即词语因子、速度因子、推理因子和记忆因子。,6. 因子分析,31,三、描述性统计与多元统计分析,7. 判别分析,判别分析（discriminant analysis）是根据所研究的个体的观测指标来推断该个体所属类型的一种统计方法。 方法：距离判别、Fisher判别、Bayes判别,例如 某种产品的生产厂家有12 家，其中7 家的产品受消费者欢迎，属于畅销品，定义为1 类；5 家的产品不大

20、受消费者欢迎，属于滞销品，定义为2 类。将12 家的产品的式样，包装和耐久性进行了评估后，得分资料见下表。 今有3 家新的厂家，得分分别为(6,4,5),(8,1,3),(2,4,5),试对3 个新厂家进行分类。,32,三、描述性统计与多元统计分析,8. 典型相关分析,利用综合变量对之间的相关关系来反映两组指标之间的整体相关性的多元统计分析方法。 它的基本原理是：为了从总体上把握两组指标之间的相关关系，分别在两组变量中提取有代表性的两个综合变量U1和V1（分别为两个变量组中各变量的线性组合），利用这两个综合变量之间的相关关系来反映两组指标之间的整体相关性。,例如 为了研究扩张性财政政策实施以后

21、对宏观经济发展的影响，就需要考察有关财政政策的一系列指标如财政支出总额的增长率、财政赤字增长率、国债发行额的增长率、税率降低率等与经济发展的一系列指标如国内生产总值增长率、就业增长率、物价上涨率等两组变量之间的相关程度。 例如 在分析评估某种经济投入与产出系统时，研究投入和产出情况之间的联系时，投入情况面可以从人力、物力等多个方面反映，产出情况也可以从产值、利税等方面反映。,33,依据相关信息对被评价的对象所进行的客观、公正、合理的全面评价。 如果把被评价对象视为系统，则综合评价问题：在若干个(同类)系统中，如何确定哪个系统的运行(或发展)状况好，哪个状况差？即哪个优，哪个劣？ 一类多属性(或

22、多指标)的综合评价问题。,综合评价：,四、综合评价方法,34,综合评价过程的流程:,四、综合评价方法（参考资料-10）,35,四、综合评价方法,适用条件:各评价指标之间相互独立。 对不完全独立的情况，其结果将导致各指标间信息的重复，使评价结果不能客观地反映实际。,1. 线性加权综合法,主要特点： （1）各评价指标间作用得到线性补偿； （2）权重系数的对评价结果的影响明显。,用线性加权函数 作为综合评价模型， 对个系统进行综合评价。,36,2. 非线性加权综合法,四、综合评价方法,主要特点： （1）突出了各指标值的一致性，即平衡评价指标值较小的指标影响的作用； （2）权重系数大小的影响不是特别明

23、显，而对指标值的大小差异相对较敏感。,37,四、综合评价方法,3. 逼近理想点（TOPSIS）方法,38,四、综合评价方法,4. 层次分析法,基本步骤： （i）建立递阶层次结构模型； （ii）构造出各层次中的所有判断矩阵； （iii）层次单排序及一致性检验； （iv）层次总排序及一致性检验。,39,四、综合评价方法,5. 模糊综合评判法（参考资料-11）,主要步骤：,40,四、综合评价方法,5. 模糊综合评判法,主要算子及特点：,41,四、综合评价方法,6. 主成分分析法（参考资料-12）,主成分分析是将多个指标（变量）化为少数几个指标（变量）互不相关的指标（变量）的统计方法。 降维思想：在实

24、际问题的研究中，往往会涉及众多有关的变量。但是，变量太多不但会增加计算的复杂性，而且也会给合理地分析问题和解释问题带来困难。一般说来，虽然每个变量都提供了一定的信息，但其重要性有所不同，而在很多情况下，变量间有一定的相关性，从而使得这些变量所提供的信息在一定程度上有所重叠。因而人们希望对这些变量加以“改造”，用为数极少的互补相关的新变量来反映原变量所提供的绝大部分信息，通过对新变量的分析达到解决问题的目的。,42,四、综合评价方法,6. 主成分分析法,主要步骤：,43,四、综合评价方法,7. 数据包络分析法,DEA是根据多指标投入和多指标产出对相同类型的单位(部门)进行相对有效性或效益评价的一

25、种系统分析方法。它是处理多目标决策问题的好方法。,44,四、综合评价方法,适用性:（1）DEA以决策单位个输入/输出的权重为变量，从最有利于决策单元的角度进行评价，从而避免了确定各指标在优先意义下的权重。 （2）假定每个输入都关联到一个或者多个输出，而且输入/输出之间确实存在某些关系，使用DEA方法则不必确定这种关系的显示表达式。 主要特点：无需任何权重假设，每一个输入/输出的权重不是根据评价者的主观认定，而是由决策单元的实际数据求得的最优权重。因此，DEA方法排除了很多的主观因素，具有很强的客观性。,7. 数据包络分析法,数学模型：,Charnes-Cooper变化后的数学模型：,45,四、

26、综合评价方法,8. 灰色关联分析法,（1）确定比较对象（评价对象）和参考数列（评价标准）。 （2）确定各指标值对应的权重。 （3）计算灰色关联系数。 （4）计算灰色加权关联度。 （5）评价分析。,主要步骤：,46,四、综合评价方法,9. 秩和比综合评价法 （参考资料-13）,主要步骤： （1）编秩； （2）计算秩和比； （3）计算概率单位； （4）计算直接回归方程； （5）分档排序。,基本原理：在一个n行m列矩阵中，通过秩转换，获得无量纲统计量RSR;在此基础上，运用参数统计分析的概念与方法，研究RSR的分布；以RSR值对评价对象的优劣直接排序或分档排序，从而对评价对象做出综合评价。,例如：

27、样本的数据为3,4,1,-1,0 顺序统计量为-1,0,1,3,4 而秩统计量为4,5,3,1,2,47,四、综合评价方法,10. 粗糙集综合评价法（参考资料-14）,主要步骤： （1）建立评价的信息系统； （2）指标数据离散化； （3）信息系统属性约简； （4）确定指标的权重； （5）综合评价合成。,48,1插值与拟合（小样本内部预测）,五、数据建模的预测方法,2微分方程模型,描述实际对象的某些特性随时间（或空间）而演变的过程、分析它的变化规律、预测它的未来性态、研究它的控制手段时，通常要建立对象的动态微分方程模型。 典型的模型有： （1）传染病的预测模型； （2）经济增长预测模型； （3）

28、Lanchester战争预测模型； （4）药物在体内的分布与排除预测模型； （5）人口的预测模型 等等.（参考 姜启源 数学模型）,49,3灰色预测GM(1,1)（小样本未来预测）,五、数据建模的预测方法,特点：模型使用的不是原始数据，而是生成的数据序列 优点：（1）可以解决历史数据少的、缺失及可靠性低的问题 （2）抓本质、精度高、运算简便 （3）易于检验、不考虑分布规律、不考虑变化趋势 缺点：（1）只适用于中短期的预测 （2）只适合指数增长的预测 GM(2,1),DGM(2,1)-非单调的摆动发展序列 灰色Verhulst预测模型-具有饱和状态的过程，即S形过程 GM(1,N)-N个相关因素

29、序列（参考资料-15）,50,4回归模型方法（大样本的内部预测）,五、数据建模的预测方法,一般步骤： （1）建立因变量y与自变量x1,x2,xn直接的回归模型； （2）对回归模型的可信度进行检验； （3）判断每个自变量xi(i=1,2,n)对y的影响是否显著； （4）诊断回归模型是否适合这组数据； （5）利用回归模型对y进行预报或控制。,分类：一元（多元）线性回归regress 非线性回归nlinfit 逐步回归stepwise 时间序列回归DW检验，变量的线性变换 阻滞回归logit 主成分回归,51,5神经网络方法（大样本的未来预测）,五、数据建模的预测方法,（1）自适应共振理论及反向传播

30、网络（BP）神经网络 （2）RBF神经网络,52,6时间序列,五、数据建模的预测方法,时间序列预测技术就是通过对预测目标自身时间序列的处理，来研究其变化趋势的。一个时间序列往往是以下几类变化形式的叠加或耦合。 （1）长期趋势变动。它是指时间序列朝着一定的方向持续上升或下降，或停留在某一水平上的倾向，它反映了客观事物的主要变化趋势。 （2）季节变动。 （3）循环变动。通常是指周期为一年以上，由非季节因素引起的涨落起伏波形相似的波动。 （4）不规则变动。通常它分为突然变动和随机变动。,类型：加法模型 yt=Tt+St+Ct+Rt 乘法模型 yt=Tt*St*Ct*Rt 混合模型 yt=Tt*St+

31、Rt或yt=St+Tt*Ct*Rt 其中：Tt长期趋势项，St季节变动趋势项，Ct循环变动趋势项 ，Rt随机干扰项。,53,6.1 移动平均法,五、数据建模的预测方法,当时间序列的数值由于受周期变动和不规则变动的影响，起伏较大，不易显示出发展趋势时，可用移动平均法，消除这些因素的影响，分析、预测序列的长期趋势。,方法：（1）简单移动平均法， 适用范围：短期预测，预测目标变化不大； （2）加权移动平均法， 注：近期数据的权数大，远期数据的权小； （3）趋势移动平均法， 注：对于同时存在直线趋势与周期波动的序列，是一种既能反映趋势变化，又可以有效地分离出来周期变动的方法。,54,6.2 指数平滑法,五、数据建模