第4讲数学建模赛题分析实践方法与算法ppt课件.ppt

第2讲 数学建模赛题分析、实践方法与算法,数学与统计学院 李鑫,2023/1/10,2,数学建模的赛题分析与实践方法,1.CUMCM历年赛题的简析,2.数学建模竞赛的实践方法,3.数学建模竞赛常用方法解析,4.数学建模竞赛10种常用算法,2023/1/10,3,数学建模竞赛的规模越来越大,水平越来越高；竞赛的水平主要体现在赛题水平；赛题的水平主要体现：（）综合性、实用性、创新性、即时性等；（）多种解题方法的创造性、灵活性、开放性等；（）海量数据的复杂性、数学模型的多样性、求解结果的不唯一性等。纵览20年的本科组40个题目(专科组21个)，从问题的实际意义、解决问题的方法和题型三个方面作一些简单的分析。,一、CUMCM历年赛题的简析,2023/1/10,4,1.CUMCM 的历年赛题及解法,1993年:()通讯中非线性交调的频率设计问题(拟合、规划)()足球甲级联赛排名问题(图论、层次分析、整数规划)1994年:()山区修建公路的设计造价问题(图论、插值、动态规划)()锁具的制造、销售和装箱问题(图论、组合数学)1995年:()飞机的安全飞行管理调度问题(非线性规划、线性规划)()天车与冶炼炉的作业调度问题(动态规划、排队论、图论)1996年:(A)最优捕鱼策略问题(微分方程、优化)(B)节水洗衣机的程序设计问题(非线性规划)1997年:(A)零件参数优化设计问题(非线性规划)(B)金刚石截断切割问题(随机模拟、图论),一、CUMCM历年赛题的简析,2023/1/10,5,1.CUMCM 的历年赛题及解法,1998年:(A)投资的收益和风险问题（多目标优化、非线性规划）(B)灾情的巡视路线问题（图论、组合优化）1999年:(A)自动化机床控制管理问题（随机优化、计算机模拟）(B)地质堪探钻井布局问题（0-1规划、图论）2000年:(A)DNA序列的分类问题(模式识别、Fisher判别、人工神经网络)(B)钢管的订购和运输问题（组合优化、运输问题）2001年:(A)三维血管的重建问题（曲线拟合、曲面重建）(B)公交车的优化调度问题（多目标规划）2002年:(A)汽车车灯的优化设计问题（非线性规划）(B)彩票中的数学问题（单目标决策）,一、CUMCM历年赛题的简析,2023/1/10,6,1.CUMCM 的历年赛题及解法,2003年:(A)SARS的传播问题（微分方程、差分方程）(B)露天矿生产的车辆安排问题（整数规划、运输问题）2004年:(A)奥运会临时超市网点设计问题(统计分析、数据处理、优化)(B)电力市场的输电阻塞管理问题(数据拟合、优化）2005年:(A)长江水质的评价与预测问题（预测评价、数据处理）(B)DVD在线租赁问题（随机规划、整数规划）2006年:(A)出版社的资源管理问题（整数规划、数据处理、优化）(B)艾滋病疗法的评价及预测问题（线性规划、回归分析）2007年:(A)中国人口增长预测问题（微分方程、数据处理、优化）(B)“乘公交，看奥运”问题(多目标规划、动态规划、图论、0-1规划),一、CUMCM历年赛题的简析,2023/1/10,7,2008年:(A)照相机问题（非线性方程组、优化）(B)大学学费问题（数据收集和处理、统计分析、回归分析）2009年:(A)制动器试验台的控制方法分析（物理原理建模、数值积分、物理模拟、误差分析（微分方程、模拟）(B)眼科病床的合理安排（统计分析、排队论、仿真、随机优化、模糊综合评价）2010年:(A)储油罐的变位识别与罐容表标定(数据分析、非线性优化、微积分)(B)2010年上海世博会影响力的定量评估(信息收集、开放性)2011年:(A)城市表层土壤重金属污染分析(散乱插值拟合、聚类分析、主成分分析、偏微分方程)(B)交巡警服务平台的设置与调度(最短路算法、多目标优化、0-1规划、启发式算法),一、CUMCM历年赛题的简析,2023/1/10,8,2、从问题的解决方法上分析,涉及到的数学建模方法：几何理论、组合概率、统计（回归）分析、优化方法(规划)、图论与网络优化、层次分析、插值与拟合、差分计算、微分方程、排队论、模糊数学、随机决策、多目标决策、随机模拟、灰色系统理论、神经网络、时间序列、综合评价、机理分析等方法。,一、CUMCM历年赛题的简析,2023/1/10,9,3、从问题的题型上分析,一、CUMCM历年赛题的简析,赛题题型结构形式有三个基本组成部分：（1）实际问题背景 涉及面宽-有社会，经济，管理，生活，环境，自然现象，工程技术，现代科学中出现的新问题等。一般都有一个比较确切的现实问题。（2）若干假设条件 有如下几种情况：a.只有过程、规则等定性假设，无具体定量数据；b.给出若干实测或统计数据；c.给出若干参数或图形；d.蕴涵着某些机动、可发挥的补充假设条件，或参赛者可以根据自己收集或模拟产生数据。（3）要求回答的问题 往往有几个问题（一般不是唯一的答案）:a.比较确定性的答案（基本答案）；b.更细致或更高层次的讨论结果（往往是讨论最优方案的提法和结果）。,2023/1/10,10,3、从问题的题型上分析,(1)“即时性”较强的问题(2)理论性较强的问题(3)实用性较强的问题(4)算法要求强的问题(5)数据量大的问题,一、CUMCM历年赛题的简析,2023/1/10,11,4、近几年题目的特点,(1)综合性：一题多解，方法融合，结果多样，学科交叉。(2)开放性：题意的开放性，思路的开放性，方法的开放性，结果的开放性。(3)实用性：问题和数据来自于实际，解决方法切合于实际，模型和结果可以应用于实际。(4)即时性：国内外的大事，社会的热点，生活的焦点，近期发生和即将发生被关注的问题。(5)数据结构的复杂性：数据的真实性，数据的海量性，数据的不完备性，数据的冗余性。,一、CUMCM历年赛题的简析,2023/1/10,12,常用数学模型有哪些？常用数学建模方法有哪些？参加数学建模需要具备哪些知识和能力？,二、数学建模竞赛的实践方法,2023/1/10,13,优化模型微分方程模型统计模型概率模型图论模型决策模型,1、数学模型分类,二、数学建模竞赛的实践方法,2023/1/10,14,类比法量纲分析法差分法变分法图论法层次分析法数据拟合法回归分析法数学规划（线性规划，非线性规划，整数规划，动态规划，目标规划）,2、数学建模常用的方法,二、数学建模竞赛的实践方法,2023/1/10,15,机理分析法排队方法对策方法决策方法模糊评判方法时间序列方法灰色理论方法现代优化算法（禁忌搜索算法，模拟退火算法，遗传算法，神经网络）,二、数学建模竞赛的实践方法,2、数学建模常用的方法,2023/1/10,16,3.数学建模所需要的知识和方法,数学建模应具备的数学知识：高等数学、微分方程、运筹学、线性代数、概率统计、数值计算等。,二、数学建模竞赛的实践方法,另外还需要了解排队论、对策论、决策论、模糊数学、时间序列、灰色理论等相关知识。,2023/1/10,17,问题给定一批数据点（输入变量与输出变量的数据），确定满足特定要求的曲线或曲面。插值问题要求所求曲线（面）通过所给所有数据点。数据拟合不要求曲线（面）通过所有数据点，而是要求它反映对象整体的变化趋势。,1、插值与拟合方法,三、数学建模竞赛常用方法解析,2023/1/10,18,一元函数拟合多项式拟合非线性函数拟合多元函数拟合（回归分析）函数的确定MATLAB实现,（1）数据拟合,三、数学建模竞赛常用方法解析,2023/1/10,19,一维插值的定义已知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)散乱数据差值（一般需专用的数据处理软件）,（2）插值方法,三、数学建模竞赛常用方法解析,2023/1/10,20,（1）优化模型四要素决策变量目标函数（尽量简单、光滑）约束条件（建模的关键）求解方法（MATLAB,LINDO）,2、优化方法,三、数学建模竞赛常用方法解析,2023/1/10,21,线性规划模型（目标函数和约束条件都是线性函数的优化问题）非线性规划模型（目标函数或者约束条件是非线性的函数）整数规划（决策变量是整数值的规划问题）多目标规划（具有多个目标函数的规划问题）目标规划（具有不同优先级的目标和偏差的规划问题）动态规划（求解多阶段决策问题的最优化方法）,（2）优化模型分类,三、数学建模竞赛常用方法解析,2023/1/10,22,无约束规划fminsearchfminbnd线性规划linprog非线性规划fmincon多目标规划（计算有效解）目标加权、效用函数动态规划（倒向、正向）整数规划（分支定界法、枚举法、LINDO）,（3）优化模型求解,三、数学建模竞赛常用方法解析,2023/1/10,23,回归分析对具有相关关系的现象，根据其关系形态，选择一个合适的数学模型，用来近似地表示变量间的平均变化关系的一种统计方法（一元线性回归、多元线性回归、非线性回归）回归分析在一组数据的基础上研究这样几个问题：建立因变量与自变量之间的回归模型（经验公式）对回归模型的可信度进行检验判断每个自变量对因变量的影响是否显著判断回归模型是否适合这组数据利用回归模型对进行预报或控制b,bint,r,rint,stats=regress(Y,X,alpha)（线性回归）rstool（x，y，model,alpha）（多元二项式回归）beta,r,J=nlinfit（x，y，model,beta0）（非线性回归）,3、统计方法,（1）回归分析,三、数学建模竞赛常用方法解析,2023/1/10,24,逐步回归分析从一个自变量开始，视自变量作用的显著程度，从大到小依次逐个引入回归方程当引入的自变量由于后面变量的引入而变得不显著时，要将其剔除掉引入一个自变量或从回归方程中剔除一个自变量，为逐步回归的一步对于每一步都要进行值检验，以确保每次引入新的显著性变量前回归方程中只包含对作用显著的变量这个过程反复进行，直至既无不显著的变量从回归方程中剔除，又无显著变量可引入回归方程时为止stepwise(x,y,inmodel,alpha)SPSS,SAS,（2）逐步回归分析,三、数学建模竞赛常用方法解析,2023/1/10,25,聚类分析所研究的样本或者变量之间存在程度不同的相似性，要求设法找出一些能够度量它们之间相似程度的统计量作为分类的依据，再利用这些量将样本或者变量进行分类系统聚类分析将n个样本或者n个指标看成n类，一类包括一个样本或者指标，然后将性质最接近的两类合并成为一个新类，依此类推。最终可以按照需要来决定分多少类，每类有多少样本（指标）,（3）聚类分析,三、数学建模竞赛常用方法解析,2023/1/10,26,系统聚类方法步骤：计算n个样本两两之间的距离构成n个类，每类只包含一个样品合并距离最近的两类为一个新类计算新类与当前各类的距离（新类与当前类的距离等于当前类与组合类中包含的类的距离最小值），若类的个数等于1，转5，否则转3画聚类图决定类的个数和类。,（3）聚类分析,三、数学建模竞赛常用方法解析,2023/1/10,27,判别分析在已知研究对象分成若干类型，并已取得各种类型的一批已知样品的观测数据，在此基础上根据某些准则建立判别式，然后对未知类型的样品进行判别分类。距离判别法首先根据已知分类的数据，分别计算各类的重心，计算新个体到每类的距离，确定最短的距离（欧氏距离、马氏距离）Fisher判别法利用已知类别个体的指标构造判别式（同类差别较小、不同类差别较大），按照判别式的值判断新个体的类别Bayes判别法计算新给样品属于各总体的条件概率，比较概率的大小，然后将新样品判归为来自概率最大的总体,（4）判别分析,三、数学建模竞赛常用方法解析,2023/1/10,28,模糊数学研究和处理模糊性现象的数学（概念与其对立面之间没有一条明确的分界线）与模糊数学相关的问题（一）模糊分类问题已知若干个相互之间不分明的模糊概念，需要判断某个确定事物用哪一个模糊概念来反映更合理准确模糊相似选择 按某种性质对一组事物或对象排序是一类常见的问题，但是用来比较的性质具有边界不分明的模糊性,4、模糊数学方法,三、数学建模竞赛常用方法解析,2023/1/10,29,模糊聚类分析根据研究对象本身的属性构造模糊矩阵，在此基础上根据一定的隶属度来确定其分类关系 模糊层次分析法两两比较指标的确定模糊综合评判综合评判就是对受到多个因素制约的事物或对象作出一个总的评价，如产品质量评定、科技成果鉴定、某种作物种植适应性的评价等，都属于综合评判问题。由于从多方面对事物进行评价难免带有模糊性和主观性，采用模糊数学的方法进行综合评判将使结果尽量客观从而取得更好的实际效果,4、模糊数学方法,三、数学建模竞赛常用方法解析,2023/1/10,30,时间序列是按时间顺序排列的、随时间变化且相互关联的数据序列通过对预测目标自身时间序列的处理，来研究其变化趋势（长期趋势变动、季节变动、循环变动、不规则变动）自回归模型一般自回归模型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个时刻进入系统的扰动存在一定的依存关系,5、时间序列分析方法,三、数学建模竞赛常用方法解析,2023/1/10,31,数据的预处理：数据的剔取及提取趋势项取n=1，拟合ARMA(2n,2n-1)（即ARMA(2,1)）模型n=n+1，拟合ARMA(2n,2n-1)模型用F准则检验模型的适用性。若检验显著，则转入第2步。若检验不显著，转入第5步。检查远端时刻的系数值的值是否很小，其置信区间是否包含零。若不是，则适用的模型就是ARMA(2n,2n-1)。若很小，且其置信区间包含零，则拟合ARMA(2n-1,2n-2)。,5、时间序列分析方法,时间序列建模的基本步骤：,三、数学建模竞赛常用方法解析,2023/1/10,32,利用F准则检验模型ARMA(2n,2n-1)和ARMA(2n-1,2n-2)，若F值不显著，转入第7步；若F值显著，转入第8步。舍弃小的MA参数，拟合m2n-2的模型ARMA(2n-1,m)，并用F准则进行检验。重复这一过程，直到得出具有最小参数的适用模型为止舍弃小的MA参数，拟合m2n-1的模型ARMA(2n,m)，并用F准则进行检验。重复这一过程，直到得出具有最小参数的适用模型为止。,时间序列建模的基本步骤：,三、数学建模竞赛常用方法解析,2023/1/10,33,最短路问题两个指定顶点之间的最短路径给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线（Dijkstra算法）每对顶点之间的最短路径（Dijkstra算法、Floyd算法）最小生成树问题连线问题欲修筑连接多个城市的铁路设计一个线路图，使总造价最低（prim算法、Kruskal算法）图的匹配问题人员分派问题：n个工作人员去做件n份工作，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？(匈牙利算法),6、图论方法,三、数学建模竞赛常用方法解析,2023/1/10,34,遍历性问题中国邮递员问题邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线最大流问题运输问题最小费用最大流问题在运输问题中，人们总是希望在完成运输任务的同时，寻求一个使总的运输费用最小的运输方案,6、图论方法,三、数学建模竞赛常用方法解析,2023/1/10,35,（1）蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是2002年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。,四、数学建模竞赛10种常用算法,2023/1/10,36,（2）数据拟合、参数估计、插值等数据处理算法 比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具 数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是98 年美国赛A 题，生物组织切片的三维插值处理，94 年A 题逢山开路，山体海拔高度的插值计算，还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法，观察数据的走向进行处理。此类问题在MATLAB中有很多现成的函数可以调用，熟悉MATLAB，这些方法都能游刃有余的用好。,四、数学建模竞赛10种常用算法,2023/1/10,37,（3）线性规划、整数规划、多元规划、二次规划等规划类问题 建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现 竞赛中很多问题都和数学规划有关，可以说不少的模型都可以归结为一组不等式作为约束条件、几个函数表达式作为目标函数的问题，遇到这类问题，求解就是关键了，比如98年B 题，用很多不等式完全可以把问题刻画清楚，因此列举出规划后用Lindo、Lingo 等软件来进行解决比较方便，所以还需要熟悉这两个软件。,四、数学建模竞赛10种常用算法,2023/1/10,38,（4）图论算法 这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备 98 年B 题、00 年B 题、95 年锁具装箱等问题体现了图论问题的重要性，这类问题算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配等问题。每一个算法都应实现一遍，否则到比赛时再写就晚了。,四、数学建模竞赛10种常用算法,2023/1/10,39,（5）动态规划、回溯搜索、分治算法、分支定界等计算机算法 这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中。比如92 年B 题用分枝定界法，97 年B 题是典型的动态规划问题，此外98 年B 题体现了分治算法。这方面问题和ACM 程序设计竞赛中的问题类似，推荐看一下计算机算法设计与分析（电子工业出版社）等与计算机算法有关的书。,四、数学建模竞赛10种常用算法,2023/1/10,40,（6）最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法 这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。比如：97 年A 题的模拟退火算法，00 年B 题的神经网络分类算法，象01 年B 题这种难题也可以使用神经网络，还有美国竞赛89 年A 题也和BP 算法有关系，当时是86 年刚提出BP 算法，89 年就考了，说明赛题可能是当今前沿科技的抽象体现。03 年B 题伽马刀问题也是目前研究的课题，目前算法最佳的是遗传算法。,四、数学建模竞赛10种常用算法,2023/1/10,41,（7）数值分析算法 如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用 这类算法是针对高级语言而专门设的，如果你用的是MATLAB、Mathematica，大可不必准备，因为象数值分析中有很多函数一般的数学软件是具备的。,四、数学建模竞赛10种常用算法,2023/1/10,42,（8）一些连续离散化方法 很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后运用差分代替微分、求和代替积分等思想是非常重要的 大部分物理问题的编程解决，都和这种方法有一定的联系。物理问题是反映我们生活在一个连续的世界中，计算机只能处理离散的量，所以需要对连续量进行离散处理。这种方法应用很广，而且和上面的很多算法有关。事实上，网格算法、蒙特卡罗算法、模拟退火都用了这个思想。,四、数学建模竞赛10种常用算法,2023/1/10,43,（9）网格算法和穷举法 网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具 网格算法和穷举法一样，只是网格法是连续问题的穷举。比如要求在N 个变量情况下的最优化问题，那么对这些变量可取的空间进行采点。比如97 年A 题、99 年B 题都可以用网格法搜索，这种方法最好在运算速度较快的计算机中进行，还有要用高级语言来做，最好不要用MATLAB 做网格，否则会算很久的。,四、数学建模竞赛10种常用算法,2023/1/10,44,（10）图象处理算法 赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理 01年A 题中需要你会读BMP 图象、美国赛98 年A 题需要你知道三维插值计算，03 年B 题要求更高，不但需要编程计算还要进行处理，而数模论文中也有很多图片需要展示，因此图象处理就是关键。做好这类问题，重要的是把MATLAB 学好，特别是图象处理的部分。,四、数学建模竞赛10种常用算法,2023/1/10,45,平等地位、相互尊重、充分交流杜绝武断评价不要回避责任不要对交流失去信心,竞赛中的群体思维方法,2023/1/10,46,借助于一系列问题来展开思路这个问题与什么问题相似？如果将问题分解成两个或几个部分会怎样？极限情形（或理想状态）如何？综合问题的条件可得到什么结果？要实现问题的目标需要什么条件？借助于下意识的联想（灵感）来展开思路抓住问题的个别条件或关键词展开联想或猜想综合所得到的联想和猜想，得到一些结论进一步思考找出新思路和方法,竞赛中的发散性思维方法,2023/1/10,47,认真仔细地识题明确条件和任务通过关键词捕捉关键信息分清是非，勿入陷井,对赛题的把握和理解问题,2023/1/10,48,谢谢大家!,