IE09_SMS05 CH3 离散事件系统建模方法 and CH4 随机变量的产生1

第1页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新第5讲目录CH3离散事件系统建模方法§3.1系统建模概述§3.2实体流图法§3.3活动周期法回顾与补充§3.4Petri网CH4随机变量的实现第2页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新§3.2实体流图法实体流图法（EntityFlowChart）采用与计算机程序流程图相类似的图示符号和原理，建立表示临时实体产生、在系统中流动、接受永久实体“服务”以及消失等过程的流程图。可以表示事件、状态变化以及实体间相互作用的逻辑关系。四种符号：圆端矩形框、矩形框、菱形框、箭头线。第3页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新§3.2实体流图法步骤：（1）辨识系统实体（2）分析状态的状态和活动（3）分析实体状态的变化情况（4）分析引起状态变化的事件（5）分析队列实体的操作（6）画出系统实体流动图（7）确定模型参变量（8）给出排队规则第4页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新§3.3活动周期图活动周期图（ACD）建模方法将实体的状态分为静寂状态（Dead）和激活（Active）两种类型，并用相应的符号表示（P133）状态之间用箭线相连，不同的实体采用不同的线型，表示各种实体的状态变化过程。第5页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新§3.3活动周期图步骤：（1）辨识组成系统的实体及其属性（2）分析各类实体的活动和状态，确定实体状态的类型（激活或静寂），分析实体状态变化的顺序关系（3）根据实体的状态分别画出各实体的活动周期图（4）将实体的活动周期图连接成系统活动周期图（5）增添必要的虚拟实体（6）标明活动发生（实体进入激活状态）的约束条件和占用资源的数量（7）给出模型参数的取值、参变量的计算方法及属性描述变量的取值方法，并给出排队规则和服务规则第6页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新§3.3活动周期图例3.4机床加工系统考虑一个简单的加工车间。车间内有若干台数控机床，由一名工人负责看管。工人的任务是：（a）如果机床的刀具完好，则为机床安装工件，然后按下运行按钮。（b）如果机床的刀具破损或需要更新，则先要重装刀具，然后完成任务（a）。只有当机床完成一次自动加工工序并停止运行后，工人才能执行上述两项任务。假定每台机床均可加工各种工件，并且不会发生工件和刀具短缺的现象。建模的目的是为了研究工人的忙闲率。第7页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新§3.3活动周期图AWAYWAITINGRETOOLRESETRETOOLRESETOKRUNNINGREADYSTOPED工人的活动周期机床的活动周期图第8页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新§3.3活动周期图RETOOLRESETOKRUNNINGREADYSTOPEDAWAYWAITING机床加工系统ACD第9页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新OK①②③RESETRUNNINGREADYWAITING图3.24J机床加工系统初始状态OK③RESET②RUNNING①READYWAITING133x,6图3.25机床加工系统建模型运行结果（TIME=3）第10页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新表3.4机床加工系统模型人工运行结果时间开始结束安装RESET加工RUNNING安装RESET加工RUNNING0√（3）3√（6）√（13）√6√（9）√（16）√9√（19）√13√（16）√16√（19）√（26）√√19√（22）√（29）√√22√（32）√26√（29）√29√（32）√（39）√√第11页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新§3.4Petri网3.4.1Petri定义（P123）（6.3.1)3.4.2Petri网的变迁（P125）（6.3.2)第12页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新例1售票窗口服务系统剧院雇佣一名售票员同时负责剧票的窗口销售和对电话询问者的咨询服务。购票者按先到先购票的原则在窗口排队购票，询问者打来的电话由电话系统存储后按先来先服务的原则一一转接到售票员予以答复，电话服务比窗口服务有更高的优先级。售票员正在售票时若有电话打入，则售票员必须完成本次售票活动后再接电话。系统建模的目的是研究售票员的忙闲率。第13页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新WAITELSEW_HERECALLTALKPHONE=0IDLESERVICEOUTSIDEQUEUEARRIVALCUSTOMER=0询问者售票员购票者售票窗口服务系统ACD第14页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新1234abcdefg5678图3.26售票窗口系统的Petri网库所集A:购票者等待B:售票员为购票者售票C:购买票的顾客D:售票员闲E:问询者等待F:售票员为问询者咨询G:问询完的顾客变迁集1:购票者到达2:开始售票3:购票毕4:购票者离去5:问询电话打入6:开始询问7:问询毕8:问询者离开第15页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新例2生产线有一条工业生产线，它要完成两个工业操作，用t1和t2表示。第一个变迁t1将传入生产线的半成品s1和部件s2用两个螺丝钉s3固定在一起，变成半成品s4。第二个变迁t2再将s4和部件s5用3个螺丝钉s3固定在一起，得到新的半成品。完成t1和t2操作时都要用到工具s37。假定由于存放空间的限制，停放在生产线上的半成品最多不超过5件。第16页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新图3.27生产线Petri网S1S4S6S2S3S5t1t2S7K=5K=100K=1000K=100第17页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新S3S2S1t1t2t6S4S5S10t3t4S6S7t5S8S9t8t7图3.28网系统例3网系统的执行示例第18页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新变迁之间的关系S1t1S2t2S3顺序S1t1S2t2S3S4t3S5并发S1t1S2S3t2冲突S1S2t1t2S3冲撞图3.29变迁之间的关系S1t1S3t3S5S2t2S4t4S6S5t4S3t1S1S6t3S4t2S2死锁陷阱第19页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新例4加工车间Petri网系统某加工车间有三台不同的机器M1、M2和M3，两个操作工F1和F2。操作工F1可以操作机器M1和M2，操作工F2可以操作机器M1和M3。工件分为两个阶段加工，第一阶段必须用M1加工，第二阶段可用M2或M3加工，当M2和M3均处于空闲状态时，工件在M2上加工；否则工件在空闲的机器上面加工。试建立该加工车间的Petri网模型。第20页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新12345678910adigeklfhcbj图3.30机器加工车间的Petri网模型库所集A:工件到达，等待用M1加工B：工件由M1加工完，等待M2或M3加工C:工件完成加工D:机器M1空闲E:机器M2空闲F:机器M3空闲G:操作员F1空闲H:操作员F2空闲I：机器M1由F1操作J：机器M1由F2操作K：机器M2由F1操作L：机器M3由F2操作变迁集1:工件到达，2：操作员F1开始在M1上加工3:操作员F1结束在M1上加工4:操作员F2开始在M1上加工5:操作员F2结束在M1上加工6:操作员F1开始在M2上加工7:操作员F1结束在M2上加工8:操作员F2开始在M3上加工9：操作员F2结束在M3上加工10：工件输出第21页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新§3.4Petri网3.4.3Petri网性能分析（P127）（6.3.3)1、可达性2、有界性与安全性3、活性4、死锁5、冲突第22页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新CH4随机变量的实现§4.1随机数的产生§4.2随机数的检验§4.3随机变量的产生第23页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新§4.1随机数的产生什么是随机数？单个的数字不是随机数是指一个数列，其中的每一个体称为随机数，其值与数列中的其它数无关；在一个均匀分布的随机数中，每一个体出现的概率是均等的；例如：在[0,1]区间上均匀分布的随机数序列中，0.00001与0.5出现的机会均等第24页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新§4.1随机数的产生什么是随机数？单个的数字不是随机数是指一个数列，其中的每一个体称为随机数，其值与数列中的其它数无关；在一个均匀分布的随机数中，每一个体出现的概率是均等的；例如：在[0,1]区间上均匀分布的随机数序列中，0.00001与0.5出现的机会均等第25页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新§4.1随机数的产生第26页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新CH4随机变量的实现产生均匀随机数的方法:1、手工方法：（掷骰子、抽签、发纸牌等）2、随机数表：（查随机数表）3、物理方法：在计算机上装上一台物理随机数发生器，把具有随机性质的物理过程（如以放射性物质为随机源），在计算机上直接转换成随机数字。4、数学方法：得用数据递推公式在计算机上产生随机数。由于这种方法只能近似地具备随机性质，称之为伪随机数（Pseudorandomnumber）第27页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新4.1.1线性同余方法（LinearCongruentialMethod)mod:取模运算：(aIn+c)除以m后的余数实型随机数序列：mCaZZiimod)(1caZmca,,0,01951年由Lehmer提出的一种产生伪随机数的方法，是最常用的方法。1、递推公式：其中：Z0：初始值（种子seed)a：乘法器（multiplier)c：增值（additiveconstant)m：模数（modulus)mod：取模运算：(aIn+c)除以m后的余数a,c和m皆为整数产生整型的随机数序列,随机性来源于取模运算如果c=0乘同余法：速度更快，也可产生长的随机数序列第28页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新]1,0[)1()1,0[)(mfloatZZmfloatZUiiii1mZmZii2、实型随机数序列：3、特点：1）最大容量为m：mIn02）独立性和均匀性取决于参数a和c的选择例：a=c=Z0=7,m=107,6,9,0,7,6,9,0,…第29页西南科技大学制造科学与工程学院工业工程与设计系石宇强厚德博学笃行创新4、模数m的选择：•m应尽可能地大，因为序列的周期不可能大于m;•通常将m取为计算机所能表示的最大的整型量，在32位计算机上，m=231=2x1095、乘数因子a的选择：1961年，M.Greenberger证明：用线性乘同余方法产生的随机数序列具有周期m的条件是：1.c和m为互质数；2.a-1是质数p的倍数，其中p是a-1和m的共约数；3.如果m是4的倍数，a-1也是4的倍数。例：a=5,c=1,m=16,I0=1周期=m=161,6,15,12,13,2,11,8,9,14,7,4,5,10,3,0,1