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

随机模拟与蒙特卡洛方法11/21/20221随机模拟与蒙特卡洛方法11/21/20221随机模拟与蒙特卡洛方法模拟：把某一现实的或抽象的系统的部分状态或特征用另一系统(称为模型)来代替或模仿计算机模拟在复杂系统或过程的研究中发挥着越来超重要的作用随机模拟和蒙特卡洛(MonteCarIo)方法11/21/20222随机模拟与蒙特卡洛方法模拟：把某一现实的或抽象的系统的部分状蒙特卡洛方法的基本思想基本思想：把各种随机事件的概率特征与数学分析的解联系起来，用试验的方法确定事件的相应概率与数学期望特点：概率模型的解是由试验得到的，而不是计算出来的。作用：可以解决其它方法无法解决的实际问题、对理论研究进行补充及辅助11/21/20223蒙特卡洛方法的基本思想基本思想：把各种随机事件的概率特征与随机模拟试验的目的系统的比较与评价，在指定的性能指标下对实际存在的或所设计的系统性能做出对比和评价；系统的分析与预测，分析确定一些因素对整个系统性能的影响以及系统在某些条件下的性能；系统的优化，在许多因素中找出使系统性能最优的因素参数；系统的假设检验，用模拟结果与系统实际状态作对比以检验对系统所作假设是否合理。11/21/20224随机模拟试验的目的系统的比较与评价，在指定的性能指标下对实际随机模拟的优势对无法实施的一类问题进行模拟对大量方案的比较和选优对大型复杂系统进行模拟对有危险的试验或训练进行模拟对无法重复的现象进行模拟11/21/20225随机模拟的优势对无法实施的一类问题进行模拟11/21/202随机数的产生随机模拟能够成功应用的关键是在计算机上实现随机抽样，而随机抽样的基础是随机数随机数：具有给定概率分布的随机变量的可能值。最重要的随机数：(0，1)均匀分布的随机数伪随机数产生随机数的方法：迭代取中法、移位法、同余法11/21/20226随机数的产生随机模拟能够成功应用的关键是在计算机上实现随机抽进行计算机模拟需要大样本的均匀分布随机数数列，如何获得？真随机数：由随机物理过程来产生，如：放射性衰变、电子设备的热噪音、宇宙射线的触发时间伪随机数：由计算机按递推公式大量产生冯.诺曼平方取中法

乘加同余

11/21/20227进行计算机模拟需要大样本的均匀分布随机数数列，如MATLAB软件中随机数的产生rand(m,n)生成区间(0,1)上的均匀分布的m行n列随机矩阵；randn(m,n)生成标准正态分布N(0,1)的m行n列随机矩阵；randperm(N)生成1,2,…,N的一个随机排列随机种子例将种子设置为系统时间，：rand(‘state’，surn(100*clock))11/21/20228MATLAB软件中随机数的产生rand(m,n)生成区间蒲丰投针问题

1777年法国科学家蒲丰提出了下面的著名问题，这是几何概率的一个早期例子。

平面上画着一些平行线，它们之间的距离都等于a，向此平面任意投一长度为l的针（l<a），试求此针与任一平行线相交的概率．

根据几何概率的知识可求得此概率为。

由于最后的答案与π有关，因此不少人想利用它来计算π的数值，其方法是投针N次，计算出针与线相交的次数n，再用频率值n/N作为概率p的值代入上式，求得2lN/an。11/21/20229蒲丰投针问题

1777年法国科学家蒲丰提出了下面程序如下：

a=2;

l=1.2;

N=100000;

n=0;

fori=1:1:N

x=a*rand(1)/2;

t=pi*rand(1);

rand(1);

ifx<l*sin(t)/2

n=n+1;

end

end

n

pii=2*l*N/n/a

增加N值试验，改变a和l的值，重新试验，观察pii的值。11/21/202210程序如下：

a=2;

l=1.2;

N=100000;

