[管理学]系统建模与仿真第三章课件.ppt

1、系统建模与仿真系统建模与仿真第三章第三章 离散事件系统建模离散事件系统建模管理科学与工程学院管理科学与工程学院付付 赟赟2022-6-23系统建模与仿真23.1 离散事件系统n离散事件系统的性质与连续系统完全不同，这类系统的状态只在离散的时间点上发生变化，而且这些离散的时间点是不确定的。n例1：理发店就是一个典型的离散事件系统的例子。2系统建模与仿真2022-6-232022-6-23系统建模与仿真33.1 离散事件系统n对于离散事件系统来说，系统的内部状态变化是随机的，同一个内部状态可以向多种状态转变，因此很难用函数形式来描述系统内部状态的变化，通常所关心的是系统内部状态变化的统计规律。n系

2、统的内部状态只在离散的随机时间点上发生变化，且状态在一段时间内保持不变。因此在建立离散事件系统模型时，只需考虑系统内部状态发生变化的时间点以及产生这些状态变化的原因，而不用描述系统内部状态发生变化的过程。3系统建模与仿真2022-6-232022-6-23系统建模与仿真41、实体、实体1）定义：）定义： 实体实体(Entity)是指一个系统边界内部的客观对象，离散事件系统是由实体组成的。2）分类：）分类： 临时实体临时实体 先进入系统并经过相应的环节后再离开系统，且在系统中的数量经常变化的实体，又称为主动实体、活动实体。 永久实体永久实体 经常处于系统之内，其数量保持稳定的实体，又称为被动实体

3、。3.1.1 离散事件系统要素4系统建模与仿真2022-6-232022-6-23系统建模与仿真53.1.1 离散事件系统要素n系统的工作过程实质上就是临时实体流动和接受加工、处理的过程。n如：排队的顾客，待加工的工件等n永久实体只要系统处于活动状态，它就一定存在。n如：商店的营业员，加工设备等n临时实体按一定规律不断到达，在永久实体作用下通过系统，最后离开系统。系统状态的变化主要是由实体的状态变化而产生的。5系统建模与仿真2022-6-232022-6-23系统建模与仿真62、事件、事件1）定义）定义 事件事件(Event)是引起系统状态发生变化的行为。 离散事件系统可以看做是由事件驱动事件

4、驱动的，它是在某一时间点的瞬间行为，如：待加工工件、顾客等的“到达”或“离开”等。 事件不仅用来协调两个实体之间的同步活动，还用于各实体之间的信息传递。3.1.1 离散事件系统要素6系统建模与仿真2022-6-232022-6-23系统建模与仿真73.1.1 离散事件系统要素2）分类）分类n时间事件和状态事件时间事件和状态事件n时间事件：时间事件：依照系统的作业规则在预订时间发生的事件。n状态事件状态事件：当系统状态符合某种条件下发生的事件。n基本事件和二次事件基本事件和二次事件n基本事件：基本事件：其发生可以事先加以预测的事件。n二次事件：二次事件：发生与否则取决于其他事件。n如：顾客到达和

5、接受服务7系统建模与仿真2022-6-232022-6-23系统建模与仿真83.1.1 离散事件系统要素3、活动、活动 活动活动(Active)是实体在两个事件之间保持某一状态的持续过程。 如如：顾客接受服务的过程，工件被加工的过程 活动因某一事件的发生而开始，因下一事件的发生而结束，因此它标志着实体状态迁移的一个片段。 如如：在“顾客到达”与“服务开始”两个事件之间存在一个“排队等候”活动；“服务开始”与“服务结束”之间存在“顾客接受服务”活动。 8系统建模与仿真2022-6-232022-6-23系统建模与仿真93.1.1 离散事件系统要素 4、进程、进程 进程进程(Process)是由与

6、某类实体相关的事件和若干活动组成的，它描述了这些事件和活动间的相互逻辑关系和时序关系。 如：“顾客到达系统排队开始接受服务服务结束”的过程就构成了一个进程。 进程是事件与活动的组合，它可以更加完整地描述实体状态的迁移过程。9系统建模与仿真2022-6-233.1.1 离散事件系统要素2022-6-23系统建模与仿真10理发店例子中进程的含义理发店例子中进程的含义10系统建模与仿真2022-6-232022-6-23系统建模与仿真11 3.1.1 离散事件系统要素5、属性、属性 属性属性(Attribute)是实体特征的描述，是实体所拥有的全部特征的一个子集，用特征参数变量表示。 在仿真建模中，

