《管理系统模拟》PPT课件.ppt

管理系统模拟,系统研究的有效方法,哈尔滨工业大学管理学院 马维忠副教授 ,管理科学与工程系列课程,绪论,讨论一些概念 引出模拟的概念,管理系统模拟 马维忠,3,概念,系统？ System 元素 关系 集合 系统研究：物理、解析。 模型？ Model 模拟=仿真？ Simulation Modelling & Simulation,管理系统模拟 马维忠,4,用途,有必要仿真的情形： 1 系统不存在 2 在系统上实验会造成破坏或损失 3 系统无法恢复 4 实验条件无法保障,管理系统模拟 马维忠,5,类型,仿真分类： 物理仿真 数学仿真 物力-数学仿真,管理系统模拟 马维忠,6,计算机的作用,计算机仿真常用于以下几种情况： 难以建立数学模型，无法用数学公式表示； 数学模型过于复杂，而用计算机仿真能提供简单的方法 系统的运行由于费用过高或者有一定的危险性，不适合实际运行，比如研究航天飞船的飞行 某些数学模型可通过计算机仿真进行检验,管理系统模拟 马维忠,7,管理系统,连续系统 离散（事件）系统,管理系统模拟 马维忠,8,课程内容 一、数理统计基础 二、概念模型及建模 三、物理模型及建模 四、结果分析 五、仿真模型校验 六、仿真语言与集成环境,管理系统模拟 马维忠,9,参考书目,1、孙铮编，管理系统模拟，哈尔滨工业大学，1996 2、王维平等编著，离散事件系统建模与仿真，国防科技大学出版社，1997 3、顾启泰编著，离散事件系统建模与仿真，清华大学出版社，1999 4、周德才等编著，计算机随机模拟原理、方法及计算程序，华中理工大学出版社，1998 5、王维平等编著，仿真模型有效性确认与验证，国防科技大学出版社，1998,管理系统模拟 马维忠,10,6 何江华。计算机仿真导论。科学出版社。2001 7 黄柯棣等。系统仿真技术。国防科技大学出版社。1998 8 肖田元等。系统仿真导论。清华大学出版社。2000 9 陈理荣。数学建模。北京邮电大学出版社。1999,一、数理统计基础,概率论的基本概念 数值属性的相关算法,管理系统模拟 马维忠,12,本部分内容,1 概率统计基本概念 2 常用的概率分布形 3 系统概率分布模型 4 随机变量模型的确定 5 随机数的产生 6 随机变量的产生,管理系统模拟 马维忠,13,1 概率统计基本概念,确定事件： 在给定条件下进行的试验中，一定发生或一定不发生的事件称为必然事件和不可能事件，这类事件是确定性的，总称为确定事件。,管理系统模拟 马维忠,14,随机事件： 在给定条件下进行的试验中，可能发生也可能不发生，而在大量重复试验中却具有某种规律性的事件，称为随机事件。,管理系统模拟 马维忠,15,随机变量： 如果试验的每个结果用变量的一个值来表示，即变量的值根据试验结果来确定，因而它的取值是随机的，而且对任意实数，是一个随机事件，这种变量称为随机变量。,管理系统模拟 马维忠,16,概率： 对大量重复试验，得到统计规律的属性， 表明事件发生的可能性大小是事件本身固有的客观属性。 称事件发生的可能性的大小为事件的概率，记为P(A)。当试验次数n足够大时，可以用事件的频率作为事件概率的近似值，即P(A)m/n。,管理系统模拟 马维忠,17,概率分布： 对于随机变量，事件x的概率Px是实变量x的函数，称之为的概率分布函数，简称为分布函数，记为F(x),即F(x)= Px， （-x+） 离散型随机变量可能取的值为x1,x2,xn, = xk 为一随机事件，其发生概率记为Pk=P=xk,k=1,2,n。Pk为离散型随机变量的概率分布，Pk满足Pk0。,管理系统模拟 马维忠,18,分布密度函数： 连续型随机变量的分布函数F(x)能表示成某个函数f(x)的积分，f(x)称的分布密度函数，简称密度函数。,管理系统模拟 马维忠,19,均值，也称数学期望：E(),表示随机变量取值的平均大小。,离散型随机变量 连续型随机变量,管理系统模拟 马维忠,20,方差： D(),描述随机变量的取值与其均值E()的分散程度，反映了数据波动的大小。,离散型随机变量 连续型随机变量,管理系统模拟 马维忠,21,总体：概率统计计算的全部元素所组成的集合。 个体：组成总体的最小研究单位。 抽样：通过试验观测得到的总体的部分结果。 样本量：抽样中包括的个体数量。,管理系统模拟 马维忠,22,2 常用的概率分布形,(0-1)分布：随机变量只能取0和1二值 P=1=p P=0=1-p E()=1*p + 0*(1-p)=p D()=(1-p)2*p+(0-p)2*(1-p)=p(1-p),管理系统模拟 马维忠,23,二项分布：设试验E只有两种可能结果，成功（记为A）和失败（记为B）,P(A)=p, P(B)=1-p, 将E独立地重复进行n次，则称这n次重复独立的试验为n重Bernoulli试验，简称Bernoulli试验。以随机变量表示n重Bernoulli试验中事件A发生的次数，则A恰好发生k(0kn)次的概率为P(=k)=Pn(k)=,k=0,1,n E()=np D()=np(1-p),管理系统模拟 马维忠,24,几何分布：几何分布式关于Bernoulli试验的序列问题，所考虑的随机变量定义为达到第一次成功的试验次数。 P(=K)=(1-P)K-1P E()= 1/p D()= (1-p)/p2,管理系统模拟 马维忠,25,泊松(Poisson)分布：随机变量所有可能取值为0，1，2，P(=k)=,E()=D()=,管理系统模拟 马维忠,26,均匀分布：连续型随机变量在有限区间（a,b）内取值，且落在任意等长的子区间的可能性相同。,管理系统模拟 马维忠,27,E()=(a+b)/2 D()=(b-a)2/12,管理系统模拟 马维忠,28,指数分布：称服从参数为的指数分布，若,E()=1/,D()=1/2,管理系统模拟 马维忠,29,正态分布：称服从参数为，的正态分布，若,E()= D()=2,管理系统模拟 马维忠,30,3 系统概率分布模型,在离散事件系统的建模过程中，经常要研究一些不确定的随机事件，需要引入概率分布 排队系统 库存系统 系统可靠性、维修性研究,管理系统模拟 马维忠,31,排队服务系统,在排队系统中，主要有两种类型的活动，即实体到达和实体接受服务 实体到达的时间间隔： 固定值 随机变量：泊松/指数，均匀 实体接受服务的时间： 固定值 随机变量：均匀，指数，正态,管理系统模拟 马维忠,32,服从泊松分布到达的实体： 在一定时间间隔内到达实体的数目仅与时间间隔的长短有关，而与这段时间间隔的起始时刻无关。 在某个时间间隔内到达的实体数目与在此之前到达的实体数目无关，也不影响在此之后的实体到达。 不存在两个或两个以上实体同时到达的情况。 若在一定时间内到达系统的实体数目x服从参数为的泊松分布，则相邻到达的两个实体之间的到达时间间隔T服从参数为的指数分布。,管理系统模拟 马维忠,33,库存系统,在现实库存系统中有三个随机变量： 每次订货或单位周期内的需求量； 两次需求间的时间间隔； 发出订单到收到订货的时间间隔，也成为提前期。,管理系统模拟 马维忠,34,可靠性与维修性,在系统可靠性与维修性建模中，优先考虑的随机变量是系统中部件的无故障工作时间和故障后的修复时间 通常部件发生故障的时间分布和修复时间分布用指数分布来描述。正态分布适用于多数故障是由于磨损产生的系统。,管理系统模拟 马维忠,35,综上所述，在离散事件系统建模过程中，随机变量较常采用的分布形式是指数分布和正态分布， 其主要原因是： 指数分布简单，数据处理容易。,管理系统模拟 马维忠,36,指数分布的一个重要特点是无记忆性，这与大多数与时间有关的随机现象是一致的 指数分布与许多其他分布形式有关。 正态分布虽然没有指数分布那样多的优点，但也是描述随机变量所必不可少的一种分布形式。正态分布的特点之一是可以使随机变量取值相对集中或者使随机变量散布很大甚至接近于均匀分布。这个特点使它具有很广的应用范围。,管理系统模拟 马维忠,37,4 随机变量模型的确定,在获得了有关随机变量概率分布的观测数据后，可以分析随机变量的分布特性，并在此基础上建立相应的模型。在建模过程中，需要完成以下两个任务： 由观测数据确定随机变量的概率分布形式。 在随机变量概率分布类型已知的情况下，由观测数据确定分布参数。,管理系统模拟 马维忠,38,分布类型假设 由观测数据来确定随机变量的分布类型，最常用的方法是对观测数据进行适当的预处理， 然后将预处理的结果与已知分布类型的相应结果进行比较，做出随机变量概率分布的假设。,管理系统模拟 马维忠,39,预处理的方法有两种： 点统计法 直方图法,管理系统模拟 马维忠,40,点统计法的思想是比较随机变量概率分布数字特征之间的关系，即通过比较概率分布的偏差系数来进行分布类型的假设。 对于随机变量，其偏差系数定义为： = D()1/2/E()，即偏差系数为均方差与期望值的比。,管理系统模拟 马维忠,41,管理系统模拟 马维忠,42,直方图法是一种直观的近似求分布密度函数的图解方法。它将观测数据的取值范围(a0,a1)划分为k个断开的相邻区间，每个区间宽度相等。令fj表示第j个区间上观测数据出现的频率，构成分段函数h(x)。根据函数h(x)图像的形状选择类似的分布。,管理系统模拟 马维忠,43,分布参数的估计 对随机变量的观测数据可以用来判断随机变量的分布类型，同时也需要利用观测数据来确定分布中的参数。 参数估计分为点估计和区间估计，以下仅讨论分布参数的点估计问题。,管理系统模拟 马维忠,44,每一类分布都具有其相应的分布参数，分布参数影响分布的统计性质。从几何角度看，分布参数的影响主要体现在三个方面： a位置参数：确定一个分布的密度函数在横坐标上的取值范围，以及分布密度曲线与坐标原点的相对位置。P(x - ) b比例参数：决定分布密度函数在其取值范围内的比例尺，比例参数的改变只是使分布密度取现在横坐标上压缩或扩张。 P(x) c形状参数：确定分布函数的形状，影响分布行数的性质。 P(x),管理系统模拟 马维忠,45,5 随机数的产生,在许多系统中，事件的发生是随机的，或者事件的属性值的确定具有偶然性 要模仿这些偶然性 需要随机数,管理系统模拟 马维忠,46,使用过的真正随机数的发生源有： 一袋小球，进行可替换抽样； 微秒级时钟上的低阶数字； 一个随机电子噪声源的周期性量化输出值 共同的缺点是在仿真过程中，用这些方法产生的随机数通常不能复现,管理系统模拟 马维忠,47,伪随机数 所产生的数必须服从均匀分布 所产生的数必须是统计独立的 所产生的随机数序列必须是可以重现的 所产生的随机数序列在需要的长度内必须不重复-周期。 随机数产生的速度必须快 用于产生随机数的方法应当占用尽可能小的存储空间,管理系统模拟 马维忠,48,第一种方法是利用某种手段生成一个随机数序列并将它永久保存起来，例如存在计算机硬盘上 第二种方法是利用某种手段生成一个随机数序列并将其保留在计算机内存中 第三种方法也是最常用的一种方法，是利用某种算法根据指定的输入值来产生随机数,管理系统模拟 马维忠,49,平方取中法 平方取中法是冯纽曼（John von Neumann）在40年代中期提出的 这个方法首先从某个初始的种子数开始，求出这个数的平方，取这个平方数的中间几位数作为随机数序列中的第2个数；再求出第2个数的平方，又取这个平方数的中间几位数作为随机数序列中的第3个数；不断按这个方式继续此算法，即可得到相应的伪随机序列。,管理系统模拟 马维忠,50,管理系统模拟 马维忠,51,线性同余法 线性同余法在1951年由莱默尔（Lehmer）首先提出。 在这个算法中，随机数序列中的数由下列递推关系产生,种子,乘子,增量,模数,管理系统模拟 马维忠,52,常数的值对所产生的随机数序列的周期长度有很大影响。 例如设a=5 c=3 m=16，取x0=7，利用线性同余法产生随机数序列。 在n=16时出现循环。 为了使重复周期充分长，对常数的选择比较重要,管理系统模拟 马维忠,53,加同余法 加同余法需要个数的序列作为种子，这个序列可以应用其它的方法产生，应用家同与法可以是这个序列不断扩大。其算法是,管理系统模拟 马维忠,54,二次平方同余法 二次平方同余法适用于为的幂次的情况，这种方法的递推关系式为,管理系统模拟 马维忠,55,伪随机数系列的质量需要检验 伪随机数的产生用于模仿在一个连续分布上的抽样，对伪随机数序列的检验和确认通常需要将该伪随机数序列与均匀分布的期望情况进行比较 随机度 均匀 独立性 周期,管理系统模拟 马维忠,56,6 随机变量的产生,随机变量的产生就是生成非均匀分布的随机数的过程。 方法 常用的随机变量,管理系统模拟 马维忠,57,反变换法 当分布密度函数f(X)可积分得出累计分布函数F(X)或F(X)是一个经验分布,管理系统模拟 马维忠,58,例1：某随机变量的概率分布函数由下式给出,管理系统模拟 马维忠,59,求出其逆函数为,管理系统模拟 马维忠,60,若产生的标准均匀分布的伪随机数序列为0.1021, 0.2162, 0.7621，则得到的随机变量为：,管理系统模拟 马维忠,61,例2：随机变量x的概率分布函数由下表确定,若x为连续的随机变量，可以根据例1中的方法产生，如生成的标准均匀分布随机数为0.25， 则可以在1.0与1.5之间线性插值获得，x=1.0833。 若x为离散性的随机变量，x=1.0。,管理系统模拟 马维忠,62,函数变换法 当通过F(x)无法获得反函数表达式时，函数变换是一种变通方式。做法是利用变量替换，试图获得一种能求出反函数的形式，求出随机变量后再替换回来。,管理系统模拟 马维忠,63,设连续型随机变量x的概率分布函数F(x)不存在反函数形式，做变量替换，令,管理系统模拟 马维忠,64,设g(y)的一阶导数存在，则随机变量y的概率密度函数为,管理系统模拟 马维忠,65,从而得到其分布函数,管理系统模拟 马维忠,66,若G(y)的反函数存在，则可确定随机变量y,从而得到随机变量x的值为,管理系统模拟 马维忠,67,组合法 组合法的基础思想是随机变量的分布函数可以表示成若干其他分布之和,其中Fj(x)比F(x)容易获得。,管理系统模拟 马维忠,68,拒绝法，也称接受拒绝法。 基本思想是构造随机变量概率密度函数f(x)的变换Cf(x)，使,管理系统模拟 马维忠,69,步骤为 a)将f(x)的值域归一化，即选择常数C，使,b)定义x为a, b上的均匀连续随机变量,管理系统模拟 马维忠,70,c)生成一对随机数r1，r2 d)若,则随机变量取,否则返回c),管理系统模拟 马维忠,71,常用分布的随机变量产生,非标准均匀分布 标准均匀分布的取值范围在0, 1)，因此a, b上均匀分布的随机变量可用,管理系统模拟 马维忠,72,指数分布 指数分布的概率密度函数为,利用反变换法，取其逆函数,指数分布的随机变量x可由下式产生,管理系统模拟 马维忠,73,正态分布 利用组合法：根据中心极限定理，n个均值为 方差为 的独立同分布的随机变量 的和服从均值为 方差为 的近似正态分布,管理系统模拟 马维忠,74,拒绝法：标准正态分布的概率密度函数为,在,时取得极大值,，因此取,管理系统模拟 马维忠,75,1)生成一对随机数r1，r2 2)若,，则随机变量取,；否则返回1),二、概念模型及建模,模型 建模方法 实例,管理系统模拟 马维忠,77,模型：为了达到系统研究的目的，用于收集和描述系统有关信息的实体。 模型是为研究用的和系统有关的信息的组合，他放映了系统某些方面属性的本质。,管理系统模拟 马维忠,78,离散事件系统的时间是连续变化的，而系统的状态仅在一些离散的时刻上由于随机事件的驱动而发生变化。 由于状态是离散变化的，而引发状态变化的事件是随机发生的，因此这类系统的模型很难用数学方程是来描述。,管理系统模拟 马维忠,79,实体流程图法与计算机流程图的画法类似，可以描述临时实体的产生、流动、消亡及其被永久实体加工、处理的过程和逻辑关系，应用比较广泛；所建立的实体流程图模型易于转换为面向事件的仿真模型。,管理系统模拟 马维忠,80,活动周期图法针对实体的行为模式进行建模，可以直观地表示出某类实体生命周期中的活动和状况，具有规范化的特点，对不同实体之间协同关系的描述十分清晰、明确。而且，应用活动周期图法建立的系统模型，转换为面向活动的仿真模型比较方便。,管理系统模拟 马维忠,81,Petri网方法适用于建立加工系统等多种离散事件系统的模型，并可对网系统的特性进行比较严密的数学分析，得到对并发、冲突、死锁等现象的深刻认识，应用也比较广泛。,管理系统模拟 马维忠,82,1 基本建模术语,实体（Entity） 实体是被仿真系统中可单独辨识和刻划的构成要素。例如，工厂中的机器，商店中的服务员，生产线上的工作，交通道路上的车辆等。在建模人员看来，实际系统就是由互相存在一定关系的实体集合组成的，实体间的相互联系和作用产生系统特定的行为。 属性和行为相同或相近的实体可以用类来描述，这样可以简化系统的组成和关系。例如，理发店服务系统可以看成是由“服务员”和“顾客”两类实体组成的，而两类实体间存在服务与被服务的关系。,管理系统模拟 马维忠,83,属性（Attribute） 属性是实体特征的描述，一般是实体所拥有的全部特征的一个子集，用特征参数或变量表示。选用哪些特征参数作为实体的属性与建模目的有关，可以参照下属原则选取： a便于实体的分类：例如，考虑将顾客的“性别”作属性，每类顾客占用不同的服务台； b便于实体行为描述：飞机的“速度”属性便于描述飞行时间； c便于排队规则的确定：工件加工的“优先级”属性便于按有限级别分别排队。,管理系统模拟 马维忠,84,活动（Activity） 实体在一段时间内持续进行的操作或过程。活动所占用的世间区段称为忙期（Duration），忙期可以是定时的或随机的。在离散事件系统建模中，一般要给出忙期的计算公式或概率分布函数，保证实体一进入某一活动时期忙期就可以计算，或从某一分布函数中抽取到。,管理系统模拟 马维忠,85,状态（State） 对实体活动的特征状况或状态的划分，其表征量称为状态变量。活动总是与一个或几个实体的状态相对应的。,管理系统模拟 马维忠,86,事件（Event） 导致系统状态产生变化的瞬间操作或行为。事件发生的时刻称为事件点。不关心事件所代表的操作和行为意义时，事件和事件点是同义语。若事件的发生是有前提的，则称为条件事件。 考察活动、状态和事件三者的联系。由于事件的发生会导致状态的变化，而实体的活动可以与一定的状态相对应，因此可以用事件来标识活动的开始和结束。,管理系统模拟 马维忠,87,进程（Process） 一组按发生时间排列的事件/活动序列。,管理系统模拟 马维忠,88,管理系统模拟 马维忠,89,队列（Queue） 处于等待状态的实体序列。一般按新到的实体排在队尾的次序组成队列。在离散事件系统建模中，队列可以作为一种状态或特殊实体对待。,管理系统模拟 马维忠,90,2 实体流图法,在离散事件系统中，实体可以分为两大类： 临时实体 永久实体,管理系统模拟 马维忠,91,临时实体按一定的规律由系统外部进入系统，在系统内部接受永久实体的作用，按照一定的流程通过系统，最后离开系统。因此，临时实体只在系统中存在一段时间即自行消失。,管理系统模拟 马维忠,92,与临时实体相反，那些永久驻留在系统中的实体称为永久实体，它们是系统产生功能的必要条件。 系统要对临时实体产生作用，就必须有永久实体的活动，这是临时实体和永久实体协同完成了某项活动，永久实体被作为活动的资源而占用。,管理系统模拟 马维忠,93,实体流程图法采用计算机程序流程图的图示符号，建立表示临时实体产生、在系统中流动、接受永久实体服务以及消失等过程的流程图。借助实体流程图，可以表示事件、状态变化及实体间相互作用的逻辑关系。,管理系统模拟 马维忠,94,建模可以按如下思路： 辨识组成系统的实体及属性。将队列作为一种特殊的实体来考虑。 分析各种实体的状态和活动，及其相互间的影响。队列实体的状态是队列的长度。 考察有哪些事件导致了活动的开始和结束，或者可以作为活动开始或结束的标志，以确定引起实体状态变化的时间，并合并条件事件。 分析各种事件发生时，实体状态的变化规律。 在一定的服务流程下，分析与队列实体有关的特殊操作（如换队等）。 通过以上分析，以临时实体的流动为主线，用约定的图示符号画出被仿真系统的实体流程图。 给出模型参数的取值、参变量的计算方法及属性描述变量的取值方法。 给出队列的排队规则。有多个队列存在时，还应给出其服务规则，包括队列的优先次序、换队规则等。,管理系统模拟 马维忠,95,例1 理发店服务系统：有一个理发店只有一个理发员。顾客来到理发店后，若有人正在理发就坐在一旁等候。理发员按先来先服务的原则为每位顾客服务，而且只要有顾客就不停歇。建模的目的是在假定顾客到达时间间隔和理发花费的时间服从一定的概率分布时，考察理发员的忙闲情况。,管理系统模拟 马维忠,96,该系统由3类实体组成：理发员、顾客及顾客队列。 理发员是永久实体，其活动为“理发”，由“忙”和“闲”两种状态。 顾客是临时实体，他与理发员协同完成“理发”活动，有“等待服务”、“接受服务”等状态，其中“接受服务”状态对应理发员的“忙”状态。 顾客队列是抽象实体，其状态以队列长度标识。,管理系统模拟 马维忠,97,三类实体的活动和状态之间存在如下逻辑关系： (1) 一个顾客到达时，若理发员处于“忙”状态，则顾客进入“等待服务”状态；否则，进入“接受服务”状态； (2) 理发员完成对一个顾客的服务后，如果队列处于“非零”状态，则立即开始服务活动；否则进入闲状态。,管理系统模拟 马维忠,98,“顾客到达”或“顾客结束排队”可以导致“服务”活动的开始，而“顾客离去”可以导致“服务”活动的结束，可以看作事件。而“顾客结束排队”是以理发员的状态为“闲”为条件的，是条件事件，可以不单独考虑。,管理系统模拟 马维忠,99,管理系统模拟 马维忠,100,例2 分时计算机系统：分时计算机系统由一个CPU和多台终端组成。用户从终端输入作业，请求CPU服务。CPU按FIFO分时轮流执行作业，每个作业执行一个时间片后若未完成则重新排队。某终端的作业完成后才可以继续输入作业。建模的目的是研究用户的等待时间。,管理系统模拟 马维忠,101,管理系统模拟 马维忠,102,例3 售票窗口系统：剧院由一名售票员负责在窗口售票并同时接待电话咨询服务，窗口服务比电话服务优先。问讯电话可以由电话存储系统按先后顺序存储并由售票员一一答复。建模的目的是研究售票员的忙闲情况。,活动周期模型,管理系统模拟 马维忠,103,管理系统模拟 马维忠,104,模型的人工运行 建立实体流程图模型后，选取有代表性的例子观察系统按模型的运行情况，称人工运行。人工运行模型的要求是遍历流程图的各个分支和实体的各种状态，在时间逐步变化的动态条件下，分析事件的发生及状态的变化过程，以检验模型的组成关系和逻辑关系是否正确。,管理系统模拟 马维忠,105,在例1中，假定： 系统的初始状态：初始时刻，理发店开门营业时；理发员状态，闲；队列状态，长度为0；,管理系统模拟 马维忠,106,模型参数及变量取值：本模型的参变量包括第I个顾客与第I-1个顾客到达的时间间隔Ai，以及理发员为第I个顾客理发的时间Si。一般来说，Ai与Si均为随机变量，这里为便于解释，取其样本值为： A1=15，A2=32，A3=24，A4=40，A5=22， S1=43，S2=36，S3=34，S4=28，,管理系统模拟 马维忠,107,本模型运行的规则： 规则1确定当前时间。当前时间TIME在开始运行时取仿真初始时刻，并随时间逐步推移递取最早事件发生的时刻。在当前时间，若发生顾客到达事件，执行规则2；若发生顾客离去事件，执行规则3。 规则2顾客到达事件处理。若理发员忙，队列长度加1；否则，开始理发，置理发员为“忙”，经Si后离去。 规则3顾客离去事件处理。若队列长为0，置理发员为“闲”；否则，队列首的顾客开始理发，队列长度减1，经Si后离去。,管理系统模拟 马维忠,108,人工运行过程如下：,管理系统模拟 马维忠,109,3 活动周期图法,系统中实体的行为模式在有限的几种情况之间周而复始地变化，表现出一定的生命周期形式。活动周期图（Activity Cycle Diagram, ACD）正是基于这样的一种思想逐步形成的离散事件系统建模方法。,管理系统模拟 马维忠,110,活动周期图以直观的方式显示了实体的状态变化历程和各实体之间的交互作用关系，便于理解和分析。活动周期图可以充分反映各类实体的行为模式，并将系统的状态变化以“个体”状态变化的集合方式表示出来，因此可以更好地表达众多实体的并发活动和实体之间的协同。但是，它只描述了系统的稳态，而没有表示系统的瞬态，即活动的开始和结束事件。,管理系统模拟 马维忠,111,活动周期图建模方法将实体的状态分为静寂（Dead）和激活（Active）两种，并分别用不同的符号表示。,管理系统模拟 马维忠,112,管理系统模拟 马维忠,113,状态之间用箭头线相连，不同的实体用不同的线型，表示各种实体的状态变化历程。,管理系统模拟 马维忠,114,激活状态通常是实体的活动，模型中活动的忙期可以采用随机抽样的方法事先加以确定。 静寂状态通常表示无活动发生，是实体等待参加某一活动的状态，其持续时间在模型中无法事先确定，取决于有关活动的发生时刻和忙期。,管理系统模拟 马维忠,115,每一类实体的生命周期都由一系列状态组成。随着时间的推移和实体间的相互作用，各个实体从一个状态变化到另一个状态，形成一个动态变化过程。,管理系统模拟 马维忠,116,活动周期图建模过程如下： 1、辨识组成系统的实体及属性 辨识组成系统的永久实体和临时实体，队列不作为实体考虑。 2、分别画出各实体的活动周期图 实体活动周期图的绘制要以实际过程为依据。队列作为排队等待状态来处理。在实体流程图法中当作事件看待的某些操作获悉，要拓展为活动来处理。,管理系统模拟 马维忠,117,活动周期图服从以下原则： 交替原则 静寂状态和激活状态必须交替出现。如果系统中某一活动完成后其后续活动就立即开始，则后续活动称直联活动。为了使直联活动与其前置活动的连接仍符合交替规则，规定这两个活动之间存在一个虚拟队列。 闭合原则 每类实体的活动周期图必须是闭合的，其中临时实体的活动周期表是一个或单位实体从产生到消失的循环过程，而永久实体的活动周期则表示一个或几个实体被占用和释放的循环往复过程。,管理系统模拟 马维忠,118,3、将各实体的活动周期图连接成系统活动周期图 以各实体之间的协同活动为纽带，将各种实体的活动周期图合并在一起。,管理系统模拟 马维忠,119,4、添加必要的虚拟实体 在活动周期图中，当一个活动的所有前置静寂状态取非0值（队列不空）时，该活动才可能发生。利用这一特性，可以添加某些必要的虚拟实体，并假定它们与另外的实体协同完成某项活动。用这种办法可以为实体活动的发生加上某种附加条件，从而实现“隔时发生”的建模效果。,管理系统模拟 马维忠,120,5、标明活动发生的约束条件和占用资源数量 包括：活动是否可以发生的判断条件，这些条件应是用ACD图示符号无法或不便表达的；永久实体在参加一次协同活动是被占用或活动完成时释放的数量。活动发生的条件一般是某种表达式，标在活动框的旁边。协同活动发生时占用/释放永久实体的数量标在相应箭头线的旁边（带有+/-符号），数量为1时不标。,管理系统模拟 马维忠,121,6、给出模型参数的取值、参变量的计算方法及属性描述变量的取值方法，并给出排队规则和服务规则。,管理系统模拟 马维忠,122,例1 机床加工系统：考虑一个简单的加工车间。车间内有数台自动机床，由1名工人负责看管。工人的任务是：如果机床的刀具完好，则为机床安装工件，然后按下运行按钮；如果机床的刀具损坏，则先要重装刀具，然后完成任务。只有当机床完成一次自动加工工序并停止运行后，工人才能执行上述两项任务。假定每台机床均可加工各种工件，并且不会发生工件短缺的情况。建模的目的是研究工人的忙闲情况。,管理系统模拟 马维忠,123,显然，建模时要考虑两类实体：机床和工人。 1）工人 工人从事两项主要活动：“安装工件”和“安装刀具”。当工人不处于上述两种激活状态时，就处于静寂状态“等待”。,管理系统模拟 马维忠,124,管理系统模拟 马维忠,125,2）机床 机床有三种激活状态：“安装刀具”、“安装工件”和“加工”，其中前两个是与工人实体协同完成的活动。,管理系统模拟 马维忠,126,管理系统模拟 马维忠,127,管理系统模拟 马维忠,128,例2 售票窗口系统：剧院由一名售票员负责在窗口售票并同时接待电话咨询服务，窗口服务比电话服务优先。问讯电话可以由电话存储系统按先后顺序存储并由售票员一一答复。建模的目的是研究售票员的忙闲情况。,实体流程模型,管理系统模拟 马维忠,129,管理系统模拟 马维忠,130,模型的人工运行 在运行模型之前，首先要确定系统的初始状态。系统出是状态的确定要符合被仿真系统运行前的实际情况。 标记临时实体在初始状态下的位置。一般，它们处于静寂状态。 标记永久实体在初始状态下的位置。一般，它们处在“等待”、“空闲”等静寂状态。,管理系统模拟 马维忠,131,初始状态确定后，按下列规则运行模型： 规则1活动的发生与执行 按照服务优先级，依次检查各临时实体每项活动的前置状态（均为静寂状态）和标在活动上访的发生条件，判断活动是否可以开始。满足以下2条件的活动可以开始： a. 活动的所有前置状态中均有实体停留，且各类永久实体的数量超过或等于相应箭头上标明的资源占用量。 b. 活动发生的约束条件已经满足。 如果某项活动可以开始，则将其前置状态中标号最小的临时实体的标记移至该活动框中。然后，修改该活动前置状态中各永久实体当前资源量，修改方法是从各永久实体的当前资源量中分别减去该活动对该资源的占用量。如果某类永久实体的当前资源量变为0，则取消其在活动前置状态中的标记；否则予以保留。 对于那些被确定可以开始的活动，需根据各项活动的忙期分别确定其活动终止时间，并将终止时间表在活动框外，然后转规则2。,管理系统模拟 马维忠,132,规则2确定当前时间 检查所有活动的终止时间，从中选出最小者作为当前时间，然后转为规则3。,管理系统模拟 马维忠,133,规则3活动完成 从所有已发生的活动中，检出终止时间等于当前时间的临时实体，删掉其标在活动框外的终止时间。然后，将相应活动框内的临时实体的标记移至相关的后续状态之中。参与活动的永久实体的资源量增加，增加的数量等于该活动完成后的释放量。最后，将参与活动的各永久实体的后续状态分别作上标记，转规则1。,管理系统模拟 马维忠,134,25 18 27 16 31,5 9 8 11 3 ,15 32 24 40 22 ,2 4 5 4 3,管理系统模拟 马维忠,135,现在，我们总结一下实体流程图法与活动周期法的区别与各自特点：,管理系统模拟 马维忠,136,实体流程图（以下简记为EFC）是以临时实体在系统中的流动过程为主线建立的模型，永久实体浓缩于表示状态和事件的图示符号之中，队列被作为一种特殊的实体来对待。对这三种实体的描述交织在一起，使得临时实体和永久实体没有单独的图示。活动周期图ACD则基于各类临时实体和永久实体的行为模式，它们均有单独的图示表达，队列很自然地成为实体生命周期中的一种状态。,管理系统模拟 马维忠,137,ACD种，各类实体的图示是“环形”的循环图，整个系统的ACD由多个环组成；而EFC则是带有小循环的“树型”流程图。,管理系统模拟 马维忠,138,事件是EFC的重要组成部分，在EFC中有显示的表达；而在ACD种，事件蕴含在活动中，没有显示表达。,管理系统模拟 马维忠,139,状态判断框在EFC中的作用十分重要。ACD将EFC中需要作判断的状态用“空闲”、“等待”等静寂状态表示，而对于实体是否处于该状态中的判断则勿需标在图中，而升华为规则。,管理系统模拟 马维忠,140,从运行规则看，ACD的运行规则与模型无关；而EFC除第1条规则是通用的外，其余的规则要从EFC中抽取，普适性很差。,管理系统模拟 马维忠,141,由和知，ACD更易于用面向对象的技术实现，软件上也更易于实现仿真程序的自动生成。另外，由知，ACD表示冲突和并发现象更为方便、直观。,管理系统模拟 马维忠,142,正由于EFC没有ACD那样规范，因此，在不考虑模型运行问题时，EFC比ACD的适用范围更广。另外，EFC中可以对队列的排队规则和服务规则进行比较详细的描述。,管理系统模拟 马维忠,143,4 Perti网方法,Petri网的概念是德国Carl Adam Petri博士1960年首先提出的。 经过近40年的发展，Petri网建模方法已经在机械加工、计算机通讯系统、C3I系统等多个领域内得到广泛的应用，并得到不断改进，产生了很多改进形式。,管理系统模拟 马维忠,144,网,定义1 Petri网 三元组,称为Petri网的充要条件是：,管理系统模拟 马维忠,145,条件和表明，Petri网由S和T两类元素组成；其中S叫做的库所集，T叫做变迁集。条件表明，F是由一个元素S和一个元素T组成的有序偶的集合；F称为的流关系。,管理系统模拟 马维忠,146,条件表明，,不能有孤立元素，从而,和,均不能为空集。,管理系统模拟 马维忠,147,Petri网又称有向网，简称网。,称为,的元素集。,管理系统模拟 马维忠,148,定义2 元素的输入和输出集,设,为网,的一个元素，令,，则,称为,的输入集或前集；,称为,的输出集或后集。,管理系统模拟 马维忠,149,Petri网的标准图形表示是用圆圈代表库所，用方框或竖线表示变迁，用从x到y的有向弧线表示有序偶(x, y)。如果(x, y)是从x到y的有向弧，就称x是y的输入，y是x的输出。,管理系统模拟 马维忠,150,下图给出了窗口售票系统的Petri网模型图。,管理系统模拟 马维忠,151,库所集： a 购票者等待 b 售票员为购票者售票 c 买票的顾客 d 售票员闲 e 问讯者等待 f 售票员为问讯者咨询 g 问讯完的顾客,管理系统模拟 马维忠,152,变迁集： 1 购票者到达 2 开始购票 3 购票完毕 4 购票者离去 5 问讯电话打入 6 开始问讯 7 问讯完毕 8 问讯者离开,管理系统模拟 马维忠,153,网系统,网是系统静态结构的基本描述，要模拟系统的动态特性，需要定义网系统。,管理系统模拟 马维忠,154,定义3 容量、标识和权,设,是有向图，,称为,上的一个容量函数。,表示,的容量为无穷。,映射,管理系统模拟 马维忠,155,若,是,上的容量函数，映射,称为,的一个标识的充要条件是,，均满足,。,管理系统模拟 马维忠,156,映射,称为,的权函数。,在弧,上的值用,表示。,管理系统模拟 马维忠,157,管理系统模拟 马维忠,158,管理系统模拟 马维忠,159,弧上标出的整数用以表示某一变迁对资源的消耗量或产品的生产量（默认1），也就是弧上的权值。 用给出的数字说明某一库所中允许存放资源的最大数量，即为库所的容量值。未加标注的库所的容量为无穷大。,管理系统模拟 马维忠,160,库所中的黑点数表示该库所当前的实际资源/产品数。这里，同一库所中的资源或产品被看作是完全等价的个体，均用黑点表示；黑点称为令牌或标记，各个库所中的黑点数就是标识。,管理系统模拟 马维忠,161,管理系统模拟 马维忠,162,管理系统模拟 马维忠,163,管理系统模拟 马维忠,164,管理系统模拟 马维忠,165,管理系统模拟 马维忠,166,当变迁不断发生时，网系统的状态也不断发生变化，这一过程称为网系统的执行。网系统的执行规则由定义5给出。,管理系统模拟 马维忠,167,管理系统模拟 马维忠,168,管理系统模拟 马维忠,169,定义5中的变迁条件和发生规则可以解释如下： 一个变迁被授权发生，当且仅当该变迁的每一个输入库所的令牌数大于或等于输入弧的权值，并且该变迁的输出库所已有令牌数与输出弧权值的和小于输出库所的容量；简言之，“前面够用，后面够放”。,管理系统模拟 马维忠,170,变迁发生（点火）的充要条件是该变迁是授权的。 变迁发生时，从该变迁的输入库所中移出与输入弧权值相等的令牌数，在该变迁的输出库所中产生与数出弧权值相等的令牌数。,管理系统模拟 马维忠,171,管理系统模拟 马维忠,172,管理系统模拟 马维忠,173,管理系统模拟 马维忠,174,在网系统中，可以定义变迁之间的顺序、并发、冲突和冲撞关系，如下图。另外，库所集还存在死锁和陷阱的可能性。,管理系统模拟 马维忠,175,管理系统模拟 马维忠,176,管理系统模拟 马维忠,177,管理系统模拟 马维忠,178,管理系统模拟 马维忠,179,管理系统模拟 马维忠,180,定时Petri网（Timed Petri Net）考虑事件发生到结束所需的时间。它将每一时间标在对应的库所旁，这样库所中的令牌要经过一段时间才能参与到Petri网的运行。,管理系统模拟 马维忠,181,也可以将时间标在变迁上，这样授权发生的变迁需要延迟一段时间才能发生； 或者变迁发生后立即丛输入库所移走相应数量的令牌，但要延迟一定的时间才在输出库所产生令牌。,管理系统模拟 马维忠,182,高级Petri网（High-level Nets）给令牌赋予某种属性，以丰富Petri网的模型语义。 典型的高级Petri网有谓词/变迁网（Predicate/Transition Nets），着色Petri网（Colored Petri Nets, CPN）和随机Petri网（Statistic Petri Nets, SPN）。,管理系统模拟 马维忠,183,谓词变迁网为变迁的发生规定了谓词条件； 着色Petri网为网中每一个库所定义了一个令牌色彩集，并且为网中的每一个变迁定义了一个动作色彩集； 随机Petri网则把变迁的发生看作是一个随机过程，其持续时间服从一定的概率分布。,三、物理模型及建模,模型结构 程序设计 实例,管理系统模拟 马维忠,185,前面一讲介绍了离散事件系统模型的建模方法。 为了使模型能在计算机上运行，需要将系统模型转换为仿真模型（也称计算机模型，Computerized Model），这是从模型到计算机仿真的一个必不可少的步骤。,管理系统模拟 马维忠,186,将系统模型转换为一个可以在计算机上运行的仿真模型，一般需要完成三部分工作： 设计仿真策略，具体地说，就是确定仿真模型的控制逻辑和仿真时钟推进机制； 构造仿真模型，即确定模型的具体操作； 仿真程序设计与实现，即采用某种程序设计方法及语言，实现仿真策略和仿真模型。,管理系统模拟 马维忠,187,上述过程称为仿真模型的设计与实现。,管理系统模拟 马维忠,188,3.1 仿真策略,要将系统模型转换为计算机模型，首先要从总体上确定仿真模型的控制逻辑和仿真时钟推进机制，即确定仿真策略。 仿真策略是仿真模型的核心，反映了仿真模型的本质，从根本上决定了仿真模型的结构。,管理系统模拟 马维忠,189,迄今为止，离散事件系统已形成三种基本的仿真策略，分别是 事件调度法（Event Scheduling, ES） 活动扫描法（Activity Scanning, AS） 进程交互法（Process Interaction, PI）。 其它仿真策略均是以这三种仿真策略为基础的。,管理系统模拟 马维忠,190,3.1.1 事件调度法,事件调度法最早于1963年由兰德公司的Markowitz等人提出。 它的基本思想是，将事件例程作为仿真模型的基本模型单元，按照事件发生的先后顺序不断执行相应的事件例程。 每一事先可预知其发生时间的确定事件都带有一个事件例程，用以处理事件发生后对实体状态所产生的影响，并安排后续事件；条件事件不具有事件例程，对它的处理隐含在某一确定事件的例程中。,管理系统模拟 马维忠,191,因此，事件调度法中所说的事件是指确定事件。 对实体流程图法建立的概念模型，一般可采用事件调度法建立其仿真模型。,管理系统模拟 马维忠,192,1初始化 置仿真的开始时间t0和结束时间tf； 置实体的初始状态； 置初始事件及其发生时间ts； 2仿真时钟TIME=ts； 3确定当前时钟TIME下发生的事件类型Ei，i=1,2,n，并按解结规则排序； 4如果TIMEtf，执行 case Ei of E1：执行E1的事件例程，产生后续事件类型及发生时间； En：执行En的事件例程，产生后续事件类型