Petri网-基本概念.ppt

变迁t2发生 s1 t1 t2 t3 s2 s3 s4 ?1=(N, M1) M1: M1(s1)=0, M0(s2)=M0(s3)=1, M0(s4)=0 M1=(0, 1, 1, 0) t4 变迁t1发生 s1 t1 t2 t3 s2 s3 s4 ?2=(N, M2) M2: M1(s1)=1, M0(s2)=M0(s4)=0, M0(s3)=1 M2=(1, 0, 1, 0) t4 变迁t4发生 s1 t1 t2 t3 s2 s3 s4 ?3=(N, M3) M3: M1(s1)=0, M0(s2)=M0(s3)=0, M0(s4)=1 M3=(0, 0, 0, 1) t4 问题 当网系统运行到标识M1时，变迁t1和t4都可以发生点火。网系统根据什么原则，选取变迁呢？ 当网系统运行到标识M2时，还可以继续运行下去吗？ 当网系统运行到标识M3时，还可以继续运行下去吗？ 不确定性 停止 3、网系统分类(1/2) 容量函数 K: S?N+?{?} N+是自然数集， ?是无穷 标识 M: S?N0为一个标识的充要条件，?s?S有M(s)?K(s)。 权函数W: F?N+。用W(x, y)表示值。 我们前面学习的网系统：K(s)=?, W(x, y)=1 网系统分类(2/2) 根据Ｋ及Ｗ分成四类： 基本网系统（ＥＮ系统）:K?1, W ?1 库所／变迁网（Ｐ／Ｔ网） :K??, W ?1 库所／变迁系统（Ｐ／Ｔ系统）:K和W为任意容量函数和权函数 高级Petri网：谓词Petri网和有色Petri网 基本网系统（Ｅ／Ｎ系统） K?1, W ?1； 四元组N= (B, E; F, Cin)， 库所?条件：真或假；B表示条件集； 变迁?事件 E表示事件集； 由于库所为条件，即Ｍ(ｓ)＝０或１，可以不用向量表示Ｍ，而用Ｂ的子集表示: c={b?B|M(b)=1}，称为情态 cin={b?B|M0(b)=1}，称为初始情态 例子 c1 c2 c4 c3 c5 c6 c7 a1 a2 a3 M0=(1, 1, 0, 1, 1, 0, 0) M0=(c1, c2, c4, c5) P/T网 K??, W ?1 1962年，联邦德国的Carl Adam Petri在他的博士论文《用自动机通信》中提出的Petri网。 基本网系统是P/T网的特例，P/T网是P/T系统的特例。 案例：四季系统(1/3) 用EN系统建模四级的变化? 四季系统(2/3) 春暖花开 赤日炎炎 秋风落叶 寒风刺骨 春暖花开 四季系统(3/3) ?春暖花开 赤日炎炎 秋风落叶 事件 t1（变化） t2 t3 t4 条件 s1（状态） s2 s3 寒风刺骨 s4 春暖花开 s1 a1 c1 c2 a2 c3 a3 c4 a4 案例：生产流水线（P/T系统） 生产流水线：半成品在流水线上移动，每个生产环节再组装上一两个部件，直到产生产品。 t1: 半成品s1 部件s2 二个螺丝s3 t2: 工具s7 半成品s4 部件s5 四个螺丝s3 工具s7 半成s４ 半成品s6 说明 变迁t1的产生：用工具(s7)，两个螺丝钉(s3)把一个部件(s2)装配到半成品(s1)，产生一个新的半成品(s4)，并退换工具。 变迁t2的产生：用四个螺丝钉(s3)把一个部件(s5)装配到半成品(s4)，产生一个新的半成品(s6)，并退换工具。 问题 变迁t1和t2的关系? t2会不会永远不执行？ 4、基本网系统（Ｅ／Ｎ系统） 局部确定性 e e . . c 一个变迁是否发生， 取决于变迁的外延， 与全局状态无关。 事件间的基本关系 设c为E/N系统EN=(B, E; F, cin)的情态，e1, e2?E为EN的任意两个事件。 1、顺序关系（sequential relation） 如果c[e1, 但?c[e2，而c’[e2，其中c’是c的后继； c[e1 c’, 就说e1和 e2在c有顺序关系。 c1 c2 c3 e1 e2 2、冲突关系（in conflict） 若c[e1?c[e2，但? c[{e1, e2}，则e1和 e2在c有互相冲突。 c1 c2 e1 e2 3、冲撞关系（contact） 若有b?B和e?E使得?e?c，又b?c且b? e?，则说在情态c条件b处有冲撞。 c1 c2 e1 e2 c3 c4 c5 4、并发关系 若?e 1? ?e 2=?则? ?e 1? ?e 2?c，说e1和 e2在c有并发关系。 e1 e2 总结 1）Petri网不仅可以刻画系统的结构，而且可以描述系统的动态行为； 2）Petri网既有直观的图形化表示，又有许多数学方法对其性质进行分析； 3）Petri网可以描述真并发语