7、只需要使用与研究目的相关的一部分就可以了。11系统建模与仿真2022-6-232022-6-23系统建模与仿真123.1.1 离散事件系统要素6、状态、状态 状态状态(State)是指在某时间点上对系统的所有实体属性和活动的描述。当一个系统的所有实体处于状态协调并定义状态的属性时，则认为系统处于特定状态。 如：在随机服务系统模型中，“顾客”有“等待服务”和“接受服务”等状态，“服务员”有“忙”和“闲”等状态。 活动总是与一个或几个实体的状态相对应，状态可作为动态属性进行描述。12系统建模与仿真2022-6-232022-6-23系统建模与仿真133.1.1 离散事件系统要素13系统建模与仿真2

8、022-6-232022-6-23系统建模与仿真143.1.1 离散事件系统要素7、仿真时钟、仿真时钟 仿真时钟仿真时钟用于表示仿真时间的变化及作为仿真过程的时序控制，它是系统运行时间在仿真过程中的表示。 仿真时钟推进的方式：仿真时钟推进的方式： 固定步长时间推进机制 下次事件时间推进机制 仿真时钟推进的时间间隔称为仿真步长，离散事件系统仿真时钟的推进步长是随机的，取决于系统的当前状态和事件发生的条件。14系统建模与仿真2022-6-232022-6-23系统建模与仿真153.1.1 离散事件系统要素8、系统环境、系统环境 系统环境系统环境(System Environment)是系统周围的对

9、象及过程(实体和活动)。发生于系统内部的活动称为内生活动，发生于系统环境中并对系统产生影响的活动称为外生活动，将活动划分为内生活动和外生活动就确定了系统的边界。15系统建模与仿真2022-6-233.1.1 离散事件系统要素n确定系统的状态变量系统的状态变量是很重要的。n由于进行仿真研究的系统状态变量并不总是固定唯一的，它应当根据系统仿真研究的目的而确定。n描述系统状态变化的流程系统状态变化的流程n到达并进入系统中实体的类型和数目n使系统状态发生变化的事件类型n事件发生时间的分布规律等2022-6-23系统建模与仿真1616系统建模与仿真2022-6-232022-6-23系统建模与仿真173

10、.1.1 离散事件系统要素系统系统实体实体属性属性活动活动系统状态系统状态事件事件工业生产机器、零件生产能力、故障加工要求加工时间、故障时间机器忙、机器闲加工开始、加工结束通信信号、信道信号长度、传输终端传输信道发送忙、信道发送闲信号开始传输、信号传输结束仓储仓库、物品库房容量进货库存水平、欠付需求需求交通道路、交叉口车辆信号机车道数、车型、车速周期运动时间、信号时间系统总车数、红绿灯车辆到达、绿灯开始离散系统实例离散系统实例17系统建模与仿真2022-6-232022-6-23系统建模与仿真183.1.2 离散事件系统建模方法n建模是仿真的前提，是计算机仿真的关键技术内容之一；模型不正确，仿

11、真的结果也失去意义n由于随机事件系统的模型很难用常规的微分方程、差分方程来描述；随着系统科学和管理科学的发展机及其在各领域中应用的不断深入，逐步形成了一些与连续系统不同的建模方法n主流方法：主流方法：流图流图和网络图网络图18系统建模与仿真2022-6-233.1.2 离散事件系统建模方法n1、实体流图法、实体流图法n与计算机程序流程图类似n可以描述实体产生、流动、消亡及其被永久实体加工、处理的过程和逻辑关系n实体流图模型易于转换为面向事件面向事件的仿真模型2022-6-23系统建模与仿真1919系统建模与仿真2022-6-233.1.2 离散事件系统建模方法n2、活动周期图法、活动周期图法n

12、针对实体的行为模式进行建模n可以直观地表示出某类实体生命周期中的活动和状况n具有规范化的特点n对不同实体之间协同关系的描述清晰、明确n易于转换为面向活动面向活动的仿真模型2022-6-23系统建模与仿真2020系统建模与仿真2022-6-233.1.2 离散事件系统建模方法n3、Petri网法网法n适于建立加工系统等多种离散事件系统的模型n对网系统的特性进行较严密的数学分析n处理并发、冲突、死锁等现象2022-6-23系统建模与仿真2121系统建模与仿真2022-6-232022-6-23系统建模与仿真223.2 实体流图法n系统要对临时实体产生作用，就必须有永久实体的活动，也就是必须有永久实

13、体。n临时实体和永久实体协同完成了某项活动，永久实体作为活动的资源而被占用。n理发店的服务员，交通路口的红绿灯等都是永久实体的例子。22系统建模与仿真2022-6-233.2.1 实体流图法概述 实体流图法实体流图法(Entity Flow Chart，EFC)采用与计算机程序流程图相类似的图示符号和原理，建立表示临时实体产生、在系统中流动、接受永久实体“服务”，以及消失等过程的流程图。 借助实体流程图，可以表示事件状态变化及实体间相互作用的逻辑关系。 在离散事件系统中实体流图法应用比较普遍，原因如下：1）计算机程序框图的思想和方法已广为人们所接受；2）实体流图法简单，且对离散事件系统的描述比

