1-随机模拟与蒙特卡洛方法课件.ppt

1、随机模拟与蒙特卡洛方法随机模拟与蒙特卡洛方法o模拟：把某一现实的或抽象的系统的部分状模拟：把某一现实的或抽象的系统的部分状态或特征用另一系统态或特征用另一系统(称为模型称为模型)来代替或模来代替或模仿仿o计算机模拟在复杂系统或过程的研究中发挥计算机模拟在复杂系统或过程的研究中发挥着越来超重要的作用着越来超重要的作用o随机模拟和蒙特卡洛随机模拟和蒙特卡洛(Monte CarIo)方法方法蒙特卡洛方法的基本思想蒙特卡洛方法的基本思想o基本思想：把各种随机事件的概率特征基本思想：把各种随机事件的概率特征 与与数学分析的解联系起来，用试验的方法确定数学分析的解联系起来，用试验的方法确定事件的相应概率与

2、数学期望事件的相应概率与数学期望o特点：概率模型的解是由试验得到的，而不特点：概率模型的解是由试验得到的，而不是计算出来的。是计算出来的。o作用：可以解决其它方法无法解决的实际问作用：可以解决其它方法无法解决的实际问题、对理论研究进行补充及辅助题、对理论研究进行补充及辅助随机模拟试验的目的随机模拟试验的目的o系统的比较与评价，在指定的性能指标下对实际存系统的比较与评价，在指定的性能指标下对实际存在的或所设计的系统性能做出对比和评价；在的或所设计的系统性能做出对比和评价；o系统的分析与预测，分析确定一些因素对整个系统系统的分析与预测，分析确定一些因素对整个系统性能的影响以及系统在某些条件下的性能

3、；性能的影响以及系统在某些条件下的性能；o系统的优化，在许多因素中找出使系统性能最优的系统的优化，在许多因素中找出使系统性能最优的因素参数；因素参数；o系统的假设检验，用模拟结果与系统实际状态作对系统的假设检验，用模拟结果与系统实际状态作对比以检验对系统所作假设是否合理。比以检验对系统所作假设是否合理。随机模拟的优势o对无法实施的一类问题进行模拟对无法实施的一类问题进行模拟o对大量方案的比较和选优对大量方案的比较和选优o对大型复杂系统进行模拟对大型复杂系统进行模拟o对有危险的试验或训练进行模拟对有危险的试验或训练进行模拟o对无法重复的现象进行模拟对无法重复的现象进行模拟随机数的产生o随机模拟能

4、够成功应用的关键是在计算机上随机模拟能够成功应用的关键是在计算机上实现随机抽样，而随机抽样的基础是随机数实现随机抽样，而随机抽样的基础是随机数o随机数：具有给定概率分布的随机变量的可随机数：具有给定概率分布的随机变量的可能值。能值。o最重要的随机数：最重要的随机数：(0，1)均匀分布的随机均匀分布的随机数数o伪随机数伪随机数o产生随机数的方法：迭代取中法、移位法、产生随机数的方法：迭代取中法、移位法、同余法同余法 进行计算机模拟需要大样本的均匀分布随机数数列，如何获得？真随机数：真随机数：由随机物理过程来产生，如：放射性衰变、电子设备的热噪音、宇宙射线的触发时间 伪随机数：伪随机数：由计算机按

