数学建模常用的十种解题方法
数学建模常用的十种解题方法 摘要
当需要从定量的角度分析和研究一个实际问题时，人们就要在深入调查研究、了解对象信息、作出简化假设、分析内在规律等工作的基础上，用数学的符号和语言，把它表述为数学式子，也就是数学模型，然后用通过计算得到的模型结果来解释实际问题，并接受实际的检验。这个建立数学模型的全过程就称为数学建模。数学建模的十种常用方法有蒙特卡罗算法；数据拟合、参数估计、插值等数据处理算法；解决线性规划、整数规划、多元规划、二次规划等规划类问题的数学规划算法；图论算法；动态规划、回溯搜索、分治算法、分支定界等计算机算法；最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法；网格算法和穷举法；一些连续离散化方法；数值分析算法；图象处理算法。
关键词：数学建模；蒙特卡罗算法；数据处理算法；数学规划算法；图论算法 一、蒙特卡罗算法
蒙特卡罗算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法。在工程、通讯、金融等技术问题中, 实验数据很难获取, 或实验数据的获取需耗费很多的人力、物力, 对此, 用计算机随机模拟就是最简单、经济、实用的方法; 此外, 对一些复杂的计算问题, 如非线性议程组求解、最优化、积分微分方程及一些偏微分方程的解⑿, 蒙特卡罗方法也是非常有效的。
一般情况下, 蒙特卜罗算法在二重积分中用均匀随机数计算积分比较简单, 但精度不太理想。通过方差分析, 论证了利用有利随机数, 可以使积分计算的精度达到最优。本文给出算例, 并用MA TA LA B实现。
1蒙特卡罗计算重积分的最简算法-------均匀随机数法
二重积分的蒙特卡罗方法(均匀随机数)
实际计算中常常要遇到如⎰⎰f (x , y )dxdy D 的二重积分, 也常常发现许多时候被积函数的原函数很难求出, 或者原函数根本就不是初等函数, 对于这样的重积分, 可以设计一种蒙特卡罗的方法计算。
定理1 (1) 设式f (x , y )区域D 上的有界函数, 用均匀随机数计算⎰⎰f (x , y )dxdy
D 的方法:
(l) 取一个包含D 的矩形区域Ω,a ≦x ≦b, c ≦y ≦d , 其面积A =(b 一a) (d 一c) ;
(x y ),i=1,…,n 在Ω上的均匀分布随机数列, 不妨设(x y ), j=1，…k 为落在D 中i , j i , j
的k 个随机数,
则n 充分大时, 有
定理2 用定理1的公式（1）作近似计算时，其方差为
证略。
2 蒙特卡罗计算重积分的一般方法-----任意随机数法
2.1 二重积分的蒙特卡罗算法(一般随机数)
定理3 设f (x , y )区域D 上的有界函数，用一般的随机数计算⎰⎰f (x , y )dxdy D 的方法：
(l) 取一个包含D 的矩形区域Ω,a ≦x ≦b, c ≦y ≦d , 其面积A =(b 一a) (d 一c) ;
取任一概率密度函数g (x , y )，满足
i , i ⎰⎰g (x , y )dxdy =1Ω； i , i (x y )，i=1,…,n, 是以g (x , y )为概率密度的随机数列，设(x y )，i-1, …k, 为落在D 中的随机数，则n 充分大时，有
证略。
3 蒙特卡罗计算重积分的最优算法—有利随机数法
任意随机数都能用于积分计算, 对于不同的随机数, 计算结果的方差显然不同, 在定理3 中,
取
即方差最小，
称为有利密度函数，以g (x , y )为概率密度的随机数称为有利随
机数。这样得到方差最优的蒙特卡罗算法, 叙述如下:
定理5 根据二重积分的最优蒙特卡罗算法(有利随机数), 设f (x , y )区域D 上的有界函数，f (x , y )≧0，那么按如下步骤得到
(l) 取一个包含D 的矩形区域Ω； 取有利概率密度
i , i 时，计算方差为零, ⎰⎰f (x , y )dxdy D 方差最优值。 其中c=⎰⎰f (x , y )dxdy D ； i , i (x y )，i=1,…,n, 是以g (x , y )为概率密度的随机数列，设(x y )，i-1, …k, 为落在D
中的随机数，则n 充分大时，有
实际计算中, 由于c 是要计算的, 不可能事先得到, 所以只能先估算c 。
二、数据处理算法
数据处理算法有数据拟合、参数估计、插值等，比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab 作为工具。 1数据拟合
在实验中，实验和戡测常常会产生大量的数据。为了解释这些数据或者根据这些数据做出预测、判断，给决策者提供重要的依据。需要对测量数据进行拟合，寻找一个反映数据变化规律的函数。它所处理的数据量大而且不能保证每一个数据没有误差，所以要求一个函数严格通过每一个数据点是不合理的。数据拟合方法求拟合函数。
例：在某化学反应中，测得生成物的质量浓度y(10-3g /cm3) 与时间t （min ）的关系如表所示
显然，连续函数关系y(t)是客观存在的。但是通过表中的数据不可能确切地得到这种关系。何况，由于仪器和环境的影响，测量数据难免有误差。因此只能寻求一个近拟表达式
y= (t)
寻求合理的近拟表达式，以反映数据变化的规律，这种方法就是数据拟合方法。
数据拟合需要解决两个问题：第一，选择什么类型的函数ϕ(t)作为拟合函数（数学模型）；第二，对于选定的拟合函数，如何确定拟合函数中的参数。
数学模型应建立在合理假设的基础上，假设的合理性首先体现在选择某种类型的拟合函数使之符合数据变化的趋势（总体的变化规律）。拟合函数的选择比较灵活，可以选择线性函数、多项式函数、指数函数、三角函数或其它函数，这应根据数据分布的趋势作出选择。为了问题叙述的方便，将例1的数据表写成一般的形式
（1）．线性拟合（线性模型）
假设拟合函数是线性函数，即拟合函数的图形是一条平面上的直线。而表中的数据点未能精确地落在一条直线上的原因是实验数据的误差。则下一步是确定函数 y= a + b x
中系数a 和b 各等于多少？从几何背景来考虑，就是要以a 和b 作为待定系数，确定一条平面直线使得表中数据所对应的10个点尽可能地靠近这条直线。一般来讲，数据点将不会全部落在这条直线上，如果第k 个点的数据恰好落在这条直线上，则这个点的坐标满足直线的方程，即
a+bxk =yk
如果这个点不在直线上，则它的坐标不满足直线方程，有一个绝对值为|a+bxk -y k |的差异（残差）。于是全部点处的总误差是∑|a+bxk -y k |
k =110
这是关于a 和b 的一个二元函数，合理的做法是选取a 和b ，使得这个函数取最小值。但是在实际求解问题时为了操作上的方便，常常是求a 和b 使得函数 F (a , b )=∑（a+bxk -y k ）2
k =110
达到极小。为了求该函数的极小值点，令
得
求解这个二元线性方程组便得待定系数a 和b ，从而得线性拟合函数y=a+bx。下图中直线是数据的线性拟合的结果。
（2）．二次函数拟合（二次多项式模型）
假设拟合函数不是线性函数，而是一个二次多项式函数。即拟合函数的图形是一条平面上的抛物线，而表中的数据点未能精确地落在这条抛物线上的原因是实验数据的误差。则下一步是确定函数
y=a0+a1x+a2x 2
中系数a 0,a 1和a 2各等于多少？从几何背景来考虑，就是要以a 0,a 1和a 2为待定系数，确定二次曲线使得表中数据所对应的10个点尽可能地靠近这条曲线。一般来讲，数据点将不会全部落在这条曲线上，如果第k 个点的数据恰好落在曲线上，则这个点的坐标满足二次曲线的方程，即
a 0+a1x k +a2x k 2=yk
这是关于a 0,a 1和a 2的一个三元函数，合理的做法是选取a 0,a 1和a 2，使得这个函数取最小值。为了求该函数的极小值点，令
得
这是关于待定系数a 0,a 1和a 2的线性方程组，写成等价的形式为
这就是法方程，求解这一方程组可得二次拟合函数中的三个待定系数。下图反映了例题所给数据的二次曲线拟合的结果
（3）数据的n 次多项式拟合（略）
2. 参数估计
数学建模的一个重要工作是建立变量间的数学关系式，但公式中总是涉及一些参数。
求模型中的参数的估计值有三种常用的方法：图解法，统计法，机理分析法 。
（1）图解法：对经验模型的精度不高，只需对参数做出粗略估计时刻采用图解法。
（2）统计法：参数估计的统计处理，往往用最小二乘法估计。
（3）机理分析法：统计分析法应用于变量间存在相关关系的情形，并且需要较多数据位基础。
3. 插值
插值的基本思想 ·
◎已知有n +1个节点(x j , y j )，j = 0,1,…, n，其中x j 互不相同，节点（x j y j ）可看成由某个函数 y= f（x ）产生;
◎构造一个相对简单的函数 y=P(x);
◎使P 通过全部节点, 即 P (x k ) = y k ,k=0,1,…, n ;
◎用P (x)作为函数f ( x )的近似