14、较全面。23系统建模与仿真2022-6-233.2.2 实体流图法的建模思路n对建模者的两点要求：对建模者的两点要求：n1）对实际系统的工作过程有深刻的理解和认识n2）将事件、状态变化、活动和队列等概念贯穿于建模过程中n常用的图示符号：常用的图示符号：n菱形框（判断）；矩形框（事件、状态、活动）；圆角矩形框（开始和结束）；箭头（逻辑关系）24系统建模与仿真2022-6-233.2.2 实体流图法的建模思路n建模的一般步骤如下：建模的一般步骤如下：n1）明确组成系统的各个实体及其属性n2）分析各种实体的状态和活动，及其相互间的影响。n3）考察那些导致活动的开始或结束的事情，或者是可以作为活动开始

15、或结束的标志的事件，以确定引起实体状态变化的事件，并将条件事件合并。n4）分析各种事件发生时实体状态是如何变化的。n5）在一定的服务流程下，分析与队列实体有关系的特殊操作(如换队等)。25系统建模与仿真2022-6-233.2.2 实体流图法的建模思路n6）根据以上分析，以临时实体的流动为主线，用约定的图示符号画出被仿真系统的实体流图。n7）确定模型参数的取值、参变量的计算方法及属性描述变量的取值方法。属性描述变量(例如顾客到达时间、服务时间等)既可以取一组固定值，也可以由某一公式计算得到，还可以是一个随机变量。如果属性描述变量是随机变量，就应该给出其分布函数。n8）确定队列的排队规则。当有多

16、个队列存在时，还应给出其服务规则，例如队列的优先权、换队规则等。26系统建模与仿真2022-6-233.2.3 实体流图法的实例分析n例例1 ：理发店服务系统：理发店服务系统 单服务台、单队列服务系统单服务台、单队列服务系统n有一个小理发店只有一个理发员，顾客来到理发店后，如果有其他顾客正在理发就坐在一旁等候。理发员按先来先理的原则为每一位顾客服务，而且只要有顾客就不停歇。建模目的是在假定顾客到达时间间隔和理发花费的时间服从一定的概率分布时，考察理发员的忙闲情况。2022-6-23系统建模与仿真2727系统建模与仿真2022-6-233.2.3 实体流图法的实例分析n（1）辨识系统实体）辨识系

17、统实体n三个实体：理发员是永久实体，顾客是临时实体，顾客队列是一类特殊实体n（2）分析实体的状态和活动类实体的组成）分析实体的状态和活动类实体的组成n理发员的活动有“理发理发”和“休息休息”，对应“忙忙”和“闲闲”两种状态n顾客与理发员协同完成理发活动，有“等待服务等待服务”和“接受服务接受服务”两种状态n顾客队列的状态由队列长度队列长度来标识n三类实体的活动及状态之间存在逻辑上的关系2022-6-23系统建模与仿真2828系统建模与仿真2022-6-233.2.3 实体流图法的实例分析n（3）分析实体状态的变化情况）分析实体状态的变化情况n某一顾客到达时，如果理发员处于“忙忙”状态，则该顾客

18、进入“等待服务等待服务”状态；否则进入“接受服务接受服务”状态n理发员完成对某一顾客的服务时，如果队列处于“非零非零”状态，则立即开始服务活动；否则进入“闲闲”状态n处于排队等待中的顾客，如果理发员完成了对前一顾客的服务，则进入“接受服务接受服务”状态；否则保持“等待服等待服务务”状态2022-6-23系统建模与仿真2929系统建模与仿真2022-6-233.2.3 实体流图法的实例分析n（4）分析引起状态变化的事件）分析引起状态变化的事件n“顾客到达顾客到达”或“顾客结束排队顾客结束排队”导致“服务服务”活动的开始；而“顾客理完离去顾客理完离去”导致“服务服务”活动的结束；这三个瞬时行为均可

19、以作为事件看待。n“顾客结束排队顾客结束排队”是以理发员状态是“闲闲”为条件的；而队列状态是“非零非零”时理发员状态为“闲闲”是以事件“顾客理完离去顾客理完离去”为条件的；以上两个条件事件顺序、互为因果。n将“顾客结束排队顾客结束排队”事件并入“顾客理完离去顾客理完离去”事件，不予单独考虑，即合并条件事件。n“顾客到达顾客到达”将使理发员由“闲闲”变为“忙忙”，或使“队列长度队列长度”增加1。n“顾客理完离去顾客理完离去”将使理发员由“忙忙”变为“闲闲”。n“顾客结束排队顾客结束排队”将使“队列长度队列长度”减少1，并使理发员由“闲闲”变为“忙忙”。2022-6-23系统建模与仿真3030系统

