数学建模中的常用算法

《数学建模中的常用算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学建模中的常用算法成都信息工程学院计算科学系胡建成jianchenghu@163.com2009-5-20数学建模竞赛网上资源CUMCM网站:http://mcm.edu.cnMCM和ICM网站:http://www.comap.com中国数学建模:http://www.shumo.com中科大建模网站:http://mcm.ustc.edu.cnMATLAB网站:http://www.mathworks.comGOOGLE大学7/10/2021数学建模竞赛中的算法(1)93A非线性交调的频率设计:拟合、规划93B足球队排名次:矩阵论、图

2、论、层次分析法、整数规划94A逢山开路:图论、插值、动态规划94B锁具装箱问题:图论、组合数学95A飞行管理问题:非线性规划、线性规划95B天车与冶炼炉的作业调度:非线性规划、动态规划、层次分析法、PETRI方法、图论方法、排队论方法96A最优捕鱼策略：微分方程、积分、非线性规划7/10/202196B节水洗衣机：非线性规划97A零件参数设计：微积分、非线性规划、随机模拟97B截断切割：组合优化、几何变换、枚举、蒙特卡罗、递归、最短路98A投资收益与风险：线性规划、非线性规划98B灾情巡视：最小生成树、Hamilton圈、旅行商问题99A自

3、动化车床：积分、概率分布、随机模拟、分布拟合度检验数学建模竞赛中的算法(2)7/10/202199B钻井布局：几何变换、枚举、最大完全子图、混合整数规划00ADNA分类：神经网络、最小二乘拟合、统计分类00B管道订购：最短路、二次规划01A血管的三维重建：数据挖掘、曲面重建与拟合01B公交车调度：非线性规划02A车灯光源优化设计：最优化02B彩票中的数学：概率与优化数学建模竞赛中的算法(3)7/10/2021MATLABMapleMathematicaLindoLingoSASSPSSC&C++FortranPascal数学建模常用软件7/

4、10/20211.蒙特卡罗方法(Monte-Carlo方法,MC)数学建模竞赛常用算法(1)该算法又称计算机随机性模拟方法，也称统计试验方法。MC方法是一种基于“随机数”的计算方法，能够比较逼真地描述事物的特点及物理实验过程，解决一些数值方法难以解决的问题。MC方法的雏型可以追溯到十九世纪后期的蒲丰随机投针试验，即著名的蒲丰问题。MC方法通过计算机仿真(模拟)解决问题，同时也可以通过模拟来检验自己模型的正确性，是比赛中经常使用的方法。7/10/202197年的A题每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着

5、的是一个极其复杂的公式和108种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。02年的B题关于彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。数学建模竞赛常用算法7/10/202198年美国赛A题生物组织切片的三维插值处理94年A题逢山开路山体海拔高度的插值计算数学建

6、模竞赛常用算法(2)2.数据拟合、参数估计、插值等数据处理算法比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MATLAB作为工具。与图形处理有关的问题很多与拟合有关系。此类问题在MATLAB中有很多函数可以调用，只有熟悉MATLAB，这些方法才能用好。7/10/202198年B题用很多不等式完全可以把问题刻画清楚数学建模竞赛常用算法(3)3.规划类问题算法此类问题主要有线性规划、整数规划、多元规划、二次规划等。竞赛中很多问题都和数学规划有关，可以说不少的模型都可以归结为一组不等式作为约束条件、几个函数表达式作为

7、目标函数的问题，遇到这类问题，求解就是关键了。因此列举出规划后用Lindo、Lingo等软件来进行解决比较方便，所以还需要熟悉这两个软件。7/10/202198年B题、00年B题、95年锁具装箱等问题体现了图论问题的重要性。数学建模竞赛常用算法(4)4.图论问题这类问题算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配等问题。7/10/202192年B题用分枝定界法97年B题是典型的动态规划问题98年B题体现了分治算法数学建模竞赛常用算法(5)5.计算机算法设计中的问题计算机算法设计包括很多

8、内容：动态规划、回溯搜索、分治算法、分枝定界等计算机算法.这方面问题和ACM程序设计竞赛中的问题类似，可看一下与计算机算法有关的书。7/10/202197年A题用模拟退火算法00