数学建模中的常用算法数学建模中的常用算法成都信息工程学院计算科学系胡建成jianchenghu@163.com2006-8-6AlgorithmsinMathematicalModelingGeneticAlgorithm数学建模竞赛网上资源¾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大学28/6/2006AlgorithmsinMathematicalModelingGeneticAlgorithm数学建模竞赛中的算法¾93A非线性交调的频率设计:拟合、规划¾93B足球队排名次:矩阵论、图论、层次分析法、整数规划¾94A逢山开路:图论、插值、动态规划¾94B锁具装箱问题:图论、组合数学¾95A飞行管理问题:非线性规划、线性规划¾95B天车与冶炼炉的作业调度:非线性规划、动态规划、层次分析法、PETRI方法、图论方法、排队论方法38/6/2006AlgorithmsinMathematicalModelingGeneticAlgorithm数学建模竞赛中的算法¾96A最优捕鱼策略：微分方程、积分、非线性规划¾96B节水洗衣机：非线性规划¾97A零件参数设计：微积分、非线性规划、随机模拟¾97B截断切割：组合优化、几何变换、枚举、蒙特卡罗、递归、最短路48/6/2006AlgorithmsinMathematicalModelingGeneticAlgorithm数学建模竞赛中的算法¾98A投资收益与风险：线性规划、非线性规划¾98B灾情巡视：最小生成树、Hamilton圈、旅行商问题¾99A自动化车床：积分、概率分布、随机模拟、分布拟合度检验¾99B钻井布局：几何变换、枚举、最大完全子图、混合整数规划58/6/2006AlgorithmsinMathematicalModelingGeneticAlgorithm数学建模竞赛中的算法¾00ADNA分类：神经网络、最小二乘拟合、统计分类¾00B管道订购：最短路、二次规划¾01A血管的三维重建：数据挖掘、曲面重建与拟合¾01B公交车调度：非线性规划¾02A车灯光源优化设计：最优化¾02B彩票中的数学：概率与优化68/6/2006AlgorithmsinMathematicalModelingGeneticAlgorithm数学建模常用数学软件¾MATLAB¾SAS¾Maple¾SPSS¾Mathematica¾C&C++¾Lindo¾Fortran¾Lingo¾Pascal78/6/2006AlgorithmsinMathematicalModelingGeneticAlgorithm数学建模应掌握的十类算法1.蒙特卡罗方法(Monte-Carlo方法,MC)该算法又称计算机随机性模拟方法，也称统计试验方法。这一方法源于美国在第一次世界大战进行的研制原子弹的“曼哈顿计划”。该计划的主持人之一、数学家冯·诺伊曼用驰名世界的赌城—摩纳哥的MonteCarlo—来命名这种方法。MC方法是一种基于“随机数”的计算方法，能够比较逼真地描述事物的特点及物理实验过程，解决一些数值方法难以解决的问题。MC方法的雏型可以追溯到十九世纪后期的蒲丰(Buffon)随机投针试验，即著名的蒲丰问题。MC方法通过计算机仿真(模拟)解决问题，同时也可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。88/6/2006AlgorithmsinMathematicalModelingGeneticAlgorithm数学建模应掌握的十类算法997年的A题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。902年的B题，关于彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。98/6/2006Alg