20、建模与仿真2022-6-233.2.3 实体流图法的实例分析n（5）分析队列实体的操作）分析队列实体的操作n该问题只有一个队列，而且顾客不会因为排队人数太多而离去，因此队列规则简单，没有换队等特殊的队列操作。n（6）画出系统实体流程图）画出系统实体流程图n基于实体、活动和事件的分析n从实体进入系统开始，按照事件和活动相互交替的原则，按顺序画出实体在系统中的流动过程。n对条件事件，可在事件框前加入条件判断2022-6-23系统建模与仿真3131系统建模与仿真2022-6-233.2.3 实体流图法的实例分析2022-6-23系统建模与仿真32单线框：事件单线框：事件双线框：活动双线框：活动理发员

21、为忙、理发员理发员为忙、理发员为闲：为闲：设置系统标志的特殊设置系统标志的特殊操作，可以不画操作，可以不画32系统建模与仿真2022-6-233.2.3 实体流图法的实例分析n（7）确定模型参变量）确定模型参变量n顾客的到达时间（随机变量）n理发员为一个顾客理发所需的服务时间（随机变量）n（8）给出排队规则）给出排队规则n队列的排队规则是先到先服务（FIFO）n说明：实体流图是为描述实体流动和相互间逻辑关系而绘制的，与计算说明：实体流图是为描述实体流动和相互间逻辑关系而绘制的，与计算机程序框图不同机程序框图不同2022-6-23系统建模与仿真3333系统建模与仿真2022-6-233.2.3

22、实体流图法的实例分析n例例2：售票窗口服务系统：售票窗口服务系统 两类顾客竞争资源两类顾客竞争资源n电影院雇用一名售票员同时负责电影票的销售和对电话问询者的咨询服务。窗口服务比电话服务优先级高。问询者打来的电话由电话系统存储后按先来先服务的规则一一予以答复。建模的目的是研究售票员的忙闲率。2022-6-23系统建模与仿真3434系统建模与仿真2022-6-233.2.3 实体流图法的实例分析n（1）辨识系统实体）辨识系统实体n售票员：永久实体；n购票者和电话问询者：临时实体；n购票队列和问询队列：特殊实体。2022-6-23系统建模与仿真3535系统建模与仿真2022-6-233.2.3 实体

23、流图法的实例分析n（2）分析实体状态和活动类实体组成）分析实体状态和活动类实体组成n售票员有“空闲空闲”、“售票售票”和“接电话接电话”3个活动，对应的是“闲闲”和“忙忙”两种状态n购票者有“排队排队”和“购票购票”2个活动，对应的是“等待等待”和“购票购票”两种状态n问询者有“排队排队”和“问询问询”2个活动，对应的是“等待等待”和“问询问询”两种状态n顾客队列的状态以队列长度队列长度标识n4类实体的活动及状态存在逻辑上的联系36系统建模与仿真2022-6-233.2.3 实体流图法的实例分析n（3）分析实体状态变化的情况）分析实体状态变化的情况n购票者或者问询者到达时，如果售票员处于“忙忙

24、”状态，则该顾客进入“等待等待”状态；否则，进入“购票购票”或“问询问询”状态n处于排队等待中的顾客，如果售票员完成了对前一顾客的服务，则进入“购票购票”或“问询问询”状态；否则，继续保持“等待等待”状态37系统建模与仿真2022-6-233.2.3 实体流图法的实例分析n（4）分析引起状态变化的事件）分析引起状态变化的事件n“购票者到达购票者到达”、“问询者到达问询者到达”、“购票者结购票者结束排队束排队”或者“问询者结束排队问询者结束排队”导致售票员“服务服务”活动的开始n“购票者买票后离去购票者买票后离去”或“问询者咨询后离去问询者咨询后离去”导致售票员“服务服务”活动结束38系统建模与

25、仿真2022-6-233.2.3 实体流图法的实例分析n（5）分析队列实体的操作）分析队列实体的操作n该问题有两个队列，但两个队列中的顾客不会互换队列n（6）画出系统实体流程图）画出系统实体流程图n以临时实体为主线，画出实体流程39系统建模与仿真2022-6-233.2.3 实体流图法的实例分析40系统建模与仿真2022-6-233.2.3 实体流图法的实例分析n（7）确定模型参变量）确定模型参变量n购票者到达时间n电话问询者到达时间n售票服务时间n电话服务时间n（8）给出排队规则）给出排队规则n排队规则：FIFOn服务规则：购票者和问询者分别排队，优先进行购票活动41系统建模与仿真2022-

