数学建模中的常用算法.ppt

Algorithms in Mathematical Modeling Algorithms in Mathematical Modeling 数学建模中的常用算法 成都信息工程学院 计算科学系 胡建成 jianchenghu@163.com 2009-5-20 数学建模竞赛网上资源 CUMCM网站: MCM和ICM网站: 中国数学建模: 中科大建模网站: MATLAB网站: GOOGLE大学 数学建模竞赛中的算法(1) 93A 非线性交调的频率设计: 拟合、规划 93B 足球队排名次: 矩阵论、图论、层次分析法、整数规划 94A 逢山开路: 图论、插值、动态规划 94B 锁具装箱问题: 图论、组合数学 95A 飞行管理问题 : 非线性规划、线性规划 95B 天车与冶炼炉的作业调度: 非线性规划、动态规划、层次分析法、PETRI方法、图论方法、排队论方法 96A 最优捕鱼策略：微分方程、积分、非线性规划 数学建模竞赛中的算法(2) 96B 节水洗衣机：非线性规划 97A 零件参数设计：微积分、非线性规划、随机模拟 97B 截断切割：组合优化、几何变换、枚举、蒙特卡罗、递归、最短路 98A 投资收益与风险：线性规划、非线性规划 98B 灾情巡视：最小生成树、Hamilton圈、旅行商问题 99A 自动化车床：积分、概率分布、随机模拟、分布拟合度检验 数学建模竞赛中的算法(3) 99B 钻井布局：几何变换、枚举、最大完全子图、混合整数规划 00A DNA分类：神经网络、最小二乘拟合、统计分类 00B 管道订购：最短路、二次规划 01A 血管的三维重建：数据挖掘、曲面重建与拟合 01B 公交车调度：非线性规划 02A 车灯光源优化设计：最优化 02B 彩票中的数学：概率与优化 数学建模常用软件 MATLAB Maple Mathematica Lindo Lingo 数学建模竞赛常用算法(1) 1. 蒙特卡罗方法(Monte-Carlo方法, MC) 数学建模竞赛常用算法 97年的A题 每个零件都有自己的标定值，也都有自 己的容差等级，而求解最优的组合方案将要面对着的是一 个极其复杂的公式和108种容差选取方案，根本不可能去求 解析解，那如何去找到最优的方案呢？随机性模拟搜索最 优方案就是其中的一种方法，在每个零件可行的区间中按 照正态分布随机的选取一个标定值和选取一个容差值作为 一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从 中选取一个最佳的。 02年的B题 关于彩票第二问，要求设计一种更好的方 案，首先方案的优劣取决于很多复杂的因素，同样不可能 刻画出一个模型进行求解，只能靠随机仿真模拟。 数学建模竞赛常用算法(2) 98 年美国赛A 题 生物组织切片的三维插值处理 94 年A 题逢山开路 山体海拔高度的插值计算 数学建模竞赛常用算法(3) 98年B 题 用很多不等式完全可以把问题刻画清楚 数学建模竞赛常用算法(4) 98 年B 题、00年B 题、95 年锁具装箱等问题体现了图论问题的重要性。 数学建模竞赛常用算法(5) 92 年B 题用分枝定界法 97 年B 题是典型的动态规划问题 98 年B 题体现了分治算法 数学建模竞赛常用算法(6) 97年A 题用模拟退火算法 00年B 题用神经网络分类算法 01年B 题这种难题也可以使用神经网络 美国89年A 题也和BP 算法有关系 美国03年B 题伽马刀问题也是目前研究的课题，目前算法最佳的是遗传算法。 数学建模竞赛常用算法(7) 97 年A 题、99 年B 题都可以用网格法搜索 数学建模竞赛常用算法(8) 很多问题都是实际来的，数据可以是连续的，而计 算机只能处理离散的数据，因此需要将连续问题进行 离散化处理后再用计算机求解。比如差分代替微分、 求和代替积分等思想都是把连续问题离散化的常用方 法。 数学建模竞赛常用算法(9) 数值分析研究各种求解数学问题的数值计算方法， 特别是适合于计算机实现方法与算法。 数学建模竞赛常用算法(10) 01年A 题中需要你会读BMP 图象 98年美国A 题需要你知道三维插值计算 03年B 题要求更高，不但需要编程计算还要进行处理 三个孩子的年龄(1) 两个多年未见的朋友相遇，聊了很多事情。… 三个孩子的年龄(2) 三个孩子的年龄(3) 根据对话信息，用搜索的方法来解此问题。 三个孩子的年龄(4) 智能优化算法 常用的智能优化算法 遗传算法 Genetic A