蒙特卡洛介绍

1、王健华 交通运输工程 蒙特卡洛 Monte Carlo蒙特卡洛的基本思想及产生蒙特卡洛的方法基础用蒙特卡洛方法解用蒙特卡洛方法解决食堂排队问题目 录蒙特卡洛方法的优缺点及发展蒙特卡洛的基本思想及产生 MC方法亦称为随机模拟方法，有时方法亦称为随机模拟方法，有时也称为随机抽样实验方法。他的基本思也称为随机抽样实验方法。他的基本思想是，为了求解数学、物理、工程技术想是，为了求解数学、物理、工程技术以及生产管理方面的问题，首先建立一以及生产管理方面的问题，首先建立一个概率模型或随机过程，使它的参数等个概率模型或随机过程，使它的参数等于随机问题的解；然后通过对模型或者于随机问题的解；然后通过对模型或者

2、过程的观察或抽样实验来计算所求参数过程的观察或抽样实验来计算所求参数的统计特征，最后给出所求解的近似值。的统计特征，最后给出所求解的近似值。蒙特卡洛的基本思想及产生 假设所要求的假设所要求的x是随机变量是随机变量 的数学期望的数学期望 ，那么近似确定那么近似确定x的方法是对的方法是对 进行进行N次重复抽样，产生次重复抽样，产生相互独立的相互独立的 值的序列值的序列 ，并计算其算术，并计算其算术平均值：平均值：根据克尔莫格罗夫加强大数定理有：根据克尔莫格罗夫加强大数定理有：因此，当因此，当N充分大时，充分大时，成立的概率为成立的概率为1，亦即可以用，亦即可以用 作为所求量作为所求量x的估计的估计

3、值。值。蒙特卡洛的基本思想及产生 MC MC理论依据理论依据: : 均匀分布的算术平均收敛于真值均匀分布的算术平均收敛于真值 ( (大数法则大数法则) ) 置信水平下的统计误差置信水平下的统计误差 ( (中心极限中心极限) ) MC MC方法可以解决的问题：方法可以解决的问题： 确定性的数学问题，如计算多重积分，求逆矩，确定性的数学问题，如计算多重积分，求逆矩，解线性方程组等。解线性方程组等。随机性问题，如中子在介质中的扩散等。随机性问题，如中子在介质中的扩散等。蒙特卡洛的基本思想及产生 MC方法的定名和系统的发展约始于二十世纪方法的定名和系统的发展约始于二十世纪四十年代，它的名字来源于摩纳哥

4、蒙特卡洛城市四十年代，它的名字来源于摩纳哥蒙特卡洛城市的名字，但如果从方法特征的角度来说，可以一的名字，但如果从方法特征的角度来说，可以一直追溯到十九世纪后半叶的直追溯到十九世纪后半叶的蒲丰随机投针实验蒲丰随机投针实验，即所谓的即所谓的蒲丰问题蒲丰问题。蒙特卡洛的方法基础进行计算机模进行计算机模拟需要大样本拟需要大样本的均匀分布随的均匀分布随机数数列，如机数数列，如何获得？何获得？伪随机数的产生伪随机数的产生真随机数：真随机数：由随机物理过程来产生，例如：放射性衰变、电子设备的热噪 音、宇宙射线的触发时间等等 伪随机数伪随机数：由计算机按递推公式大量产生蒙特卡洛的方法基础 设 为2s个数码，自

5、乘后，去头截尾，然后相应的除以 或 ，作为0,1上的伪随机数，如此重复这一过程，直至或者为0，或者与已出现的数字重复（周期性）时为止。公式表示如下：伪随机数的产生伪随机数的产生x 表示不超过x的最大整数X=a (mod M) 表示x等于a被M除的余数蒙特卡洛的方法基础例：十进制2s=4,并取 =6406， 则 =6406， =41036836， 而 即为410368/ 的余数， 所以， 如此重复，则有 伪随机数的产生伪随机数的产生 蒙特卡洛的方法基础蒙特卡洛的方法基础伪随机数的产生伪随机数的产生自 开始出现周期，故序列长度（从初值到发生周期或退化前，序列中的伪随机数的个数）为20。结论结论蒙特

