数学建模-计算机模拟技术.ppt

模拟技术,四川大学数学学院谭英谊,1 模拟基础2 Monte-Carlo模拟3 模拟模型案例,1 模拟基础1.0 模拟的背景、思路应用领域：第二次世界大战期间，等人将进行的“中子扩散”的科研项目取名为“Monte-Carlo”运输系统模拟摩天大楼安全疏散系统模拟国民经济发展模拟人口增长系统模拟供水系统模拟,管理系统模拟雷达系统模拟战争系统模拟模拟思路：“模拟”对系统抽象建模“试验”根据模型设计算法，编程进行反复试验“估计”根据试验数据“收集”根据试验结果作出判断,1.1 模拟的基本知识,1.1.1 模拟的概念及作用现实系统的数学或逻辑模型可能十分复杂，例如大多数具有随机因素的复杂系统，其中的一些随机性因素很难用准确的数学公式表述，从而也无法对整个系统采用解析法求解。模拟是处理这类实际问题的有力工具。,模拟通常借助于计算机进行。计算机模拟：在已经建立的数学、逻辑模型的基础之上，通过计算机试验，对一个系统按照一定的决策原则或作业规则，由一个状态变换为另一个状态的行为进行描述和分析。,模拟的作用：对于很难用解析方法加以处理的问题，模拟是一种有效的技术；对建模过程中的假设进行鉴定，对理论研究的结论加以检验；对不同的实现方案进行多次模拟，按照既定的目标函数对不同方案进行比较，从中选择最优方案。,1.1.2 模拟的分类通常，模拟时间是模拟的主要自变量。设计正确的模拟时间推进机理：模拟过程中应根据系统的特性正确推进模拟时间，使系统中各要素与发生的事件保持同步。,推进模拟时间的基本方法：下次事件法：将模拟时间由一个事件发生的时间点推进到紧接着的下一次事件发生的时间点。固定时间步长法：模拟时间每次均以相等的固定步长向前推进，每到达一个新的模拟时间点需检查相应时间段内是否发生了事件。需根据实际问题合理设置模拟时间发生改变的步长。,根据模拟过程中因变量的变化情况进行分类：1）离散型模拟：因变量在与事件时间有关的具体模拟时间点呈离散性变化。大多数系统（如排队服务系统）可采用离散型模拟。时间推进方法：一般采用下次事件法应当重点对系统状态可能发生改变的事件进行描述，并确定这些事件之间的逻辑关系。,排队系统通常采用离散型模拟模型。其中，发生系统状态变化的事件有两个：一是有顾客到达；二是服务员完成服务。将最近发生上述两种事件之一的时刻设置为下次事件发生点，就可将服务过程描述为图2所示的模拟模型。,2）连续型模拟：因变量随时间的改变呈连续性变化。在大多数计算机模拟过程中，按固定的步长推进模拟时间。通常需建立一系列的由系统状态变量组成的状态方程组，以描述状态变量与模拟时间的关系。3）混合型模拟：因变量随时间的推移而作连续性的变化并具有离散性的突变，如库存控制系统。,1.1.3 模拟的方式终态模拟：在规定的时间T内进行模拟运行，时间达到T时，模拟终止。其性能指标明显取决于系统的初始状态。稳态模拟：随着模拟时间的推移，系统的性能逐渐趋于平稳。其目的是研究非终态系统长期运行条件下的稳态性能，模拟时间的长短取决于能否获得系统性能的优良估计（可由模拟输出的精度确定）。,1.1.4 模拟的一般步骤明确问题，建立模型。正确描述待研究问题，明确规定模拟的目的和任务，确定衡量系统性能或模拟输出结果的目标函数，然后根据系统的结构及作业规则，分析系统各状态变量之间的关系，以此为基础建立所研究的系统模型。,收集和整理数据资料。模拟技术的正确运用，往往由大量的输入数据作依靠。在随机模拟中，应认真分析具体收集到的随机性数据资料，确定系统中随机性因素的概率分布特性，以此为依据产生模拟过程所必需的抽样数据。编制程序，模拟运行。分析模拟输出结果：模拟结果的统计特性（样本均值、方差、置信区间等），灵敏性分析，选择最优方案。,注：模拟结果的统计分析模拟的输出结果是分布特征未知的随机变量，每次运行的结果仅仅是对该随机变量所有观察值总体的一次抽样，对总体的代表性很差，虽然可以增加模拟运行的时间从而增加抽样次数，但这些数据总是由一个“种子”经过一定的算法而获得的伪随机序列，它们是自相关的，并不能构成统计上独立的随机样本。,【问题】如图，一列火车从A站开往B站，某人每天赶往B站上这趟火车.,A,B,火车运行方向,某人,他已了解到：1）火车从A站到B站的运行时间是均值为30分钟，标准差为2分钟的随机变量；,思考：请研究他能否赶上这趟火车。,1.2 随机模拟案例：赶上火车的概率,他到达B 站的时刻的频率分布为,他能否及时赶上火车？,2）火车在下午大约1点离开A站，离开时刻的频率分布如下：,明确问题：他能及时赶上火车的概率是多少？,i）分析法：用概率统计知识建立分析模型，求解析解。（思考）,ii）模拟法：用概率统计知识建立模型，通过模拟求近似解。即先建立模拟模型，然后通过计算机模拟得到问题的近似解。在同样条件下多次试验，计算他能及时赶上火车的频率。,建模方向（思路）：,问题分析：能及时赶上火车的充要条件是：,其中 T1火车从A站出发的时刻；,T2火车的运行时间；,T3他到达B站的时刻。,是什么变量？如何模拟？,ii）将午后1时记为t=0，设火车运行时间T2服从正态分布：T2 N（30，22）。,基本假设：i）假设T1，T2，T3都是相互独立的随机变量;,火车出发时刻T1和人到达B站时刻T3的分布律分别为：,建立模型：为了简化计算，将下午1点记为初始时刻。得到随机变量T1和T3的分布律如下：,能及时赶上火车的概率 p=PT3T1T2,如果r为在(0,1)均匀分布的随机数，为了模拟随机变量T1和T3，可以通过如下方法：,则t1和t3可分别用来模拟随机变量T1和T3。,主要变量说明：n 模拟次数k 临时变量，存储当前累计模拟次数count 存储赶上火车的次数,两种不同风格的算法描述,模拟算法设计,输入：赶火车次数（天数）输出：赶上火车的频率,第 1 步 输入模拟次数n第 2 步 k=1，count=0第 3 步 当k T3,count=count+1，END第 10 步 执行第3步第 11 步 输出赶上火车频率p=count/n,算法1（分步骤描述）,i）初始化：输入模拟次数n;count=0;ii)模拟n次for i=1 to n,模拟随机变量T1,T2,T3，分别赋给t1,t2,t3;if t1+t2 t3,count=count+1end if end forapp_prb=count/n;,算法2（伪代码描述）,n=input(输入模拟次数：);count=0;for i=1:n,rt1=rand;%模拟随机变量t1（火车从A站出发的时刻）if rt1=0.7 endend%forprob=count/n,模拟程序,模拟结果：每次模拟1000次或5000次,系统模拟注意事项：一次模拟结果毫无意义！模拟是试验性的,是思维结果的验证。必须进行足够多次的模拟，并对结果进行统计分析。系统模拟特点：系统模拟是研究系统，特别是动态系统的重要方法，对于：结构复杂的系统；很难用解析方法求出变量关系的系统；内部机理不明的“黑箱”系统；为验证用其他方法建立的模型及结果,应是较好的选择。,1.3 随机变量的建模利用理论分布，基于对问题的实际的、合理的假设，选择适当的理论分布模拟随机变量优点是给出了各种理论结果出现的概率，便于进行数学分析和处理。但此方法仅限于十分简单的情况，当问题越复杂，数学处理变得越困难，并且丢失了试验数据的信息。基于实际数据的频率做近似模拟优点在于完全与观察数据相符，并且随实际问题的复杂程度增大不会产生更大的困难，仅增大工作量而已。缺点是不便于进行数学分析，不得不依赖于模拟得到的统计结果。应用常将两种模拟方法结合起来使用,1.4 均匀分布随机变量模拟1.4.1 平方取中法,1.4.2 线性同余法,线性同余法程序：产生0c整数,1.5 Matlab随机模拟函数：1.5.1 常见分布随机变量的模拟,1.5.2 其它随机变量的模拟,2 Monte-Carlo模拟,2.1 Monte-Carlo原理,2.2 蒙特卡罗法应用,2.2.1 求解非线性规划,2.2.2 估算圆周率,2.2.3 估算定积分,1）频率法,2）平均值法,例1：某港口提供有足够的泊位供船舶停靠，但现在仅有一个可供装卸的泊位，船舶先到则先进行装卸，如果船舶得不到及时装卸而造成的滞期费为每小时100元。现要弄清该系统的性能，重点考察船舶进入该港后等待装卸的滞留时间以及卸位（即装卸用的泊位）的利用率，从而进行经济效益分析。,3 模拟模型案例,首先，对进入该港口的100艘船进行实际调查，记录其活动情况，得到这100艘船到达港口的时间间隔和装卸时间的分布情况的频数和累积频率分布。,表1 100艘船到达港口的时间间隔频数表,表2 100艘船装卸时间频数表,表3 船舶到达港口的时间间隔累积分布表,表4 船舶装卸时间累积分布表,为了比较准确地反映系统的性能，我们采用稳态模拟方式，可以考察系统运行360天的情况。假定港口每天24小时连续工作，因此模拟时间T设置为8640小时。考虑到船舶到达港口的事件是影响整个系统状态的主要因素，可以将模拟事件设置为该事件的发生时刻。,所用变量说明：t：一艘船到达港口的时间；tl：前一艘船驶离港口的时间；td：两艘船到达港口的时间间隔；ts：当前船舶装卸所需时间；tw：t时刻所有已到达港口的船舶等待装卸时间总和；tf：t时刻装卸位已空闲时间总和；,初始化数据 t=tl=tf=tw=0,产生船舶到达间隔时间 td设置模拟时间 t=t+td,t8640,打印输出,产生装卸服务时间ts,ttl,统计装卸位空闲时间tf=tf+t-tl,统计船舶等候时间tw=tw+tl-t,设置船舶离港时间Tl=t+ts,设置船舶离港时间Tl=tl+ts,是,是,否,否,表5 某港口对船舶服务的模拟结果,经过6次模拟计算，装卸泊位的平均利用率为95.3%，但到达的船舶的却因得不到及时的服务而造成平均每艘滞留9.295小时，每年到港船舶总滞留6843小时，因此港口每年约需支付68万元的滞留费，这显然是一笔不小的开支。为此，可修改模拟模型，考虑增设一个装卸泊位，并重新进行模拟运行，将这些数据提供给决策者一确定是否需要再新建一个装卸泊位。,练习：某公共汽车站每隔30分钟到达一辆汽车，但可能有0,3分钟的误差，此误差大小与前一辆汽车的运行无关。汽车最多容纳50名旅客，到达该汽车站时车内旅客人数服从20，50的均匀分布。到站下车的旅客人数服从3，7的均匀分布，每名旅客下车的时间服从1，7秒的均匀分布。旅客按每30分钟到达12个人的泊松分布到达汽车站，单列排队等车，先到先上，如果某位旅客未能上车，他将不再等候。旅客上车时间服从,4，12秒的均匀分布。上下车的规则是：先下后上，逐个上车，逐个下车。假设每天共发25辆汽车，现在要求模拟一天汽车的运行情况，了解一天中在站内等候汽车的总人数、能上车及不能上车的人数、旅客排队时间分布情况、不能上车人数的分布情况等。,例2：露天矿用电铲采掘矿石，然后用卡车运送到卸场。假设共有m辆卡车装运，有n台（nm）电铲同时采掘供n辆卡车同时装卸；卸场有s个卸位（s=m），可供s辆卡车同时卸料。装运过程以班为单位，每个班开始工作时，m辆中的n辆卡车由n台电铲装车，其余mn辆卡车排队等候，每辆卡车装满矿石后驶离装料处，排于队列首位的待装卡车驶至空闲电铲前并调转车头接收装料，而刚才已装满的卡车驶至卸场时，若卸位空闲则调头卸完矿石并重新驶会采掘场，排在待装卡车的队尾。,为了充分发挥每台电铲、每辆卡车的效率，提高班产量，就需要确定电铲、卡车及卸位之间的一个适当匹配数量。假定我们总共要模拟20个班运行的情况。已知每个班连续工作6小时，并且每个班开始工作时的初始状态均一致，即全部卡车都在采掘场等待装料。,经过对该矿开采情况进行收集与处理，得到以下有关数据：（1）装车时间N（1.32,0.27*0.27）；（2）重载运行时间近似一个常数4分钟；（3）卡车调头时间近似一个常数0.67分钟；（4）卸车时间e（1/0.74）；（5）卡车空载运行时间近似一个常数3分钟；（6）每辆卡车装载量N（22.5,0.83*0.83）;,记Ci（i=1m）为第i辆卡车。每辆卡车在运行过程中均要经过装车、重载运行、卸车和空载运行四个阶段（这里将卸车时和返回时接受装料的调头分别纳入卸车和空载运行），因此，可为每辆卡车Ci定义一个状态Ci.s，代表卡车所处的各个不同阶段（i=1m）。可以假定每辆卡车开始时均在采掘场，第一辆卡车开始装料后就开始影响整个系统中各辆卡车的状态，随着时间的推进，各卡车进入各自的阶段，所以又为每辆卡车Ci设置了一个进入某一阶段的时间Ci.t（i=1m）。这样，就可将模拟时间推进到所有卡车进入各自阶段时刻的最小值，相应地安排该阶段的服务，服务结束后进入下一阶段并重新设置状态值。,为简单计，这里仅考虑了在只有一个电铲和一个卸位（即ns1）的情况下，应该配备多少辆卡车m才能尽量提高电铲、卡车的效率以及班产量。,表6 不同卡车数的模拟结果表,图3 卡车数量与电铲和卡车利用率的关系,