第三部分Petri网的分析方法.ppt
《第三部分Petri网的分析方法.ppt》由会员分享,可在线阅读,更多相关《第三部分Petri网的分析方法.ppt(32页珍藏版)》请在三一文库上搜索。
1、第三部分 Petri网的分析方法,提纲,可达标识图与可覆盖性树 关联矩阵与状态方程 Petri网语言 Petri网进程,可达标识图与可覆盖性树,对于有界Petri网,其可达标识集R(M0)是一个有限集合,因此可以以R(M0)作为顶点集,以标识之间的直接可达关系为弧集构成一个有向图,称为Petri网的可达标识图(reachable marking graph)。 定义3.1. 设PN=(P,T;F, M0)为一个有界Petri网。PN的可达标识图定义为一个三元组RG(PN)=(R(M0),E, L),其中 E=(Mi,Mj)| Mi, Mj R(M0),tk T: Mi tk Mj L:ET,L
2、(Mi,Mj)= tk 当且仅当Mi tk Mj 称R(M0)为顶点集,E为弧(边)集, 若L(Mi,Mj) = tk,则称tk为弧(Mi,Mj)的旁标。,可达标识图与可覆盖性树,通过可达标识图RG(PN)可以分析有界Petri网PN的各种性质。 定理3.1. 对任意Mi,Mj R(M0),Mj是从 Mi可达的当且仅当在RG(PN)中,从Mi到Mj存在一条有向路。 推论3.1. 在RG(PN)中,从M0到每个结点都有一条有向路。 推论3.2. M R(M0)是PN的一个死标识当且仅当在RG(PN)中,M是一个终端标识。 定理3.2. 设pj P,在Petri网PN中pj的界 B(pj )等于R
3、G(PN)中各个顶点向量的第j个分量的最大值。 推论3.3. PN是安全的当且仅当RG(PN)中每个顶点的向量都是0-1向量。,可达标识图与可覆盖性树,定理3.3. 有界Petri网PN是活的当且仅当在RG(PN)中,从顶点M0出发的每条有向路都走入一个强连通子图,而且在每个这样的强连通子图中,每个t T至少是一条有向弧的旁标。 定理3.4. 有界Petri网PN的两个变迁t1和t2处于公平关系的充分必要条件是在RG(PN)的每条有向回路C中, t1是其中的一条弧的旁标当且仅当t2也是其中一条弧的旁标。 定理3.5. PN是公平Petri网的充分必要条件是在RG(PN)的每条有向回路C中,每个
4、 t T 都至少是C中一条弧的旁标。,定理3.3、3.4和3.5在无界Petri网中还成立吗?,?,可达标识图与可覆盖性树,若PN不是有界网,则R(M0)是一个无限集合,无法画出PN的可达标识图。 为了用有限形式表达一个有无限个状态的系统的运行情况,引入一个表示无界量的符号。 具有下述性质: (1)对任意正整数n: n, n= (2) 当库所pj中的标识数在Petri网的运行过程中趋向于无限增长时,就把标识向量中的第j个分量改为 ,以此覆盖所有这类标识。 通过引入 ,就可以用有限树来反映无界Petri网的运行情况,称该有限树为Petri网PN的可覆盖性树(coverability tree),
5、记为CT(PN)。,可达标识图与可覆盖性树,算法3.1. Petri网可覆盖性树的构造算法 输入: PN=(P,T;F, M0) 输出:CT(PN) 算法步骤: Step0:以M0作为CT(PN)的根结点,并标之以“新”; Step1:While 存在标注为“新”的结点 Do 任选一个标注为“新”的结点,设为M; Step2: If 从M0 到M的有向路上有一个结点的标识等于M Then 把M的标注改为“旧”,返回Step1; Step3: If tT:Mt Then 把M的标注改为“端点”,返回Step1 Step4: For 每个满足Mt 的tT Do 4.1: 计算MtM中的M; 4.2
6、: If 从M0 到M的有向路上存在M使MM Then 找出使M(pj) M(pj)的分量j,把M的第j个分量改为; 4.3: 在CT(PN)中引入一个“新”结点M,从M到M画一条有向弧,并把此弧旁标以t; Step5: 擦去结点M的“新”标注,返回Step1。,可达标识图与可覆盖性树,M0 : (1,0,0,0),t1,(1,0, ,0),新,新,(1,0, 1,0),新,新,新,新,新,旧,旧,新,端点,可达标识图与可覆盖性树,定理3.1. PN是有界Petri网当且仅当(按算法3.1构造的)CT(PN)中,每个结点的标识向量都不含有分量。 对有界Petri网PN,按照算法3.1构造出来的
7、树结构称为PN的可达性树(reachability tree),记为RT(PN)。 定义3.2. 设CT(PN)为Petri网的可覆盖性树。若将CT(PN)中标识向量相同的结点合并在一起,便得到PN的可覆盖性图,记为CG(PN)。,M0 : (1,0,0,0),t1,(1,0, ,0),(1,0, ,0),t1,(1,0, ,0),t3,t1,t3,提纲,可达标识图与可覆盖性树 关联矩阵与状态方程 Petri网语言 Petri网进程,关联矩阵与状态方程,网的结构可以用一个矩阵来表示,从而可以引入线性代数的方法对Petri网进行分析。 定义3.3. 设PN=(P,T;F, M0)为一个Petri
8、网。 P=p1, p2,pm ,T=t1, t2,tn ,则网N =(P,T;F)可以用一个n行m列矩阵 A=aijnm (3.1) 来表示,称A为PN(N)的关联矩阵(incidence matrix)。其中,关联矩阵与状态方程,PN的输出矩阵 PN的输入矩阵 行向量 列向量 标识M,关联矩阵与状态方程,p1,p2,t1,t2,p4,t3,t4,p3,0 1 0 0,1 0 0 0,0 0 1 1,0 1 1 0,1 0 0 0,0 1 1 0,1 0 0 0,0 0 0 1,1 -1 0 0,-1 1 1 0,1 0 -1 -1,0 -1 -1 1,关联矩阵与状态方程,引理3.1. 设PN
9、=(P,T;F, M0)为一个Petri网。A为PN的关联矩阵, tiT,则Mti的充分必要条件是,引理3.2. 设PN=(P,T;F, M0)为一个Petri网。A为PN的关联矩阵, 如果Mti M,则有,定理3.2. 设PN=(P,T;F, M0)为一个Petri网。A为PN的关联矩阵, 若M R(M0),则存在非负整数的n维向量X,使得,上式称为Petri网的状态方程(state equation)。,状态方程是M从M0可达的一个必要条件,而非充分条件。,关联矩阵与状态方程,证:,变迁发生序列与Petri网语言,Petri网进行分析的另一种方法是考察网系统中所有可能发生的变迁序列以及这些
10、序列构成的集合的性质。 一个字母表上满足某些特定条件的字符串的集合,称为该字母表上的一个语言。 将Petri网的变迁集T看作一个字母表,或者给出变迁集到某个字母表上的一个映射,那么该Petri网所有可能发生的变迁序列(或其映射)的集合就是T(或)上的一个语言。,变迁发生序列与Petri网语言,定义3.4.设PN=(P,T;F, M0)为一个Petri网。 : T为标注函数,Qt R(M0)。令 L=() *|T*:M0M,M Qt L=() *|(T*:M0M) (MQt ,MM) (1)若Qt是预先给定R(M0)的一个子集,则称L为PN产生的L-型语言;L称为PN产生的G-型语言。 (2)若
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第三 部分 Petri 分析 方法
链接地址:https://www.31doc.com/p-2557936.html