26、6-233.2.3 实体流图法的实例分析n两个与服务规则有关的判断和特殊操作两个与服务规则有关的判断和特殊操作n当“电话问询者电话问询者”和“窗口购票者窗口购票者”同时到达，且售票员处于“闲闲”的状态，后者接受服务，前者加入电话队列n当服务完毕，且购票队列和电话队列均不为空时，先进行购票服务n由于本例中有两类临时实体同时流动由于本例中有两类临时实体同时流动,因此可能出现资源冲突因此可能出现资源冲突,对此类问对此类问题的描述题的描述,活动周期图有其独到之处活动周期图有其独到之处.42系统建模与仿真2022-6-233.2.4 模型的人工运行n建立实体流程图模型后，选取有代表性的例子将流程图全部走

27、一遍，即所谓人工运行。n人工运行模型要求遍历流程图的各个分支和实体的各种可能状态，在时间逐步变化的动态条件下，分析事件的发生及状态的变化过程，以检查模型的组成和逻辑关系是否正确。2022-6-23系统建模与仿真433.2.4 模型的人工运行n例例1中，假定：中，假定：n（1）系统的初始状态）系统的初始状态n包括永久实体“理发员理发员”的状态及特殊实体“队列队列”的状态n初始时刻是仿真开始的时刻，理发员为“闲闲”，队列长度为0n（2）模型参数及变量的取值）模型参数及变量的取值n第i个顾客与第i-1个顾客到达的时间间隔Ain理发员为第i个顾客的理发时间Sin两个都是随机变量，可根据其分布函数来产生

28、2022-6-2344系统建模与仿真3.2.4 模型的人工运行n模型需按照一定的规则运行，本模型的人工模型需按照一定的规则运行，本模型的人工运行规则如下：运行规则如下：n规则规则1确定当前时间确定当前时间n模型人工运行开始时，取当前时间TIME=t0（初始仿真时刻）n人工运行开始后，当前时间逐步向前推移，且递取下一最早发生事件的发生时刻n如果当前时间有顾客到达事件发生 ，转规则2n若有顾客离去事件发生，则转规则32022-6-2345系统建模与仿真3.2.4 模型的人工运行n规则规则2顾客到达事件处理顾客到达事件处理n假定在时刻TIME有顾客i到达，如果理发员“忙忙”，则入队列等待，队列长度加

29、1n否则，置理发员为“忙忙”状态，顾客开始理发，且在di=TIME+Si时刻理毕离去n规则规则3顾客离去事件处理顾客离去事件处理n假定在时刻TIME有顾客i离去，如果此时队列长度为0，置理发员为“闲闲”状态n否则，队列中排在队首的一名顾客开始理发，队列长度减1，顾客在di=TIME+Si时刻理毕离去2022-6-2346系统建模与仿真3.2.4 模型的人工运行n令A1=15，A2=32，A3=24，A4=40，n令S1=43，S2=36，S3=34，S4=28，n（1）在）在TIME=t0时刻，无任何事件发生时刻，无任何事件发生n下一最早发生的事件为“顾客顾客1到达到达”，发生时刻为a1=TI

30、ME+A1=15n（2）在）在TIME=15时刻，顾客时刻，顾客1到达到达n按规则2，理发员开始为顾客1理发，状态由“闲闲”变“忙忙”n顾客1离去时刻d1=TIME+S1=15+43=58n下一最早发生的事件为“顾客顾客2到达到达”，顾客2到达的时刻为a2=a1+A2=15+32=47582022-6-2347系统建模与仿真3.2.4 模型的人工运行n（3）在）在TIME=47时刻，顾客时刻，顾客2到达到达n因理发员“忙忙”，顾客2排队等待，队列长度变成1n下一最早发生的事件为“顾客顾客1离去离去”，离去时刻 d1=580）n（2）小货车）小货车n与大货车类似2022-6-23系统建模与仿真6

31、7leaveemptyunloadoutsidewaitarrivequeuemove大货车大货车exitfullloadelsewheredockedcomeparkenter小货车小货车2022-6-2368系统建模与仿真2022-6-23系统建模与仿真693.3.2 活动周期图法建模举例n（3）装、卸仓位）装、卸仓位n（4）装、卸工人）装、卸工人n（5）进、出通道）进、出通道unloadunbay卸货仓位卸货仓位loadbay装货仓位装货仓位unloadloadlabour装卸工装卸工leaveroadoutmoveexit出口通道leaveroadinmoveenter进口通道2022

