十类数学建模中的算法

《十类数学建模中的算法》由会员分享，可在线阅读，更多相关《十类数学建模中的算法（8页珍藏版）》请在金锄头文库上搜索。

1、十类数学建模中的算法1、蒙特卡罗算法： 在大多数建模赛题中都离不开计算机的仿真，随机性模拟是非常常见的算法之一。 # Y) b; b E“ _5 / H 举个例子就是 97 年的 A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求 解最优的组合方案将要面对着的是一个极其复杂的公式和 108 种容差选取方案，根本不可 能去解析求解的，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种 方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作 为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例 子就是去年的彩票第二问，要求设计

2、一种更好的方案，首先方案的优劣决定于很多复杂的 因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。 ! Z* ?. W# W n, c5 0 g 2、数据拟合、参数估计、插值等算法： 数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是 98 年美赛 A 题，生物组织切片的三维插值处理，94 年 A 题逢山开路，山体海拔高度的插 值计算，还有吵的沸沸扬扬可能会考的非典问题也要用到数据拟合算法，观察数据的走向 进行处理。此类问题在 Matlab 中有很多数据处理现成的函数可以调用，熟悉 Matlab，这些 方法都能游刃有余的做好。 3、规划类问题算法： 竞赛中

3、很多问题都和数学规划有关，可以说不少的模型都可以归结为一组不等式组作为约 束条件、几个函数表达式作为目标函数的问题，遇到这类问题，求解就是关键了，比如 98B，用很多不等式完全可以把问题刻画清楚，因此列举出规划后用 Lindo、Lingo 等软件 来进行解决比较方便，所以还需要熟悉这两个软件。 T: y# q F1 % $ K 4、图论问题： 98B、00B、95 锁具装箱等问题体现了图论问题的重要性，这类问题算法有很多，包括： Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配等问题。每一个算法认真的话都 应该写一遍，否则到比赛时再写就晚了， 5、计算机算法设

4、计中的问题： 计算机算法设计包括很多内容：动态规划、回溯搜索、分治算法、分支定界。比如 92B 用 分支定界法，97B 是典型的动态规划问题，此外 98B 体现了分治算法。这方面问题和 acm 中的问题类似，推荐的书籍有计算机算法设计与分析电子工业出版社等与计算机算法 有关的书。 6、最优化理论的三大非经典算法： 模拟退火法、神经网络、遗传算法。这十几年来最优化理论有了飞速发展，这三类算法发 展很快，近几年的赛题越来越复杂，很多问题没有什么很好的模型可以借鉴，于是这三类 算法很多时候可以派上用场，比如：97A 的模拟退火算法、00B 的神经网络分类算法、象 01B 这种难题也可以使用神经网络、

5、还有美国竞赛 89A 也和 BP 算法有关系，当时是 86 年 刚提出 BP 算法，89 年就考了，说明赛题可能是当今前沿科技的抽象体现。03B 伽马刀问 题也是目前研究的课题，目前算法最佳的是遗传算法。 3 Y S3 d 9、数值分析算法 . p2 F: y% 4 r1 u6 E 这类算法是针对高级语言而专门设的，如果你用的是 Matlab、Mathematica，大可不必准备， 因为象数值分析中有很多函数一般的数学工具是具备的。 10、图象处理算法 01A 中需要你会读 bmp 图象、98 美赛 A 需要你知道三维插值计算，03B 要求更高，不但 需要编程计算还要进行处理，而数模论文中也有

6、很多图片需要展示，因此图象处理就是关 键，做好这类问题，重要的是把 Matlab 学好，特别是图象处理的部分。 “ W“ r5 y g、数学建模竞赛中应当掌握的十类算法1蒙特卡罗算法 该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可 以来检验自己模型的正确性，是比赛时必用的方法。 2数据拟合、参数估计、插值等数据处理算法 比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用 Matlab 作为工具。 3线性规划、整数规划、多元规划、二次规划等规划类问题 建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通 常使用

7、Lindo、Lingo 软件实现。 4图论算法 这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以 用这些方法解决，需要认真准备。 5动态规划、回溯搜索、分治算法、分支定界等计算机算法 这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中。 6最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法 这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算 法的实现比较困难，需慎重使用。 7网格算法和穷举法 网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型 本身而轻视算法的时候，可以使用这种暴力方案，最好使

8、用一些高级语言作为编程工具。 8一些连续离散化方法 很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离 散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9数值分析算法 如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10图象处理算法 赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形 如何展示以及如何处理就是需要解决的问题，通常使用 Matlab 进行处理。二、数学软件的主要分类有哪些？各有什么特点？数学软件从功能上分类可以分为通用数学软件包

9、和专业数学软件包，通用数学包功能比较 完备，包括各种数学、数值计算、丰富的数学函数、特殊函数、绘图函数、用户图形届面 交互功能，与其他软件和语言的接口及庞大的外挂函数库机制（工具箱） 。 常见的通用数学软件包包括 Matlab 和 Mathematica 和 Maple，其中 Matlab 是一个高性能的 科技计算软件，广泛应用于数学计算、建模、仿真和数据分析处理及工程作图， Mathematica 是数值和符号计算的代表性软件，Maple 以符号运算、公式推导见长。 专用数学包包括绘图软件类 MathCAD，Tecplot，IDL，Surfer，Origin, SmartDraw,DSP20

