数学建模选修大作业

中华女子学院

成绩

2014 — 2015学年第二学期期末考试
（论文类）




论文题目 数学建模算法之蒙特卡罗算法







课程代码 01

课程名称 数学建模

学 号 9

姓 名 陈可心

院 系 计算机系

专 业 计算机科学与技术

考试时间 2015年5月27日


一、数学建模十大算法

1、蒙特卡罗算法

该算法又称随机性模拟 算法，是通过计算机仿真来解决问题的算法，
同时可以通过模拟可以来检验自己模型的正确性，是比赛时 必用的方法。
接下来本文将着重介绍这一算法。

2、数据拟合、参数估计、插值等数据处理算法

比赛中通常会遇到大量的数据需要处 理，而处理数据的关键就在于这
些算法，通常使用Matlab作为工具。

3、线性规划、整数规划、多元规划、二次规划等规划类问题

建模竞赛大多数问题属 于最优化问题，很多时候这些问题可以用数学
规划算法来描述，通常使用Lindo、Lingo软件实 现。这个也是我们数学

建模选修课时主要介绍的问题，所以对这方面比较熟悉，也了解了 Lindo、
Lingo软件的基本用法。

4、图论算法

这类算法可以分为很多种，包括最短路、网络流、二分图等算法，
涉及到图论的问题可以用这 些方法解决，上学期数据结构课程以及离
散数学课程中都有介绍。它提供了对很多问题都很有效的一种简 单而系统
的建模方式。

5、动态规划、回溯搜索、分治算法、分支定界等计算机算法

这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中

6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法
这些问题是用来解决 一些较困难的最优化问题的算法，对于有些问题
非常有帮助，但是算法的实现比较困难，需慎重使用。< br>
7、网格算法和穷举法

网格算法和穷举法都是暴力搜索最优点的算法，在很 多竞赛题中有应
用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最
好使用 一些高级语言作为编程工具。

8、
一些连续离散化方法

< br>很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散
的数据，因此将其离散化后进 行差分代替微分、求和代替积分等思想是非
常重要的。

9、数值分析算法

如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的
算法比如方程组求解、矩阵 运算、函数积分等算法就需要额外编写库函数
进行调用。

10、
图象处理算法

赛题中有一类问题与图形有关，即使与图形无关，论文 中也应该要不
乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使
用Mat lab进行处理。

二、蒙特卡罗方法

算法简介

蒙特·卡罗方法（Monte Carlo method），也称统计模拟方法，1946
年，美国拉斯阿莫斯国家实验室的三位科学家John von Neumann,Stan Ulam
和 Nick Metropolis共同发明了，蒙 特卡罗方法。此算法被评为20世纪
最伟大的十大算法之一。是二十世纪四十年代中期由于科学技术的发 展和
电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重
要的数值计算方法 。是指使用来解决很多计算问题的方法。由于传统的经

验方法由于不能逼近真实的物理过 程，很难得到满意的结果，而蒙特卡罗
方法由于能够真实地模拟实际物理过程，故解决问题与实际非常符 合，可
以得到很圆满的结果。与它对应的是确定性算法。蒙特·卡罗方法在金融
工程学，宏观经 济学，计算物理学（如粒子输运计算、量子热力学计算、
计算）等领域应用广泛。

蒙特卡罗方法的特点?

蒙特卡罗方法通过抓住事物运动的几何数量和几何特征，利用 数学方
法来加以模拟，即进行一种数字模拟实验。它是以一个概率模型为基础，
按照这个模型所 描绘的过程，通过模拟实验的结果，作为问题的近似解。

蒙特卡罗方法与一般计算方法有很大 区别，一般计算方法对于解决多
维或因素复杂的问题非常困难，而蒙特卡罗方法对于解决这方面的问题却
比较简单。其特点如下：
1、直接追踪粒子，物理思路清晰，易于理解。
2、 采用随机抽样的方法，较真切的模拟粒子输运的过程，反映了统
计涨落的规律。
3、不受系统多维、多因素等复杂性的限制，是解决复杂系统粒子输
运问题的好方法。

蒙特卡罗方法的基本原理及思想如下：当所要求解的问题是某种事件
出现的概率，或者是某个随 机变量的期望值时，它们可以通过某种“试

