9 MOnte Carlo 仿真.ppt

Chap9MonteCarlo方法,基本思想,MonteCarlo方法亦称为随机模型（Randomsimulation）方法，有时也称作随机抽样技术或统计试验方法。是一类通过随机模拟和统计试验求解数学、物理和工程技术问题近似解的数值方法。,基本思想是：当实验次数充分多时，某一事件出现的频率近似于该事件发生的概率。,蒙特卡洛方法，也叫蒙特卡洛分析，是一种使用随机抽样统计来估算数学函数的计算方法。它需要一个良好的随机数源。这种方法往往包含一些误差，但是随着随机抽取样本数量的增加，结果也会越来越精确。蒙特卡洛方法在纯数学方面一般用来求解一个函数的定积分。它的计算过程如下：先在一个区间或区域内随机抽取一定数量的独立变量样本，然后求相应的独立因变量的平均值，最后用随机样本所在区间（或区域）的长度（或大小）乘以所求出的平均值。它与传统的估算定积分的方法有很大差别，传统方法在区间或区域内抽取样本点时是间隔相等、均匀抽取的。蒙特卡洛方法以其在第二次世界大战时被用于原子弹的设计而闻名于世。现在它也已经被应用于多种领域，如超高速公路的运输流量分析、行星演变模型的建立以及股票市场波动的预测。这种方法同样也可应用于集成电路设计、量子力学和通信工程。,MonteCarlo方法,根据车比雪夫定理，设x1,x2,xn,是相互独立的随机变量序列，它们服从相同的分布，且有有限的数学期望a和方差，则x1,x2,xn，的算术平均值当时按概率1收敛于a，即对于任意0有：,由中心极限定理得到：,即当n很大时,近似服从标准正态分布。,MonteCarlo方法,例：用MonteCarlo方法计算积分,分析：任取一列相互独立的、都具有a,b中均匀分布的随机变量xi,则g(xi)也是一列相互独立的随机变量，而且：,所以,只要求出,由车比雪夫定理,便能得到J的数值。为求,这样一来，只要能生成随机变量序列,就能计算积分值了。,MonteCarlo方法,仿真程序如下：#include#includedoubleg(doublex)/被积函数return(x*x*x);/return(exp(x);,下面用C程序实现求,MonteCarlo方法,voidmain（void）/主函数inti,j;doublea,b,x,result,gx;a0.0;b1.0;gx=result=0.0;randomize();for(j=0;j1000;j+)gx=0.0;for(i=0;i30000;i+)x=a+(b-a)*random(32969)/32969;gx+=g(x);result+=(b-a)*gx/30000;result/=1000;printf(Result=%fn,result);运行结果：Result=0.249980/Result=1.918209,应用举例-投资可行性分析,例：投资可行性分析某港口有一个万吨级泊位，根据长期观察记录，依次到港的两艘船只的间隔时间有如表所示的规律,港口现有一台装卸机，根据其它港口的经验，若用两台装卸机可以节约装卸时间经过统计，两种情况下的装卸规律下表,应用举例-投资可行性分析,船只装卸时，按照先到先装卸的原则进行船到港口，若泊位有空，立即停靠卸货；如泊位不空，则排队等候,应用举例-投资可行性分析,按照规定，到港船只必须在15-30h内装卸完毕，其中包括等待和装卸时间若超过30h时，港口每小时支付赔偿费200元；若能少于15h时，每提前1h港口得奖励250元港口在没有船只装卸时，每小时经济损失为400元，而每艘船在港口每停泊1h损失200元已知一台装卸机购置与安装费用为60万元，折旧期为10年每台装卸机每月维修及油料等开支为3000元,请用计算机仿真的方法分析该港口增添第二台装卸机在经济上是否合算？,应用举例-投资可行性分析,增添设备的经济可行性以投资回收期来衡量，若其短于标准投资期，则增添设备是可行的；否则便不可取投资回收期为=k/c,其中k=60万元为增添设备的投资,c是一台装卸机和两台装卸机两种情况下的经营费用之差，即经营费用的节约值。,经营费用包括：船只等待与卸货时间之和小于15h时的奖励费c1；船只等待与卸货时间之和多于30h时的赔偿费c2；船只停港损失费c3；港口空闲损失费c4；装卸机折旧费c5；维修与油料费c6.其中c5和c6两项是确定性费用，c1,c2,c3,c4这四项费用和船只到港间隔时间及卸货时间有关，因而是随机性的,可以由仿真来确定,应用举例-投资可行性分析,船只到港间隔时间的模拟抽样规则，即到港间隔时间与均匀随机数的对应规则如表3所示,表3,应用举例-投资可行性分析,一台及两台装卸机装卸时间的模拟抽样规则，即装卸时间与随机数的对应关系如表4所示,表4,应用举例-投资可行性分析,根据前面的分析，可以产生两组随机数，一组随机数用来模拟相邻两船到港间隔时间，另一组随机数用来模拟对各船的卸货时间在仿真过程中，不断累积船只在港超过30h的时间和不足15h的时间，累积船只在港时间以及港口空闲时间，以此来求得港口空闲时间，从而求到费用c1，c2，c3和c4。,应用举例-投资可行性分析,我们就可以产生初始数据表，利用事件步长法进行仿真记A为船只到港事件，B为装卸结束事件，对一台装卸机的情况，前几步的仿真过程如下：,（1）产生初始事件表(表6),表6,应用举例-投资可行性分析,（2）处理1号事件由表6得，最早的是发生在第15h的1号事件A，置仿真时钟t15它是第一艘到港船只，到港后可立即装卸，这时需要将装卸机由闲变为忙，随机产生装卸结束事件B和下一个船只到港事件A，计算港口空闲损失费c4=15400=6000元处理完后删去1号事件A刷新后的事件表见表7,表7,应用举例-投资可行性分析,（3）处理3号事件B由表8看出，最早的是3号事件B，为装卸结束事件，它发生在第31h，故置t=31判断装卸结束的船只到港停留时间是否小于15h或大于30h累加装卸机的工作时间,表8,应用举例-投资可行性分析,重复上面的过程（2）或（3），每一步都找最早的事件处理，累加一些量，判断一下是否到了应该结束的预定仿真时刻，最后可以得到一台装卸机时的各种费用同理可仿真得出两台装卸机时的费用两种情况下的费用比较如表8所示,由表8看出，用两台装卸机时，每月可以节约经营费用11950元所以投资回收期为：,T=60000/(1195012)=4.19年,因此，若规定的投资回收期大于4.19年时，港口增添一台装卸机在经济上是可行的,城市公共交通线路的仿真,现在，我们用时间步长法仿真一条市内公共交通线路上车辆的运行情况，以便对该线路上车辆配置、发车时间绘出合理的安排在以下的分析和仿真过程中，我们对实际问题进行了必要的简化和假设,1问题的提出,假设某条公共汽车线路上，总共有2n个车站，来回单程各有n个车站为了保证正点运行，将其中某些车站作为校时站，记录车辆通过校时站的时间以计算正点率总共有2m辆汽车在运行，开始时线路两端的停车场中各停放汽车m辆这些汽车将按照发车时刻表及到达次序顺次发车，循环往返地运行来完成运送乘客的任务在每个车站，乘客随机地到达、排队、乘车到各自的目的地其运行示意图见下图,城市公共交通线路的仿真,公共交通线路车辆运行示意图,城市公共交通线路的仿真,影响该系统的主要因素有汽车的数量、乘客人数与到站规律。发车间隔及线路上其它随机因素对车辆运行的干扰等评价这样一个公共汽车运行结果的指标很多，一般说来，好的运行效果应做到以下三点：,（1）正点率高，运行秩序好其中正点率=100%；,校时站正点通过车次数,校时站通过车次总数,（2）总留乘时间少，减少乘客等待时间，提高服务质量其中总留乘时间=(第i个车站留乘人数)(留乘时间);,2n,i=1,城市公共交通线路的仿真,（3）满载率高，运行车公里数少其中车公里数=（车次数）（线路长度）,显然，减少乘客等待时间和减少运行公里数两个要求相互矛盾如何在这些目标中找一个合理的匹配关系，是运输管理中的一个重要问题我们可以利用计算机仿真得到在不同车辆配置、不同发车间隔、不同乘客流量下的总留乘时间、车公里数、正点率等以便公交管理部门能根据不同的情况制订出较好的运行方案,城市公共交通线路的仿真,2.系统分析在此系统中，实体是汽车、车站和乘客汽车的属性包括在车站排队还是运行，运行至哪一点，运行时间，车上乘客人数等乘客的属性有等车、等车时间、乘车车站的属性是该站是否有乘客等车,系统中所涉及的事件有首站发车事件，到达中途站事件，到达终点站事件，乘客到达事件，上、下车事件,城市公共交通线路的仿真,在这个系统中，汽车的活动起着主导作用，我们将汽车的活多分为下面几种：,（1）首站发车活动根据发车时刻表从首站发车，这要考虑是否到了发车时刻及车场是否有车可发，还要考虑首站的上车人数，到达下一站的时间,（2）到达中途站活动这需计算在本站上下车的人数，确定乘车人数及时间，预测汽车下一个后续活动的出现时间，累加运行公里数,（3）末站调头活动就是确定汽车的去向，即立即发出还是参加排队等待发车,城市公共交通线路的仿真,我们作以下假设：,假设1：单位时间内到达第i个车站的人数服从泊松分布，其均值为i（i=1，2，2n）,假设2：各辆汽车从第i站到第i+1站的运行时间服从正态分布,均值为i方差为i2（i=1,2,2n-1）,假设3：各辆汽车的最大容量为Q个乘客，起点站按等间隔发车，时间间隔为TS秒,假设4:车上每位乘客在以后各站下车的概率相等，由此计算出的下车人数非整数时，按四舍五入处理,假设5:每位乘客上、下车各需时间TD秒,以上的参数n,i,i,i2,Q,TD可以根据统计数据估计出来，而车辆总数2m、发车间隔TS是可控制的变量我们进行比较，选择出合理的匹配方案,城市公共交通线路的仿真,3仿真过程取时间步长为1min初始状态为每辆汽车均在各自的停车场上排队待发，各个车站还没有乘客等车根据时间步长法的思路，可以按照以下流程对系统进行仿真,城市公共交通线路的仿真,主控程序流程图,城市公共交通线路的仿真,城市公共交通线路的仿真,城市公共交通线路的仿真,城市公共交通线路的仿真,MonteCarlo方法,在许多情况下，由于对象过于复杂或提出的解释性模型难以处理，建模者无法得到一个能够充分说明对象行为的分析（符号）模型，而当必须对对象的行为做出预报时，建模者可以进行实验（或收集数据）来研究在某个范围内因变量与自变量的选择值之间的关系。为了收集数据可以直接观测对象的行为，在另外，些情况中，对象的行为应能够在可控制的条件下重现（如预测爆破物形成的弹坑的大小）。,MonteCarlo方法,在某些情况下，对对象的行为进行直接观测或重复试验可能是不可行的，例如早高峰时电梯系统提供的服务在明确了一个合适的问题及确定了什么是好的服务之后，我们可以提出若干供选择的电梯运行模式，如设定停偶数层、奇数层的电梯或直达电梯理论上，对每种供选择的模式都能够做若干次试验，以确定哪一种模式能为那些要到达特定楼层的乘客提供最好的服务，然而这种做法可能是难以接受的，因为在收集统计数据时要再三惊扰乘客，并且电梯运行模式的不断变化也会使乘客感到迷惑与此有关的另一个问题是大城市交通控制系统可供选择的运行模式的检验，为了做试验而不停地改变单行道的交通方向和配置交通信号将是不现实的,MonteCarlo方法,还有另一些情况，需要对可供选择的模式做试验的系统甚至可以不存在例如，对于一座办公大楼，要确定几个通讯网络中哪一个最好又如，确定一个新工厂的各台机器的布局进行试验的费用可能是很高的，当核电站发生事故时，为防护和疏散居民而预测各种方案的影响所做的试验就是这种情况。在对象的行为不能做分析性的解释，或数据无法直接收集的情况下，建模者可以用某种方式间接地模拟其行为，试验所研究的供选择的各种方案，以估计它们怎样影响对象的行为，然后收集数据来确定哪种方案是最好的例如，为了得到一艘拟建造的潜艇受到的阻力，造一个原型是不可行的，我们可以按比例建一个模型，去模拟实际的潜艇的行为又如，在风洞里利用喷气飞机的比例模型可以估计高速飞