Chap9 Monte Carlo方法基本 思想Monte Carlo方法亦称为随机模型（Random simulation）方法，有时也称作随机抽样技术 或统计试验方法。是一类通过随机模拟和统计 试验求解数学、物理和工程技术问题近似解的 数值方法。基本思想是：当实验次数充分多时， 某一事件出现的频率近似于该事件发 生的概率。蒙特卡洛方法，也叫蒙特卡洛分析，是一种使用随机抽样统计来估算数学函 数的计算方法。它需要一个良好的随机数源。这种方法往往包含一些误差， 但是随着随机抽取样本数量的增加，结果也会越来越精确。 蒙特卡洛方法在纯数学方面一般用来求解一个函数的定积分。它的计算过程 如下：先在一个区间或区域内随机抽取一定数量的独立变量样本，然后求相 应的独立因变量的平均值，最后用随机样本所在区间（或区域）的长度（或 大小）乘以所求出的平均值。它与传统的估算定积分的方法有很大差别，传 统方法在区间或区域内抽取样本点时是间隔相等、均匀抽取的。蒙特卡洛方 法以其在第二次世界大战时被用于原子弹的设计而闻名于世。现在它也已经 被应用于多种领域，如超高速公路的运输流量分析、行星演变模型的建立以 及股票市场波动的预测。这种方法同样也可应用于集成电路设计、量子力学 和通信工程。Monte Carlo方法根据车比雪夫定理，设x1, x2,xn,是相互独立 的随机变量序列，它们服从相同的分布，且有有限的数学 期望a和方差 ，则x1, x2,xn，的算术平均值当时 按概率1收敛于a，即对于任意 0有：由中心极限定理得到：即当n很大时近似服从标准正态分布。Monte Carlo方法例：用Monte Carlo方法计算积分分析：任取一列相互独立的、都具有a,b中均匀分布的 随机变量xi,则g(xi)也是一列相互独立的随机变量 ，而且：所以只要求出 由车比雪夫定理,便能得到J的数值。为求这样一来，只要能生成随机变量序列 就能计算积分值了。Monte Carlo方法仿真程序如下： #include #include double g(double x) /被积函数 return (x*x*x);/return (exp(x);下面用C程序实现求Monte Carlo方法void main（void）/主函数 int i,j;double a,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应用举例-投资可行性分析例：投资可行性分析 某港口有一个万吨级泊位，根据长期观察记录，依次 到港的两艘船只的间隔时间有如表所示的规律船只到港时间间 隔h151015203040频率 0.150.100.12 0.140.19 0.26 0.06港口现有一台装卸机，根据其它港口的经验，若用两 台装卸机可以节约装卸时间经过统计，两种情况下 的装卸规律下表应用举例-投资可行性分析每条船的装卸时间h频率 一台装卸机 两台装卸机 14100.05 16120.50 18140.20 20150.20 22190.05船只装卸时，按照先到先装卸的原则进行船到港 口，若泊位有空，立即停靠卸货；如泊位不空，则排 队等候应用举例-投资可行性分析按照规定，到港船只必须在15-30 h内装卸完毕，其中 包括等待和装卸时间若超过30 h时，港口每小时支 付赔偿费200元；若能少于15 h时，每提前1h港口得奖 励250元港口在没有船只装卸时，每小时经济损失为 400元，而每艘船在港口每停泊1h损失200元已知一 台装卸机购置与安装费用为60万元，折旧期为10年 每台装卸机每月维修及油料等开支为3000元请用计算机仿真的方法分析该港口增添第二台装 卸机在经济上是否合算？应用举例-投资可行性分析增添设备的经济可行性以投资回收期来衡量，若其短 于标准投资期，则增添设备是可行的；否则便不可取 投资回收期为 =k/c , 其中k =60万元为增 添设备的投资, c是一台装卸机和两台装卸机两种情 况下的经营费用之差，即经营费用的节约值。经营费用包括：船只等待与卸货时间之和小于 15 h时 的奖励费c1；船只等待与卸货时间之和多于30 h时的赔 偿费c2；船只停港损失费c3；港口空闲损失费c4；装卸 机折旧费c5；维修与油料费c6.其中c5和c6两项是确定性 费用，c1,c2,c3,c4这四项费用和船只到港间隔时间及卸 货时间有关，因而是随机性的,可以由仿真来确定应用举例-投资可行性分析船只到港间隔时间的模拟抽样规则，即到港间隔时间 与均匀随机数的对应规则如表3所示船只到港间隔时间 h频率随机数区间10.15（0,0.15） 50.100.15,0.25） 100.120.25,0.39）150.140.39,0.51）200.190.51,0.68） 300.260.68,0.94） 400.060.94,1）表3应用举例-投资可行性分析一台及两台装卸机装卸时间的模拟抽样规则，即装卸 时间与随机数的对应关系如表4所示每条船的装卸时间h频率随机数区间 一台装卸机 两台装卸机 14100.05(0,0.05) 16120.500.05 ,0.55) 18140.200.55,0.95) 20150.200.95,0.95) 22190.050.95,1)表4应用举例-投资可行性分析根据前面的分析，可以产生两组随机数，一组随机数 用来模拟相邻两船到港间隔时间，另一组随机数用来 模拟对各船的卸货时间在仿真过程中，不断累积船 只在港超过30 h的时间和不足15 h的时间，累积船只 在港时间以及港口空闲时间，以此来求得港口空闲时 间，从而求到费用c1，c2，c3和c4。应用举例-投资可行性分析我们就可以产生初始数据表，利用事件步长法进行仿 真记A为船只到港事件，B为装卸结束事件，对一台 装卸机的情况，前几步的仿真过程如下：（1）产生初始事件表(表6)序号事件类型发生时刻 1A15 2B45表6应用举例-投资可行性分析（2）处理1号事件由表6得，最早的是发生在第 15 h 的1号事件A，置仿真时钟t15它是第一艘到港船只 ，到港后可立即装卸，这时需要将装卸机由闲变为忙 ，随机产生装卸结束事件B和下一个船只到港事件 A， 计算港口空闲损失费c4=15400=6000元处理完后删 去1号事件A刷新后的事件表见表7序号事件类型发生时刻 2A40 3B31 4A65表7应用举例-投资可行性分析（3）处理 3号事件 B由表8看出，最早的是 3号事 件 B，为装卸结束事件，它发生在第31h，故置t=31 判断装卸结束的船只到港停留时间是否小于15h或大于 30h累加装卸机的工作时间费用一台装卸机两台装卸机 c125019000 c2120002200 c3160800108200 c455200116400 c549469891 c630116021总经营费 用235909223912表8应用举例-投资可行性分析重复上面的过程（2）或（3），每一步都找最早的事 件处理，累加一些量，判断一下是否到了应该结束的 预定仿真时刻，最后可以得到一台装卸机时的各种费 用同理可仿真得出两台装卸机时的费用两种情况 下的费用比较如表8所示由表8看出，用两台装卸机时，每月可以节约经营费用 11 950元所以投资回收期为：T=60000/(1195012)=4.19年因此，若规定的投资回收期大于4.19年时，港口 增添一台装卸机在经济上是可行的城市公共交通线路的仿真现在，我们用时间步长法仿真一条市内公共交通线路 上车辆的运行情况，以便对该线路上车辆配置、发车 时间绘出合理的安排在以下的分析和仿真过程中， 我们对实际问题进行了必要的简化和假设1问题的提出 假设某条公共汽车线路上，总共有2n个车站，来回单 程各有n个车站为了保证正点运行，将其中某些车站 作为校时站，记录车辆通过校时站的时间以计算正点 率总共有2m辆汽车在运行，开始时线路两端的停车 场中各停放汽车m辆这些汽车将按照发车时刻表及到 达次序顺次发车，循环往返地运行来完成运送乘客的 任务在每个车站，乘客随机地到达、排队、乘车到 各自的目的地其运行示意图见下图城市公共交通线路的仿真公共交通线路车辆运行示意图m 2 1 2m 2m+2 m+1 n+1 n+2 n n-1 2n 2n-1 2n-21 2 3n+4n-2n+3城市公共交通线路的仿真影响该系统的主要因素有汽车的数量、乘客人数与到 站规律。发车间隔及线路上其它随机因素对车辆运行 的干扰等评价这样一个公共汽车运行结果的指标很 多，一般说来，好的运行效果应做到以下三点：（1）正点率高，运行秩序好其中正点率= 100%；校时站正点通过车次数 校时站通过车次总数（2）总留乘时间少，减少乘客等待时间，提高服务质 量其中总留乘时间=(第i个车站留乘人数)(留乘时间);2ni=1城市公共交通线路的仿真（3）满载率高，运行车公里数少其中车公里数= （车次数）（线路长度）显然，减少乘客等待时间和减少运行公里数两个 要求相互矛盾如何在这些目标中找一个合理的匹配 关系，是运输管理中的一个重要问题我们可以利用 计算机仿真得到在不同车辆配置、不同发车间隔、不 同乘客流量下的总留乘时间、车公里数、正点率等以 便公交管理部门能根据不同的情况制订出较好的运行 方案城市公共交通线路的仿真2.系统分析在此系统中，实体是汽车、车站和乘客汽车的 属性包括在车站排队还是运行，运行至哪一点，运行 时间，车上乘客人数等乘客的属性有等车、等车时 间、乘车车站的属性是该站是否有乘客等车,系统中 所涉及的事件有首站发车事件，到达中途站事件，到 达终点站事件，乘客到达事件，上、下车事件城市公共交通线路的仿真在这个系统中，汽车的活动起着主导作用，我们将汽 车的活多分为下面几种：（1）首站发车活动根据发车时刻表从首站发车，这要 考虑是否到了发车时刻及车场是否有车可发，还要考 虑首站的上车人数，到达下一站的时间（2）到达中途站活动这需计算在本站上下车的人数， 确定乘车人数及时间，预测汽车下一个后续活动的出 现时间，累加运行公里数（3）末站调头活动就是确定汽车的去向，即立即发出 还是参加排队等待发车城市公共交通线路的仿真我们作以下假设： 假设1：单位时间内到达第i个车站的人数服从泊松分 布，其均值为i（i=1，2，2n） 假设2：各辆汽车从第i站到第i+1站的运行时间服从正 态分布,均值为i 方差为i 2 （i=1,2,2n-1） 假设3：各辆汽车的最大容量为 Q个乘客，起点站按等 间隔发车，时间间隔为TS秒 假设4:车上每位乘客在以后各站下车的概率相等，由 此计算出的下车人数非整数时，按四舍五入处理 假设5:每位乘客上、下车各需时间TD秒 以上的参数n, i, i , i2 ,Q,TD可以根据统计数据 估计出来，而车辆总数2m、发车间隔TS是可控制的变 量我们进行比较，选择出合理的匹配方案城市公共交通线路的仿真3仿真过程取时间步长为1min初始状态为每辆汽车均在各 自的停车场上排队待发，各个车站还