n=随机模拟的应用：报童问题问题提出：报童，每天批发报纸后零售，每卖一份报可赚钱a元，卖不完则可再退回每退一份报要赔钱b元历史数据：k300350400450500550600650700pk0.0250.050.10.1750.30.1750.10.050.02511/21/202211随机模拟的应用：报童问题问题提出：报童，每天批发报纸后零售随机模拟的应用：报童问题利润公式：11/21/202212随机模拟的应用：报童问题利润公式：11/21/202212随机模拟的应用：报童问题产生服从经验概率分布的随机数产生一[0，1]上的均匀分布的随机数U，Y=1000*U11/21/202213随机模拟的应用：报童问题产生服从经验概率分布的随机数11/随机模拟的应用：报童问题具体实现：对n=300,…,700,分别进行以下操作：产生随机数r;计算利润L重复N次进行平均选出L平均值最大的n11/21/202214随机模拟的应用：报童问题具体实现：对n=300,…,700随机模拟的应用：码头卸货效率分析问题的提出有一个只有一个舶位的小型卸货专用码头，船舶运送某些特定的货物（如矿砂，原油等）在此码头卸货。若相邻两艘船到达的时间间隔在15分钟到145分钟之间变化，每艘船的卸货时间由船的大小、类型所决定，在45分钟到90分钟的范围内变化。现在需对该码头的卸货效率进行分析，即设法计算每艘船在港口停留的平均时间和最长时间；每艘船等待卸货的时间；卸货设备的闲置时间的百分比等。11/21/202215随机模拟的应用：码头卸货效率分析问题的提出11/21/20数学模型的建立为简单计，假设前一艘船卸货结束后马上离开码头，后一艘船立即可以开始卸货。引进如下记号：——第j艘船的到达时间。——第j艘船与第j+1艘船到达之间的时间间隔。——第j艘船的卸货时间。——第j艘船的离开时间。——第j艘船的等待时间。——第j艘船在港口的停留时间。——卸完第j艘到开始卸第j+1艘船之间的设备闲置时间。——船只最长等待时间。——船只平均等待时间。——船只最长停留时间。——船只平均停留时间。——设备闲置总时间。——设备闲置百分比。11/21/202216数学模型的建立11/21/202216为了分析码头的效率，我们考虑共有条船到达码头卸货的情形，原则上讲，越大越好。由于船到达码头的时间和卸货时间都是不确定的，因此，我们要用随机模拟的方法来建立数学模型。首先，我们假设两船到达之间的时间间隔是一个随机变量，服从15分钟到145分钟之间的均匀分布；各船卸货时间也是一个服从15分钟到45分钟间均匀分布的随机变量。然后我们可以用发生均匀分布的随机数的方法，分别产生n个[15,145]和[45,90]之间的随机数和模拟n艘船两两之间到达的时间间隔和各艘船的卸货时间。利用船舶到达的时间间隔，设初始时刻为0，我们可以计算出各船的到达时间。11/21/202217为了分析码头的效率，我们考虑共有条船到达码头卸货的情形，原则有了这些数据后，我们就可以计算各艘船在码头等待卸货的时间，离开的时间，以及两艘船之间卸货设备的闲置时间。第一艘船到港就可以卸货，卸完货即可离开，因而有而在该船到达之前设备闲置，即以后各艘船到达码头时，若前一艘船已经离港，则马上可以卸货，否则必须等待，等待时间为上一艘船的离港时间与本船到达时间之差，从而第j艘船的等待时间为11/21/202218有了这些数据后，我们就可以计算各艘船在码头等待卸货的时间，离由此可得若第艘船需等待卸货，设备不会闲置，但若第艘船的到达时间迟于第艘船的离开时间，那么这段时间差就是设备的闲置时间，即11/21/202219由此可得若第艘船需等待卸货，设备不会闲置，但若第艘船的到达时船只停留时间为以及船只平均和最大停留时间以及平均和最大等待时间11/21/202220船只停留时间为以及船只平均和最大停留时间以及平均和最大等待也可以计算设备闲置总时间和闲置时间百分比