6、卡洛的方法基础伪随机数的检验伪随机数的检验均匀性检验均匀性检验: :0,1分成k个相等子区间，进行N次抽样，投入各子区间如均匀,则各区间落入数Ni应为 12kiiiNNNNkNi可视为(，)的一组无关样本测量，服从则(k)蒙特卡洛的方法基础独立性检验独立性检验: : 即xi与xi+1的前后无关性0,1上进行2N次抽样，分成两个序列132121:,.,.,iNXx xxx2422:,.,.,iNYx xxx在XY平面内划分kk方格，如独立, 则各格内落入数应为,12222kiji jijNnNnk则服从c2分布满足以上统计性检验的递推抽样序列，可视为满足以上统计性检验的递推抽样序列，可视为0,1

7、0,1均匀分布伪随机数均匀分布伪随机数蒙特卡洛的方法基础随机变量的抽样随机变量的抽样直接抽样法直接抽样法：求分布函数 ) )01xF xf x dx则令 )xF )x1 F例例 对指数分布的直接抽样 )., 00, 0,其它xexfx蒙特卡洛的方法基础例例 对指数分布的直接抽样 )., 00, 0,其它xexfx积分得到分布函数 ) )xxtxedtedttfxF10令 )xeF1则指数分布的随机变量抽样为蒙特卡洛方法与Matlab结合蒙特卡洛方法与Visual Basic结合蒙特卡洛方法与Excel结合蒙特卡洛方法解蒲丰投针试验蒲丰投针试验 1777年年,法国科学家蒲丰法国科学家蒲丰(Buf

8、fon)提出了投针提出了投针试验问题试验问题.平面上画有等距离为平面上画有等距离为a(a0)的一些平行直的一些平行直线线,现向此平面任意投掷一根长为现向此平面任意投掷一根长为( ba )的针的针,试求试求针与某一平行直线相交的概率针与某一平行直线相交的概率.解解,直直线线的的距距离离到到最最近近的的一一条条平平行行针针的的中中点点表表示示针针投投到到平平面面上上时时以以Mxax M.夹夹角角表表示示针针与与该该平平行行直直线线的的 .),(完完全全确确定定置置可可由由那那么么针针落落在在平平面面上上的的位位 xax M矩形区域矩形区域果与果与投针试验的所有可能结投针试验的所有可能结0 ,20)

