petri网理论教程.ppt

Petri 网理论 1 Petri网起源网起源 1962年联邦德国的卡尔 ·A·佩特里在他的博士论文《用自动机通信》中首次使用网状结构模拟通信系统这种系统模型后来以Petri网为名流传现在Petri网一词既指这种模型，又指以这种模型为基础发展起来的理论有时又把Petri网称为网论(net theory) 2 Petri网的发展网的发展 五十多年来 Petri网的理论和应用都有了长足的进步其发展过程大体可分为三个阶段 60年代，Petri网的研究以孤立的网系统为对象，以寻求分析技术和应用方法为目标这些内容统称为特殊网论(special net theory)此处“特殊”是与“一般”或“通用”比较而言，指的就是孤立的网系统个体 3 Petri网的发展网的发展 通用网论的(general net theory)研究始于70年代初以C．A．Petri为核心的一批科学家以网系统的全体作为对象，研究其分类及各类网之间的关系，发展了以并发论，同步论，网逻辑和网拓为主要内容的理论体系 80年代开始为 Petri网综合发展阶段，以理论与应用的结合及计算机辅助工具的开发为主要内容。

发展到现在Petri网已经广泛应用于自动化、机械制造、军事指挥等学科领域 4  Petri网基本概念网基本概念 Petri网是一种网状信息流模型，包括条件和事件两类节点，在条件和事件为节点的有向二分图基础上添加表示状态信息的托肯（token）分布，并按引发规则使得事件驱动状态演变，从而反映系统动态运行过程 通常情况下，用小矩形表示事件 （称作变迁）结点，用小圆形表示条件（称作位置）结点，变迁结点之间、位置结点之间不能有有向弧，变迁结点与位置节点之间连接有向弧，由此构成的有向二分图称作网网的某些位置结点中标上若干黑点（token），从而构成Petri网 5 网系统演示：网系统演示： P1 P2 t1 P3 t2 t6 P4 P10 t7 t3 P6 P8 t5 P7 P9 t4 t8 P5 图1 6 Petri网模型特点网模型特点 模拟性：从组织结构的角度，模拟系统的控制和管理，不涉及系统实现所依赖的物理和化学原理； 客观性：精确描述事件（变迁）间的依赖（顺序）关系和不依赖（并发）关系这种关系客观存在，与观察无关； 描述性：用统一的语言（网）描述系统结构和系统行为； 7 Petri网模型特点网模型特点 流特征：适合描述以有规则的流动为行为特征的系统，包括能量流、物质流和信息流； 分析性：网系统具有与应用环境无关的动态行为，是可以独立研究的对象。

这样，可按特定方式进行系统性质的分析和验证； 基础性：网系统在各个应用领域得到不同的解释，是沟通不同领域的桥梁网论是这些领域的共同理论基础 8 Petri网的应用网的应用 Petri 网是一种图形演绎方法，应用 Petri网分析系统故障就是将系统所不希望发生的事件作为顶库所，逐步找出导致这一事件的所有可能因素作为中间库所和底库所 故障树可以看作是系统中故障传播的逻辑关系，一般的单调关联故障树只含有与门和或门故障树可以很方便地用Petri网表示，如与门采用多输入变迁代替，或门采用两个变迁代替 9 故障树的故障树的Petri网模型表示网模型表示 故障树表示 Petri网表示 或门 与门 图2 10  Petri 网的图形表示方法更为形象、直观，可以表达故障的动态传递过程从图2中可以看出，用Petri网的基本元素 —库所和变迁的不同连接可以表示故障树模型的不同逻辑关系，可以充分利用图论的方法来解决故障模型的诊断推理问题 11 举例：举例： P5 t2 t3 P3 P4 t1 P1 P2 图3 故障树模型和其对应的 Petri网模型 12 应用关联矩阵求割集应用关联矩阵求割集 在故障树分析中，当一些底事件同时发生时，顶事件必然发生，能使顶事件发生的这些底事件的集合就称为割集。

如果割集中的任一底事件不发生时，顶事件也不发生，则这样的割集称为最小割集 13  关联矩阵是 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 14 求图3中Petri网模型的关联矩阵： P5 t2 t3 P3 P4 t1 P1 P2 求图3中Petri网模型的关联矩阵： 割集求解步骤割集求解步骤 (1)找出关联矩阵中只有 1和0，没有-1的行，则该 行对应的为顶库所（只有输入库所，没有输出库所），由此库所开始寻找（在此关联矩阵中为最后一行） (2)由顶库所对应行的 1出发按列寻找到 -1，此-1所对应行代表的库所为顶库所的一个输入库所，如果该列有多个 -1，则说明对应同一变迁有多个输入库所，并且输入的库所为“相与”关系。

