第4章 随机模拟Word文档下载推荐.docx
- 文档编号:6364564
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:17
- 大小:170.60KB
第4章 随机模拟Word文档下载推荐.docx
《第4章 随机模拟Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《第4章 随机模拟Word文档下载推荐.docx(17页珍藏版)》请在冰点文库上搜索。
x为M与最近平行线的距离;
θ为针与平行线的夹角。
0≤x≤d,0≤θ≤π。
如果针的一半长度在竖直方向的投影大于从针中点到最近平行线的距离,则针与平行线相交(如图(a)),反之则不相交(如(b)和(c))。
事实上,我们已经看到(再看图4-1所示的3种情况),针中点离边界的距离如果小于半根针的竖直投影,则针就会与边界相交。
这时,代表这个距离和角度的点在正弦曲线x=lsinθ之下。
与此相反,针完全落在两条平行线之间时,相应的点在曲线之上。
这样,可以给出针与平行直线相交的充要条件为:
0≤x≤lsinθ。
见图4-2。
于是,我们把原问题转化为如下问题:
在图4-2中的矩形区域S:
0≤x≤d,0≤θ≤π里随机地投一个点,求点落入阴影区域
的概率p。
由几何概率的求法的知,此概率为两个区域的面积之比,即
。
由微积分可计算得D得面积等于2。
所以
如果
的值已知,则以
代入即可计算得出概率值p。
反之,如果已知概率值p,则可以利用上式求π值。
而概率值P可以用随机模拟的方法得到其近似值:
假设投针N次,其中针与平行线相交n次,则概率n/N可作为p的估计值,于是由
,
可得:
历史上有一些学者曾经亲自做过这个试验,表4-1记录了他们的试验结果,其中,拉扎里尼(Lazzerini)1901年得到的结果与π的精确值最接近,一直到第七位小数才开始不相同。
表4-1
试验者
年份
l/d
投掷次数N
相交次数n
Π的近似值
沃尔夫(Wolf)
1850
0.8
5000
2532
3.1596
福克斯(Fox)
1884
0.75
1030
489
3.1595
Lazzerini
1901
0.83
3408
1808
3.1415
雷纳(Reina)
1925
0.54
2520
859
3.1795
通过这个例子,蒙特卡洛方法的基本思想可见一斑:
设计一个随机试验,使一个事件的概率与某个未知数有关,然后通过重复试验,以频率估计概率,即可求得未知数的近似解。
一般来说,模拟试验的目的有以下几个方面:
(1)系统地比较与评价,在指定的性能指标下对实际存在的或所设计的系统性能做出对比和评价;
(2)系统地分析与预测,分析确定一些因素对整个系统性能的影响以及系统在某些条件下的性能;
(3)系统地优化,在许多因素中找出使系统性能最优的因素参数;
(4)系统地假设检验,用模拟结果与系统实际状态作对比以检验对系统所作假设是否合理。
随着计算机技术的迅速发展和普及,计算机模拟技术的发展也很快。
一方面是从尖端军事科学技术的应用推广到一般民用技术的应用。
计算机模拟技术是随着导弹、原子弹等尖端技术发展起来的。
随着计算机特别是微型计算机的普及,促进了计算机模拟技术的发展。
另一方面是从自然科学的应用推广到社会科学的应用。
模拟方法本来是自然科学和工程技术工作者经常使用的,但是随着计算机技术的发展,社会科学工作者发现,他们也可以在计算机上建立模型,进行模型试验,并且取得了很好的效果。
因此在商业、经济、管理等部门越来越普遍地采用计算机模拟方法。
目前,计算机模拟技术已经是企业使用的最有效的方法之一。
有人对美国1000家大公司做了统计,在公司计划中使用计算机模拟技术的频率占29%,大于其他各种数学方法的使用频率,见表4-2。
表4-2
使用的数学方法
使用频率(%)
计算机模拟
线性规划
网络分析
29
21
14
库存理论
非线性规划
动态规划
12
8
4
整数规划
排队论
其他
3
6
计算机模拟应用得如此广泛,主要在于它在解决如下问题上有较大的优势。
1.无法实施的一类问题
在现实世界中有许多问题无法以付诸实施来解决,例如要预测未来5年或10年的经济计划执行情况,我们不可能让国民经济去实际运行一段时间以取得有关经济指标。
但可以构造一个经济模拟模型,利用尽可能收集到的数据,根据不同设想对其进行模拟实验,从而得到各种预测的经济计划指标。
又如在研究某地区的抗灾能力时,可以在若干假定的条件下,应用计算机模拟来估计自然灾害对于某些设施可能遭受的破坏程度。
2.大量方案的比较和选优
当某个计划的执行存在大量的备选方案时,例如要设计一条地铁线路,由于线路配置和线路参数的变化,若想把全部方案都计算出来进行比较选优,其工作量之大是难以想象的。
这一类问题适宜于用计算机模拟来解决。
电子线路设计的模拟以及企业的财务计划的模拟等等都是属于这种情况。
在国外,已经研究出了许多计算机模拟软件,用来对某些系统的设计进行比较选优,以获得经济合理地方案。
3.大型复杂系统
有一些复杂系统,如宇宙飞船系统、交通运输系统、生产调度系统等,其运行状况难以用一般的理论分析或数学求解的方法来进行。
为此,可以把整个系统分解并构建模拟模型,然后利用模拟实验来检验和判明系统的内部性能和内在联系,作为系统最佳运行的依据。
4.有危险的试验或训练
在研制新产品或者进行新的开拓性试验时,也存在着大量的风险,一旦遇到挫折或失败,会遭到巨大的经济损失,甚至对企业带来致命的打击。
对于这样一类问题,要事先进行各方面的调研和分析,构造模拟模型,并进行模拟实验,然后制定出对策。
在工业发达国家,应用计算机模拟进行投资风险性分析,已经得到了迅速的发展与应用。
还用一种情况是对于某些有危险地呃训练,例如飞行员、宇航员的培训,往往需要利用模拟飞行器在地面上作充分的训练后才能进行实际飞行训练,以保证训练的安全,并能节约大量的人力和财力。
5.无法重复的现象
对于大型工程项目的建设,例如,新建世博会场馆,一条磁悬浮铁路或一个机场,一旦建成后发现有问题,想再改建或重建,需要花费大量的人力、物力和财力。
所以,在设计时如何确定设计参数、安排施工进度和步骤,以及完工后对其他方面的影响等等,都要求事先给出答案。
因此,把要设计的交通系统构造成模拟模型,对将要新建的交通设施反复进行模拟实验。
这样一来,无法重现的现象可以在计算机中反复地重演,为我们提供有关的试验数据。
4.2随机数的产生
计算机模拟能够成功应用的关键是在计算机上实现真正的随机抽样,而随机抽样产生的基础是随机数。
所谓随机数,就是具有给定概率分布的随机变量的可能值。
例如区间(0,1)上均匀分布的随机数。
在随机数中,最简单、最基本、最重要的是(0,1)均匀分布的随机数。
它的产生方法虽简单;
但是其他任何分布的随机变量,都可以通过(0,1)随机数的变换而获得。
一、随机数的产生方法
1.随机数乘
为了产生随机数,可以利用随机数表。
随机数表有0,1,…,9等10个数字组成,相互独立地以等概率0.1的概率出现,这些数字序列叫做随机数字序列。
如果要想得到具有M位有效数字的随机数,只需将表中每个相邻的随机数字合并在一起。
用随机数表产生随机数存在两大缺点。
第一个缺点是它占用计算机大量存储单元,如果存入磁盘或磁带中,还会占用大量的计算机时间。
第二个缺点是,随机数表再大,也很难满足蒙特卡洛方法对随机数需要量非常大的要求。
由于这两个缺点,用随机数产生随机数的方法现在很少被人采用。
2.产生随机数的物理方法
利用某些物理现象可以产生随机数。
再电子计算机上增加一些特殊设备,可以在电子计算机上直接产生随机数,这些特殊设备成为随机数发生器。
其原理是利用电子线路中的噪声或核辐射衰变现象,把具有随机性质过程的随机物理量变换为随机数。
用物理方法产生的随机数,随机性特好,但代价高昂,不能重复,使用不便。
3.产生随机数的数学方法
随机数还可以利用数学迭代或递推公式,产生随机数。
用数学方法产生的随机数存在两大问题,其一,递推公式以及初始值一旦确定后,整个随机数序列便被唯一确定下来了。
或者说,随机数序列中除前几个随机数是选定的外,其他的所有随机数都是被它前面的随机数所唯一确定,不满足随机数相互独立的要求。
其二,既然随机数序列是用递推公式确定的,而在电子计算机上所能表示的[0,1]上的数又是有限多的,因此,这样的随机数序列就不可能不出现重复并出现周期性的循环想象。
由于上述两个原因,常称用数学方法所产生的随机数为伪随机数。
伪随机数的第一个缺点,虽然不能从本质上加以改变,但是,只要产生伪随机数的递推公式选得比较好,随机数的相互独立性是可以近似地满足的。
至于第二个缺点,则不是本质上的。
因为用蒙特卡洛方法解决任何问题时,所使用的随机数个数总是有限的,只要其个数不超过伪随机数序列出现循环现象时的长度就可以了。
用数学方法产生伪随机数非常容易在电子计算机上实现,而且还可以复算。
因此,虽然这种方法存在着一些问题,但是仍然被广泛地在随机模拟方法中使用,是在电子计算机上产生随机数的最主要的方法。
产生随机数的数学方法有迭代取中法、移位法和同余法。
用数论中的同余运算产生伪随机数的数学方法称为同余法。
由于同余法产生伪随机数序列的周期较长,概率统计特性较好,是近来在计算机上应用得最广泛的一种方法。
同余法有加同余法、乘同余法、混合同余法和组合同余法等。
在介绍同余法之前,先回忆一下同余的概念。
一般来说,若两整数A,B之差A-B为整数M的倍数,则称A和B为按M同余,记为
上述定义表面,A-B可被M整除,
由于计算中使用的数一般表示为十进制和二进制两种形式,因此人们在模拟工作中取模数M时,一般都取为10或2的幂。
如果令M=10,则下面几个数都是同余数。
下面我们着重介绍最常用的线性同余法,包括乘同余法和混合同余法。
1949年勒摩尔(Lehmer)首次提出同乘同余法产生均匀随机数,其迭代公式为
1061年,格雷贝格尔(Greenberger)将它推广为
称为混合同余法。
上式中,a为乘子,c为增量,M为模。
若给定初值x0,则可迭代算出x1,x2,…,只要给定了a,c,M就完全确定了数列{xi}。
尽管如此,只要恰当地选取a,c,M,由此产生的数列{xi}在其均匀性、随机性和独立性等方面,仍然非常近似于真正的均匀随机数列,将它们除以M,即可得到[0,1]区间均匀分布的随机数ri:
下面我们用一个具体数值例子,说明用混合同余法产生均匀随机数的计算过程。
设M=16,a=5,c=3,x0=7,分别计算出i=1,2,…,19时均匀随机整数xi和[0,1]区间随机数ri的值,如表4-3所示。
再往下,数列将出现循环。
这就是说,一旦M被确定之后,对于给定的x0,在x0重新在伪随机数序列中出现之前,xi可以有P个不同的值(P≥Ma,c若取得不好,则P会小于M)。
P就是伪随机数发生器的循环周期,我们希望P越大越好。
恰当地选取参数M,a和c,使得伪随机数的循环周期尽量长一些。
表4-3
1
2
5
7
11
10
15
0.375
0.063
0.500
0.688
0.625
0.313
0.750
0.938
9
13
16
0.875
0.563
0.000
0.188
0.125
0.813
0.250
0.438
二、MATLAB软件中随机数的产生
很多计算机软件中都有产生随机数的命令。
甚至有些袖珍计算器也有对应的命令按钮。
下面我们着重介绍数学运算软件MATLAB中相关的命令。
rand(m,n)生成区间(0,1)上的均匀分布的m行n列随机矩阵;
randn(m,n)生成标准正态分布N(0,1)的m行n列随机矩阵;
randperm(N)生成1,2,…,N的一个随机排列。
上述命令生成的都是伪随机数,其生成机制由随机种子控制。
Rand和randn是MATLAB两个最基本的随机数产生函数,它们允许用户自己设置随机种子。
若讲随机种子设为特定值。
就可以使随机模拟成为可再现的。
若将种子设置为系统时间,例如:
rand(‘state’,sum(100*clock)),
则几乎可得到真正的随机序列。
通用随机数生成函数random(name,p1,p2,…,m,n)生成以p1,p2,…为参数的m行n列各种类型分布随机数矩阵。
Name是表示分布类型的字符串,random可适用的分布类型包括’unid’(离散均匀分布),’bino’(二项分布),’unif’(均匀分布),’norm’(正态分布),’poiss’(Possion分布),’exp’(指数分布)等等。
例如random(‘norm’,1,4,1,10)就会产生1行10列正态分布N(1,4)的随机数。
此外,还有几个专用的随机数生成函数:
unidrnd(N,m,n)生成1,2,…,N的等概率m行n列随机矩阵;
binornd(k,p,m,n)生成参数为k,p的m行n列二项分布随机矩阵;
unifrnd(a,b,m,n)生成区间[a,b]上的连续型均匀分布m行n列二项分布随机矩阵。
Normrnd(mu,sigma,m,n)生成均值为mu,均方差为sigma的m行n列正态分布随机矩阵。
利用这些函数,可以方便地生成所需的随机数。
4.3随机模拟的应用
例2
计算面积,考虑图4.3中曲线下方阴影部分D的面积。
利用微积分知识,可以算出该面积等于1/3。
现在我们用蒙特卡洛方法计算D的面积。
构造一个随机试验:
在区域
(如图4-3所示)中随机投一个点,容易得到,这个点正好落在区域
的概率为
我们让计算机产生n个(例如2000个)在区域S中均匀分布的随机点,统计处这n个点中落在区域D中的点的个数(记为m),则
执行上述随机模拟的MATLAB程序如下:
>
clear;
%清空
n=2000;
%确定模拟次数
x=rand(n,1);
%产生2000个(0,1)区间上的均匀分布的随机数作为随机点的横坐标
y=rand(n,1);
%产生2000个(0,1)区间上的均匀分布的随机数作为随机点的纵坐标
c=(x.^2)>
y;
%识别并记录落入D中的随机点
m=sum(c);
%计算落入D中的随机点个数
I=m/n%计算频率作为概率的估计值,并以此作为所求面积的近似值
运行的结果:
I=
0.3370
蒙特卡洛方法的优势还在于,当某图形面积用微积分方法难以计算时,用蒙特卡洛方法依然很方便。
例3报童问题。
报童问题是一个古典的概率统计分析问题,虽然该问题并不复杂,但其应用广泛,是现代企业制定计划进货、销售、库存计划的较为实用的数学模型的基础。
本书第12章习题9也是由该问题简化而得。
有一个报童,每天从报刊发行处购进报纸后零售,每卖一份报纸可赚钱a元,若晚上报纸卖不完则可再退回发行处,此时每退一份报纸要赔钱b元。
报童若购进的报纸太少,不过卖,会少赚钱;
如果购进太多,卖不完,将会赔钱。
轻微报童筹划一下,他应该如何确定每天购进报纸的数量,以使得期望收益达到最大。
显然,应该根据需求量确定购进量,每天的需求量是随机的,报童可以根据以往对报纸需求量的统计来估计每天能卖出k份报纸的概率pk。
设报童每天购进量为n份,而报纸每天的需求量为r份,r为随机变量,其概率分布为
如果这天的需求量r≤n,则他售出r份,退回n-r份;
如果这天的需求量r>n,则n份报纸将全部售完。
所以期望收益为
我们要找到能使L(n)取最大值的n*:
当需求量r的概率分布已知且不太复杂时,我们可以用以上解析的方法求解n*,见本书第12章习题9。
而当需求量r的概率分布比较复杂时,用解析的方法求解n*对中学生朋友就有些困难了。
此时,我们可以用随机模拟的方法来求解。
假设该报童根据以往报纸需求量的统计,估计每天能卖出k份报纸的概率pk见表4-4。
表4-4
k
300
350
400
450
500
550
600
650
700
pk
0.025
0.05
0.1
0.175
0.3
.005
假设a=0.2元,b=0.4元。
对于给定的购进量n值,我们可以利用计算机产生服从以上概率分布的随机数r即可作为报童当天的实际需求量,根据购进量,可以计算出当天报童卖报的实际利润。
经多次模拟试验后(比如模拟1000天的利润)就可获得使报童卖报纸一天的平均利润最大的最优购进量n*。
如何在计算机上产生服从以上概率分布的随机数?
我们可以这样做:
让计算机产生一服从[0,1]区间上的均匀分布的随机数,记为U。
并令Y=1000U。
令
显然,r就是满足要求的随机数。
根据上述思路,我们先定一个购进量n,让计算机产生随机数r,然后判断r是否小于n。
若r小于n,则说明有n-r份报纸卖不掉,所以,当天的利润为ar-(n-r)b;
若r大于等于n,则n份报纸全能卖完,利润为an,如此反复模拟若干次,就可以计算出在购进量为n的情况下,每天的平均利润。
对不同的n进行搜索,就可以找到最佳购进量n*。
假设:
Tm——预定模拟天数;
T——模拟天数累计值;
n——订报量;
n*——最优订报量;
N——订报量n的上界估计值;
L——累计利润值;
Lmax——利润最大值;
L0——利润初始值;
模拟框图见图4-4,模拟结果为n*=450。
利用以上方法不难求出在每天报纸需求量数服从任意分布的情况下,使报童期望利润最大的购进量,而且对该报童问题模拟系统适当修改可用于企业的订货和库存策略研究。
例4单服务台排队系统模拟
我们都有在超市排队付款的经历。
在运筹学这门学科中,有一个分支叫排队论,就是专门研究这种排队系统的。
在本例中,我们仅对单服务台排队系统进行随机模拟。
我们利用随机模拟来了解在单服务台排队系统中第i个顾客在系统中的平均排队时间。
假设第i个顾客到达服务台的时间为ti;
第i个顾客在系统中的排队时间为Wi;
第i个顾客接受服务需要的时间为Si;
第i-1个顾客至第i个顾客到达的时间间隔为Ai(i=1,2,…)。
第一个顾客在t1=0时刻到达,此时系统是空的,因此有下列递推公式
其中顾客接受服务需要的时间Si,第i-1个顾客至第i个顾客到达的时间间隔Ai为随机变量。
假设Si与第i个顾客的购物数量Ki成正比,而Si=aKi,Ki为在1,2,…,N中等概率取值的随机数,其中a为每件商品的平均服务时间,N为顾客最大购物数。
并假设Ai服从参数为lamed(即相继来到服务台的顾客到达的时间间隔的平均值lamed)的指数分布。
为计算平均排队时间E(Wi),我们需重复试验M次,在每次试验中都计算第i个顾客的排队时间,最后统计出其平均值。
我们假定每件商品的平均服务时间a=3(秒);
顾客最大购物数N=15(件);
重复试验次数M=100;
分别对顾客到达的时间间隔的平均值lamed=10(秒),lamed=20(秒),lamed=30(秒),lamed=50(秒)。
模拟的MATLAB程序如下:
forj=1:
100
w
(1)=0;
fori=2:
w(i)=w(i-1)+3*random(‘DiscreteUniform’,15)-random(‘exp’,lamed);
end
c=w>
0;
b(j,:
)=w.*c;
mean(b)
运行结果见表4-5.
表4-5
16.85
30.71
40.35
52.94
68.87
81.00
95.07
106.85
117.54
20
12.48
18.51
23.63
30.53
34.54
39.59
48.91
53.36
61.65
30
7.11
10.27
12.40
12.09
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第4章 随机模拟 随机 模拟