建模与仿真(petri网部分)

建模与仿真主讲人：许良Petri网经济管理学院工业工程系一、Petri网起源1962年联邦德国的卡尔·A·佩特里在他的博士论文《用自动机通信》中首次使用网状结构模拟通信系统。这种系统模型后来以Petri网为名流传。现在Petri网一词既指这种模型，又指以这种模型为基础发展起来的理论。有时又把Petri网称为网论(nettheory)。Petri网的发展五十多年来Petri网的理论和应用都有了长足的进步。其发展过程大体可分为三个阶段。60年代，Petri网的研究以孤立的网系统为对象，以寻求分析技术和应用方法为目标。这些内容统称为特殊网论(specialnettheory)。此处“特殊”是与“一般”或“通用”比较而言，指的就是孤立的网系统个体。通用网论的(generalnettheory)研究始于70年代初。以C．A．Petri为核心的一批科学家以网系统的全体作为对象，研究其分类及各类网之间的关系，发展了以并发论，同步论，网逻辑和网拓为主要内容的理论体系。80年代开始为Petri网综合发展阶段，以理论与应用的结合及计算机辅助工具的开发为主要内容。发展到现在Petri网已经广泛应用于自动化、机械制造、军事指挥等学科领域。用简单图形较好的表示并发、同步、因果等关系。以网图的方式简洁、直观的模拟离散事件系统目前已得到广泛应用,有限状态机、通信协议、同步控制、生产系统、形式语言、多处理器系统等建模中二、Petri网基本概念Petri网是一种网状信息流模型，包括条件和事件两类节点，在条件和事件为节点的有向二分图基础上添加表示状态信息的托肯（token）分布，并按引发规则使得事件驱动状态演变，从而反映系统动态运行过程。通常情况下，用小矩形表示事件（称作变迁）结点，用小圆形表示条件（称作位置）结点，变迁结点之间、位置结点之间不能有有向弧，变迁结点与位置节点之间连接有向弧，由此构成的有向二分图称作网。网的某些位置结点中标上若干黑点（token），从而构成Petri网。P1P2P3P10P4P5P8P6P7P9t5t1t2t4t8t3t7t6•资源：与系统状态变化有关的因素，如原料、产品、工具、设备等•状态元素：资源归类后的抽象•库所：一个场所，存放状态元素•变迁：资源状态变化•事件：引起条件的变迁称为事件•容量：库所的最大资源数量resourcestateplace,“S”transitioneventCapability，“K”•一个Petri网是一个三元组•P={p1，p2，…，pm}为库所（place）的集合；•T={t1，t2，…，tn}为变迁（transition）的集合；•F=（P×T）∪（T×P）为输入函数和输出函数集，称为流关系。(,,)NPTFPetri网数学定义P1P4P5P3P2t1t3t2一个简单的Petri网Petri网数学定义三元组N=（P，T；F）构成网（net）的充分必要条件：①P∩T=ф，规定了库所和变迁是两类不同的元素；②P∪T≠ф，表示网中至少有一个元素；③F=（P×T）∪(T×P)，建立了从库所到变迁、从变迁到库所的单方向联系，并且规定同类元素之间不能直接联系；容量和权函数定义•设N=（P，T，F）为有向图•K为N上P的容量•K:P{1,2,3,,,,}•在网图中用库所中的黑点表示，无黑点的表示无穷大•W为N上F的权重•W：F{1,2,3,,,,}•在网图中用有向弧上的数字表示，无数字的表示权重为1。带权重和库所容量的Petri网P1P4P5P3P2t1t3t242Petri网描述系统的最基本概念是库所和变迁库所表示系统的状态。变迁表示资源的消耗、使用及使系统状态产生的变化。•变迁的发生受到系统状态的控制，即变迁发生的前置条件必须满足；•变迁发生后，某些前置条件不再满足，而某些后置条件则得到满足。图形化表示：以圆圈表示为库所以粗实线表示变迁以联结库所与变迁之间的有向弧表示输入输出函数用令牌（token）表示库所中拥有的资源数量。——黑点或数字表示P1P4P5P3P2t1t3t242库所变迁库所中令牌分布决定变迁的使能（enabled）和激发（fire），变迁的激发又将改变令牌的分布。以变迁激发导致令牌在库所间的流动，Petri网可以用于模拟系统的动态运行过程，反映系统的动态特性。网N=（P，T；F）构成了描述系统静态结构框架，但还不能描述系统静态结构的全貌。网论尊重资源有限的事实。实际上，变迁发生所需的资源是有限的，库所容量也应是有限的。完整的网系统应指明资源的初始分布，规定变迁的活动原则，确定库所容量和变迁与资源数量之间的关系。实例1：工业生产线的Petri网模型•有一工业生产线，要完成两项操作，分别为变迁t1和t2表示，变迁t1将进入生产线的半成品s1s2用两个部件s3固定在一起，后形成中间件s4。然后第2个变迁t2将s4和s5用3个部件s3固定在一起形成中间件s6。完成t1和t2都需要用到工具s7•假设受空间限制s2s5最多不能超过100件，s4最多不能超过5件，s3最多不能超过1000件。S1S6S7S4t1t2S2S3S5K=100K=1000K=100K=523实例2：基于Petri网的柔性制造系统（FMS）建模举例板材加工FMS主要由以下三部分组成：①数控加工设备，包括：数控冲床、数控剪板机和数控折弯机等及其上下料辅助装置；②自动化物料运储装置，如立体仓库、堆垛机及上下料小车等；③计算机控制及管理系统。与金属切削FMS相比，板材FMS具有以下特点：①零件的种类、批量及复杂程度存在较大差异；②板料和零件的出入库等操作以托盘为单位，加工过程则以托盘上的单张板料或零件为单位；③作业计划制定涉及零件混合排样问题，零件种类、排样方法及调度策略等对机床的换模形式、换模时间以及FMS效率具有重要影响；④板材零件的加工工序较为简单和固定。从板料到零件需要只经过冲压、剪切和折弯等三道工序，有些零件则只需冲压和剪切等两道工序。具有冲压、剪切和折弯单元的板材加工FMS物理配置图从系统建模角度，将板材加工FMS中的活动分为三类：①以冲压和剪切为特征的冲剪操作；②冲剪后零件的折弯操作；③板料以及冲剪后零件的出入库操作。采用Petri网建模的基本步骤：①划分和定义系统内所有活动及其相互关系；②采用Petri网描述上述活动及其关系，得到系统Petri网模型其中，“▕”表示变迁，t1～t16为系统中的变迁“◯”表示普通库所，p0～p20为普通库所“◎”表示决策库所，pd0～pd7为决策库所Petri网是一种图形演绎方法，应用Petri网分析系统故障就是将系统所不希望发生的事件作为顶库所，逐步找出导致这一事件的所有可能因素作为中间库所和底库所。故障树可以看作是系统中故障传播的逻辑关系，一般的单调关联故障树只含有与门和或门。故障树可以很方便地用Petri网表示，如与门采用多输入变迁代替，或门采用两个变迁代替。案例3Petri网的应用案例39与门或门故障树表示Petri网表示图2故障树的Petri网模型表示应用关联矩阵求割集在故障树分析中，当一些底事件同时发生时，顶事件必然发生，能使顶事件发生的这些底事件的集合就称为割集。如果割集中的任一底事件不发生时，顶事件也不发生，则这样的割集称为最小割集。关联矩阵是Petri网的主要分析方法之一。在表示Petri网结构的有向图中，库所以圆表示；变迁以矩形表示(图3)。若从库所P到变迁t的输入函数取值为非负整数w，记为I(P，t)=w，用从P到t的一有向弧并旁注w表示；若从变迁t到库所P的输出函数取值为非负整数w，记为O(P，t)=w，用从t到P的一有向弧并旁注w表示。特别地,若w=1,则不必标注；若I(P，t)=0或O(P，t)=0,则不必画弧。I与O均可表示为nxm非负整数矩阵，O与I之差(AT=O-I)称为关联矩阵。这里我们探讨规范网，所以w=1。求图3中Petri网模型的关联矩阵：P3t1P5P1P2P4t2t3求图3中Petri网模型的关联矩阵：(1)找出关联矩阵中只有1和0，没有-1的行，则该行对应的为顶库所（只有输入库所，没有输出库所），由此库所开始寻找（在此关联矩阵中为最后一行）。(2)由顶库所对应行的1出发按列寻找到-1，此-1所对应行代表的库所为顶库所的一个输入库所，如果该列有多个-1，则说明对应同一变迁有多个输入库所，并且输入的库所为“相与”关系。割集求解步骤(3)由步骤（2）中找到的-1按行寻找1，如有1则说明该库所为中间库所，继续按步骤（2）所述循环查找，直到所在行没有1为止。没有1，则说明该库所是一个底库所即基本事件。如果该行有多个1，则说明由这些1对应的库所对应多个变迁，应为“相或”关系。(4)按步骤（2）、步骤（3）继续查找，直到查找到最底层库所。(5)按照上面的“相与”“相或”关系将底库所展开,则得到所有割集。(6)按照布尔吸收律、等幂率或素数法可求得最小割集。注：布尔吸收律A+AB=AA(A+B)=A四、Petri网的行为特性与其它建模方法相比，Petri网的优点不仅表现在建模能力上，更主要表现在它所具有的分析能力上。Petri网具有一些专门的分析手段，对系统活性（liveness）及死锁（deadlock）进行分析，分析系统中的顺序、并发及冲突等复杂事件关系。采用可达树（reachabilitytree）理论分析系统的有界性（boundness）与安全性（safety）等P1t1P2P3t2顺序关系P1t1P2P3t2P4P5t3并发关系1可达性•是研究任何系统动态特性的基础,决定系统能否到达一个指定的状态.•(1)系统按照一定的流程运行，系统是否能够实现一定的状态；或者不期望的状态不出现。•比如：生产调度计划的验证（按照一定的生产调度计划进行生产，一定的生产任务是否能够完成）（2）要求到达一定的状态，如何确定系统的运行轨迹（流程）。比如：生产调度，如何安排作业顺序？P1t1P2P3t2P4t3P5P6t4死锁关系2活性•在系统中用于检测是否存在死锁。一个系统存在的一个潜在问题是死锁，为了避免死锁，系统的Petri网模型必须具有活性。•（1）互斥：同时争夺唯一资源•（2）占用且等待•（3）无抢占•（4）循环等待P1t1P2P3t2P4t3冲突的实质是竞争资源。冲突就是指这种两者都有发生权，但在同一时刻只能有一个发生的关系。逻辑关系图：冲突（互斥）\冲撞关系冲突双方谁先发生由系统实际运行环境及状态决定，即谁有优先权是不确定的。冲突又称为选择（choice）或不确定（nondeterminism），是对系统性能影响最大的事件类型。3有界性•是一个非常重要的特性,它保证系统在运行过程中不会需要无限的资源.•有界性反映一个库所在系统运行过程中能够获得的最大的令牌数,即所能获得的最大资源数,它与系统的初始令牌有关.•在实际系统设计中,必须使网络中的每个库所在任何状态下的令牌数小于库所的容量,这样才能保证系统的正常运行。4安全性（是否会溢出）•决定系统中正在执行的操作不会发出请求.若Petri网为1有界,则称此Petri网是安全的.这种网的每一个库所要么有一个令牌，要么没有令牌。安全性是有界性的一种特殊情况。5可逆性和回家状态（主宿状态）•在制造业系统和过程控制系统中存在着一个重要的问题：错误复原，即系统能否重新回到原来状态(保证系统的循环特性)。•可逆——系统可自生初始化•主宿（回家）——系统经过有限步骤，将回到期望状态6守恒性•在一个Petri网系统中,令牌被用来描述系统资源,对这类Petri网,守恒性是一个重要性质,要使代表资源的令牌在Petri网运行中既不会增加也不会减少,最简单的方法就是网中总令牌数保持恒定。基本逻辑关系表达：顺序、并发、冲突、异或、死锁事例与进程，进程的合成P1t1P2P3t2P1t1P2P3t2P4P5t3顺序并发P1t1P2P3t2P4t3P1t1P2P3t2P4P5t3异或冲突P1t1P2P3t2P4t3P5P6t4死锁Petri网性能分析•覆盖树（Coverabilit