17 割集求解步骤割集求解步骤 (3)由步骤（ 2）中找到的 -1按行寻找 1，如有 1 则说明该库所为中间库所，继续按步骤（2）所述循环查找，直到所在行没有1为止没有 1，则说明该库所是一个底库所即基本事件如果该行有多个1，则说明由这些 1对应的库所对应多个变迁，应为“ 相或”关系 (4)按步骤（ 2）、步骤（ 3）继续查找，直到查找到最底层库所 18 割集求解步骤割集求解步骤 (5)按照上面的“相与”“相或”关系将底 库所展开,则得到所有割集 (6)按照布尔吸收律、等幂率或素数法可求得最小割集 注：布尔吸收律A+AB=A A(A+B)=A 19 开始开始 程程序序流流程程图图找到只有0和1的行，并记下值 为1的列数Ai(i=1,2,3,…,m),i=0 Ai各列对应库所为“相或”关找到Ai列中值为-1的行数 系 Bj(j=1,2,3,…,n),j=0 i++; i≤m? N 利用布尔吸收率、等 幂率得到最小割集 结束结束 N Bj各列对应库所Y 为“相或”关找到Bj中值为1的列数 系 Ck(i=1,2,3,…,P),k=0 j++; j≤n? Ck各列对应库所为“相或”关系 k++; k≤P? Y N 20 求含重复事件的求含重复事件的Petri网模型的最小割集网模型的最小割集 在故障树建模过程中会出现重复事件 , 即树中的两个图元代表同一事件。

这样的重复事件应用 Petri网模型可以用同一个库所表示 , 如图下图所示 P5 t2 t3 P4 t1 P1 P2 P3 图4 （a）故障树模型 （b） Petri网模型 21  由图4a中可以看出 B1为重复事件，在对应的Petri网模型中 P1为与B1相对应的重复事件，可见用Petri网模型表达不但图形简单明了，而且算法简便，没有相同序号的图形出现图 4b中Petri网模型的关联矩阵如下： t1t2t3p1?10?1 p2?100T A?p30?10 p1?104p501122  应用关联矩阵法按前述步骤查找，可得： 顶库所为P5，由第5行中的1向上查找可知P3、 P4 为“相与”事件，两者同时与 P1“相或”而P4 又为P1、P2 的“ 相与”事件所以P5 =P1+P3P4 =P1+ P1P2P3，从而最小割集为P1 23 实例分析实例分析 应用上面提出的算法求解一个简单的舰艇防空系统故障的最小割集，其故障树模型及 Petri网模型如图5所示 图(5-1)防空系统故障树 24 P13 t7 t8 t9 t10 P9 t5 P1 P10 P11 P12 t6 P2 P7 P8 t2 t3 t4 t1 P3 P4 P5 P6 图(5-2)防空系统故障树对应Petri网模型 25 由图5可以写出关联矩阵如下 : 26  (1)搜索此关联矩阵 , 找出没有 -1即顶库所在行为第13行，记录下每个 1所在的列分别为第 7、8、9、10列。

(2)从第7列出发，搜索此列记录下这一列中 -1所在的行为第9行 (3)继续搜索第 9行，记录下这一行中 1所在的列为 5, 并且第 5列中对应有两个 -1，则说明这两个 -1所对应的库所P1、P2同为P9的输入库所，则P1、P2为“相与”关系，即P9 =P1P2 27  (4)再从第8列出发即搜索第10行, 只有一个底库所为P10 (5)从第9列出发，搜索第11行，重复步骤(2)、(3), 可得P11=P7P8=(P3+P4)( P5+P6) (6)搜索第12行只有一个底库所为 P12 (7)根据上述步骤, 即有: P13=P9+P10+P11+P12 =P1P2+P10+( P3+P4)( P5+P6) +P12 28  (8)再应用布尔吸收率即可求得最小割集为 { P1, P2} 、 { P10} 、 { P12} 、 { P3, P5} 、 { P4,P5} 、 { P3, P6} 、 { P4, P6} 上述方法充分利用了 Petri网的理论 ,使Petri网的图形方法与其关联矩阵有效结合, 更易于最小割集的求取 29 故障树故障树 故障树将系统所不希望发生的事件 (故障事件)作为分析的目标，逐级找出导致这一事件发生的所有可能因素。

故障树采用相应的符号表示这些事件,再用描述事件间逻辑因果关系的逻辑门符号把顶事件、中间事件与底事件连接成倒立的树状图形，用以表示系统特定顶事件与其各子系统或各元件的故障事件及其他有关因素之间的逻辑关系 31 。