数学建模中的常用算法 —数学建模与系统仿真 主讲:王晓峰 E-mail:xfwang828@126.com
数学建模中的常用算法 ——数学建模与系统仿真 主讲：王晓峰 E-mail:xfwang828@126.com
数学建模竞赛网上资源 > CUMCM网站:htp/ mcm. edu. cn MCM和CM网站http://www.comap.com >中国数学建模:htp/ vw shumo. com >中科大建模网站:http://mcm.ustc.edu.cn MATLABI网站:htp:/ w. mathworks com GGE学 Google 22021/12/12
2 数学建模竞赛网上资源 ➢ CUMCM网站: http://mcm.edu.cn ➢ MCM和ICM网站: http://www.comap.com ➢ 中国数学建模: http://www.shumo.com ➢ 中科大建模网站: http://mcm.ustc.edu.cn ➢ MATLAB网站: http://www.mathworks.com ➢ GOOGLE大学 2021/12/12
数学建模竞赛中的算法(1) >93A非线性交调的频率设让:拟合、规划 >93B足球队排名次:矩阵论、图论、层次分析法、整 数规划 >94A逢山开路:图论、插值、动态规划 >94B锁具装箱问题:图论、组合数学 >95A飞行管理问题:非线性规划、线性规划 >95B天车与冶炼炉的作业调度:非线性规划、动态规 划、层次分析法、PER工方法、图论方法、排队论方 法 >96A最优捕鱼策略:微分方程、积分、非线性规划 32021/12/12
3 数学建模竞赛中的算法(1) ➢ 93A 非线性交调的频率设计: 拟合、规划 ➢ 93B 足球队排名次: 矩阵论、图论、层次分析法、整 数规划 ➢ 94A 逢山开路: 图论、插值、动态规划 ➢ 94B 锁具装箱问题: 图论、组合数学 ➢ 95A 飞行管理问题 : 非线性规划、线性规划 ➢ 95B 天车与冶炼炉的作业调度: 非线性规划、动态规 划、层次分析法、PETRI方法、图论方法、排队论方 法 ➢ 96A 最优捕鱼策略：微分方程、积分、非线性规划 2021/12/12
数学建模竞赛中的算法(2) >96B节水洗衣机:非线性规划 >97A零件参数设计:微积分、非线性规划、随机模拟 >97B截断切割:组合优化、几何变换、枚举、蒙特卡 罗、递归、最短路 >98A投资收益与风险:线性规划、非线性规划 >98B灾情巡视:最小生成树、Hami1ton圈、旅行商问 题 99A自动化车床:积分、概率分布、随机模拟、分布 拟合度检验 42021/12/12
4 数学建模竞赛中的算法(2) ➢ 96B 节水洗衣机：非线性规划 ➢ 97A 零件参数设计：微积分、非线性规划、随机模拟 ➢ 97B 截断切割：组合优化、几何变换、枚举、蒙特卡 罗、递归、最短路 ➢ 98A 投资收益与风险：线性规划、非线性规划 ➢ 98B 灾情巡视：最小生成树、Hamilton圈、旅行商问 题 ➢ 99A 自动化车床：积分、概率分布、随机模拟、分布 拟合度检验 2021/12/12
数学建模竞赛中的算法(3) >99B钻井布局:几何变换、枚举、最大完全子图、混 合整数规划 >00ADNA分类:神经网络、最小二乘拟合、统计分类 >00B管道讧购:最短路、二次规划 01A血管的三维重建:数据挖掘、曲面重建与拟合 >01B公交车调度:非线性规划 >02A车灯光源优化设让:最优化 >02B彩票中的数学:概率与优化 52021/12/12
5 数学建模竞赛中的算法(3) ➢ 99B 钻井布局：几何变换、枚举、最大完全子图、混 合整数规划 ➢ 00A DNA分类：神经网络、最小二乘拟合、统计分类 ➢ 00B 管道订购：最短路、二次规划 ➢ 01A 血管的三维重建：数据挖掘、曲面重建与拟合 ➢ 01B 公交车调度：非线性规划 ➢ 02A 车灯光源优化设计：最优化 ➢ 02B 彩票中的数学：概率与优化 2021/12/12
数学建模常用软件 MATLAB SAS > Maple SPSS Ⅳ Mathematica c&ct+ > Lindo Fortran Lingo Pasca 62021/12/12
6 数学建模常用软件 ➢ MATLAB ➢ Maple ➢ Mathematica ➢ Lindo ➢ Lingo 2021/12/12 ➢ SAS ➢ SPSS ➢ C&C++ ➢ Fortran ➢ Pascal
数学建模竞赛常用算法(1) 1.蒙特卡罗方法( Monte-Carlo方法,MC 该算法又称计算机随机性模拟方法,也称统计试验 方法。MC方法是一种基于“随机数”的计算方法,能够 比较逼真地描述事物的特点及物理实验过程,解决一些 数值方法难以解决的问题 MC方法的雏型可以追溯到十九世纪后期的蒲丰随机 投针试验,即著名的蒲丰问题。MC方法通过计算机仿 真(模拟)解决问题,同时也可以通过模拟来检验自己 模型的正确性,是比赛中经常使用的方法 72021/12/12
7 数学建模竞赛常用算法(1) 1. 蒙特卡罗方法(Monte-Carlo方法, MC) 2021/12/12 该算法又称计算机随机性模拟方法，也称统计试验 方法。MC方法是一种基于“随机数”的计算方法，能够 比较逼真地描述事物的特点及物理实验过程，解决一些 数值方法难以解决的问题。 MC方法的雏型可以追溯到十九世纪后期的蒲丰随机 投针试验，即著名的蒲丰问题。 MC方法通过计算机仿 真(模拟)解决问题，同时也可以通过模拟来检验自己 模型的正确性，是比赛中经常使用的方法
数学建模竞赛常用算法 √97年的A题每个零件都有自己的标定值,也都有自 己的容差等级,而求解最优的组合方案将要面对着的是一 个极其复杂的公式和108种容差选取方案,根本不可能去求 解析解,那如何去找到最优的方案呢?随机性模拟搜索最 优方案就是其中的一种方法,在每个零件可行的区间中按 照正态分布随机的选取一个标定值和选取一个容差值作为 种方案,然后通过蒙特卡罗算法仿真出大量的方案,从 中选取一个最佳的 √02年的B题关于彩票第二问,要求设计一种更好的方 案,首先方案的优劣取决于很多复杂的因素,同样不可能 刻画出一个模型进行求解,只能靠随机仿真模拟 82021/12/12
8 数学建模竞赛常用算法 ✓ 97年的A题 每个零件都有自己的标定值，也都有自 己的容差等级，而求解最优的组合方案将要面对着的是一 个极其复杂的公式和108种容差选取方案，根本不可能去求 解析解，那如何去找到最优的方案呢？随机性模拟搜索最 优方案就是其中的一种方法，在每个零件可行的区间中按 照正态分布随机的选取一个标定值和选取一个容差值作为 一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从 中选取一个最佳的。 ✓ 02年的B题 关于彩票第二问，要求设计一种更好的方 案，首先方案的优劣取决于很多复杂的因素，同样不可能 刻画出一个模型进行求解，只能靠随机仿真模拟。 2021/12/12
数学建模竞赛常用算法(2) 2.数据拟合、参数估计、插值等数据处理算法 比赛中通常会遇到大量的数据需要处理,而处理数 据的关键就在于这些算法,通常使用 MATLAB作为工 具。与图形处理有关的问题很多与拟合有关系。 98年美国赛A题生物组织切片的三维插值处理 √94年A题逢山开路山体海拔高度的插值计算 此类问题在 MATLAB中有很多函数可以调用,只有熟 悉 MATLAB,这些方法才能用好 92021/12/12
9 数学建模竞赛常用算法(2) ✓ 98 年美国赛A 题 生物组织切片的三维插值处理 ✓ 94 年A 题逢山开路 山体海拔高度的插值计算 2021/12/12 2. 数据拟合、参数估计、插值等数据处理算法 比赛中通常会遇到大量的数据需要处理，而处理数 据的关键就在于这些算法，通常使用MATLAB 作为工 具。与图形处理有关的问题很多与拟合有关系。 此类问题在MATLAB中有很多函数可以调用，只有熟 悉MATLAB，这些方法才能用好
数学建模竞赛常用算法(3) 3.规划类问题算法 此类问题主要有线性规划、整数规划、多元规划 二次规划等。竞赛中很多问题都和数学规划有关,可以 说不少的模型都可以归结为一组不等式作为约束条件、 几个函数表达式作为目标函数的问题,遇到这类问题, 求解就是关键了 √98年B题用很多不等式完全可以把问题刻画清楚 因此列举出规划后用 Lindo、 Lingo等软件来进行解决 比较方便,所以还需要熟悉这两个软件。 102021/12/12
10 数学建模竞赛常用算法(3) ✓ 98年B 题 用很多不等式完全可以把问题刻画清楚 2021/12/12 3. 规划类问题算法 此类问题主要有线性规划、整数规划、多元规划、 二次规划等。竞赛中很多问题都和数学规划有关，可以 说不少的模型都可以归结为一组不等式作为约束条件、 几个函数表达式作为目标函数的问题，遇到这类问题， 求解就是关键了。 因此列举出规划后用Lindo、Lingo 等软件来进行解决 比较方便，所以还需要熟悉这两个软件