9、,( axxS.中中的的所所有有点点一一一一对对应应由投掷的任意性可知由投掷的任意性可知这是一个几何概型问题这是一个几何概型问题. .中中的的点点满满足足发发生生的的充充分分必必要要条条件件为为针针与与某某一一平平行行直直线线相相交交所所关关心心的的事事件件SA .0,sin20 bxo的面积的面积的面积的面积SGSGAP )()()(2dsin20 ab .22abab o蒲丰投针试验的应用及意义蒲丰投针试验的应用及意义2)(abAP 那么那么的近似值代入上式的近似值代入上式作为作为即可即可则频率值则频率值的次数的次数测出针与平行直线相交测出针与平行直线相交很大时很大时当投针试验次数当投针试

10、验次数根据频率的稳定性根据频率的稳定性,)(,APnmmn2abnm .2ambn . 的的近近似似值值利利用用上上式式可可计计算算圆圆周周率率蒙特卡洛方法解a=1; % 设置两条平行线之间的距离b=0.6; % 投针的长度counter=0; % 针与平行线相交的次数n=10000000; % 投掷的次数x=unifrnd(0,a/2,1,n); %产生n个（0，a/2）之间均匀分布的随机数，这里a/2是投针的中点到最近的平行线的距离phi=unifrnd(0,pi,1,n); % 产生n个（0，pi）之间均匀分布的随机数，这里pi是投针到最近的平行线的角度for i=1:nif x(i)b

11、*sin(phi(i)/2 % 只要x小于b*sin（phi（i）/2,则相交counter=counter+1;endendfrequency=counter/n; % 计算相交的频率，即相交次数与总次数比Pi=2*b/(a*frequency) % 从相交的频率求pi使用使用蒙特卡洛法与蒙特卡洛法与Matlab结合结合求求的近似值的近似值蒙特卡洛方法解蒙特卡洛方法解 利用求单位正方形与内接圆面积的比例关系来求得的近似值 。单位圆的1/4面积是一个扇形，它是边长为1单位正方形的一部分。 如果能求出扇形面积s1在正方形面积s中占的比例k=s1/s，它的值也等于/4，从而就计算得到的值。 怎样求

12、出扇形面积在正方形面积中占的比例k呢？蒙特卡洛法是在正方形中随机投入很多点，使所投的点落在正方形中每一个位置的机会相等。有些点将落在扇形内，而另一些点将会落在扇形外，落在扇形内的点数m与所投点的总数n之间比m/n即为k的近似值。使用使用蒙特卡洛法与蒙特卡洛法与VB结合结合求求的近似值的近似值蒙特卡洛方法解Private Sub Command1_Click() Dim Pi As Double, x As Double, y As Double Dim m As Long, n As Long Randomize Timer 随机数初始化 n = Val(Text1.Text) 读入投放次数n

13、 If n = 0 Then MsgBox 请输入投放次数n Exit Sub End If m = 0 For I = 1 To n x = Rnd() y = Rnd() If x 2 + y 2 = 1 Then m = m + 1 判断是否在扇形内 Next I Pi = 4 * m / n 计算出的近似值 Text2.Text = Str(Pi)End Sub蒙特卡洛方法解蒙特卡洛方法解使用使用蒙特卡洛法与蒙特卡洛法与Excel结合结合求求的近似值的近似值原理：面积为原理：面积为1的正方形内一内切圆。随机扔一点在圆的正方形内一内切圆。随机扔一点在圆内的概率为内的概率为/4。那么用。那

14、么用Monte Carlo求出概率使之等于求出概率使之等于/4，则可以计算出，则可以计算出。方法：使用方法：使用excel的的rand（）函数取随机数，以及二维坐标圆的公式（）函数取随机数，以及二维坐标圆的公式 x2+y2=A2。第一步：第一步：A1代表扔一点后距正方形右边距离，代表扔一点后距正方形右边距离，B1代表扔一点后距正方形底代表扔一点后距正方形底边距离，在边距离，在A1输入输入 =rand（），在（），在B1输入输入=rand（），在（），在C1输入输入=IF(A1-0.5)2+(B1-0.5)20.52,4,0)第二步：用第二步：用excel拖动填充功能，向下拖单元格，想做多少次拖

15、动填充功能，向下拖单元格，想做多少次montecarlo模拟，就拖多少行，越多越准确。假设拖模拟，就拖多少行，越多越准确。假设拖100行。行。第三部：在第三部：在C101输入输入=average（C1：C100),所得结果即为所得结果即为。蒙特卡洛方法解用蒙特卡洛方法解决食堂排队问题 用蒙特卡洛法在用蒙特卡洛法在Excel上对大学食堂的窗口服务状上对大学食堂的窗口服务状态和排队等待问题进行模拟，态和排队等待问题进行模拟，分别模拟了食堂在开设一个分别模拟了食堂在开设一个窗口和两个窗口的情况下学窗口和两个窗口的情况下学生的排队问题，通过生的排队问题，通过500次次模拟的统计分析得出，该方模拟的统计

16、分析得出，该方法具有简便、易行、实用性法具有简便、易行、实用性强的特点，为决策者提供了强的特点，为决策者提供了参考依据。参考依据。我要我要吃吃 饭饭用蒙特卡洛方法解决食堂排队问题 学生食堂的排队问题是一个学生们十分关心的问题，学生食堂的排队问题是一个学生们十分关心的问题，学生希望增加窗口数，减少排队等待时间。然而就食堂的学生希望增加窗口数，减少排队等待时间。然而就食堂的角度来说，虽说增加窗口数量可以减少排队等待时间，提角度来说，虽说增加窗口数量可以减少排队等待时间，提高学生对该食堂的满意度，从而让更多的学生到该食堂就高学生对该食堂的满意度，从而让更多的学生到该食堂就餐，但是同时也会增加食堂的运

17、营成本，因此如何在这两餐，但是同时也会增加食堂的运营成本，因此如何在这两者之间进行权衡，找到最佳的窗口数量，对学生和食堂双者之间进行权衡，找到最佳的窗口数量，对学生和食堂双方来说都是很重要的。蒙特卡罗方法，或称计算机随机模方来说都是很重要的。蒙特卡罗方法，或称计算机随机模拟方法，是一种基于拟方法，是一种基于“随机数随机数”的计算方法，通过建立动的计算方法，通过建立动态模型，模拟食堂窗口的排队问题，当只有一个窗口服务态模型，模拟食堂窗口的排队问题，当只有一个窗口服务的情况下，前一个学生未被服务完毕的时候，后一个学生的情况下，前一个学生未被服务完毕的时候，后一个学生必须等待，直到前一个学生离开服务