验”的方法，得到这种事件出现的频率，或者 这个随机变数的平均值，并
用它们作为问题的解。这就是蒙特卡罗方法的基本思想。蒙特卡罗方法通过抓住事物运动的几何数量和几何特征，利用数学方法来加以模拟，即进
行一种数字模拟实验。它是 以一个概率模型为基础，按照这个模型所描绘
的过程，通过模拟实验的结果，作为问题的近似解。

适用模型

假设我们要计算一个不规则图形的面积，那么图形的不规则程度和分< br>析性计算（比如，积分）的复杂程度是成正比的。蒙特卡洛方法是怎么计
算的呢？，我们可以想象 把图形画在一块方形布上，然后找来一袋豆子，
然后将所有豆子洒在布上，落在图形内豆子的重量比上那 块布上所有豆子
的重量再乘以布的面积就是他所要求的图形的面积。这确实是一个求面积
的好方 法，将整个坐标轴看成一个固定的面积，然后均匀的这个分成N（N
的大小取决于划分的步长）个点，然 后找出N个点中有多少个点是属于阴
影部分中，假设这个值为k，则阴影部分的面积就求出来了。

此方法是利用蒙特卡罗方法计算阴影部分面积，是把豆子均匀分布在
布上；就计算结果的精 度而言，取决点的分割是否够密，即N是否够大；

在数值积分法中，利用求单位圆的14的面 积来求得Pi4从而得到
Pi。单位圆的14面积是一个扇形，它是边长为1单位正方形的一部分。只要能求出扇形面积S1在正方形面积S中占的比例K=S1S就立即能得到
S1，从而得到Pi的 值。怎样求出扇形面积在正方形面积中占的比例K呢？

一个办法是在正方形中随机投入很 多点，使所投的点落在正方形中每一个
位置的机会相等看其中有多少个点落在扇形内。将落在扇形内的点 数m与
所投点的总数n的比mn作为k的近似值。P落在扇形内的充要条件是
x
2
?y
2
?1
。


s1mP i
已知：K=
s
，K
?
n
，s=1，s1=
4，求Pi。

s1mmm
?*s
由
sn
，知s1
?
n
=
n
，

Pim
*4
4n
而s1=，则Pi=


程序：

* 利用蒙特卡洛算法近似求圆周率Pi*

#include<>

#include<>

#include<>

#define COUNT 800 *循环取样次数，每次取样范围依次变大*

void main()

{







*













}

y=rand()*RAND_MAX;

if((x*x+y*y)<=1)

num++; *统计落在四分之一圆之内的点数*

double x,y;

int num=0;

int i;

for(i=0;i


{

x=rand()*RAND_MAX; *RAND_MAX=32767，包含在<>中
printf(值等于：%fn

}

printf(

结果：测试6次的结果显示：

循环取样次数

求得的Pi值

800


8000


80000


800000


8000000





（可以看出: 随着点数的增加，求得的Pi值渐渐接近真实值。）

此外，蒙特· 卡罗方法在金融工程学，宏观经济学，计算物理学(如
粒子输运计算、量子热力学计算、空气动力学计算 )等领域应用广泛。

算法应用实例

例：在我方某前沿防守地域，敌人以一 个炮排（含两门火炮）为单位
对我方进行干扰和破坏．为躲避我方打击，敌方对其阵地进行了伪装并经< br>常变换射击地点． 经过长期观察发现，我方指挥所对敌方目标的指示有
50％是准确的，而我方 火力单位，在指示正确时，有13的概率能毁伤敌
人一门火炮，有16的概率能全部消灭敌人．现在希望 能用某种方式把我
方将要对敌人实施的1次打击结果显现出来，利用频率稳定性，确定有效
射击 (毁伤一门炮或全部消灭)的概率.

分析： 这是一个复杂概率问题，可以通过理论计算得到相应的概率.
为了直观地显示我方射击的过程，现采用模拟的方式。

1. 问题分析

需要模拟出以下两件事：

[1] 观察所对目标的指示正确与否 模拟试验有两种结 果，每一种结果出
现的概率都是12。因此，可用投掷一枚硬币的方式予以确定,当硬币出现
正 面时为指示正确，反之为不正确。

[2] 当指示正确时，我方火力单位的射击结果情况。模 拟试验有三种结果：
毁伤一门火炮的可能性为13，毁伤两门的可能性为16，没能毁伤敌火