建模与仿真(petri网部分)课件

建模与仿真主讲人：许良Petri网经济管理学院工业工程系建模与仿真主讲人：许良Petri网经济管理学院建模与仿真(petri网部分)ppt课件一、Petri网起源1962年联邦德国的卡尔·A·佩特里在他的博士论文《用自动机通信》中首次使用网状结构模拟通信系统。这种系统模型后来以Petri网为名流传。现在Petri网一词既指这种模型，又指以这种模型为基础发展起来的理论。有时又把Petri网称为网论(nettheory)。

一、Petri网起源1962年联邦德国的卡尔·APetri网的发展五十多年来Petri网的理论和应用都有了长足的进步。其发展过程大体可分为三个阶段。

60年代，Petri网的研究以孤立的网系统为对象，以寻求分析技术和应用方法为目标。这些内容统称为特殊网论(specialnettheory)。此处“特殊”是与“一般”或“通用”比较而言，指的就是孤立的网系统个体。Petri网的发展五十多年来Petri网的理论和应用通用网论的(generalnettheory)研究始于70年代初。以C．A．Petri为核心的一批科学家以网系统的全体作为对象，研究其分类及各类网之间的关系，发展了以并发论，同步论，网逻辑和网拓为主要内容的理论体系。80年代开始为Petri网综合发展阶段，以理论与应用的结合及计算机辅助工具的开发为主要内容。发展到现在Petri网已经广泛应用于自动化、机械制造、军事指挥等学科领域。通用网论的(generalnettheor用简单图形较好的表示并发、同步、因果等关系。以网图的方式简洁、直观的模拟离散事件系统目前已得到广泛应用,有限状态机、通信协议、同步控制、生产系统、形式语言、多处理器系统等建模中用简单图形较好的表示并发、同步、因果等关系。以网图的方式简洁二、Petri网基本概念Petri网是一种网状信息流模型，包括条件和事件两类节点，在条件和事件为节点的有向二分图基础上添加表示状态信息的托肯（token）分布，并按引发规则使得事件驱动状态演变，从而反映系统动态运行过程。

通常情况下，用小矩形表示事件（称作变迁）结点，用小圆形表示条件（称作位置）结点，变迁结点之间、位置结点之间不能有有向弧，变迁结点与位置节点之间连接有向弧，由此构成的有向二分图称作网。网的某些位置结点中标上若干黑点（token），从而构成Petri网。二、Petri网基本概念Petri网是一种网状信息流模型，包P1P2P3P10P4P5P8P6P7P9t5t1t2t4t8t3t7t6P1P2P3P10P4P5P8P6P7P9t5t1t2t4t资源：与系统状态变化有关的因素，如原料、产品、工具、设备等状态元素：资源归类后的抽象库所：一个场所，存放状态元素变迁：资源状态变化事件：引起条件的变迁称为事件容量：库所的最大资源数量resourcestateplace,“S”transition

eventCapability，“K”资源：与系统状态变化有关的因素，如原料、产品、工具、设备等r一个Petri网是一个三元组P={p1，p2，…，pm}为库所（place）的集合；T={t1，t2，…，tn}为变迁（transition）的集合；F=（P×T）∪（T×P）为输入函数和输出函数集，称为流关系。Petri网数学定义一个Petri网是一个三元组Petri网数学定义一个简单的Petri网一个简单的Petri网Petri网数学定义三元组N=（P，T；F）构成网（net）的充分必要条件：①P∩T=ф，规定了库所和变迁是两类不同的元素；②P∪T≠ф，表示网中至少有一个元素；③F=（P×T）∪(T×P)，建立了从库所到变迁、从变迁到库所的单方向联系，并且规定同类元素之间不能直接联系；Petri网数学定义三元组N=（P，T；F）构成网（net）容量和权函数定义设N=（P，T，F）为有向图K为N上P的容量K:P{1,2,3,,,,}在网图中用库所中的黑点表示，无黑点的表示无穷大W为N上F的权重W：F{1,2,3,,,,}在网图中用有向弧上的数字表示，无数字的表示权重为1。容量和权函数定义设N=（P，T，F）为有向图带权重和库所容量的Petri网带权重和库所容量的Petri网Petri网描述系统的最基本概念是库所和变迁

库所表示系统的状态。变迁表示资源的消耗、使用及使系统状态产生的变化。变迁的发生受到系统状态的控制，即变迁发生的前置条件必须满足；变迁发生后，某些前置条件不再满足，而某些后置条件则得到满足。Petri网描述系统的最基本概念是库所和变迁库所表示系统

图形化表示：以圆圈表示为库所

以粗实线表示变迁

以联结库所与变迁之间的有向弧表示输入输出函数用令牌（token）表示库所中拥有的资源数量。

——黑点或数字表示库所变迁图形化表示：库所变迁库所中令牌分布决定变迁的使能（enabled）和激发（fire），变迁的激发又将改变令牌的分布。以变迁激发导致令牌在库所间的流动，Petri网可以用于模拟系统的动态运行过程，反映系统的动态特性。网N=（P，T；F）构成了描述系统静态结构框架，但还不能描述系统静态结构的全貌。网论尊重资源有限的事实。实际上，变迁发生所需的资源是有限的，库所容量也应是有限的。完整的网系统应指明资源的初始分布，规定变迁的活动原则，确定库所容量和变迁与资源数量之间的关系。库所中令牌分布决定变迁的使能（enabled）和激发（fi建模与仿真(petri网部分)ppt课件建模与仿真(petri网部分)ppt课件建模与仿真(petri网部分)ppt课件建模与仿真(petri网部分)ppt课件建模与仿真(petri网部分)ppt课件建模与仿真(petri网部分)ppt课件实例1：工业生产线的Petri网模型有一工业生产线，要完成两项操作，分别为变迁t1和t2表示，变迁t1

将进入生产线的半成品s1s2用两个部件s3固定在一起，后形成中间件s4。然后第2个变迁t2

将s4和s5用3个部件s3固定在一起形成中间件s6。完成t1和t2

都需要用到工具s7假设受空间限制s2s5最多不能超过100件，s4最多不能超过5件，s3最多不能超过1000件。实例1：工业生产线的Petri网模型有一工业生产线，要完成两建模与仿真(petri网部分)ppt课件建模与仿真(petri网部分)ppt课件建模与仿真(petri网部分)ppt课件建模与仿真(petri网部分)ppt课件建模与仿真(petri网部分)ppt课件实例2：基于Petri网的柔性制造系统（FMS）建模举例板材加工FMS主要由以下三部分组成：①数控加工设备，包括：数控冲床、数控剪板机和数控折弯机等及其上下料辅助装置；②自动化物料运储装置，如立体仓库、堆垛机及上下料小车等；③计算机控制及管理系统。实例2：基于Petri网的柔性制造系统（FMS）建模举例

与金属切削FMS相比，板材FMS具有以下特点：①

零件的种类、批量及复杂程度存在较大差异；②板料和零件的出入库等操作以托盘为单位，加工过程则以托盘上的单张板料或零件为单位；③作业计划制定涉及零件混合排样问题，零件种类、排样方法及调度策略等对机床的换模形式、换模时间以及FMS效率具有重要影响；④板材零件的加工工序较为简单和固定。从板料到零件需要只经过冲压、剪切和折弯等三道工序，有些零件则只需冲压和剪切等两道工序。

与金属切削FMS相比，板材FMS具有以下特点：具有冲压、剪切和折弯单元的板材加工FMS物理配置图具有冲压、剪切和折弯单元的板材加工FMS物理配置图

从系统建模角度，将板材加工FMS中的活动分为三类：①以冲压和剪切为特征的冲剪操作；②冲剪后零件的折弯操作；③板料以及冲剪后零件的出入库操作。

采用Petri网建模的基本步骤：①划分和定义系统内所有活动及其相互关系；②采用Petri网描述上述活动及其关系，得到系统Petri网模型从系统建模角度，将板材加工FMS中的活动分为三类：采用P其中，“▕”表示变迁，t1～t16为系统中的变迁“◯”表示普通库所，p0～p20为普通库所“◎”表示决策库所，pd0～pd7为决策库所其中，“▕”表示变迁，t1～t16为系统中的变迁建模与仿真(petri网部分)ppt课件建模与仿真(petri网部分)ppt课件建模与仿真(petri网部分)ppt课件Petri网是一种图形演绎方法，应用Petri网分析系统故障就是将系统所不希望发生的事件作为顶库所，逐步找出导致这一事件的所有可能因素作为中间库所和底库所。故障树可以看作是系统中故障传播的逻辑关系，一般的单调关联故障树只含有与门和或门。故障树可以很方便地用Petri网表示，如与门采用多输入变迁代替，或门采用两个变迁代替。

案例3Petri网的应用案例Petri网是一种图形演绎方法，应用Petr39与门或门故障树表示Petri网表示图2故障树的Petri网模型表示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。关联矩阵是Petri网的主要分析方法之一。在表示Pe求图3中Petri网模型的关联矩阵：P3t1P5P1P2P4t2t3求图3中Petri网模型的关联矩阵：P3t1P5P1P2P4求图3中Petri网模型的关联矩阵：求图3中Petri网模型的关联矩阵：

(1)找出关联矩阵中只有1和0，没有-1的行，则该行对应的为顶库所（只有输入库所，没有输出库所），由此库所开始寻找（在此关联矩阵中为最后一行）。(2)由顶库所对应行的1出发按列寻找到-1，此-1所对应行代表的库所为顶库所的一个输入库所，如果该列有多个-1，则说明对应同一变迁有多个输入库所，并且输入的库所为“相与”关系。割集求解步骤(1)找出关联矩阵中只有1和0，没有-1的行，则该

(3)由步骤（2）中找到的-1按行寻找1，如有1则说明该库所为中间库所，继续按步骤（2）所述循环查找，直到所在行没有1为止。没有1，则说明该库所是一个底库所即基本事件。如果该行有多个1，则说明由这些1对应的库所对应多个变迁，应为“相或”关系。(4)按步骤（2）、步骤（3）继续查找，直到查找到最底层库所。建模与仿真(petri网部分)ppt课件

(5)按照上面的“相与”“相或”关系将底库所展开,则得到所有割集。(6)按照布尔吸收律、等幂率或素数法可求得最小割集。

注：布尔吸收律A+AB=AA(A+B)=A(5)按照上面的“相与”“相或”关系将底库所展开,则得到四、Petri网的行为特性与其它建模方法相比，Petri网的优点不仅表现在建模能力上，更主要表现在它所具有的分析能力上。

Petri网具有一些专门的分析手段，对系统活性（liveness）及死锁（deadlock）进行分析，分析系统中的顺序、并发及冲突等复杂事件关系。采用可达树（reachabilitytree）理论分析系统的有界性（boundness）与安全性（safety）等四、Petri网的行为特性与其它建模方法相比，Petri网顺序关系并发关系顺序关系并发关系1可达性是研究任何系统动态特性的基础,决定系统能否到达一个指定的状态.

(1)系统按照一定的流程运行，系统是否能够实现一定的状态；或者不期望的状态不出现。比如：生产调度计划的验证（按照一定的生产调度计划进行生产，一定的生产任务是否能够完成）（2）要求到达一定的状态，如何确定系统的运行轨迹（流程）。比如：生产调度，如何安排作业顺序？1可达性是研究任何系统动态特性的基础,决定系统能否到达一个死锁关系死锁关系2活性在系统中用于检测是否存在死锁。一个系统存在的一个潜在问题是死锁，为了避免死锁，系统的Petri网模型必须具有活性。（1）互斥：同时争夺唯一资源（2）占用且等待（3）无抢占（4）循环等待2活性在系统中用于检测是否存在死锁。一个系统存在的一个潜在冲突的实质是竞争资源。

冲突就是指这种两者都有发生权，但在同一时刻只能有一个发生的关系。逻辑关系图：冲突（互斥）\冲撞关系冲突的实质是竞争资源。冲突就是指这种两者都有发生权，但在同

冲突双方谁先发生由系统实际运行环境及状态决定，即谁有优先权是不确定的。冲突又称为选择（choice）或不确定（nondeterminism），是对系统性能影响最大的事件类型。冲突双方谁先发生由系统实际运行环境及状态决定，即谁有优冲突3有界性是一个非常重要的特性,它保证系统在运行过程中不会需要无限的资源.有界性反映一个库所在系统运行过程中能够获得的最大的令牌数,即所能获得的最大资源数,它与系统的初始令牌有关.

在实际系统设计中,必须使网络中的每个库所在任何状态下的令牌数小于库所的容量,这样才能保证系统的正常运行。3有界性是一个非常重要的特性,它保证系统在运行过程中不会需建模与仿真(petri网部分)ppt课件4安全性（是否会溢出）决定系统中正在执行的操作不会发出请求.若Petri网为1有界,则称此Petri网是安全的.这种网的每一个库所要么有一个令牌，要么没有令牌。安全性是有界性的一种特殊情况。4安全性（是否会溢出）决定系统中正在执行的操作不会发出请5可逆性和回家状态（主宿状态）在制造业系统和过程控制系统中存在着一个重要的问题：错误复原，即系统能否重新回到原来状态(保证系统的循环特性)。可逆——系统可自生初始化主宿（回家）——系统经过有限步骤，将回到期望状态5可逆性和回家状态（主宿状态）在制造业系6守恒性在一个Petri网系统中,令牌被用来描述系统资源,对这类Petri网,守恒性是一个重要性质,要使代表资源的令牌在Petri网运行中既不会增加也不会减少,最简单的方法就是网中总令牌数保持恒定。6守恒性在一个Petri网系统中,令牌被用来描述系统资源,基本逻辑关系表达：顺序、并发、冲突、异或、死锁事例与进程，进程的合成顺序并发基本逻辑关系表达：顺序、并发、冲突、异或、死锁顺序并发异或冲突异或冲突死锁死锁Petri网性能分析覆盖树（Coverabilitytree）——可达图不变量（Invariation）Petri网性能分析覆盖树（Coverabilitytre覆盖树性能分析法1、标识向量m初始标识m0=(11000)T标识m1=(00100)Tm2=(00011)T覆盖树性能分析法1、标识向量m覆盖的数学定义覆盖的数学定义分析步骤1、m0作为“树根”（可作上new记号）2、对有new记号的标识m做以下事情，否则终止；3、选择某一“new”标识m；（1）若m与树中间已有的其他标识m相同，则将其记为“old”，转向其他“new”标识；（2）若在m下无变迁使能，则将m记为“deadend”；4、对于m下有使能的所有变迁t，做以下事情：（1）激发t，产生标识m’；（2）若从树根至m’的路径上存在一标识m’’,使得m’覆盖m’’，但m’’不等于m’（m’>m’’）,则对于那些使m’(p)>m’’(p)成立的p：用ω取代m’(p);（3）以m’为一节点，从m到m’画一有向线，将其记为t，并将m’记为“new”5、除去m的“new”标志，回到步骤2分析步骤1、m0作为“树根”（可作上new记号）建模与仿真(petri网部分)ppt课件当且仅当树中所有节点上均不出现ω时，PN网是有界的；（可以在树中找出所有库所中最大的托肯数K，称为PN是K有界的）当且仅当树中所有的节点上仅包含0或1时，则PN网是安全的。否则没有记为ω的库所是安全的。在不包含ω的树中，若给定任何2个节点之间，都存在一有向路径，在该路径上所有变迁都出现，则PN是活的。(包含ω的树无法确定活性)在不包含ω的树中，若从任何节点到根节点之间都存在一有向路径，则PN是可逆的。(包含ω的树无法确定活性)基本性能分析当且仅当树中所有节点上均不出现ω时，PN网是有界的；（可以在基本Petri网：每个库所容量为1，这样库所可称为条件，变迁可称为事件。故又称为条件/事件系统C/E低级Petri网：库所容量和权重为>=1的任意整数，称为库所/变迁网。简作P/T网定时Petri网：将各事件的持续时长标在库所旁边，库所中新产生的标记经过一须时间后才加入到网中，或是标在变迁上，经过时间延迟后发生。高级Petri网：谓词/事件网、染色网、随机网等。Petri网类型基本Petri网：每个库所容量为1，这样库所可称为条件，变迁建模与仿真(petri网部分)ppt课件Petri网模型特点模拟性：从组织结构的角度，模拟系统的控制和管理，不涉及系统实现所依赖的物理和化学原理；客观性：精确描述事件（变迁）间的依赖（顺序）关系和不依赖（并发）关系。这种关系客观存在，与观察无关；描述性：用统一的语言（网）描述系统结构和系统行为；Petri网模型特点模拟性：从组织结构的角度，模拟系统的控制流特征：适合描述以有规则的流动为行为特征的系统，包括能量流、物质流和信息流；分析性：网系