论文部分内容阅读
【摘要】本文主要阐述了如何利用计算机模拟来解决数学建模中的实际问题.首先，提出问题，根据问题的具体模式对其进行分析整理.其次，对上述问题进行数学建模.然后，利用计算机进行模拟，主要分为随机模拟（蒙特—卡洛方法）、离散系统模拟和连续系统模拟三种类型.最后对结果进行分析，说明计算机模拟方法在数学建模中的有效性.
【关键词】计算机模拟；数学建模；随机模拟；离散系统
【中图分类号】O242【文献标识码】A
一、引言
模型（Model）和模型建构（Modeling）不仅仅是科学理论体系中的重要内容，也是我们认识世界的重要工具和方法.计算机技术的飞速发展给许多学科带来了巨大的影响，计算机使问题的求解变得更加简单方便，同时，也使解决问题的领域变得更加宽泛.计算机适合解决不确定、规模大且难以解析化的数学模型.例如，对于一些带随机因素的复杂系统的问题，建模之前常需要做一些简化假设，这可能导致与实际情况相距甚远，解答无法应用.此时，利用计算机进行模拟几乎成为了唯一的选择.在历届全国和國际大学生数学建模比赛（MCM/ICM）中，计算机模拟常用于去求解、检验，是建模过程中非常重要的一种方法[1].
一般地，计算机模拟在以下几种情况中能有效解决问题：
（1）难以在实际环境中进行实验和观察，只能用计算机模拟，比如太空飞行的研究；
（2）需要在短时间内观察到系统发展的全过程，用来估计某些参数对系统变化的影响；
（3）需要对系统进行长时间观察、运行比较，从大量方案中寻求最优方案；
（4）难以用解析式表示的系统；
（5）虽然有解析式，但是分析、计算过程过于复杂，只能借助计算机模拟来提供简单可行的方法.
在通常情况下，计算机模拟是按时间来划分的，因为计算机模拟实质上是系统随时间变化而变化的动态写照.目前，计算机模拟大致可以分为随机模拟（蒙特—卡洛方法）、离散系统模拟和连续系统模拟三类.其中，蒙特—卡洛（MontoCarlo）方法是典型的静态模拟；离散系统模拟和连续系统模拟是属于动态模拟.下面将就具体问题讨论这三种数学建模竞赛中经常用到的模拟方法.
二、问题的定义与分类
数学建模的第一步，就是提出问题，对具体问题进行分析、整理与归类.
1.问题的定义
问题是指不能直接利用已有知识处理，但是可以间接用已有知识处理的情境[2].
2.问题的分类
根据计算机模拟的种类，问题主要可以分为以下三种模式：非线性规划问题、离散系统问题和连续系统问题三种类型.下面举例说明一下这三种不同类型的问题.
（1）非线性规划（nonlinearprogramming）问题
非线性规划是具有非线性约束条件或目标函数的数学规划，研究一个n元实函数在一组等式或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数.
例1非线性规划问题
minf（x）x∈En.s.t.gi（x）≥0i=1，2，…，m.aj≤xj≤bjj=1，2，…，n.
（2）离散系统（discretesystem）问题
离散系统是指系统状态只在有限的时间点或可数的时间点上有随机事件发生的系统.
例如排队系统，显然，状态量的变化只是在离散的随机事件点上完成.假设离散系统状态的变化是在一个时间点上瞬间完成的.
例2离散系统问题：库存问题
在销售部门、工厂等领域中都存在库存问题，库存太多造成浪费以及资金积压，库存太少不能满足需求也会造成损失.部门的工作人员需决定何时进货，进多少，使得所花费的平均费用最少，而收益最大，这就是库存问题.
某企业当天生产的产品必须售出，否则就会变质.该产品单位成本为2.5元，单位产品售价为5元.企业为避免存货过多而造成损失，拟从以下2种库存方案中选出一个较优的方案：
方案甲：按前1天的销售量作为当天的库存量；
方案乙：按前2天的平均销售量作为当天的库存量.
（3）连续系统（continuoussystem）问题
连续系统是指时间和各个组成部分的变量都具有连续变化形式的系统.例如自动控制系统，只有当受控过程和控制方式同时为连续时的系统才称为连续控制系统.
例3连续系统问题：追逐问题
追逐问题如图，正方形ABCD的四个顶点各有一人.在某一时刻，四人同时出发以匀速v=1m/s按顺时针方向追逐下一人，如果他们始终保持对准目标，则最终按螺旋状曲线交汇于中心点O.试求出这种情况下每个人的行进轨迹.
三、模型的建立与计算机模拟
1.随机模拟（蒙特—卡洛方法）
（1）蒙特—卡洛（MontoCarlo）方法简介
蒙特—卡洛（MontoCarlo）方法（或称随机模拟法），是计算机模拟的基础，源于1977年法国科学家蒲丰提出的一种计算圆周率π的方法—随机投针法，即著名的蒲丰投针问题[3].蒙特—卡洛方法的基本思想，是建立一个概率模型，使所求问题的解正好是该模型的参数或其他有关的特征量.然后，通过模拟多次随机抽样实验，统计出某事件发生的百分比.只要实验次数n很大，该百分比便近似于事件发生的概率.蒙特—卡洛方法属于试验数学的一个分支.
（2）模型建立
例1中，对于非线性规划问题
minf（x），x∈En.
s.t.gi（x）≥0（i=1，2，…，m）.
aj≤xj≤bj（j=1，2，…，n）.
用蒙特—卡洛方法求解的基本思想是，在估计的区域{（x1，x2，……，xn）|xj∈[aj，bj]，j=1，2，……，n}. 内随机取若干个试验点，然后从试验点中找出可行点，再从可行点中选择最小点.
假设试验点的第j个分量xj服从[aj，bj]内的均匀分布.
符号假设
P：试验点总数；maxP：最大试验点总数；
K：可行点总数；maxK：最大可行点数；
X：迭代产生的最优点；
Q：迭代产生的最小值f（X），其初始值为计算机所能表示的最大数.
2.离散系统模拟
离散系统模拟是指对离散系统，即系统状态只在有限的时间点或可数的时间点上有随机事件发生的系统进行模拟.例如排队系统.本文例2中討论某企业生产的库存系统的计算机模拟方法，这是排队系统的一个典型例子.下面对例2中的问题进行分析模拟：
（1）模型建立
假定市场对该产品的每天需求量是一个随机变量，并且从以往的统计分析得知它服从正态分布：N（135，22.4）.
计算机模拟的思路如下：
一、获得市场对该产品需求量的数据；
二、计算出按照2种不同方案，经T天后企业所得的利润值；
三、比较大小，并从中选出一个更优的方案.
引入下列记号：
D：每天需求量；
Q1：方案甲当天的库存量；
Q2：方案甲当天的库存量；
S1：方案甲前1天的销售量；
S21：方案乙前1天的销售量；
S22：方案乙前2天的销售量；
S3：方案甲当天实际销售量；
S4：方案乙当天实际销售量；
L1：方案甲当天的利润；
L2：方案乙当天的利润；
TL1：方案甲累计总利润；
TL2：方案甲累计总利润；
T：预定模拟天数.
（2）模型的求解
利用Matlab编程来实现这一过程，这需要建立如下的M-文件：
function[TL1，TL2]=kucun（T，S1，S21，S22）
TL1=0；TL2=0；k=1；
whilek Q1=S1；Q2=（S21 S22）/2；
D=normrnd（135，22.4）；
ifD S3=Q1；
else
S3=D；
end
ifD S4=Q2；
else
S4=D；
end
L1=5*S3-2.5*Q1；L2=5*S4-2.5*Q2；
TL1=TL1 L1；TL2=TL2 L2；
k=k 1；
end
S1=S3；S22=S21；S21=S4；
给出一个初值，反复运行上述程序，通过比较最后可得出每一个方案的优劣.计算机模拟在排队系统中其他方面如加工制造系统、订票系统、计算机系统、交通控制系统等，都有广泛的应用.
3.连续系统模拟
对连续系统的模拟，实际上是将连续状态变量在时间上进行离散化处理，并由此模拟系统的运行状态.下面对例3中的问题进行分析模拟：
（1）模型建立
a.建平面直角坐标系A（x1，y1），B（x2，y2），C（x3，y3），D（x4，y4）.
b.取时间间隔为Δt，计算每一点在各个时刻的坐标.
设某点在t时刻的坐标为（xi，yi），则在t Δt时刻的坐标为（xi vΔtcosα，yi vΔtsinα），
其中cosα=xi 1-xid，sinα=yi 1-yid，
d=（xi 1-xi）2 （yi 1-yi）2.
c.取足够小的ε，当d<ε时结束算法.
d.连接每一个点在各个时刻的位置，即得所求运动轨迹（如图2）.
（2）模型的求解
利用Matlab编程来实现这一过程，这需要建立如下的M-文件：
v=1；dt=0.05；x=[001010]；x=[010100]；fori=1：4plot（x（i），y（i），’.’），holdonendd=20；while（d>0.1）x（5）=x（1）；y（5）=y（1）；fori=1：4d=sqrt（（x（i 1）-x（i））^2 （y（i 1）-y（i））^2）；x（i）=x（i） v*dt*（x（i 1）-x（i））/d；y（i）=y（i） v*dt*（y（i 1）-y（i））/d；plot（x（i），y（i），’.’），holdonendend
四、结果分析
对以上各个例子中的结果进行分析，发现计算机模拟的结果能更加真实的表现系统实际的动态变换过程.事实上，还有很多实际问题都可以用计算机模拟来解决，如背包问题、安排比赛选手的比赛日程、三国时期的“华容道”问题等等都可以用计算机模拟来解决.
总之，使用计算机模拟来进行数学建模，可以使求解更加快捷、方便和精确，另外，也使得解决问题的领域扩大，从离散、连续确定性领域延伸到随机的非确定性领域，计算机模拟正是处理此类问题的重要方法.
【参考文献】
[1]谢国瑞，郝志峰，汪国祥.概率论与数理统计[M].北京：高等教育出版社，2012.
[2]王沫然.Matlab7.0与科学计算[M].北京：电子工业出版社，2011.
[3]赵静，但琦，严尚安，等.数学建模与数学实验[M].北京：高等教育出版社，2010.
【关键词】计算机模拟；数学建模；随机模拟；离散系统
【中图分类号】O242【文献标识码】A
一、引言
模型（Model）和模型建构（Modeling）不仅仅是科学理论体系中的重要内容，也是我们认识世界的重要工具和方法.计算机技术的飞速发展给许多学科带来了巨大的影响，计算机使问题的求解变得更加简单方便，同时，也使解决问题的领域变得更加宽泛.计算机适合解决不确定、规模大且难以解析化的数学模型.例如，对于一些带随机因素的复杂系统的问题，建模之前常需要做一些简化假设，这可能导致与实际情况相距甚远，解答无法应用.此时，利用计算机进行模拟几乎成为了唯一的选择.在历届全国和國际大学生数学建模比赛（MCM/ICM）中，计算机模拟常用于去求解、检验，是建模过程中非常重要的一种方法[1].
一般地，计算机模拟在以下几种情况中能有效解决问题：
（1）难以在实际环境中进行实验和观察，只能用计算机模拟，比如太空飞行的研究；
（2）需要在短时间内观察到系统发展的全过程，用来估计某些参数对系统变化的影响；
（3）需要对系统进行长时间观察、运行比较，从大量方案中寻求最优方案；
（4）难以用解析式表示的系统；
（5）虽然有解析式，但是分析、计算过程过于复杂，只能借助计算机模拟来提供简单可行的方法.
在通常情况下，计算机模拟是按时间来划分的，因为计算机模拟实质上是系统随时间变化而变化的动态写照.目前，计算机模拟大致可以分为随机模拟（蒙特—卡洛方法）、离散系统模拟和连续系统模拟三类.其中，蒙特—卡洛（MontoCarlo）方法是典型的静态模拟；离散系统模拟和连续系统模拟是属于动态模拟.下面将就具体问题讨论这三种数学建模竞赛中经常用到的模拟方法.
二、问题的定义与分类
数学建模的第一步，就是提出问题，对具体问题进行分析、整理与归类.
1.问题的定义
问题是指不能直接利用已有知识处理，但是可以间接用已有知识处理的情境[2].
2.问题的分类
根据计算机模拟的种类，问题主要可以分为以下三种模式：非线性规划问题、离散系统问题和连续系统问题三种类型.下面举例说明一下这三种不同类型的问题.
（1）非线性规划（nonlinearprogramming）问题
非线性规划是具有非线性约束条件或目标函数的数学规划，研究一个n元实函数在一组等式或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数.
例1非线性规划问题
minf（x）x∈En.s.t.gi（x）≥0i=1，2，…，m.aj≤xj≤bjj=1，2，…，n.
（2）离散系统（discretesystem）问题
离散系统是指系统状态只在有限的时间点或可数的时间点上有随机事件发生的系统.
例如排队系统，显然，状态量的变化只是在离散的随机事件点上完成.假设离散系统状态的变化是在一个时间点上瞬间完成的.
例2离散系统问题：库存问题
在销售部门、工厂等领域中都存在库存问题，库存太多造成浪费以及资金积压，库存太少不能满足需求也会造成损失.部门的工作人员需决定何时进货，进多少，使得所花费的平均费用最少，而收益最大，这就是库存问题.
某企业当天生产的产品必须售出，否则就会变质.该产品单位成本为2.5元，单位产品售价为5元.企业为避免存货过多而造成损失，拟从以下2种库存方案中选出一个较优的方案：
方案甲：按前1天的销售量作为当天的库存量；
方案乙：按前2天的平均销售量作为当天的库存量.
（3）连续系统（continuoussystem）问题
连续系统是指时间和各个组成部分的变量都具有连续变化形式的系统.例如自动控制系统，只有当受控过程和控制方式同时为连续时的系统才称为连续控制系统.
例3连续系统问题：追逐问题
追逐问题如图，正方形ABCD的四个顶点各有一人.在某一时刻，四人同时出发以匀速v=1m/s按顺时针方向追逐下一人，如果他们始终保持对准目标，则最终按螺旋状曲线交汇于中心点O.试求出这种情况下每个人的行进轨迹.
三、模型的建立与计算机模拟
1.随机模拟（蒙特—卡洛方法）
（1）蒙特—卡洛（MontoCarlo）方法简介
蒙特—卡洛（MontoCarlo）方法（或称随机模拟法），是计算机模拟的基础，源于1977年法国科学家蒲丰提出的一种计算圆周率π的方法—随机投针法，即著名的蒲丰投针问题[3].蒙特—卡洛方法的基本思想，是建立一个概率模型，使所求问题的解正好是该模型的参数或其他有关的特征量.然后，通过模拟多次随机抽样实验，统计出某事件发生的百分比.只要实验次数n很大，该百分比便近似于事件发生的概率.蒙特—卡洛方法属于试验数学的一个分支.
（2）模型建立
例1中，对于非线性规划问题
minf（x），x∈En.
s.t.gi（x）≥0（i=1，2，…，m）.
aj≤xj≤bj（j=1，2，…，n）.
用蒙特—卡洛方法求解的基本思想是，在估计的区域{（x1，x2，……，xn）|xj∈[aj，bj]，j=1，2，……，n}. 内随机取若干个试验点，然后从试验点中找出可行点，再从可行点中选择最小点.
假设试验点的第j个分量xj服从[aj，bj]内的均匀分布.
符号假设
P：试验点总数；maxP：最大试验点总数；
K：可行点总数；maxK：最大可行点数；
X：迭代产生的最优点；
Q：迭代产生的最小值f（X），其初始值为计算机所能表示的最大数.
2.离散系统模拟
离散系统模拟是指对离散系统，即系统状态只在有限的时间点或可数的时间点上有随机事件发生的系统进行模拟.例如排队系统.本文例2中討论某企业生产的库存系统的计算机模拟方法，这是排队系统的一个典型例子.下面对例2中的问题进行分析模拟：
（1）模型建立
假定市场对该产品的每天需求量是一个随机变量，并且从以往的统计分析得知它服从正态分布：N（135，22.4）.
计算机模拟的思路如下：
一、获得市场对该产品需求量的数据；
二、计算出按照2种不同方案，经T天后企业所得的利润值；
三、比较大小，并从中选出一个更优的方案.
引入下列记号：
D：每天需求量；
Q1：方案甲当天的库存量；
Q2：方案甲当天的库存量；
S1：方案甲前1天的销售量；
S21：方案乙前1天的销售量；
S22：方案乙前2天的销售量；
S3：方案甲当天实际销售量；
S4：方案乙当天实际销售量；
L1：方案甲当天的利润；
L2：方案乙当天的利润；
TL1：方案甲累计总利润；
TL2：方案甲累计总利润；
T：预定模拟天数.
（2）模型的求解
利用Matlab编程来实现这一过程，这需要建立如下的M-文件：
function[TL1，TL2]=kucun（T，S1，S21，S22）
TL1=0；TL2=0；k=1；
whilek
D=normrnd（135，22.4）；
ifD
else
S3=D；
end
ifD
else
S4=D；
end
L1=5*S3-2.5*Q1；L2=5*S4-2.5*Q2；
TL1=TL1 L1；TL2=TL2 L2；
k=k 1；
end
S1=S3；S22=S21；S21=S4；
给出一个初值，反复运行上述程序，通过比较最后可得出每一个方案的优劣.计算机模拟在排队系统中其他方面如加工制造系统、订票系统、计算机系统、交通控制系统等，都有广泛的应用.
3.连续系统模拟
对连续系统的模拟，实际上是将连续状态变量在时间上进行离散化处理，并由此模拟系统的运行状态.下面对例3中的问题进行分析模拟：
（1）模型建立
a.建平面直角坐标系A（x1，y1），B（x2，y2），C（x3，y3），D（x4，y4）.
b.取时间间隔为Δt，计算每一点在各个时刻的坐标.
设某点在t时刻的坐标为（xi，yi），则在t Δt时刻的坐标为（xi vΔtcosα，yi vΔtsinα），
其中cosα=xi 1-xid，sinα=yi 1-yid，
d=（xi 1-xi）2 （yi 1-yi）2.
c.取足够小的ε，当d<ε时结束算法.
d.连接每一个点在各个时刻的位置，即得所求运动轨迹（如图2）.
（2）模型的求解
利用Matlab编程来实现这一过程，这需要建立如下的M-文件：
v=1；dt=0.05；x=[001010]；x=[010100]；fori=1：4plot（x（i），y（i），’.’），holdonendd=20；while（d>0.1）x（5）=x（1）；y（5）=y（1）；fori=1：4d=sqrt（（x（i 1）-x（i））^2 （y（i 1）-y（i））^2）；x（i）=x（i） v*dt*（x（i 1）-x（i））/d；y（i）=y（i） v*dt*（y（i 1）-y（i））/d；plot（x（i），y（i），’.’），holdonendend
四、结果分析
对以上各个例子中的结果进行分析，发现计算机模拟的结果能更加真实的表现系统实际的动态变换过程.事实上，还有很多实际问题都可以用计算机模拟来解决，如背包问题、安排比赛选手的比赛日程、三国时期的“华容道”问题等等都可以用计算机模拟来解决.
总之，使用计算机模拟来进行数学建模，可以使求解更加快捷、方便和精确，另外，也使得解决问题的领域扩大，从离散、连续确定性领域延伸到随机的非确定性领域，计算机模拟正是处理此类问题的重要方法.
【参考文献】
[1]谢国瑞，郝志峰，汪国祥.概率论与数理统计[M].北京：高等教育出版社，2012.
[2]王沫然.Matlab7.0与科学计算[M].北京：电子工业出版社，2011.
[3]赵静，但琦，严尚安，等.数学建模与数学实验[M].北京：高等教育出版社，2010.