由于和是随机产生的，重复进行计算，结果是会有差异的。所以仅用一次计算的结果作为分析的依据是不合理的。较好的做法是重复进行多次模拟，取各项数据的平均值作为分析的依据。11/21/202221也可以计算设备闲置总时间和闲置时间百分比由于和是随机产生的模型的求解与应用我们以n＝100为例，列出6次模拟的结果如表1所示，其中所有时间均以分钟为单位。表1船在港口的平均停留时间1068510111611294船在港口的最长停留时间287180233280234264船的平均等待时间392035504427船的最长等待时间213118172203167184设备闲置时间的百分比0.180.170.150.20.140.21若为了提高码头的卸货能力，增加了部分劳力和改善了设备从而使卸货时间减少至35至75分钟之间，两艘船到达的间隔仍为15—145分钟，六次模拟的结果如表2所示。表2船在港口的平均停留时间746264676773船在港口的最长停留时间161116167178173190船的平均等待时间19610121216船的最长等待时间10258102110104131设备闲置时间的百分比0.250.330.320.30.310.2711/21/202222模型的求解与应用表1船在港口的平均停留时间1068从表2可见，每艘船的卸货时间缩短了15—20分钟，等待时间明显缩短，但设备闲置时间的百分比增加了一倍。为了提高效率，可以接纳更多的船只来港卸货，于是将两艘船到达的时间间隔缩短为10—120分钟。在装载时间仍为35—75分钟的情况下，再进行6次模拟，其结果如表3所示。此时等待时间有增加了，但设备闲置时间减少了。表3船在港口的平均停留时间114799688126115船在港口的最长停留时间248224205171371223船的平均等待时间572441357161船的最长等待时间175152155122309173设备闲置时间的百分比0.150.190.120.140.170.0611/21/202223从表2可见，每艘船的卸货时间缩短了15—20分钟，等待时间明随机模拟的应用：眼科病床的合理安排医院就医排队是大家都非常熟悉的现象，它以这样或那样的形式出现在我们面前，例如，患者到门诊就诊、到收费处划价、到药房取药、到注射室打针、等待住院等，往往需要排队等待接受某种服务。我们考虑某医院眼科病床的合理安排的数学建模问题。该医院眼科门诊每天开放，住院部共有病床79张。该医院眼科手术主要分四大类：白内障、视网膜疾病、青光眼和外伤。附录中给出了2008年7月13日至2008年9月11日这段时间里各类病人的情况。白内障手术较简单，而且没有急症。目前该院是每周一、三做白内障手术，此类病人的术前准备时间只需1、2天。做两只眼的病人比做一只眼的要多一些，大约占到60%。如果要做双眼是周一先做一只，周三再做另一只。外伤疾病通常属于急症，病床有空时立即安排住院，住院后第二天便会安排手术。其他眼科疾病比较复杂，有各种不同情况，但大致住院以后2-3天内就可以接受手术，主要是术后的观察时间较长。这类疾病手术时间可根据需要安排，一般不安排在周一、周三。由于急症数量较少，建模时这些眼科疾病可不考虑急症。该医院眼科手术条件比较充分，在考虑病床安排时可不考虑手术条件的限制，但考虑到手术医生的安排问题，通常情况下白内障手术与其他眼科手术（急症除外）不安排在同一天做。当前该住院部对全体非急症病人是按照FCFS（Firstcome,Firstserve）规则安排住院，但等待住院病人队列却越来越长，医院方面希望你们能通过数学建模来帮助解决该住院部的病床合理安排问题，以提高对医院资源的有效利用。11/21/202224随机模拟的应用：眼科病床的合理安排医院就医排队是大家都非常随机模拟的应用：眼科病床的合理安排问题一：试分析确定合理的评价指标体系，用以评价该问题的病床安排模型的优劣。问题二：试就该住院部当前的情况，建立合理的病床安排模型，以根据已知的第二天拟出院病人数来确定第二天应该安排哪些病人住院。并对你们的模型利用问题一中的指标体系作出评价。问题三：作为病人，自然希望尽早知道自己大约何时能住院。能否根据当时住院病人及等待住院病人的统计情况，在病人门诊时即告知其大致入住时间区间。问题四：若该住院部周六、周日不安排手术，请你们重新回答问题二，医院的手术时间安排是否应作出相应调整?问题五：有人从便于管理的角度提出建议，在一般情形下，医院病床安排可采取使各类病人占用病床的比例大致固定的方案，试就此方案，建立使得所有病人在系统内的平均逗留时间（含等待入院及住院时间）最短的病床比例分配模型。11/21/202225随机模拟的应用：眼科病床的合理安排问题一：试分析确定合理的随机模拟的应用：眼科病床的合理安排11/21/202226随机模拟的应用：眼科病床的合理安排11/21/20222611/21/20222711/21/202227随机模拟与蒙特卡洛方法11/21/202228随机模拟与蒙特卡洛方法11/21/20221随机模拟与蒙特卡洛方法模拟：把某一现实的或抽象的系统的部分状态或特征用另一系统(称为模型)来代替或模仿计算机模拟在复杂系统或过程的研究中发挥着越来超重要的作用随机模拟和蒙特卡洛(MonteCarIo)方法11/21/202229随机模拟与蒙特卡洛方法模拟：把某一现实的或抽象的系统的部分状蒙特卡洛方法的基本思想基本思想：把各种随机事件的概率特征与数学分析的解联系起来，用试验的方法确定事件的相应概率与数学期望特点：概率模型的解是由试验得到的，而不是计算出来的。作用：可以解决其它方法无法解决的实际问题、对理论研究进行补充及辅助11/21/202230蒙特卡洛方法的基本思想基本思想：把各种随机事件的概率特征与随机模拟试验的目的系统的比较与评价，在指定的性能指标下对实际存在的或所设计的系统性能做出对比和评价；系统的分析与预测，分析确定一些因素对整个系统性能的影响以及系统在某些条件下的性能；系统的优化，在许多因素中找出使系统性能最优的因素参数；系统的假设检验，用模拟结果与系统实际状态作对比以检验对系统所作假设是否合理。11/21/202231随机模拟试验的目的系统的比较与评价，在指定的性能指标下对实际随机模拟的优势对无法实施的一类问题进行模拟对大量方案的比较和选优对大型复杂系统进行模拟对有危险的试验或训练进行模拟对无法重复的现象进行模拟11/21/202232随机模拟的优势对无法实施的一类问题进行模拟11/21/202随机数的产生随机模拟能够成功应用的关键是在计算机上实现随机抽样，而随机抽样的基础是随机数随机数：具有给定概率分布的随机变量的可能值。最重要的随机数：(0，1)均匀分布的随机数伪随机数产生随机数的方法：迭代取中法、移位法、同余法11/21/202233随机数的产生随机模拟能够成功应用的关键是在计算机上实现随机抽进行计算机模拟需要大样本的均匀分布随机数数列，如何获得？真随机数：由随机物理过程来产生，如：放射性衰变、电子设备的热噪音、宇宙射线的触发时间伪随机数：由计算机按递推公式大量产生冯.诺曼平方取中法

