建筑数学-概率5-随机模拟-蒙特卡洛法.pptxVIP

随机模拟 蒙特卡洛法 秦佑国燕翔清华大学建筑学院 一个三岔路口 到来的车辆在此处遇到岔路 一条路通往A城 一条路通往B城 前往A城的车比前往B城的车多一倍 即来车的2 3去A城 1 3去B城 但这是长时间观察统计的结果 并非实时的情况 不是每来3辆车 就2辆开往A城 1辆开往B城 我们可以用扔骰子来模拟 扔出1点或2点 3点 4点 表示来车去A城 扔出5点或6点 表示来车去B城 前者在6个可能结果 1 6点 中占4个 概率为2 3 后者占2个 概率为1 3 扔一次骰子 表示来一辆车 一直扔下去 就可以模拟车辆去向的随机特性 而长时间 扔的次数很多时 的试验 又符合统计的结果 如果 去A城的车 其中2 3是轿车 1 3是货车 去B城的车 其中1 2是轿车 1 2是货车 也可以继续扔骰子来模拟 在前面试验扔出的结果是去A城后 再扔一颗骰子 扔出1点或2点 3点 4点 表示是轿车 扔出5点或6点 表示是货车 在前面试验扔出的结果是去B城后 再扔一颗骰子 扔出1点或2点 3点 表示是轿车 扔出4点或5点 6点 表示是货车 这种随机现象模拟是用扔骰子来进行的 称为蒙特卡罗法 蒙特卡罗是赌城 扔骰子的工作可以交给计算机去做 计算机上都有生成 0 1 区间上均匀分布的随机数 即每个数出现的概率相同 的程序 计算机每生成一个大于0 小于1的随机数 就是扔了一次骰子 0 666667 2 3近似值 表示车子去A城 0 666667 表示车子去B城 蒙特卡罗法可以模拟车流 模拟人流 电梯载客和停层 旅客的柜台服务 人员的疏散等等 服务柜台前 1分钟内 0个顾客的概率0 25 1个顾客的概率0 20 2个顾客的概率0 30 3个顾客的概率0 15 4个顾客的概率0 10 如果每个顾客平均服务时间为45秒 0 75分钟 柜台前会不会排队 可能排起几个人的队 加快工作效率 平均服务时间缩短为0 5分钟 排队情况又如何 一种是分析方法 可以先计算平均值 0 0 25 1 0 20 2 0 30 3 0 15 4 0 05 1 7 即一分钟平均有1 7个顾客 两个顾客的时间间隔是1 1 7 0 588分钟 每个顾客平均服务0 75分钟 大于0 588分钟 顾客可能出现等待 每个顾客平均服务缩短为0 5分钟 小于0 588分钟 长时间段看 不会出现等待 这种分析方法是针对长时段平均情况的 不能描述短时段可能出现的具体状况 另一种方法是蒙特卡洛法 在计算机上生成 0 1 区间上均匀分布的随机数 每产生一个随机数 表示时间间隔1分钟 0 0 25 表示这一分钟柜台前没有来顾客 0 25 0 45 0 25 0 20 表示这一分钟柜台前来了1个顾客 0 45 0 75 0 25 0 20 0 30 表示这一分钟柜台前来了2个顾客 0 75 0 90 0 25 0 20 0 30 0 15 表示这一分钟柜台前来了3个顾客 0 90 1 00 0 25 0 20 0 30 0 15 0 10 表示这一分钟柜台前来了4个顾客 同时 柜台前来了顾客 每个顾客服务0 75分钟 或0 5分钟 后离去 接待下一个顾客 随着计算机产生随机数 个数的增多 如产生60个 就是1个小时 产生120个 就是2个小时 就可以模拟柜台前到来的顾客 和可能出现的排队等候的情况 思考一下 如果顾客的服务时间也是随机变量 也有概率分布 只是平均值是0 75分钟 或0 5分钟 是否也可以模拟 只要知道其概率分布 离散型随机变量的直接抽样 随机变量X x1 x2 x3 xN 例如 x可取3个值x1 x2 x3 它们出现的几率分别为2 8 5 8 1 8 则抽得的 0 1 区间上均匀分布的随机数 小于2 8时实现x1 在区间2 8 7 8中时实现x2 大于7 8时实现x3 前面柜台前顾客数的例子就是这样做的 概率分布P p1 p2 p3 pN 从 0 1 区间中均匀抽样得到的随机数 满足下式时 则随机变量x取值为xn 上面两个例子 随机变量 来车和来柜台的人 是离散分布的 蒙特卡罗法的发展历史 蒲丰投针 1777年 蒲丰在家中请来客玩投针游戏 针长是线距之半 他事先没有给客人讲与 有关的事 客人们虽然不知道主人的用意 但是都参加了游戏 他们共投针2212次 其中704次相交 蒲丰说 2212 704 3 142 这就是 值 设针投到地面上的位置可以用一组参数 x 来描述 x为针中心的坐标 为针与平行线的夹角 如图所示 任意投针 就是意味着x与 都是任意取的 但x的范围限于 0 a 夹角 的范围限于 0 在此情况下 针与平行线相交的数学条件是 针在平行线间的位置 多次投针 次数N巨大 其中与线相交的次数为M 与N之比M N就近似于概率P 线长l a 2 1 P N M 各向同性随机投针 则夹角 在 均匀分布 所以 设投针N次 相交次数为M 则相交概率的期望值 N 大数定理 针与平行线垂直方向夹角为 则相交概率为 平行线间距 针长 d 浦丰1777年出版的著作中提出 在平面上画有一组间距为d的平行线 将一根长度为l l d 的针任意掷在这个平面上 求此针与平行线中任一条相交的概率 布丰本人证明了 这个概率是p 2l d 为圆周率 也有人用l d来试验 得到 一些人进行了实验 其结果列于下表 水塘面积测量的故事一块方形的地块 长a宽b 中有一个不规则的水塘 如何测量水塘的面积 向地块上扔石子 如果 假定可能 扔出的石子在方形地块上均匀分布 大量地扔 扔他几百次 设为N 听到水声 或溅起水花 的次数 即扔到水塘里的次数为M 那么水塘的面积近似地是 M N a b a b是方形地块的面积 问题是石子谁来扔 能保证在方形内均匀分布 让计算机来扔 还有扔出的石子怎么判断落在了水里还是地里 判别准则的确定 测量已知半径为R的圆的面积在边长为R的正方形内随机扔石子 为了扔得均匀 在计算机上独立地产生两个 0 1 上均匀分布的随机数 1 2 得到石子在正方形内的坐标 x 1R y 2R 判别这颗石子是否在圆内就检验x2 y2 R2 即 12 22 1是否成立 大量地重复试验 次数N很大 石子扔得很多 计算落在圆的次数M 则1 4圆面积 M N R2 圆面积就是4 M N R2 圆面积是4 R2 得到 4 M N 模拟步骤 1InitializeR Nmax2Generaterandomnumber 34Nt Nt 1 if N N 15If Nt Nmax goto26P N Nt 7end 的蒙特卡罗法模拟结果 定积分计算的蒙特卡罗法从上面这个测量圆面积的例子 可以看出 利用蒙特卡罗法可以计算函数的定积分 即y f x 在 x1 x2 区间内 函数曲线与x轴之间的面积 图中蓝色 y1 f x1 y2 f x2 y1与 x1 x2 线段形成一个纯蓝色的矩形 面积是S1 y1 x2 x1 而其上面 y2 y1 与 x2 x1 围成的矩形 面积S2 y2 y1 x2 x1 由两块面积组成 一块是函数曲线下的蓝色面积 一块是曲线上的白色面积 于是问题化为 向上面这个矩形中均匀分布地 扔石子 扔的量 N 很大 计算落在蓝色区域内的数 M 判别条件是 对应于一个 石子 的x坐标 其y坐标小于等于函数值f x 则此点落在蓝色区域 若大于函数值f x 则落在白色区域 于是蓝色区域的面积就近似求得为 M N S2 再加上S1 就是整个蓝色区域的面积 也就是函数y f x 在区间 x1 x2 内的定积分 由计算机产生两个独立的 0 1 上均匀分布的随机数 1 2以确定所 扔石子 的坐标 x x1 x2 x1 1y y1 y2 y1 2如果 y f x 则此点 石子 落入蓝色区域 大量地试验 次数为N 石子 落入蓝色区域的次数为M 则此定积分为 M N f x2 f x1 x2 x1 f x1 x2 x1 复杂随机现象的蒙特卡罗法模拟某个城市急救站 平均一小时会接到3个呼救电话 一次救护行动平均需要45分钟 救护车开出到送完病人回来 取决于服务范围 急救站要配备多少辆救护车 才能保证有人呼救时 有90 的概率 站上有车可出 这里有两个泊松分布 一是呼救电话的次数 或时距 一是救护车一次救护行动的时间 泊松分布的概率公式是 在前面参数估计时讲到 泊松分布的参数 是均值 在这个问题中 第一个泊松分布是呼救次数 一小时内平均有3次呼救 即 3 于是可以得出 呼救次数 概率分布和累积概率 分列三行 0 1 2 3 4 5 6 7 8 9 10 11 0 04980 1490 2240 2240 1680 10080 05040 02160 00810 00270 000810 000220 04980 1990 4230 6470 8150 91560 96600 98760 99570 99840 999200 99942用计算机产生一个 0 1 上均匀分布的随机数 看其落在第三行哪个区段内 就表示这一小时有几次呼救 例如0 0 0498表示0次 没有呼救电话打来 0 423 0 647表示3次呼救 可以看出多于8次呼救概率不到1 泊松分布的概率公式是 呼救次数问题也可以转化成两个相继呼救之间的时间间隔 时距 一小时内平均有3次呼救 即平均时距为20分钟 为了使问题简化 也不有悖于实际情况 以5分钟为时距单位 t 即一个 t时距内只计算一个呼救 于是平均时距就是4 t 上式的 4 k 1 2 3 4 5 6 7 8 9 10 11 12 k 1表示相继两次呼救间隔5分钟 一个 t 忙 k 4表示相继两次呼救间隔20分钟 平均值 k 8表示相继两次呼救间隔40分钟 较闲 时距 概率和累积概率计算列表如下 0 1 2 3 4 5 6 7 8 9 10 1112 0 01830 07330 1460 1950 1950 1560 1040 05950 02980 01320 005290 001920 000640 01830 09160 2370 4320 6270 7830 8870 94650 97630 98950 99480 99670 99735在计算机上产生一个 0 1 上均匀分布的随机数 看其落在第三行哪个区段内 就表示相继两次呼救的时间间隔 例如0 0916 0 237 k 2 相隔2 t 10分钟 0 783 0 887 k 6 相隔6 t 30分钟 救护车一次救护行动的时间T 救护车开出到送完病人回来 也是服从泊松分布的随机变量 其平均值是45分钟 和前面一样 以5分钟为服务时间单位 t 于是平均服务时间就是9 t 上式的 9 K 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 k 3表示救护车出去不到15分钟就回来 k 8表示出去一次用了40分钟 时距 概率和累积概率计算列表如下 0 1 2 3 4 5 6 7 8 9 10110 0001230 001110 00500 01500 03370 06070 09110 11710 13180 13180 11860 09700 0001230 001230 00620 02120 05490 11560 20670 32380 45560 58740 71820 815212 13 14 15 16 0 07270 05040 03240 01940 01090 88790 93830 97070 98710 9980在计算机上产生一个 0 1 上均匀分布的随机数 看其落在第三行哪个区段内 就表示救护车一次出行的服务时间 例如0 0 000123 K 1 表示救护车出去5分钟就回来了 这个概率极小 而0 3238 0 4556 K 8 表示救护车外出服务时间是40分钟 如果急救站的救护车不止一辆 其他救护车的服务时间同样模拟 于是整个急救站工作就可以模拟 起始条件t 0时 站上有车 开始计时 先生成 0 1 上均匀分布的随机数 1 确定第一个呼救电话的时间间隔k1 t t是5分钟 即t k1 t时 第一个呼救电话到来 救护车出发 然后再生成第二个随机数 2 确定第二个呼救电话的时间间隔k2 t 但同时生成 0 1 上均匀分布的随机数 以确定出发的救护车在外的服务时间T 如果T小于第二个呼救电话的时间间隔k2 t 表示救护车已经回来 可以再出车 如果T大于第二个呼救电话的时间间隔k2 t 表示出去的救护车还没有回来 如果站上只配了1辆救护车 此时无车可派 如果站上配了2辆救护车 第2辆车出发 并再生成 0 1 上均匀分布的随机数 以确定第二辆出发的救护车在外的时间 什么时候可以回来 然后生成第3个随机数 3 确定下一个呼救电话的时间间隔 并查看是否有救护车已经完成任务 回到急救站 等候派车 重复上述过程 并累计计时 检查是否出现呼救电话打来 站上无车可派 出去的车还没有回来 情况的出现 也可以允许电话打来 有短时间 例如5分钟之内 的等待 先配1辆车 长时间 试验次数很多 地模拟 如果出现较多的等待的次数 就配2