5、递推公式大量产生22122mod2/2rrnnrnnxxx冯.诺曼平方取中法 mxmcaxxnnnn/)(mod(1乘加同余 0,1nMATLAB软件中随机数的产生软件中随机数的产生orand(m,n)生成区间生成区间(0,1)上的均匀分布的上的均匀分布的m行行n 列随机矩阵；列随机矩阵；orandn(m,n)生成标准正态分布生成标准正态分布N(0,1)的的m行行n 列随机矩阵；列随机矩阵；orandperm(N)生成生成1,2,N的一个随机排列的一个随机排列o随机种子随机种子 例将种子设置为系统时间，：例将种子设置为系统时间，：orand(state，surn(100*clock)蒲丰投针问

6、题蒲丰投针问题 1777年法国科学家蒲丰提出了下面的著名问年法国科学家蒲丰提出了下面的著名问题，这是几何概率的一个早期例子。题，这是几何概率的一个早期例子。平面上画着一些平行线，它们之间的距离都等平面上画着一些平行线，它们之间的距离都等于于a，向此平面任意投一长度为，向此平面任意投一长度为l的针（的针（la），试），试求此针与任一平行线相交的概率求此针与任一平行线相交的概率 根据几何概率的知识可求得此概率为根据几何概率的知识可求得此概率为 。由于最后的答案与由于最后的答案与有关，因此不少人想利用它来有关，因此不少人想利用它来计算计算的数值，其方法是投针的数值，其方法是投针N次，计算出针与线次，

7、计算出针与线相交的次数相交的次数n，再用频率值，再用频率值n/N作为概率作为概率p的值代入的值代入上式，求得上式，求得 2lN/an 。2alp 程序如下：程序如下：a=2;l=1.2;N=100000;n=0;for i=1:1:Nx=a*rand(1)/2;t=pi*rand(1);rand(1);if xl*sin(t)/2n=n+1;endendnpii=2*l*N/n/a增加增加N值试验，改变值试验，改变a和和l的值，重新试验，观察的值，重新试验，观察pii的值。的值。随机模拟的应用：报童问题o问题提出：报童，每天批发报纸后零售，每卖一份报报童，每天批发报纸后零售，每卖一份报可赚钱可

8、赚钱a元，卖不完则可再退回每退一份报要赔钱元，卖不完则可再退回每退一份报要赔钱b元元o历史数据：历史数据：k300350400450500550600650700pk0.0250.050.10.1750.30.1750.10.050.025随机模拟的应用：报童问题o利润公式：(),.ranr brnLnarn随机模拟的应用：报童问题o产生服从经验概率分布的随机数产生服从经验概率分布的随机数o产生产生一一0，1上的均匀分布的随机数上的均匀分布的随机数U，Y=1000*U3000Y2535025Y7540075Y175450175Y350r500350Y650550650Y825600825Y92

9、5650925Y975700975Y1000随机模拟的应用：报童问题o具体实现：对n=300,700,分别进行以下操作：o产生随机数r;o计算利润Lo重复N次进行平均o选出L平均值最大的n随机模拟的应用：码头卸货效率分析 问题的提出问题的提出有一个只有一个舶位的小型卸货专用码头，船舶运送某些有一个只有一个舶位的小型卸货专用码头，船舶运送某些特定的货物（如矿砂，原油等）在此码头卸货。若相邻两特定的货物（如矿砂，原油等）在此码头卸货。若相邻两艘船到达的时间间隔在艘船到达的时间间隔在15分钟到分钟到145分钟之间变化，每艘分钟之间变化，每艘船的卸货时间由船的大小、类型所决定，在船的卸货时间由船的大小

10、、类型所决定，在45分钟到分钟到90分分钟的范围内变化。钟的范围内变化。现在需对该码头的卸货效率进行分析，即设法计算每艘船现在需对该码头的卸货效率进行分析，即设法计算每艘船在港口停留的平均时间和最长时间；每艘船等待卸货的时在港口停留的平均时间和最长时间；每艘船等待卸货的时间；卸货设备的闲置时间的百分比等。间；卸货设备的闲置时间的百分比等。数学模型的建立数学模型的建立为简单计，假设前一艘船卸货结束后马上离开码头，后一艘船立为简单计，假设前一艘船卸货结束后马上离开码头，后一艘船立即可以开始卸货。即可以开始卸货。引进如下记号：引进如下记号：第第j j艘船的到达时间。艘船的到达时间。第第j j艘船与第

11、艘船与第j+1j+1艘船到达之间的时间间隔。艘船到达之间的时间间隔。第第j j艘船的卸货时间。艘船的卸货时间。第第j j艘船的离开时间。艘船的离开时间。第第j j艘船的等待时间。艘船的等待时间。第第j j艘船在港口的停留时间。艘船在港口的停留时间。卸完第卸完第j j艘到开始卸第艘到开始卸第j+1j+1艘船之间的设备闲置时间。艘船之间的设备闲置时间。船只最长等待时间。船只最长等待时间。船只平均等待时间。船只平均等待时间。船只最长停留时间。船只最长停留时间。船只平均停留时间。船只平均停留时间。设备闲置总时间。设备闲置总时间。设备闲置百分比。设备闲置百分比。jajujljwjsjdmwjtawmsa

12、slddRnnn12,nt ttnuuu,21n111,(2,3,)jjjataatjn 为了分析码头的效率，我们考虑共有条船到达码头卸货的情形，原则上讲，越大越好。由于船到达码头的时间和卸货时间都是不确定的，因此，我们要用随机模拟的方法来建立数学模型。首先，我们假设两船到达之间的时间间隔是一个随机变量，服从15分钟到145分钟之间的均匀分布；各船卸货时间也是一个服从15分钟到45分钟间均匀分布的随机变量。然后我们可以用发生均匀分布的随机数的方法，分别产生 n 个15,145和45,90之间的随机数和模拟n艘船两两之间到达的时间间隔和各艘船的卸货时间。利用船舶到达的时间间隔，设初始时刻为0，我

13、们可以计算出各船的到达时间有了这些数据后，我们就可以计算各艘船在码头等待有了这些数据后，我们就可以计算各艘船在码头等待卸货的时间，离开的时间，以及两艘船之间卸货设备卸货的时间，离开的时间，以及两艘船之间卸货设备的闲置时间。的闲置时间。第一艘船到港就可以卸货，卸完货即可离开，因而有第一艘船到港就可以卸货，卸完货即可离开，因而有11110,wlau 而在该船到达之前设备闲置，即而在该船到达之前设备闲置，即11da以后各艘船到达码头时，若前一艘船已经离港，则马上以后各艘船到达码头时，若前一艘船已经离港，则马上可以卸货，否则必须等待，等待时间为上一艘船的离港可以卸货，否则必须等待，等待时间为上一艘船的

14、离港时间与本船到达时间之差，从而第时间与本船到达时间之差，从而第j j艘船的等待时间为艘船的等待时间为1110,(2,3,),jjjjjjjalwjnlaal 1max(0,),(2,3,)jjjwlajn 由此可得由此可得jjjjlawu若第艘船需等待卸货，设备不会闲置，但若第艘船的到达若第艘船需等待卸货，设备不会闲置，但若第艘船的到达时间迟于第艘船的离开时间，那么这段时间差就是设备的时间迟于第艘船的离开时间，那么这段时间差就是设备的闲置时间，即闲置时间，即111,(2,3,),jjjjjjjalaldjnal 0 1max(0,),(2,3,)jjjwaljn 船只停留时间船只停留时间 为

15、为(1,2,)jjjslajn 以及船只平均和最大停留时间以及平均和最大等待时间以及船只平均和最大停留时间以及平均和最大等待时间11111,1,m axm axnmjajjnjnmjajjnjssssnwwwwn 也可以计算设备闲置总时间和闲置时间百分比也可以计算设备闲置总时间和闲置时间百分比 1,nlljdnjdddRl jtju由于由于和和是随机产生的，重复进行计算，结果是会有差异的。所以仅用是随机产生的，重复进行计算，结果是会有差异的。所以仅用一次计算的结果作为分析的依据是不合理的。较好的做法是重一次计算的结果作为分析的依据是不合理的。较好的做法是重复进行多次模拟，取各项数据的平均值作为

16、分析的依据复进行多次模拟，取各项数据的平均值作为分析的依据。模型的求解与应用模型的求解与应用我们以n100为例，列出6次模拟的结果如表1所示，其中所有时间均以分钟为单位。表 1船在港口的平均停留时间1068510111611294船在港口的最长停留时间287180233280234264船的平均等待时间392035504427船的最长等待时间213118172203167184设备闲置时间的百分比0.180.170.150.20.140.21若为了提高码头的卸货能力，增加了部分劳力和改善了设备从而使卸货时间减少至35至75分钟之间，两艘船到达的间隔仍为15145分钟，六次模拟的结果如表2所示。

17、表 2船在港口的平均停留时间746264676773船在港口的最长停留时间161116167178173190船的平均等待时间19610121216110从表从表2 2可见，每艘船的卸货时间缩短了可见，每艘船的卸货时间缩短了15201520分钟，等待时间分钟，等待时间明显缩短，但设备闲置时间的百分比增加了一倍。为了提高明显缩短，但设备闲置时间的百分比增加了一倍。为了提高效率，可以接纳更多的船只来港卸货，于是将两艘船到达的效率，可以接纳更多的船只来港卸货，于是将两艘船到达的时间间隔缩短为时间间隔缩短为1012010120分钟。在装载时间仍为分钟。在装载时间仍为35753575分钟的分钟的情况下，

18、再进行情况下，再进行6 6次模拟，其结果如表次模拟，其结果如表3 3所示。此时等待时间所示。此时等待时间有增加了，但设备闲置时间减少了。有增加了，但设备闲置时间减少了。表 3船在港口的平均停留时间114799688126115船在港口的最长停留时间248224205171371223船的平均等待时间572441357161船的最长等待时间175152155122309173设备闲置时间的百分比0.150.190.120.140.170.06随机模拟的应用：眼科病床的合理安排 o医院就医排队是大家都非常熟悉的现象，它以这样或那样的形式出现在我们面前，例如，患者到门诊就诊、到收费处划价、到药房取药

19、、到注射室打针、等待住院等，往往需要排队等待接受某种服务。o我们考虑某医院眼科病床的合理安排的数学建模问题。o该医院眼科门诊每天开放，住院部共有病床79张。该医院眼科手术主要分四大类：白内障、视网膜疾病、青光眼和外伤。附录中给出了2008年7月13日至2008年9月11日这段时间里各类病人的情况。o白内障手术较简单，而且没有急症。目前该院是每周一、三做白内障手术，此类病人的术前准备时间只需1、2天。做两只眼的病人比做一只眼的要多一些，大约占到60%。如果要做双眼是周一先做一只，周三再做另一只。o外伤疾病通常属于急症，病床有空时立即安排住院，住院后第二天便会安排手术。o其他眼科疾病比较复杂，有各

20、种不同情况，但大致住院以后2-3天内就可以接受手术，主要是术后的观察时间较长。这类疾病手术时间可根据需要安排，一般不安排在周一、周三。由于急症数量较少，建模时这些眼科疾病可不考虑急症。o该医院眼科手术条件比较充分，在考虑病床安排时可不考虑手术条件的限制，但考虑到手术医生的安排问题，通常情况下白内障手术与其他眼科手术（急症除外）不安排在同一天做。当前该住院部对全体非急症病人是按照FCFS（First come,First serve）规则安排住院，但等待住院病人队列却越来越长，医院方面希望你们能通过数学建模来帮助解决该住院部的病床合理安排问题，以提高对医院资源的有效利用。随机模拟的应用：眼科病床

21、的合理安排 o问题一：试分析确定合理的评价指标体系，用以评价该问题的病床安排模型的优劣。o问题二：试就该住院部当前的情况，建立合理的病床安排模型，以根据已知的第二天拟出院病人数来确定第二天应该安排哪些病人住院。并对你们的模型利用问题一中的指标体系作出评价。o问题三：作为病人，自然希望尽早知道自己大约何时能住院。能否根据当时住院病人及等待住院病人的统计情况，在病人门诊时即告知其大致入住时间区间。o问题四：若该住院部周六、周日不安排手术，请你们重新回答问题二，医院的手术时间安排是否应作出相应调整?o问题五：有人从便于管理的角度提出建议，在一般情形下，医院病床安排可采取使各类病人占用病床的比例大致固定的方案，试就此方案，建立使得所有病人在系统内的平均逗留时间（含等待入院及住院时间）最短的病床比例分配模型。随机模拟的应用：眼科病床的合理安排