乘加同余

11/21/202234进行计算机模拟需要大样本的均匀分布随机数数列，如MATLAB软件中随机数的产生rand(m,n)生成区间(0,1)上的均匀分布的m行n列随机矩阵；randn(m,n)生成标准正态分布N(0,1)的m行n列随机矩阵；randperm(N)生成1,2,…,N的一个随机排列随机种子例将种子设置为系统时间，：rand(‘state’，surn(100*clock))11/21/202235MATLAB软件中随机数的产生rand(m,n)生成区间蒲丰投针问题

1777年法国科学家蒲丰提出了下面的著名问题，这是几何概率的一个早期例子。

平面上画着一些平行线，它们之间的距离都等于a，向此平面任意投一长度为l的针（l<a），试求此针与任一平行线相交的概率．

根据几何概率的知识可求得此概率为。

由于最后的答案与π有关，因此不少人想利用它来计算π的数值，其方法是投针N次，计算出针与线相交的次数n，再用频率值n/N作为概率p的值代入上式，求得2lN/an。11/21/202236蒲丰投针问题

1777年法国科学家蒲丰提出了下面程序如下：

a=2;

l=1.2;

N=100000;

n=0;

fori=1:1:N

x=a*rand(1)/2;

t=pi*rand(1);

rand(1);

ifx<l*sin(t)/2

n=n+1;

end

end

n

pii=2*l*N/n/a

增加N值试验，改变a和l的值，重新试验，观察pii的值。11/21/202237程序如下：

a=2;

l=1.2;

N=100000;

