天津大学《运筹学》8

第八章 随机模拟技术 8.1 随机模拟概述 8.2 蒙特卡洛模拟 8.3 库存问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的随机模拟 8.4 排队问题的随机模拟 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 8.1 随机模拟概述 一、什么是随机模拟？ 模拟是一种数量技术，它利用计算机化的数学 模型来 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 现在某些不确定的条件下所做出的实 际决策，来评价一些根据事实及假设所建立的 可供选择的行动 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 。 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 系统模拟 物理模拟 数学模拟 解析模拟 随机模拟 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 离散型随机模拟 连续型随机模拟 二、随机模拟的分类 状态变量的 变化性质 变量是否随 时间变化 动态随机模拟 静态随机模拟 问题识别 是否采用模拟技术？ 建立模型 确定随机变量及其分布 产生均匀随机数 产生随机变量的模拟数据 模型演算试验 结果分析 是否满意？ 采用解析法 或其他数值解法 三、随机模拟的步骤 决策 修正试 验参数模型修正 YN Y N N 模 拟 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 8.2 蒙特卡洛模拟 一、蒙特卡洛模拟概述 二、随机数的产生 三、蒙特卡洛模拟实例 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 一、蒙特卡洛模拟概述 蒙特卡洛模拟的起源：普丰投针试验 x F(x) 1 1 N nS Nn heart ≈易知： ，总数与落入正方形内随机点 随机点数计算落于心型区域内的 随机点，可以在正方形内均匀选 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 为了估算某道路口每天的车流量，对道路口每分 钟通过的车辆数做了100次的统计，如表所示： 引例 每分钟通过车数 30~39 40~49 50~59 60~69 70及以上 发生次数 5 25 40 28 2 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 概率分布表如下： 每分钟通过车辆数 概率 30~39 0.05 40~49 0.25 50~59 0.4 60~69 0.28 70及以上 0.02 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 概率分布和随机数取值 每分钟通过 车辆次数 概率 累积概率 随机数取值 30~39 0.05 0.05 0.30 0.70 0.98 1 01~05 40~49 0.25 06~30 50~59 0.4 31~70 60~69 0.28 71~98 70及以上 0.02 99~100 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 如何有效地产生与真实系统相似的输入变量？ 即如何产生具有一定分布的随机数？ http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 二、随机数的产生方法 1、均匀分布随机数及其产生方法 均匀分布随机数是在[0，1]区间内，以同样的概 率产生的一系列随机数，其概率密度和分布函数 为： ⎩⎨ ⎧ > ≤≤= ⎩⎨ ⎧ ≤≤= 1,0 10, )( ,0 10,1 )( x xx xF x xf 其他 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 随机数表 随机数发生器 利用数学的方法产生随机数 ““Rand TableRand Table”” 11、放射性物质随机蜕变、放射性物质随机蜕变 22、电子管回路的热噪声、电子管回路的热噪声 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 2、给定概率分布的随机数 逆转换法 上服从均匀分布。在变量，则 定义的随机是由的随机变量，为 及分布函数是具有概率密度函数定理：设 ]1,0[ )( Y XFYYF fX = 求得。由 ，然后变量区间上均匀分布的随机，产生 的随机变量，就要由此，要产生服从分布 )( ]10[ 1 RF R F − http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 证明 )(1 RFY X −=记 ))(())(( xFFxFRP XRX =≤= 成立即 XY xFxFF XXR = =∴ )())(( ⎪⎩ ⎪⎨ ⎧ ≥ ≤≤ ≤ = 11 10 00 )( x xx x xFR ))(()()( 1 xRFPxYPxF XY ≤=≤= − 1)(0 ≤≤ xFX http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 （1）连续型随机变量的模拟 1r XF 1− XF 0r 0x 1x x0 1 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 例1：求任意区间[a,b]内的均匀分布随机变量 的模拟数据。 其分布密度函数为：均匀分布的随机变量， 上是。区间的均匀随机数记作，解：将 ],[]10[ baxR ⎪⎩ ⎪⎨ ⎧ ≤≤−= 其他0 ,1 )( bxa abxf ⎪⎪⎩ ⎪⎪⎨ ⎧ > ≤≤− − < = bx bxa ab ax ax xF 1 ,0 )( Rabax bx axxFR )(,)( −+=− −== 得令 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 例2：产生参数为u的负指数分布的模拟数 据。 xexf μμ −=)( xexF μ−−= 1)( RxeR R eRexFR x xx ln1, 1 1,1)( μ μ μμ −== − =−−== − −− 则 也来自均匀分布，故令因为 即令 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 （2）离散型随机变量的模拟 0 x 1 其方法为：的随机数 为基础产生该随机变量区间上均匀分布随机数，现在欲以 ，其中，知为离散型随机变量，已设 , ,,]10[ 1,0,}{ 21 "xx pppaZPZ i iiii ∑ =≥== ⎪⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎨ ⎧ ++<≤+++ +<≤ <≤ = + … "" " ikii k k i ppxpppa ppxpa pxa Z 1121 2112 11 ; ; 0; 当 当 当 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 3、蒙特卡洛模拟实例 某生产电子产品的企业，要对某型号的产品平均 无故障运行时间做出估计。该产品由A、B、C三 个部件串联而成。因此，当这三个部件中任何一 个部件发生故障而失效时，则该电子产品也即告 失效。如果根据该产品投入运行后再对其无故障 运行时间做出估计，则费用较高。现在企业已经 得到每一种部件的有关运行试验记录资料，其中 包括用来确定部件失效时间的概率分布。 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 A部件 B部件 C部件 失效时间 概率 随机数 失效时间 概率 随机数 失效时间 概率 随机数 4 0.1 01~10 2 0.05 01~05 6 0.2 01~20 5 0.2 11~30 3 0.1 06~15 7 0.3 21~50 6 0.3 31~60 4 0.2 16~35 8 0.25 51~75 7 0.2 61~80 5 0.3 36~65 8 0.15 76~90 8 0.15 81~95 6 0.25 66~90 10 0.1 91~00 9 0.05 96~00 7 0.1 91~00 部件失效概率分布和随机数取值表 产品序号 A随机数 A失效时间 B随机数 B失效时间 C随机数 C失效时间 产品失效时间 1 33 6 24 4 52 8 4 2 50 6 72 6 85 9 6 3 13 5 19 4 79 9 4 4 82 8 20 4 86 9 4 5 59 6 91 7 72 8 6 6 30 5 88 6 20 6 5 7 24 5 95 7 12 6 5 8 02 4 38 5 21 7 4 9 15 5 41 5 99 10 5 10 38 6 51 5 58 8 5 11 12 5 08 3 04 6 3 12 85 8 23 4 36 7 4 13 92 8 55 5 01 6 5 14 79 7 27 4 84 9 4 15 59 6 80 6 13 6 6 16 11 5 26 4 06 6 4 17 97 9 54 5 15 6 5 18 39 6 47 5 73 8 5 19 71 7 14 3 64 8 3 产品失效时间仿真表 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 结论：产品失效时间 为4.6个月 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 8.3 库存问题的随机模拟 有某种货物的存贮系统，市场对这种货物 的需求量和订货提前期都是随机的，它们 的概率分布如下： http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 需求量 概率 累积概率 0 0.02 0.02 1 0.08 0.10 2 0.22 0.32 3 0.34 0.66 4 0.18 0.84 5 0.09 0.93 6 0.07 1.00 提前期 概率 累积概率 1 0.23 0.23 2 0.45 0.68 3 0.17 0.85 4 0.09 0.94 5 0.06 1.00 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 现在考虑订货、存贮、缺货损失三项费用：订 货费用每次25元，订货量每次20单位，订货点 为15单位。（即存货低于15单位时订货，但已 订货未到前不再订）存贮费每件每周10元，缺 货损失费每件每周500元。对于缺货，货到后 不补，设开始时存货为20单位。试利用所给随 机数R1（在下表内）模拟需求量，R2（50， 86，15……）模拟订货提前期。模拟14周的运 行情况： 并求订货费用、存贮费用、缺货费用以及周平均费用。 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 需求 订货 提前期随机数 R1 需求量 是否 订货 R2 提前期 缺 货 量 0 20 1 68 2 52 3 90 4 59 5 08 6 72 7 44 到 货 量 存 贮 量 周 — 4 3 5 3 1 4 3 — 16 13 √√ 50 2 8 25 24 20 17 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 需求 订货 提前期随机 数 R1 需求 量 是否 订货 R2 提前期 缺 货 量 8 95 9 81 10 94 11 28 12 89 13 60 14 03 到 货 量 存 贮 量 周 6 4 6 2 5 3 1 11 √√ 86 44 7 1 0 15 12 √√ 1 1515 11 3131 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 × × ×可求得：订货费用25 3=75，存贮费用10 200=2000，缺货费用500 1=500 1周平均费用 （75+2000+500）=183.9。14 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 8.4 排队问题的随机模拟 有一单服务台的排队系统，根据经验资料 知道到达的间隔时间和服务时间的概率分 布如下表，其他条件符合标准情形。 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 到达 间隔 概 率 累积 概率 对应随 机数(a) 2 0.4 6 0.3 10 0.2 14 0.1 服务 时间 概 率 累积 概率 对应随 机数(b) 1 0.4 3 0.4 5 0.2 0.4 0.7 0.9 1.0 0.0-0.4 0.4-0.7 0.7-0.9 0.9-1.0 0.4 0.8 1.0 0.0-0.4 0.4-0.8 0.8-1.0 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 (1)今由随机数表任选两组随机数 RNa：902,321,211,021,198,383,107,799,439 RNb：612,484,048,605,583,773,054,853,313,200 试根据这两组随机数分别产生表示开始十位顾 客的到达间隔时间的随机数AT和表示服务时间 的随机数ST。 (2)模拟这个排队系统的运行情况，这一阶段共运行 多少分钟？ (3)求系统空闲的概率P0。 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 服务时间顾 客 RNa AT 进入系 统时刻 RNb ST 开始 结束 系统空 闲时间 1 — 612 2 902 484 3 321 048 4 211 605 5 021 583 6 198 773 7 383 054 8 107 853 9 799 313 10 439 200 — 14 2 2 2 2 2 2 10 6 0 14 16 18 20 22 24 26 36 42 3 3 1 3 3 3 1 5 1 1 0 14 17 18 21 24 27 28 36 42 3 17 18 21 24 27 28 33 37 43 11 3 5 http://www.tju.edu.cn天津大学管理学院 第八章 随机模拟技术 解：先求出到达间隔与服务时间的累积概率。 （见上表）。然后求出AT，ST及求解(2)，(3)所 需的有关数据。 求解结果： (1)AT与ST见表 (2)系统此阶段（10位顾客）共运行43分钟 (3)空闲率P0=（11+3+5）/43=19/43=0.44 第八章 随机模拟技术