理论模型建模方法

第三章理论模型建模方法本章内容要求：1、掌握实体流图法、活动周期法、Petri网法、Euler网法建模的基本原理。2、能够应用所学建模方法建立并分析实际系统模型重点：实体流图法、Petri网法本章介绍几种典型的离散事件建模方法。实体流图法与计算机程序流程图的方法类似，可以描述临时实体产生、流动、消亡及其被永久实体加工、处理的过程和逻辑关系。活动周期图法针对实体的行为模式进行建模，可以直观地表示出某类实体生命周期中的活动和状况、具有规范化的特点。Petri网方法适于建立加工系统等多种离散事件系统的模型，并可对网系统的特性进行比较严密的数学分析，得到对并发、冲突、死锁等现象的深刻认识，应用也比较广泛。Euler网方法以图论和网论为数学描述语言,贯穿了面向对象的建模思想，描述方法比较规范，可以建立连续—离散事件混合系统模型，方法的通用性较强。3.1基本概念和术语(1)实体(Entity)实体是构成系统的可单独辨识和描述的功能单元。例如．工厂中的机器，商店中的服务员，生产线上的工件，交通道路上的车辆等。属性和行为相同或相近的实体可以用一类来描述，这样做可以简化系统的组成和关系。例如，理发店服务系统可以看成是由“服务员”和“顾客”两类实体组成的.而两类实体之间存在服务与被服务的关系。(2)属性(Attribute)属性是实体特征的描述．一般是实体所拥有的全部特征的一个子集，用特征参数或变量表示。选用哪些特征参数作为实体的属性与建模目的有关,可参照下述原则选取：①便于实体的分类：例如将理发店顾客的性别(“男”或“女”）作为属性考虑，可将“顾客”实体分为二类．每类顾客占用不同的服务台。②便于实体行为的描述例如将飞机的飞行速度作为届性考虑．便于对“飞机”实体的行为(如两地间的飞行时间)进行描述。③便于排队规则的确定例如生产线上待处理工件的优先级水平有时需考虑为便于“按优先级排队”规则的建立和实现。(3)活动(Activity)实体在一段时间内持续进行的操作或过程。活动所占用的时间区段称为忙期(duration)，忙期可以是定时的或随机的。(4)状态(State)对实体活动的特征状况或性态的划分，其表征量称为状态变量。在理发店服务系统模型中，“顾客”有“等待服务”、“接受服务”等状态，“服务员”有“忙”和“闲’’等状态。活动总是与一个或几个实体的状态相对应。状态可作为动态属性进行描述。(5)事件(Event)导致系统状态产生变化的瞬间操作或行为。事件发生的时刻称为事件点。不关心事件所代表的操作和行为意义时，事件与事件点是同义语。若事件的发生是有前提的．则称为条件事件。活动、状态和事件三者间的联系:由子事件的发生会导致状态的变化，而实体的活动可以与一定的状态相对应，因此可以用事件来标识活动的开始和结束。其间的关系如图3.1所示，图中S表示状态，A表示活动，E表示事件，P表示进程。(6)进程(Process)一组按发生时间排列的事件／活动序列称为一个进程。(7)队列(Queue)处于等待状态的实体序列。一般按新到的实体排在队后的次序组成队列。离散事件建模中，队列可作为一种状态或特殊实体对待。图3.1活动、状态、事件及进程3．2实体流图法3．2．1实体流图在离散事件系统中，实体可以分为两大类：临时实体和永久实体。临时实体按一定规律由系统外部到达系统，在系统中接受永久实体的作用，按照一定的流程通过系统，最后离开系统。例如进入商店购物的顾客、交通路口的车辆、生产线上的电视机、进人防空火力网的战斗机，驶入地下停车场的汽车等。与临时实体相反、那些永久驻留在系统中的实体称为永久实体。系统要对临时实体产生作用，就必须有永久实体的活动，临时实体和永久实体协同完成某项活动．如理发店的理发员，生产线上的加工、装配机械，交通路口的红绿灯等，都是永久实体的例子。实体流图法（entityflowchart,EFC)采用与计算机程序流程图相类似的图示符号和原理，建立表示临时实体产生、在系统中流动、接受永久实体“服务”以及消失等过程的流程图。借助实体流程图、可以表示事件、状态变化及实体间相互作用的逻辑关系。建立实际系统的实体流图模型一是要对实际系统的工作过程有深刻的理解和认识，二是要将事件、状态变化、活动和队列等概念贯穿于建模过程中。常用的图示符号只有菱形框(表示判断)、矩形框(表示事件、状态、活动等中间过程)、圆端矩形框(表示开始和结束)及箭头线(表示逻辑关系)等。建模时可按照以下思路进行：(1)辨识组成系统的实体及属性。将队列作为一种特殊的实体来考虑。(2)分析各种实体的状态和活动，及其相互间影响，队列实体的状态是队列的长度。(3)考察有哪些事件导致了活动的开始或结束，或者可以作为活动开始或结束的标志，以确定引起实体状态变化的事件，并合并条件事件。(4)分析各种事件发生时，实体状态的变化规律。(5)在一定的服务流程下，分析与队列实体有关的特殊操作(如换队等)。(6)通过以上分析，以临时实体的流动为主线，用约定的图示符号画出镇仿真系统的实体流程图。(7)给出模型参数的取值、参变量的计算方法及属性描述变量的取值方法。属性描述变量，例如顾客到达时间、服务时间等，可以取一组固定值，可以由某一计算公式取值．还可以是一个随机变量。属性描述变量是随机变量时，应给出其分布函数。(8)给出队列的排队规则。有多个队列存在时，还应给出其服务规则．包括队列的优先序、换队规则等。(1)辨识系统实体（2）分析实体状态变化情况（3）分析引起状态变化的事件(4)分析队列实体的操作“顾客到达”或“顾客结束排队”可以导致“服务”活动的开始，面“顾客理完离去”可以导致“服务”活动的结束，因此这三件事情均可作为事件看待。但是,由于”顾客结束排队”是以理发员状态是“闲”为条件的，因此是条件事件；而队列状态为“非零”时理发员状态为“闲”是由事件“顾客理完离去”导致的,因此将“顾客结束排队”事件并入“顾客理完离去”事件，不予单独考虑。这是实体流图法建模的一般原则。“顾客到达”将使理发员由“闲”变为“忙”，或使“队列长度”加1。“顾客理完离去”将使理发员由“忙”变为“闲”。“顾客结束排队”将使“队列长度”减1，并使理发员由“闲”变为“忙”。由于本问题中只有一个队列，面且顾客不会因排队人数太多而离去、因此队列规则很简单，没有特殊的队列操作。（5）画出系统实体流程图通过以上分析，以顾客活动为主线画出理发店服务系统的实体流图。NoYES顾客排队等待顾客进入队列有其他顾客离开顾客排在队首No顾客到达进入理发店理发员闲置理发员为忙顾客开始理发接受理发服务顾客理完离去置理发员为闲YES(6)确定模型参变量需给出的模型属性变量有：顾客的到达时间（随机变量）、理发员为一个顾客理发所需的服务时间（随机变量）等，它们的值可分别从不同的分布函数中抽取。（7）给出排队规则队列的排队规则是先到先服务（FIFO），即每到一名顾客就排在队尾，服务员先为排在队首的顾客服务.例3.2分时计算机系统分时计算机系统由一个CPU和多台计算机输入终端组成(图3.3）。用户从终端输入作业，请求CPU为其服务。所有终端输入的作业由一个CPU执行，因而形成单一队列。CPU按FIFO(先进先出)的服务规则分时轮流为各终端的作业服务。如果一个作业的CPU执行时间大于一个时间片te，则该任务执行一段时间te后退出CPU，并重新参加排队。只有当某一终端发出的服务请求执行完毕退出CPU后，才允许该终端重新输入一个新的作业，建模的目的是研究用户的等待时间。实体活动状态用户输入作业等待输入输入等候CPU执行作业等待作业忙闲作业输入作业进入队列执行作业接受输入等待执行接受处理队列队列长度分时计算机系统实体列表本系统的实体为计算机用户、计算机的CPU及用户请求执行的作业，其中前二类实体是水久实体。作业是临时实体。实体状态变化对应的活动活动开始事件活动结束事件变化前变化后用户输入等候等待输入输入完毕作业执行完毕等候输入输入作业前一作业执行完毕输入完毕CPU闲忙执行作业接到作业请求执行完毕或执行了一个时间片忙闲等待作业执行完毕或执行了一个时间片接到作业请求作业接受输入等待执行进入队列输入完毕前一作业执行完毕等待执行接受处理执行作业前一作业执行完毕作业执行完毕接受处理接受输入输入作业作业执行完毕输入完毕长度1+1作业进入队列长度-1队首作业开始执行分时计算机系统活动与事件关系假定作业“输入完毕”到CPU“接到执行请求”之间无时间延迟。则可将二者看成同一事件。根据与例3．1同样的理由，“开始输入”和“作业结柬排队”均为条件事件，且均可并入“执行完毕”事件处理。另外，“作业执行了一个时间片”与“执行完毕”标志着同样的事件处理—只是前者发生时需将作业送去重新排队，因此可看作同一类事件。这样模型中只需考虑“输入完毕”和“执行完毕或执行了一个时间片”两种类型的事件即可。要注意作业的输入(到达)是有条件的且需耗费一定的时间；而且，执行作业的结束(离去)可能是暂时的，也可能是永久的，需要加以判断。模型参数包括：终端数量，时间片长度、辅助操作时间(若一个作业在一个时间片内执行不完，CPU为完成该作业重新入队并从队列中取出下一作业所需要的时间)。模型属性变量有：作业输入时间(随机变量)、作业所需执行的时间(随机变量）等排队规则同例3．1。开始前一作业执行完毕开始输入输入完毕CPU闲置CPU为忙开始执行作业作业执行完置CPU为闲用户等待作业等待NOYESNONOYESYES执行完一个时间片其他作业执行完一个时间片作业排在队首例3.3剧院雇佣一名售票员同时负责剧票的窗口销售和对电话问讯者的咨询服务。购票者按先到先服务的原则在窗口排队买票，问讯者打来的电话由电话系统存储后按先来先服务的原则一一予以答复，电话服务比窗口服务有更高的优先级。售票员正在售票时若有电话打入，则售票员必须完成本次售票活动后再接听电话。系统建模的目的是研究售票员的忙闲率。本系统有—个永久实体，即售票员、售祟员有“窗口售票”和“电话服务”两种活动，状态包括‘空闲”、“回电话”和“售票”。电话问讯者和购票者为两类临时实体，其行为模式均与例3．1中的顾客实体类似。本例与前二个例子的主要区别是有两条服务途径，因此可同时存在二个队列，但顾客不可能换队。实体流图模型如图3.5所示。电话拨入购票者到达售票员闲售票员闲有电话同时接入购票者进入队列售票员完成一个服务置售票员为忙电话拨入排在队首售票员完成一个服务电话进入队列电话队列为空排在队首开始电话服务开始售票服务电话服务完毕售票服务完毕置售票员为闲YESNoYESYESYESYESYESYESNoNoNoNoNoNo图3.5售票窗口服务系统实体流图模型属性变量有“购票者到达时间”、“电话问讯者到达时间”、“售票服务时间”和“电话服务时间”，均为随机变量。排队规则为FIFO，服务规则是“窗口购票者和电话问讯者分别排队，优先进行电话服务”。注意，图3.5中有二处是与服务规则有关的判断相特殊操作。当“电话问讯者”和“窗口购票音”同时到达而售票员处于“闲”状态时，前者接受服务，后者加入购票者队列；当服务完毕而购票队列和电话队列均不为空时，先进行电话服务。3.2.2模型的人工运行建立实体流图模型后，选取有代表性的例子将流图全部走一遍，即所谓人工运行。人工运行模型要求遍历流图的各个分支和实体的各种可能状态，在时间逐步变化的动态条件下，分析事件的发生及状态的变化过程、以检查模型酌组成和逻辑关系是否正确。例3.1中假定：(1)系统的初始状态永久实体“理发员”的状态及特殊实体“队列”的状态。所谓初始时刻是指仿真开始的时刻，可以对应为实际系统(理发店)开门营业的时间。此时，理发员为“闲”，队列长度是o。(2)模型参数及变量的取值本模型的变量包括第i个顾客与第i-1个顾客到达的时间间隔Ai．以及理发员为第i个顾客的理发时间Si。一般说来，Ai,Si均为随机变量，应根据其分布函数来产生。这里，为了便于解释．取其样本值为A1=15A2=32A3=24A4=40A5=22,…模型需按一定的规则运行。本模型的人