n=随机模拟的应用：报童问题问题提出：报童，每天批发报纸后零售，每卖一份报可赚钱a元，卖不完则可再退回每退一份报要赔钱b元历史数据：k300350400450500550600650700pk0.0250.050.10.1750.30.1750.10.050.02511/21/202238随机模拟的应用：报童问题问题提出：报童，每天批发报纸后零售随机模拟的应用：报童问题利润公式：11/21/202239随机模拟的应用：报童问题利润公式：11/21/202212随机模拟的应用：报童问题产生服从经验概率分布的随机数产生一[0，1]上的均匀分布的随机数U，Y=1000*U11/21/202240随机模拟的应用：报童问题产生服从经验概率分布的随机数11/随机模拟的应用：报童问题具体实现：对n=300,…,700,分别进行以下操作：产生随机数r;计算利润L重复N次进行平均选出L平均值最大的n11/21/202241随机模拟的应用：报童问题具体实现：对n=300,…,700随机模拟的应用：码头卸货效率分析问题的提出有一个只有一个舶位的小型卸货专用码头，船舶运送某些特定的货物（如矿砂，原油等）在此码头卸货。若相邻两艘船到达的时间间隔在15分钟到145分钟之间变化，每艘船的卸货时间由船的大小、类型所决定，在45分钟到90分钟的范围内变化。现在需对该码头的卸货效率进行分析，即设法计算每艘船在港口停留的平均时间和最长时间；每艘船等待卸货的时间；卸货设备的闲置时间的百分比等。11/21/202242随机模拟的应用：码头卸货效率分析问题的提出11/21/20数学模型的建立为简单计，假设前一艘船卸货结束后马上离开码头，后一艘船立即可以开始卸货。引进如下记号：——第j艘船的到达时间。——第j艘船与第j+1艘船到达之间的时间间隔。——第j艘船的卸货时间。——第j艘船的离开时间。——第j艘船的等待时间。——第j艘船在港口的停留时间。——卸完第j艘到开始卸第j+1艘船之间的设备闲置时间。——船只最长等待时间。——船只平均等待时间。——船只最长停留时间。——船只平均停留时间。——设备闲置总时间。——设备闲置百分比。11/21/202243数学模型的建立11/21/202216为了分析码头的效率，我们考虑共有条船到达码头卸货的情形，原则上讲，越大越好。由于船到达码头的时间和卸货时间都是不确定的，因此，我们要用随机模拟的方法来建立数学模型。首先，我们假设两船到达之间的时间间隔是一个随机变量，服从15分钟到145分钟之间的均匀分布；各船卸货时间也是一个服从15分钟到45分钟间均匀分布的随机变量。然后我们可以用发生均匀分布的随机数的方法，分别产生n个[15,145]和[45,90]之间的随机数和模拟n艘船两两之间到达的时间间隔和各艘船的卸货时间。利用船舶到达的时间间隔，设初始时刻为0，我们可以计算出各船的到达时间。11/21/202244为了分析码头的效率，我们考虑共有条船到达码头卸货的情形，原则有了这些数据后，我们就可以计算各艘船在码头等待卸货的时间，离开的时间，以及两艘船之间卸货设备的闲置时间。第一艘船到港就可以卸货，卸完货即可离开，因而有而在该船到达之前设备闲置，即以后各艘船到达码头时，若前一艘船已经离港，则马上可以卸货，否则必须等待，等待时间为上一艘船的离港时间与本船到达时间之差，从而第j艘船的等待时间为11/21/202245有了这些数据后，我们就可以计算各艘船在码头等待卸货的时间，离由此可得若第艘船需等待卸货，设备不会闲置，但若第艘船的到达时间迟于第艘船的离开时间，那么这段时间差就是设备的闲置时间，即11/21/202246由此可得若第艘船需等待卸货，设备不会闲置，但若第艘船的到达时船只停留时间为以及船只平均和最大停留时间以及平均和最大等待时间11/21/202247船只停留时间为以及船只平均和最大停留时间以及平均和最大等待也可以计算设备闲置总时间和闲置时间百分比

由于和是随机产生的，重复进行计算，结果是会有差异的。所以仅用一次计算的结果作为分析的依据是不合理的。较好的做法是重复进行多次模拟，取各项数据的平均值作为分析的依据。11/21/202248也可以计算设备闲置总时间和闲置时间百分比由于和是随机产生的模型的求解与应用我们以n＝100为例，列出6次模拟的结果如表1所示，其中所有时间均以分钟为单位。表1船在港口的平均停留时间1068510111611294船在港口的最长停留时间287180233280234264船的平均等待时间392035504427船的最长等待时间213118172203167184设备闲置时间的百分比0.180.170.150.20.140.21若为了提高码头的卸货能力，增加了部分劳力和改善了设备从而使卸货时间减少至35至75分钟之间，两艘船到达的间隔仍为15—145分钟，六次模拟的结果如表2所示。表2船在港口的平均停留时间746264676773船在港口的最长停留时间161116167178173190船的平均等待时间19610121216船的最长等待时间10258102110104131设备闲置时间的百分比0.250.330.320.30.310.2711/21/202249模型的求解与应用表1船在港口的平均停留时间1068从表2可见，每艘船的卸货时间缩短了15—20分钟，等待时间明显缩短，但设备闲置时间的百分比增加了一倍。为了提高效率，可以接纳更多的船只来港卸货，于是将两艘船到达的时间间隔缩短为10—120分钟。在装载时间仍为35—75分钟的情况下，再进行6次模拟，其结果如表3所示。此时等待时间有增加了，但设备闲置时间减少了。表3船在港口的平均停留时间114799688126115船在港口的最长停留时间248224205171371223船的平均等待时间572441357161船的最长等待时间175152155122309173设备闲置时间的百分比0.150.190.120.140.170.0611/21/202250从表2可见，每艘船的卸货时间缩短了15—20分钟，等待时间明随机模拟的应用：眼科病床的合理安排医院就医排队是大家都非常熟悉的现象，它