数学建模中常用算法.pdf

ic Algorithm
数学建模中的常用算法
成都信息工程学院
计算科学系
胡建成
jianchenghu@
2009-5-20
Algorithms in Mathematical Modeling
ic Algorithm
数学建模竞赛网上资源
 CUMCM网站: http://mcm.
 MCM和ICM网站:
中国数学建模:
中科大建模网站: .
 MATLAB网站:
 GOOGLE大学
2013/1/20
2 Algorithms in Mathematical Modeling
ic Algorithm
数学建模竞赛中的算法(1)
 93A 非线性交调的频率设计: 拟合、规划
 93B 足球队排名次: 矩阵论、图论、层次分析法、
整数规划
 94A 逢山开路: 图论、插值、动态规划
 94B 锁具装箱问题: 图论、组合数学
 95A 飞行管理问题: 非线性规划、线性规划
 95B 天车与冶炼炉的作业调度: 非线性规划、动态
规划、层次分析法、PETRI方法、图论方法、排队论
方法
 96A 最优捕鱼策略:微分方程、积分、非线性规划
2013/1/20
3 Algorithms in Mathematical Modeling
ic Algorithm
数学建模竞赛中的算法(2)
 96B 节水洗衣机:非线性规划
 97A 零件参数设计:微积分、非线性规划、随机模拟
 97B 截断切割:组合优化、几何变换、枚举、蒙特卡
罗、递归、最短路
 98A 投资收益与风险:线性规划、非线性规划
 98B 灾情巡视:最小生成树、Hamilton圈、旅行商
问题
 99A 自动化车床:积分、概率分布、随机模拟、分布
拟合度检验
2013/1/20
4 Algorithms in Mathematical Modeling
ic Algorithm
数学建模竞赛中的算法(3)
 99B 钻井布局:几何变换、枚举、最大完全子图、
混合整数规划
 00A DNA分类:神经网络、最小二乘拟合、统计分
类
 00B 管道订购:最短路、二次规划
 01A 血管的三维重建:数据挖掘、曲面重建与拟合
 01B 公交车调度:非线性规划
 02A 车灯光源优化设计:最优化
 02B 彩票中的数学:概率与优化
2013/1/20
5 Algorithms in Mathematical Modeling
ic Algorithm
数学建模常用软件
 MATLAB  SAS
 Maple  SPSS
 Mathematica  C&C++
 Lindo  Fortran
 Lingo  Pascal
2013/1/20
6 Algorithms in Mathematical Modeling
ic Algorithm
数学建模竞赛常用算法(1)
1. 蒙特卡罗方法(Monte-Carlo方法, MC)
该算法又称计算机随机性模拟方法,也称统计试验
方法。MC方法是一种基于“随机数”的计算方法,能够
比较逼真地描述事物的特点及物理实验过程,解决一些
数值方法难以解决的问题。
MC方法的雏型可以追溯到十九世纪后期的蒲丰随机
投针试验,即著名的蒲丰问题。 MC方法通过计算机仿
真(模拟)解决问题,同时也可以通过模拟来检验自己
模型的正确性,是比赛中经常使用的方法。
2013/1/20
7 Algorithms in Mathematical Modeling
ic Algorithm
数学建模竞赛常用算法
 97年的A题每个零件都有自己的标定值,也都有自
己的容差等级,而求解最优的组合方案将要面对着的是一
个极其复杂的公式和108种容差选取方案,根本不可能去求
解析解,那如何去找到最优的方案呢?随机性模拟搜索最
优方案就是其中的一种方法,在每个零件可行的区间中按
照正态分布随机的选取一个标定值和选取一个容差值作为
一种方案,然后通过蒙特卡罗算法仿真出大量的方案,从
中选取一个最佳的。
 02年的B题关于彩票第二问,要求设计一种更好的方
案,首先方案的优劣取决于很多复杂的因素,同样不可能
刻画出一个模型进行求解,只能靠随机仿真模拟。
2013/1/20
8 Algorithms in Mathematical