32、-6-2370系统建模与仿真unloadunbayloadbayunloadloadlabourleaveemptyunloadoutsidewaitarrivequeuemoveleaveroadoutmoveexitexitfullloadelewheredockedcomeparkenterleaveroadinmoveenter2022-6-2371系统建模与仿真2022-6-23系统建模与仿真723.3.2 活动周期图法建模举例n模型参数模型参数：装卸工人的数量，装卸仓位的数量n参变量：参变量：当前卸货仓位的数量UNBAY，装货仓位的数量BAY，工人的可用数量LABOUR，进、出通道

33、数ROADIN和ROADOUTn属性变量属性变量：各个活动的忙期，随机变量n排队规则排队规则：FIFOn服务规则服务规则：大小货车各排一队，装卸工、进出通道优先为大货车服务，优先安排货车离开货场2022-6-23系统建模与仿真733.3.3 模型的人工运行n首先确定系统的初始状态n按下列原则运行模型：n规则规则1活动的发生与执行活动的发生与执行n（1）活动的所有前置状态中均有实体停留，且各类永久实体的数量超过或等于相应资源占用量；n（2）活动发生的约束条件已经满足。n依次检查每一活动，以判断此活动是否可以开始，即此活动所要求的足够的实体集合是否已经存在于所有有关的前置队列中。如果含有，则将这个

34、实体集合的标志移入此活动的矩形内，且计算出此活动的终止时间，并将此时间写在该活动的矩形内。当所有活动都检查完后，转向规则2。2022-6-23系统建模与仿真743.3.3 模型的人工运行n规则规则2确定当前时间确定当前时间n检查所有活动的终止时间，选其最小值，并设置时钟值为此选择值，然后转向规则3。n规则规则3活动的完成活动的完成n从所有已发生的活动中，检出终止时间等于当前时间的临时实体，删掉为其标注的终止时间；然后将相应临时实体的标记移至其相关的后续状态中。n参与活动的各永久实体的资源量相应增加，将参与活动的永久实体的后续状态作标记，转规则12022-6-23系统建模与仿真753.4 实体流

35、图和活动周期图的比较n第一：第一：nEFC以临时实体在系统中的流动过程为主线，永久实体浓缩于表示状态和事件的图示符合中，队列作为一种特殊实体。nACD基于各类临时和永久实体的行为模式，有独特的图示标识，队列成为实体生命周期的一种状态。n第二：第二：nEFC是带有小循环的树形流程图nACD中，各类实体是环形的循环图，整个系统由多个环套在一起2022-6-23系统建模与仿真763.4 实体流图和活动周期图的比较n第三：第三：nEFC中，事件有显式的表达nACD中，事件蕴含在活动中，没有显式表达n第四：第四：nEFC中，状态判断框的作用非常重要nACD中，将需作判断的状态用“空闲”、“等待”等静寂状

36、态表示，对实体是否处于该状态的判断也无需标注在图中，而是作为模型运行时的一般规则3.5 Petri网建模方法n改变活动周期图建模方法：改变活动周期图建模方法：1.取消临时实体ACD中的“源”状态，即不再考虑临时实体的生命周期循环2.将活动看作是“开始事件+状态+结束事件”，则，建模元素就变成“事件”和“状态”，后者包括ACD中的激活状态和静寂状态3.不强调实体模型之间的独立性n用集合论的语言描述后，可以建立规范的Petri网方法2022-6-23系统建模与仿真773.5.1 Petri网的基本概念n Petri网是由节点节点和有向弧有向弧组成的一种有向图有向图n它有两类节点：n库所库所，即状态

37、元素，它表示一个场所，而且在该场所存放了一定的资源，用 “”表示；n变迁变迁，它指资源的消耗、使用以及对应状态元素的变化，用 “ ”表示。另外，资源指的是与系统状态发生变化有关的因素。2022-6-23系统建模与仿真783.5.1 Petri网的基本概念2022-6-23系统建模与仿真79nPetri网定义：网定义：n三元组N=(S,T;F)称为Petri网的充要条件是：(1)(2)(3)(4)( )( )STSTFSTTSdom Fcod FST 3.5.1 Petri网的基本概念nS：库所集；T：变迁集nF：由一个S元素和一个T元素组成的有序偶的集合，称为N的流关系ndom（F）：F所含序

