【摘要】本文重点分析了数学建模的特点,探讨了计算机技术与数学建模之间密不可分的联系,阐述了计算机算法设计与计算机相关软件在数学建模竞赛中的作用和地位。
【关键词】数学建模;蒙特卡罗算法;遗传算法
【中图分类号】G623.5 【文献标识码】B 【文章编号】1001-4128(2010)05-0017-02
数学是研究现实世界数量关系和空间形式的科学,在它产生和发展的历史长河中,一直是和各种各样的应用问题紧密相关的。数学的特点不仅在于概念的抽象性、逻辑的严密性,结论的明确性和体系的完整性,而且在于它应用的广泛性,进入20世纪以来,随着科学技术的迅速发展和计算机的日益普及,人们对各种问题的要求越来越精确,使得数学的应用越来越广泛和深入。正如华罗庚所说:“宇宙之大、粒子之微、火箭之速、化工之巧、地球之变、生物之迷、日用之繁等各个方面,无处不有数学的重要贡献。”可见,数学无处不在。由于新技术特别是计算机技术的飞速发展,大量的实际问题需要用计算机来解决,而计算机与实际问题之间需要数学模型来沟通,所以数学建模这一门新兴的学科,在短短几十年的时间迅速辐射至全球大部分国家和地区。80年代初,我国高等院校也陆续开设了数学建模课程,随着数学建模教学活动(包括数学建模课程、数学建模竞赛和数学建模试验课程等)的开展,这门学科越来越得到重视,也深受广大师生的喜爱。
1 数学建模和计算机技术的关系
数学建模(Mathematical Modeling)就是建立数学模型,是利用数学方法解决实际问题的一种实践。即通过抽象、简化、假设、引进变量等处理过程后,将实际问题用数学方式表达,建立起数学模型,然后运用先进的数学方法及计算机技术进行求解。数学建模的过程如图1,在整个过程中模型求解,模型分析,模型检验这三部分需要应用到计算机科学知识,我们可以把这三部分的工作过程用图2来表示。通过图2揭示了利用计算机解决科学计算的步骤,把实际问题转换为程序,要经过一个对问题抽象的过程,建立起完善的数学模型,只有这样,我们才能建立一个设计良好的程序,从中我们也不难看出数学建模在计算机科学技术中的重要性及密不可分的关系。
图1 数学建模的过程
图2 计算机程序建立的过程
2 计算机算法设计在数学建模中的应用
计算机算法设计主要包括:算法及算法复杂性基本概念,算法描述,有效算法最常用的设计策略——递归和分治法,动态规划法的设计要点与适用性,贪心算法,回溯法和分支限界法,许多难解问题的高效算法——概率算法,以及NP完全理论和NP难问题的近似解法。它是一门面向设计,且处于计算机学科核心地位的教育课程,是参加数学建模活动的必修课之一。前文提到数学建模的过程可用图1、2来表示,如果把图1、2合成一个,那么数学建模的过程又可以用图3来表示。
图3 数学建模的过程
通过图3我们可以看到算法在数学建模过程中的重要性,那么数学建模经常会用到哪些算法呢?
2.1 概率算法
许多情况下,当算法在执行过程中面临一个选择时,随机性选择常比最优选择省时。因此概率算法可在很大程度上降低算法的复杂度。一般情况下,可将概率算法大致分为四类:数值概率算法,蒙特卡罗(Monte Carlo)算法,拉斯维加斯(Las Vegas)算法和舍伍德(Sherwood)算法。这里只介绍一下蒙特卡罗算法,它又称随机性模拟算法,是通过计算机仿真来解决问题的算法,同时可以通过模拟可以来检验自己模型的正确性,是数学建模竞赛时必用的方法。它的基本思想是,为了求解数学、物理、工程技术以及管理等方面的问题,首先建立一个概率模型或随机过程,使它们的参数,如概率分布或数学期望等问题的解;然后通过对模型或过程的观察或抽样试验来计算所求参数的统计特征,并用算术平均值作为所求解的近似值。对于随机性问题,有时还可以根据实际物理背景的概率法则,用电子计算机直接进行抽样试验,从而求得问题的解答。
例如1997年的A题是关于零件参数设计问题,每个零件都有自己的标定值,也都有自己的容差等级,而求解最优的组合方案将要面对着的是一极其复杂的公式和108种容差选取方案,根本不可能求解析解,那如何去找到最优的方案呢?随机性模拟搜索最优方案就是其中的一种方法,在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案,然后通过蒙特卡罗算法仿真出大量的方案,从中选取一个最佳的。
蒙特卡罗方法有很强的适应性,问题的几何形状的复杂性对它的影响不大。随着电子计算机的发展和科学技术问题的日趋复杂,蒙特卡罗方法的应用也越来越广泛。它不仅较好地解决了多重积分计算、微分方程求解、积分方程求解、特征值计算和非线性方程组求解等高难度和复杂的数学计算问题,而且在统计物理、核物理、真空技术、系统科学、信息科学 、公用事业、地质、医学,可靠性及计算机科学等广泛的领域都得到成功的应用。
2.2 并行算法
并行算法根据对象的不同分为数值并行算法和非数值并行算法两种。 多项式与线性代数方程组,矩阵与非线性方程,插值、逼近及其应用,数字信号处理,小波变换,快速傅利耶变换等内容属于数值算法。非数值算法一般包括线性表、栈、队列和串,树,图,排序、查找与文件操作,并行算法等,主要是为符号运算而设计的并行算法。常用的非数值并行算法有模拟退火算法、遗传算法、神经网络算法。由于近几年的数学建模竞赛题越来越复杂,很多问题没有什么很好的模型可以借鉴,于是这三个算法很多时候可以派上用场。例如97年A题用模拟退火算法,00年B题和01年B题用神经网络算法。遗传算法是一种基于自然群体遗传进化机制的自适应全局优化概率搜索算法,作为一种有效的工具,已广泛地应用于最优化问题求解之中。它摒弃了传统的搜索方式,模拟自然界生物进化过程,采用人工的方式对目标空间进行随机化搜索。
此外,在很多数学建模竞赛场合中,还会用到动态规划、回溯搜索、分治算法、分支定界等算法。由此可见,只有具备一定的计算机知识才能更好的处理数据,发现事物之间的内在的联系,才能更好的进行知识的转换,才能更好的构造出最优的模型。总之,具有必备的计算机知识是培养建模意识的关键,是培养数模创新能力的前提。计算机也为数学建模竞赛活动提供了有力的工具。
3 计算机软件在数学建模中的应用
在参加数学建模活动中,经常会使用一些计算机软件。常见的通用数学软件包包括Matlab和Mathematica和Maple,其中Matlab是一个高性能的科技计算软件,广泛应用于数学计算、建模、仿真和数据分析处理及工程作图。Mathematica 是数值和符号计算的代表性软件,Maple以符号运算、公式推导见长。而Madab在数值计算、矩阵计算和图形绘制方面更有优势,因此可以结合起来使用。Lingo/Lindo是计算最优化问题的专用数学软件。Lindo用于求解线性规划和二次规划,Lingo除了具有Lindo的全部功能外,还可以用于求解非线性规划,也可以用于一些线性和非线性方程组的求解以及代数方程求根等,二者都可以求解整数规划。此外,还有统计分析软件SPSS和SAS。
总之,利用计算机技术来开展数学建模,必将有利于数学模型的建立、求解、演算和表达,为探索者创造出理想的背景,同时也使我们的计算机用得越来越好、越来越活。数学建模中计算机的应用,使数学建模的进步如虎添翼;计算机中数学建模方法的使用,使得计算机的发展日益迅速,计算机技术与数学建模的结合,必将推动两者的快速发展。
参考文献
[1] 王晓东编著.计算机算法设计与分析(第2版).电子工业出版社,2006
[2] 白其峥主编.数学建模案例分析.北京:海洋出版社,2000
[3] 赵晗,郑娟娟,李阳.浅谈计算机在数学建模中的作用[J].当代经济(下半月),2007年第3期
