十类数学建模中的算法.doc

《十类数学建模中的算法.doc》由会员分享，可在线阅读，更多相关《十类数学建模中的算法.doc（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、0 Z+ m. u1 r5 D; t; D% N 3、规划类问题算法： - d8 J( F! w8 w, v 竞赛中很多问题都和数学规划有关，可以说不少的模型都可以归结为一组不等式组作为约束条件、几个函数表达式作为目标函数的问题，遇到这类问题，求解就是关键了，比如98B，用很多不等式完全可以把问题刻画清楚，因此列举出规划后用Lindo、Lingo等软件来进行解决比较方便，所以还需要熟悉这两个软件。 T: y# q F1 % $ K4、图论问题： $ z) M- Z( 9 L! k7 L: T* A# f98B、00B、95锁具装箱等问题体现了图论问题的重要性，这类问题算法有很多，包括：Dijk

4、stra、Floyd、Prim、Bellman-Ford，最大流，二分匹配等问题。每一个算法认真的话都应该写一遍，否则到比赛时再写就晚了， 2 d4 U3 J! 5 j6 u5、计算机算法设计中的问题： 9 z# J x5 L7 J% qh计算机算法设计包括很多容：动态规划、回溯搜索、分治算法、分支定界。比如92B用分支定界法，97B是典型的动态规划问题，此外98B体现了分治算法。这方面问题和acm中的问题类似，推荐的书籍有计算机算法设计与分析电子工业等与计算机算法有关的书。 * B. C4 B( P3 d8 m; ls6、最优化理论的三大非经典算法： w2 n% 8 k/ r: u模拟退火法

5、、神经网络、遗传算法。这十几年来最优化理论有了飞速发展，这三类算法发展很快，近几年的赛题越来越复杂，很多问题没有什么很好的模型可以借鉴，于是这三类算法很多时候可以派上用场，比如：97A的模拟退火算法、00B的神经网络分类算法、象01B这种难题也可以使用神经网络、还有美国竞赛89A也和BP算法有关系，当时是86年刚提出BP算法，89年就考了，说明赛题可能是当今前沿科技的抽象体现。03B伽马刀问题也是目前研究的课题，目前算法最佳的是遗传算法。 3 Y& m0 c6 f. _# v7、网格算法和穷举算法 9 S( p3 p1 L; & ?1 Y4 a. H, N网格算法和穷举法一样，只是网格法是连续

6、问题的穷举。比如要求在N个变量情况下的最优化问题，那么可以对这些变量可取的空间进行采点，比如在a,b区间取M+1个点，就是在a、a+(b-a)/M、a+2*(b-a)/M、b那么这样循环就需要进行(M+1)N次运算，所以计算量很大。 ! B& u$ K8 M1 8 q/ w9 7 C+ h( _3 w比如97年A题、99年B题都可以用网格法搜索，这种方法最好在运算速度叫快的计算机中进行，还有要用高级语言来做，最好不要用Matlab做网格，否则会算很久的。穷举法大家都熟悉，就不说了。 # m% ) U9 M, S# % d. Z8、一些连续离散化方法 0 l1 E % E& m: K+ p大部分

7、物理问题的编程解决，都和这种方法有一定的联系，物理问题是反映我们生活在一个连续的世界中，计算机求解只认离散的变量，所以需要将连续量进行离散处理，这种方法应用很广，大都和上面的很多算法有关，事实上，网格算法、蒙特卡罗算法、模拟退火都用了这个思想。 8 _* gw7 B2 t! I9 s# i; S3 d9、数值分析算法 . p2 F: y% 4 r1 u6 E这类算法是针对高级语言而专门设的，如果你用的是Matlab、Mathematica，大可不必准备，因为象数值分析中有很多函数一般的数学工具是具备的。 + m6 H9 y5 v9 g8 G10、图象处理算法 5 R1 kZs* z. N. P

8、: Z% D/ J6 d3 W+ C01A中需要你会读bmp图象、98美赛A需要你知道三维插值计算，03B要求更高，不但需要编程计算还要进行处理，而数模论文中也有很多图片需要展示，因此图象处理就是关键，做好这类问题，重要的是把Matlab学好，特别是图象处理的部分。 W r5 yg、数学建模竞赛中应当掌握的十类算法1蒙特卡罗算法该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法。2数据拟合、参数估计、插值等数据处理算法比赛常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具。3线性规划、

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

10、最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。8一些连续离散化方法很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。9数值分析算法如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。10图象处理算法赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形如何展示以与如何处理就是需要解决的问题，通常使用Matlab进行处理。二、数

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

12、，Origin, SmartDraw,DSP2000），数值计算类：（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，stat

13、istica，minitab）, 数学公式排版类（MathType，MikTeX，Scientific Workplace，Scientific Nootbook）。三、关于数模竞赛的几本好书 启源，数学模型（第二版），高等教育 启源、金星、叶俊数学建模（第三版），高等教育 萧树铁等，数学实验，高等教育 朱道元，数学建模案例精选，科学 雷功炎，数学模型讲义，大学 叶其孝等，大学生数学建模竞赛辅导教材（一）（四），教育 江裕钊、辛培清，数学模型与计算机模拟，电子科技大学 启帆、边馥萍，数学模型，大学 静等，数学建模与数学实验，高等教育，施普林格四、基础学科1数学分析 2高等代数 3概率与数理统计

14、4最优化理论 5图论 6组合数学7微分方程稳定性分析 8排队论五、常用和ftp 全国大学生数模竞赛官方 .shumo.org 中国数学建模 中科大数模 大学数模网哈工大数模 bbs.dartmouth.edu/fangq/wiki/?MathTools_FAQ 数学工具FAQ ftp:/ ftp:/166.111.163.248:40021 fT. N; |6 a3 r5 U蒙特卡罗算法蒙特卡罗算法Monte Carlo 编辑本段统计模拟法蒙特卡罗也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使

15、用随机数（或更常见的伪随机数）来解决很多计算问题的方法。蒙特卡罗方法的名字来源于摩纳哥的一个城市蒙地卡罗，该城市以赌博业闻名，而蒙特罗方是以概率为基础的方法。与它对应的是确定性算法。蒙特卡罗方法在金融工程学，宏观经济学，计算物理学(如粒子输运计算、量子热力学计算、空气动力学计算)等领域应用广泛。 基本思想当所求解问题是某种随机事件出现的概率，或者是某个随机变量的期望值时，通过某种“实验”的方法，以这种事件出现的频率估计这一随机事件的概率，或者得到这个随机变量的某些数字特征，并将其作为问题的解。 有一个例子可以使你比较直观地了解蒙特卡罗方法：假设我们要计算一个不规则图形的面积，那么图形的不规则程

16、度和分析性计算（比如，积分）的复杂程度是成正比的。蒙特卡罗方法是怎么计算的呢？假想你有一袋豆子，把豆子均匀地朝这个图形上撒，然后数这个图形之中有多少颗豆子，这个豆子的数目就是图形的面积。当你的豆子越小，撒的越多的时候，结果就越精确。在这里我们要假定豆子都在一个平面上，相互之间没有重叠。 工作过程在解决实际问题的时候应用蒙特卡罗方法主要有两部分工作：用蒙特卡罗方法模拟某一过程时，需要产生各种概率分布的随机变量。 用统计方法把模型的数字特征估计出来，从而得到实际问题的数值解。 计算步骤使用蒙特卡罗方法进行分子模拟计算是按照以下步骤进行的： 使用随机数发生器产生一个随机的分子构型。 对此分子构型的其

17、中粒子坐标做无规则的改变，产生一个新的分子构型。 计算新的分子构型的能量。 比较新的分子构型于改变前的分子构型的能量变化，判断是否接受该构型。 若新的分子构型能量低于原分子构型的能量，则接受新的构型，使用这个构型重复再做下一次迭代。 若新的分子构型能量高于原分子构型的能量，则计算玻尔兹曼常数，同时产生一个随机数。 若这个随机数大于所计算出的玻尔兹曼因子，则放弃这个构型，重新计算。 若这个随机数小于所计算出的玻尔兹曼因子，则接受这个构型，使用这个构型重复再做下一次迭代。 如此进行迭代计算，直至最后搜索出低于所给能量条件的分子构型结束。 在数学中的应用通常蒙特卡罗方法通过构造符合一定规则的随机数来

18、解决数学上的各种问题。对于那些由于计算过于复杂而难以得到解析解或者根本没有解析解的问题，蒙特卡罗方法是一种有效的求出数值解的方法。一般蒙特卡罗方法在数学中最常见的应用就是蒙特卡罗积分。 积分非权重蒙特卡罗积分，也称确定性抽样，是对被积函数变量区间进行随机均匀抽样，然后对被抽样点的函数值求平均，从而可以得到函数积分的近似值。此种方法的正确性是基于概率论的中心极限定理。当抽样点数为m时，使用此种方法所得近似解的统计误差恒为,不随积分维数的改变而改变。因此当积分维度较高时，蒙特卡罗方法相对于其他数值解法更优。 蒙特卡罗解题三个主要步骤： 构造或描述概率过程： 对于本身就具有随机性质的问题，如粒子输运

19、问题，主要是正确描述和模拟这个概率过程，对于本来不是随机性质的确定性问题，比如计算定积分，就必须事先构造一个人为的概率过程，它的某些参量正好是所要求问题的解。即要将不具有随机性质的问题转化为随机性质的问题。 实现从已知概率分布抽样： 构造了概率模型以后，由于各种概率模型都可以看作是由各种各样的概率分布构成的，因此产生已知概率分布的随机变量（或随机向量），就成为实现蒙特卡罗方法模拟实验的基本手段，这也是蒙特卡罗方法被称为随机抽样的原因。最简单、最基本、最重要的一个概率分布是(0,1)上的均匀分布（或称矩形分布）。随机数就是具有这种均匀分布的随机变量。随机数序列就是具有这种分布的总体的一个简单子样

20、，也就是一个具有这种分布的相互独立的随机变数序列。产生随机数的问题，就是从这个分布的抽样问题。在计算机上，可以用物理方法产生随机数，但价格昂贵，不能重复，使用不便。另一种方法是用数学递推公式产生。这样产生的序列，与真正的随机数序列不同，所以称为伪随机数，或伪随机数序列。不过，经过多种统计检验表明，它与真正的随机数，或随机数序列具有相近的性质，因此可把它作为真正的随机数来使用。由已知分布随机抽样有各种方法，与从(0,1)上均匀分布抽样不同，这些方法都是借助于随机序列来实现的，也就是说，都是以产生随机数为前提的。由此可见，随机数是我们实现蒙特卡罗模拟的基本工具。 建立各种估计量： 一般说来，构造了

21、概率模型并能从中抽样后，即实现模拟实验后，我们就要确定一个随机变量，作为所要求的问题的解，我们称它为无偏估计。 建立各种估计量，相当于对模拟实验的结果进行考察和登记，从中得到问题的解。 例如：检验产品的正品率问题，我们可以用1表示正品，0表示次品，于是对每个产品检验可以定义如下的随机变数Ti，作为正品率的估计量： 于是，在N次实验后，正品个数为： 显然，正品率p为： 不难看出，Ti为无偏估计。当然，还可以引入其它类型的估计，如最大似然估计，渐进有偏估计等。但是，在蒙特卡罗计算中，使用最多的是无偏估计。 用比较抽象的概率语言描述蒙特卡罗方法解题的手续如下：构造一个概率空间(W ,A,P)，其中，

22、W 是一个事件集合，A是集合W 的子集的s 体，P是在A上建立的某个概率测度；在这个概率空间中，选取一个随机变量q (w ),w Î W ,使得这个随机变量的期望值 正好是所要求的解Q ，然后用q (w )的简单子样的算术平均值作为Q 的近似值。 特点:直接追踪粒子，物理思路清晰，易于理解。 采用随机抽样的方法，较真切的模拟粒子输运的过程，反映了统计涨落的规律。 不受系统多维、多因素等复杂性的限制，是解决复杂系统粒子输运问题的好方法。 MC程序结构清晰简单。 研究人员采用MC方法编写程序来解决粒子输运问题，比较容易得到自己想得到的任意中间结果，应用灵活性强。 MC方法主要弱点是收敛

23、速度较慢和误差的概率性质，其概率误差正比于，如果单纯以增大抽样粒子个数N来减小误差，就要增加很大的计算量。 蒙特卡罗方法的计算程序：关于蒙特卡罗方法的计算程序已经有很多，如：EGS4、FLUKA、ETRAN、ITS、MCNP、GEANT等。这些程序大多经过了多年的发展，花费了几百人年的工作量。除欧洲核子研究中心（CERN）发行的GEANT主要用于高能物理探测器响应和粒子径迹的模拟外，其它程序都深入到低能领域，并被广泛应用。就电子和光子输运的模拟而言，这些程序可被分为两个系列：1EGS4、FLUKA、GRANT 2ETRAN、ITS、MCNP 这两个系列的区别在于：对于电子输运过程的模拟根据不同

24、的理论采用了不同的算法。 EGS4和ETRAN分别为两个系列的基础，其它程序都采用了它们的核心算法。 ETRAN(for Electron Transport)由美国国家标准局辐射研究中心开发，主要模拟光子和电子，能量围可从1KeV到1GeV。 ITS(The integrated TIGER Series of Coupled Electron/Photon Monte Carlo Transport Codes )是由美国圣地亚哥（Sandia）国家实验室在ETRAN的基础上开发的一系列模拟计算程序，包括TIGER 、CYLTRAN 、ACCEPT等，它们的主要差别在于几何模型的不同。TI

25、GER研究的是一维多层的问题，CYLTRAN研究的是粒子在圆柱形介质中的输运问题，ACCEPT是解决粒子在三维空间输运的通用程序。 NCNP(Monte Carlo Neutron and Photo Transport Code)由美国橡树林国家实验室(Oak Ridge National Laboratory)开发的一套模拟中子、光子和电子在物质中输运过程的通用MC 计算程序，在它早期的版本中并不包含对电子输运过程的模拟，只模拟中子和光子，较新的版本（如MCNP4A）则引进了ETRAN，加入了对电子的模拟。 FLUKA 是一个可以模拟包括中子、电子、光子和质子等30余种粒子的大型MC计算程

26、序，它把EGS4容纳进来以完成对光子和电子输运过程的模拟，并且对低能电子的输运算法进行了改进。 编辑本段世界赌城蒙特卡罗也是世界著名的赌城，是摩纳哥的标志。富丽堂皇的蒙地卡罗赌场，建于一八六三年，是一幢古色古香以与巍峨的宫殿式建筑物，再加上山明水秀，使游客抵达门前，立即发生好感。门前有一大片广场，是一个花圃，一草一木都修剪整齐，鲜花盛放，七彩缤纷，园旁有一停车场，园尽处一间宫殿式的建筑便是闻名世界的蒙地卡罗赌场了。登台阶入门，站着警卫把守。照摩纳哥法律，本国人不准入赌博，观光客自然欢迎，然后凭护照交十法朗便成为一日的会员，凭此证才能进入赌场。场气派堂皇，墙上的装饰与帷幕，加上白天也亮的钻石般闪

27、烁的水晶灯，满铺的红地毯烘托着，穿着整齐礼服的侍者，气氛上是不同凡响。有适合歌剧表演的大舞台，再过一道门进入一间大厅，便是著名的赌场了。 赌场赌场几乎等于是蒙特罗的小缩影，不管您赌不赌博，如果来到蒙特卡罗没到赌场走一遭，或者试一下手气，那可真是有入宝山空手而返的感觉。只要下点小赌注，看桌上筹码搬家的声音，想像着财富不知几时会向您面前推过来，那种经验和感觉，就值得日后向儿辈夸上老半天了。蒙特卡罗赌场以轮盘为主，现在虽加入其他赌具，但轮盘赌仍最受人欢迎。它受欢迎的理由之一，是赌客有较多获胜机会。这里的轮盘和其他赌场里稍有不同：这里的轮盘赌只有一个零（庄家统吃）而其他地方则有两个零。蒙特卡罗现有轮盘

28、赌十八桌，每个轮盘上有卅七孔（卅六个数字加上零），可容纳小象牙球的落入。赌客们可以在任何数字上下注，如果胜了，庄家付出卅五倍的钱。也可以赌单数或双数，红格或黑格（每一个孔的颜色是红黑相间的），如果下这一类的注，胜了可得与财相同的钱，不过获胜的机会是一比一的。零点的颜色是绿的，要是出了这个数，庄家除了赔系在零字上的赌注外，其他台上各门统吃。单只这个零点便给庄家带来百分之二点七的获胜机会，虽然不多，但已足够维持赌场的开支与盈利了 赛车F1赛事中历史最悠久的就是摩纳哥大奖赛。自1950 年F1大赛在这里问世以来，风景优美的蒙特卡洛城街道已经49次作为F1大奖赛的赛道。这里没有看台，有居民甚至自豪地说，他是站在自己家的阳台上观看比赛的。这里平时是街道，等到正式比赛才加上防护墙，组成了临时赛道。正是这样的原因，这条赛道自1950 年以来几乎没有做过改动。“这是一条一点错误都不能有的赛道。”舒马赫指出：“对赛车的调教必须十分小心，以应付赛道的每一种特点。我的经验是稳定性在摩纳哥是最为重要的一个方面。”驾驭马力强大的F1赛车78次穿越狭窄的街道完成这站比赛对车手来说确实是一次充满刺激的挑战。难怪有人将摩纳哥大奖赛称为F1“王冠上的明珠”，在这里夺得冠军的车手无意中也会被车迷们“看高”一个档次19 / 19