18、台，后一个学生才能必须等待，直到前一个学生离开服务台，后一个学生才能被服务。而如果有两个窗口服务的时候，则可以节省等待被服务。而如果有两个窗口服务的时候，则可以节省等待时间。时间。用蒙特卡洛方法解决食堂排队问题 在Excel下建立模拟模型，分别模拟单一窗口W1和两个窗口W2的模拟量变化情况。通过对比两个窗口的平均等待时间T等模拟量，做出决策是否增加窗口： 其中， 为第i个学生的等待时间。1、模型建立、模型建立用蒙特卡洛方法解决食堂排队问题 令 为第i个学生的到达时刻； 为第i个学生的到达间隔，它通常是一个随机数； 为第i个学生的服务开始时刻； 为第i个学生的服务完成时刻； 为第i个学生的服务时

19、间，它通常是一个随机数； 为第i个学生的等待时间； 为第i个学生的逗留时间时间。(1)学生到达间隔，服务时间学生到达间隔及服务时 间为不可控变量，用蒙特卡洛法产生随机数。(2)到达时刻 (3)开始服务时刻用蒙特卡洛方法解决食堂排队问题(4)等待时间(5)完成时刻(6)总逗留时间用蒙特卡洛方法解决食堂排队问题2、认识几个、认识几个Excel常用函数常用函数(1)产生按历史数据统计规律分布的随机数公式：=VLOOKUP(RAND()，表左上角地址：表右下角地址，变量所在列)公式中的表为随机数区间表。(2)IF条件函数:=IF(logical_test，value_if_true，value_if_

20、false)公式中第一项为逻辑判断语句，随后分别为正确时的返回值和错误时的返回值。用蒙特卡洛方法解决食堂排队问题(3)COUNTIF函数:=COUNTIF(rang,criteria)该公式用于统计在一定判断标准下满足条件的个数，其中公式中第一项为数据所在范围；第二项为判断标准；既满足第二项条件的第一项数据的个数。(4)其他常用函数：MAX:返回样本的最大值；MIN:返回样本的最小值；AVERAGE:返回样本的均值；STDEV:返回样本的标准方差；SUM:返回样本的代数和。用蒙特卡洛方法解决食堂排队问题学生序号到达间隔达到时刻服务时刻等待时间服务时间完成时间总逗留时间10.000.30100.

21、000.122020.300.55300.120.422530.550.73500.420.803040.730.85700.800.963550.850.94900.961.004060.941.00110学生到达时间间隔的分布统计学生到达时间间隔的分布统计用蒙特卡洛方法解决食堂排队问题单一窗口模型仿真结果单一窗口模型仿真结果用蒙特卡洛方法解决食堂排队问题两个窗口模拟模型两个窗口模拟模型 两个窗口和单个窗口相比，其余各变量不变，只有开始服务时刻有所变化。在两个窗口的情况下，判断何时能够开始服务要看两个窗口的状态。当学生到达时刻比两个窗口的开始空闲时刻都早时，学生得排队等待，直到至少有一个窗口

22、达到空闲状态才开始接受服务，所以这时的“开始服务时刻”应等于先进人空闲状态的那个窗口的“开始空闲时刻”(即最早开始空闲时刻)；当学生到达时刻比任意一个窗口的开始空闲时刻晚时，窗口可以立刻开始服务，所以这时的“开始服务时刻”应等于学生到达时刻。综上所述，在两个窗口的模拟问题中，我们需要在Excel中新增两列，分别为“窗口一的空闲时刻”和“窗口二的空闲时刻”，并且“开始服务时刻”的公式也要有所改变。用蒙特卡洛方法解决食堂排队问题窗口一的空闲时刻窗口一的空闲时刻： 在第一个学生被服务时，窗口二保持空闲。所以窗口一的空闲时刻等于第一个学生的完成时刻。当学生陆续到达后，如果窗口一早于窗口二到达空闲状态，则学生来到窗口一，这时窗口一的下一个开始空闲时刻等于该学生的服务完成时刻，窗口二的开始空闲时刻不变;如