38、偶的第一个元素的集合ncod（F）：第二个元素的集合nN不能有孤立元素，即S,T,F均不能为空集( ) |:( , )( ) |:( , )dom Fxyx yFcod Fyxx yF3.5.2 网系统n网是系统静态结构的基本描述网是系统静态结构的基本描述n容量、标识容量、标识和权重权重3.5.2 网系统n例例5：有一条工业生产线，它要完成两项工业操作，这两项操作用t1和t2表示。第一个变迁t1将传入生产线的半成品s1和部件s2用两个螺丝钉s3固定在一起，变成半成品s4。第二个变迁t2再将s4和部件s5用3个螺丝钉s3固定在一起，得到新的半成品s6。完成操作t1和t2时都要用到工具s7。假定由

39、于存放空间的限制，部件s2和部件s5最多不能超过100件，停放在生产线上的半成品s4最多不能超过5件，螺丝钉s3存放最多不能超过1000件。3.5.2 网系统S1S2S3 K=1000K=5 S4S7S5S6K=100K=100t2t13.5.2 网系统n（1）容量K(s)标识库所s中允许存放令牌的最大数量，其值标在表示库所的圆圈旁，不标明时容量为n（2）权W(x,y)表示变迁发生时消耗和产出的令牌数量，其值标在弧（x，y）上；不标明时表示权为1n（3）令牌表示原料、部件、产品、人员、工具、设备、数据和信息等组成系统的“资源”，标识M(s)的值用令牌数表示3.5.2 网系统2022-6-23系

40、统建模与仿真850012, ;,;(1), ;Petri(2),.,( ),niiS T F K W MNS T FK W MNMMm mmnSmM siS 六元组称为一个网系统当且仅当是网，成为 基网分别是 上的容量函数，权函数和标识。 是 的初始标识。网系统的状态用令牌在库所中的分布来表示，系统状态变量其中，3.5.3 Petri网的变迁原则n当变迁不断发生时，网系统的状态也不断发生变化，这一过程称网系统的执行。2022-6-23系统建模与仿真86 0*, ;,;(1),(2),( ),( ),(3),.( )( , );( )S T F K W MMtTttttMsS stM sW t

41、sstM sW t sK sMtM ttMtMMM tMsSM sW s tsttMM s 设为网系统，为其基网上的一个标识若称为 的外延在有发生权的条件是：对所有这时说授权 发生，记作若 在有发生权，那么 就可以发生发生的结果是把变成后继标识记作对所有的，有*( )( , );( )( , )( , );( );sW s tsttM sW s tW s tsttM s stt3.5.3 Petri网的变迁原则n1）一个变迁被授权发生，当且仅当该变迁的每一个输入库所中的令牌数大于或等于输入弧的权值，并且该变迁的输出库所中已有的令牌数与输出孤权值之和小于输出库所的容量；简单地说就是“前面够用，后

42、面够放”。n2）变迁发生(点火)的充要条件是该变迁是授权的。n3）变迁发生时，从该变迁的输入库所中移出与输入弧权值相等的令牌数，输出库所中产生与输出弧权值相等的令牌数。2022-6-23系统建模与仿真87 p1 p2 t1 t2 p4 p5 p3 t3 t4 p6 p7 t6 t5 （a）初始初始 p2 p1 t1 t2 p4 p5 p3 t3 t4 t5 t6 （b）引发）引发t1 p6 p7 3.5.3 Petri网的变迁原则 p1 p2 t1 t2 p4 p5 p3 t5 t6 p6 p7 (c) 引发引发t2 t3 t4 p2 p1 t1 t2 p4 p5 p3 t5 t6 p6 p7

43、 （d ）引发）引发t1和和t2 t3 t4 3.5.3 Petri网的变迁原则3.5.4 Petri网的行为性质Petri网的模型只给出系统的静态结构及特征， 系统的动态行为是在Petri网的运行过程中体现出来的，主要由它的一些性质来描述。状态标识为一个向量，代表网中相应序号库所中所含令牌的数量，它反映了令牌在网中的分布情况。定义定义 (可达性可达性)对于对于Petri网网N , 若存在若存在tT 使得使得MtM，则称，则称M是从是从M 直接可达的。若存在变迁序直接可达的。若存在变迁序列列=t1，t2，tk和标识序列和标识序列=M1，M2，Mk 使使得得Mt1 M1 t2 M2Mk- 1tk

44、Mk , 则称则称Mk是从是从M 可可达的，记作达的，记作MoM 。所有由。所有由M 可达的标识集合记为可达的标识集合记为R (N ,M )。 可达性用于验证系统能否达到某种状态。可达性用于验证系统能否达到某种状态。 3.5.4 Petri网的行为性质 给定一个给定一个Petri网网(N，M0)，一定可以建立起表达，一定可以建立起表达其可达集其可达集R(N，M0)的一个树状结构的图形，称之为的一个树状结构的图形，称之为Petri网网(N，M0)，的可达树。可达树具有如下一些属，的可达树。可达树具有如下一些属性：性： （1）可达树在图形结构上呈倒立状树形； （2）从树根出发，按照由树根节点激发出