10、00） ，数值计算类：（Matcom， IDL， DataFit，S- Spline，Lindo，Lingo，O-Matrix，Scilab，Octave）, 数值计算库 （linpack/lapack/BLAS/GERMS/IMSL/CXML）, 有限元计算类 （ANSYS，MARC，PARSTRAN，FLUENT，FEMLAB，FlexPDE，Algor，COSMOS, ABAQUS，ADINA） ，计算化学类（Gaussian98，Spartan，ADF2000，ChemOffice） ，数理 统计类（GAUSS，SPSS，SAS， Splus，statistica，minitab）,

11、数学公式排版类 （MathType，MikTeX，Scientific Workplace，Scientific Nootbook） 。三、关于数模竞赛的几本好书 姜启源， 数学模型（第二版） ，高等教育出版社 姜启源、谢金星、叶俊数学建模（第三版） ，高等教育出版社 萧树铁等， 数学实验 ，高等教育出版社 朱道元， 数学建模案例精选 ，科学出版社 雷功炎， 数学模型讲义 ，北京大学出版社 叶其孝等， 大学生数学建模竞赛辅导教材（一）（四） ，湖南教育出版社 江裕钊、辛培清， 数学模型与计算机模拟 ，电子科技大学出版社 杨启帆、边馥萍， 数学模型 ，浙江大学出版社 赵静等， 数学建模与数学实验

12、 ，高等教育出版社，施普林格出版社四、基础学科1数学分析 2高等代数 3概率与数理统计 4最优化理论 5图论 6组合数学 7微分方程稳定性分析 8排队论五、常用网站和 ftp http:/ 全国大学生数模竞赛官方网站 http:/www.shumo.org 中国数学建模网站 http:/ 中科大数模网站 http:/ 浙江大学数模网 http:/ 哈工大数模网站 http:/bbs.dartmouth.edu/fangq/wiki/?MathTools_FAQ 数学工具 FAQ ftp:/ ftp:/202.198.71.195 ftp:/166.111.8.229 ftp:/166.111.

13、30.174 ftp:/166.111.68.183 ftp:/166.111.158.102 ftp:/166.111.163.248:40021 ftp:/166.111.172.77蒙特卡罗算法蒙特卡罗算法 Monte Carlo 编辑本段 统计模拟法蒙特卡罗也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计 算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是 指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。蒙特卡罗方法的名字 来源于摩纳哥的一个城市蒙地卡罗，该城市以赌博业闻名，而蒙特罗方法正是以概率为基 础的方法。与它对应的是确定

14、性算法。蒙特卡罗方法在金融工程学，宏观经济学，计算物理学(如粒子输运计算、量子热力学 计算、空气动力学计算)等领域应用广泛。基本思想 当所求解问题是某种随机事件出现的概率，或者是某个随机变量的期望值时，通过某种 “实验”的方法，以这种事件出现的频率估计这一随机事件的概率，或者得到这个随机变 量的某些数字特征，并将其作为问题的解。 有一个例子可以使你比较直观地了解蒙特卡罗 方法：假设我们要计算一个不规则图形的面积，那么图形的不规则程度和分析性计算（比 如，积分）的复杂程度是成正比的。蒙特卡罗方法是怎么计算的呢？假想你有一袋豆子， 把豆子均匀地朝这个图形上撒，然后数这个图形之中有多少颗豆子，这个豆

15、子的数目就是 图形的面积。当你的豆子越小，撒的越多的时候，结果就越精确。在这里我们要假定豆子 都在一个平面上，相互之间没有重叠。工作过程在解决实际问题的时候应用蒙特卡罗方法主要有两部分工作：用蒙特卡罗方法模拟某一过程时，需要产生各种概率分布的随机变量。 用统计方法把模型的数字特征估计出来，从而得到实际问题的数值解。 计算步骤使用蒙特卡罗方法进行分子模拟计算是按照以下步骤进行的： 使用随机数发生器产生一个随机的分子构型。 对此分子构型的其中粒子坐标做无规则的改变，产生一个新的分子构型。 计算新的分子构型的能量。 比较新的分子构型于改变前的分子构型的能量变化，判断是否接受该构型。 若新的分子构型能量低于原分子构型的能量，则接受新的构型，使用这个构型重复再 做下一次迭代。 若新的分子构型能量高于原分子构型的能量，则计算玻尔兹曼常数，同时产生一个随 机数。 若这个随机数大于所计算出的玻尔兹曼因子，则放弃这个构型，重新计算。 若这个随机数小于所计算出的玻尔兹曼因子，则接受这个构型，使用这个构型重复再 做下一次迭代。 如此进行迭代计算，直至最后搜索出低于所给能量条件的分子构型结束。在数学中的应用通常蒙特卡罗方法通过构造符合一定规则的随机数来