45、的“使能变迁节点”个数来生长出相同个数的支线，并将使能变迁标注在对应的支线旁，各个支线末端为相应使能变迁发生后达到的新状态标识即新令牌分布，由此形成一批新的分支点，以这些分支点为起点，按相同原则，依次伸展；3.5.4 Petri网的行为性质（3）有限可达集对应于有限可达树，而无限可达集用）有限可达集对应于有限可达树，而无限可达集用有限可达树来表示。具体引入以下附加规定：有限可达树来表示。具体引入以下附加规定： a、分支的终止支点。、分支的终止支点。伸展出的一个新节点在先前的支点或其它分支点出现过，该分支点终止延伸； b、引入无限参量、引入无限参量。可达树构造过程中，如果某个支点M比由树根M0到

46、M的一条分支上的一个“中途”支点M*要大，即支点M和M*的每个位置节点的令牌数均有M(pj)M*(pj),则对支点M中满足“”关系的位置节点采用无限参量来替代令牌数。3.5.4 Petri网的行为性质 s3s1s2t3t2t1(1,0,0)(0,0,1)(0,1,1)(1,0)(1, ,0)(0, ,1)(0, ,1)t1t1t2t2t3t33.5.4 Petri网的行为性质定义定义 (有界性有界性)如果对于如果对于sS 及任意及任意M R (N，M0) , 都有都有M (S )K , 则称网是则称网是K有界的有界的, 特别地，当特别地，当K = 1 时称此网是时称此网是安全安全的。的。 有界

47、性保证了系统的缓冲区不会溢出, 工件在某个操作阶段不会堆积。有界性判别有界性判别：一个一个Petri网网(N，M0)为有界的为有界的,即其可达即其可达集集R (N ，M0) 为有限，当且仅当为有限，当且仅当Petri网的可达树中不网的可达树中不出现无限参量出现无限参量。安全性判别安全性判别：一个一个Petri网网(N，M0)是安全的是安全的,当且仅当当且仅当Petri网的可达树的所有支点的位置标识中，只包含网的可达树的所有支点的位置标识中，只包含0和和1两类元。两类元。3.5.4 Petri网的行为性质3.5.4 Petri网的行为性质n定义定义 (死锁死锁)对给定初始标识即初始令牌分布M0的

48、一个Petri网R(N，M0) ，称其一个变迁节点t为死锁，如果对由初始令牌分布M0可达的任一令牌分布MR(N，M0)下，此节点变迁t都是不使能即不具发射权的。n在工程系统如柔性生产系统等的设计中，务必要从结构上尽可能避免死锁的存在，以保证系统的信息和物料的运行过程不致瘫痪。s4s3s1s2t3t2t1t43.5.4 Petri网的行为性质定义定义(活性活性)对对tT 和和M R (N，M 0)，如果存在，如果存在MR (N ,M ) , 使得使得M t , 则称则称 t 是活的是活的。所有的所有的 tT 都是活的都是活的, 则称则称网网N 是活的是活的。 活性保证了系统不会出现死锁, 生产可

49、以正常连续进行。 在活性 Petri 网中, 无论怎样选取点火序列, 都保证不会出现死锁。死锁的判别死锁的判别：一个一个Petri网网(N，M0)的一个变迁的一个变迁t是死锁是死锁的，当且仅当此变迁节点的，当且仅当此变迁节点t不出现在不出现在Petri网的可达树的网的可达树的任一分支上。任一分支上。3.5.4 Petri网的行为性质 s8s9s7s6s5s10s4s3s1s2t8t4t3t7t6t2t1t5M0=(1,1,1,0,0,0,0,0,0,0)t1 、t2 冲突，让t1发生发生 s8s9s7s6s5s10s4s3s1s2t8t4t3t7t6t2t1t5M0=(1,0,0,1,0,0,

50、0,0,0,0)t3发生发生 s8s9s7s6s5s10s4s3s1s2t8t4t3t7t6t2t1t5M0=(1,0,0,0,0,1,0,0,0,1)t6发生发生 s8s9s7s6s5s10s4s3s1s2t8t4t3t7t6t2t1t5M0=(1,1,1,0,0,0,0,0,0,0)t2发生发生 s8s9s7s6s5s10s4s3s1s2t8t4t3t7t6t2t1t5M0=(0,0,0,0,1,1,0,0,0,0)t4发生发生M0=(0,0,0,0,0,1,1,0,0,1)t5 、t6并发并发 s8s9s7s6s5s10s4s3s1s2t8t4t3t7t6t2t1t5M0=(0,1,0,