《建模与仿真(petri网部分)ppt课件.ppt》由会员分享，可在线阅读，更多相关《建模与仿真(petri网部分)ppt课件.ppt（75页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 建模建模与仿真与仿真主主 讲讲 人：许人：许 良良Petri网网经济管理学院工业工程系经济管理学院工业工程系 一、一、PetriPetri网起源网起源 1962年联邦德国的卡尔A佩特里在他的博士论文用自动机通信中首次使用网状结构模拟通信系统。这种系统模型后来以Petri网为名流传。现在Petri网一词既指这种模型，又指以这种模型为基础发展起来的理论。有时又把Petri网称为网论(net theory)。 PetriPetri网的发展网的发展 五十多年来Petri网的理论和应用都有了长足的进步。其发展过程大体可分为三个阶段。 60年代，Petri网的研究以孤立的网系统为对象，以寻求分析技术和应
2、用方法为目标。这些内容统称为特殊网论(special net theory)。此处“特殊”是与“一般”或“通用”比较而言，指的就是孤立的网系统个体。 通用网论的(general net theory)研究始于70年代初。以CAPetri为核心的一批科学家以网系统的全体作为对象，研究其分类及各类网之间的关系，发展了以并发论，同步论，网逻辑和网拓为主要内容的理论体系。 80年代开始为Petri网综合发展阶段，以理论与应用的结合及计算机辅助工具的开发为主要内容。发展到现在Petri网已经广泛应用于自动化、机械制造、军事指挥等学科领域。 二、二、PetriPetri网基本概念网基本概念Petri网是一
3、种网状信息流模型，包括条件和事件两类节点，在条件和事件为节点的有向二分图基础上添加表示状态信息的托肯（token）分布，并按引发规则使得事件驱动状态演变，从而反映系统动态运行过程。 通常情况下，用小矩形表示事件（称作变迁）结点，用小圆形表示条件（称作位置）结点，变迁结点之间、位置结点之间不能有有向弧，变迁结点与位置节点之间连接有向弧，由此构成的有向二分图称作网。网的某些位置结点中标上若干黑点（token），从而构成Petri网。 P1P2P3P10P4P5P8P6P7P9t5t1t2t4t8t3t7t6 resourcestateplace ,“S”transitiontransition e
4、ventCapability，“K” 一个Petri网是一个三元组 P=p1，p2，pm为为库所（库所（place）的集合；的集合； F =（PT）（TP）为）为输入函数和输出函数集输入函数和输出函数集，称为流关系。称为流关系。( , ,)NP T FPetriPetri网数学定义网数学定义 一个简单的一个简单的Petri网网 PetriPetri网数学定义网数学定义 容量和权函数定义容量和权函数定义 设N=（P，T，F）为有向图 K为N上P的容量 K:P1,2,3, 在网图中用库所中的黑点表示，无黑点的表示无穷大 W为N上F的权重 W：F 1,2,3, 在网图中用有向弧上的数字表示，无数字的
5、表示权重为1。 带权重和库所容量的带权重和库所容量的Petri网网 库所变迁 库所中令牌分布决定变迁的使能（库所中令牌分布决定变迁的使能（enabledenabled）和激发（和激发（firefire），）， 变迁的激发又将改变令牌的分布。变迁的激发又将改变令牌的分布。 以变迁激发导致令牌在库所间的流动，以变迁激发导致令牌在库所间的流动，PetriPetri网可以用于模拟系网可以用于模拟系 统的动态运行过程，反映系统的动态特性。统的动态运行过程，反映系统的动态特性。网网N=N=（P P，T T；F F）构成了描述系统静态结构框架，但还不能描构成了描述系统静态结构框架，但还不能描述系统静态结构的
6、全貌。述系统静态结构的全貌。 网论尊重资源有限的事实。实际上，变迁发生所需的资源是有网论尊重资源有限的事实。实际上，变迁发生所需的资源是有 限的，库所容量也应是有限的。限的，库所容量也应是有限的。 完整的网系统应指明资源的初始分布，规定变迁的活动原则，完整的网系统应指明资源的初始分布，规定变迁的活动原则，确定库所容量和变迁与资源数量之间的关系。确定库所容量和变迁与资源数量之间的关系。 实例实例1 1：工业生产线的：工业生产线的PetriPetri网模型网模型 有一工业生产线，要完成两项操作，分别为变迁t1和t2表示，变迁t1 将进入生产线的半成品s1s2用两个部件s3固定在一起，后形成中间件s
7、4。然后第2个变迁t2 将s4 和s5用3个部件s3固定在一起形成中间件s6。完成t1和t2 都需要用到工具s7 假设受空间限制s2 s5最多不能超过100件， s4最多不能超过5件，s3最多不能超过1000件。 实例实例2 2： 基于基于PetriPetri网的柔性制造系统（网的柔性制造系统（FMSFMS）建模举例）建模举例 板材加工板材加工FMSFMS主要由以下三部分组成：主要由以下三部分组成： 数控加工设备，包括：数控冲床、数控剪板机和数数控加工设备，包括：数控冲床、数控剪板机和数控折弯机等及其上下料辅助装置；控折弯机等及其上下料辅助装置； 自动化物料运储装置，如立体仓库、堆垛机及上下自
8、动化物料运储装置，如立体仓库、堆垛机及上下料小车等；料小车等； 计算机控制及管理系统。计算机控制及管理系统。 与金属切削与金属切削FMSFMS相比，板材相比，板材FMSFMS具有以下特点具有以下特点： 零件的种类、批量及复杂程度存在较大差异；零件的种类、批量及复杂程度存在较大差异； 板料和零件的出入库等操作以托盘为单位，加工过程则以托盘板料和零件的出入库等操作以托盘为单位，加工过程则以托盘 上的单张板料或零件为单位；上的单张板料或零件为单位； 作业计划制定涉及零件混合排样问题，零件种类、排样方法及作业计划制定涉及零件混合排样问题，零件种类、排样方法及 调度策略等对机床的换模形式、换模时间以及调
9、度策略等对机床的换模形式、换模时间以及FMSFMS效率具有重效率具有重 要影响；要影响； 板材零件的加工工序较为简单和固定。从板料到零件需要只经板材零件的加工工序较为简单和固定。从板料到零件需要只经 过冲压、剪切和折弯等三道工序，有些零件则只需冲压和剪切过冲压、剪切和折弯等三道工序，有些零件则只需冲压和剪切 等两道工序。等两道工序。 从系统建模角度，将板材加工从系统建模角度，将板材加工FMSFMS中的活动分为三类中的活动分为三类： 以冲压和剪切为特征的冲剪操作； 冲剪后零件的折弯操作； 板料以及冲剪后零件的出入库操作。 采用采用PetriPetri网建模的基本步骤网建模的基本步骤： 划分和定义
10、系统内所有活动及其相互关系； 采用Petri网描述上述活动及其关系，得到系统Petri网模型 其中，其中，“ ”“ ”表示变迁，表示变迁，t t1 1t t1616为系统中的变迁为系统中的变迁 “ “ ” ”表示普通库所，表示普通库所，p p0 0p p2020为普通库所为普通库所 “ “ ” ”表示决策库所，表示决策库所，p pd0d0p pd7d7为决策库所为决策库所 Petri网是一种图形演绎方法，应用Petri网分析系统故障就是将系统所不希望发生的事件作为顶库所，逐步找出导致这一事件的所有可能因素作为中间库所和底库所。故障树可以看作是系统中故障传播的逻辑关系，一般的单调关联故障树只含有
11、与门和或门。故障树可以很方便地用Petri网表示，如与门采用多输入变迁代替，或门采用两个变迁代替。 案例案例3 Petri3 Petri网的应用案例网的应用案例 39与门或门故障树表示Petri网表示图2故障树的故障树的Petri网模型表示网模型表示 应用关联矩阵求割集应用关联矩阵求割集 在故障树分析中，当一些底事件同时发生时，顶事件必然发生，能使顶事件发生的这些底事件的集合就称为割集。 如果割集中的任一底事件不发生时，顶事件也不发生，则这样的割集称为最小割集。 关联矩阵是Petri网的主要分析方法之一。在表示Petri网结构的有向图中，库所以圆表示；变迁以矩形表示(图3)。若从库所P到变迁t
12、的输入函数取值为非负整数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的行，则该 行对应的为顶库所（只有输入库所，没有输出库所），由此库所开
13、始寻找（在此关联矩阵中为最后一行）。 (2)由顶库所对应行的1出发按列寻找到-1，此-1所对应行代表的库所为顶库所的一个输入库所，如果该列有多个-1，则说明对应同一变迁有多个输入库所，并且输入的库所为“相与”关系。割集求解步骤割集求解步骤 (3)由步骤（2）中找到的-1按行寻找1，如有1 则说明该库所为中间库所，继续按步骤（2）所述循环查找，直到所在行没有1为止。没有1，则说明该库所是一个底库所即基本事件。如果该行有多个1，则说明由这些1对应的库所对应多个变迁，应为“ 相或”关系。 (4)按步骤（2）、步骤（3）继续查找，直到查找到最底层库所。 (5)按照上面的“相与”“相或”关系将底 库所展
14、开,则得到所有割集。 (6)按照布尔吸收律、等幂率或素数法可求得最小割集。 注：布尔吸收律A+AB=A A(A+B)=A 四、四、PetriPetri网的行为特网的行为特性性 与其它建模方法相比，与其它建模方法相比，PetriPetri网的优点不仅表现在建模能力上，网的优点不仅表现在建模能力上，更主要表现在它所具有的分析能力上。更主要表现在它所具有的分析能力上。 顺序关系顺序关系并发关系并发关系 1 可达性可达性 是研究任何系统动态特性的基础,决定系统能否到达一个指定的状态. (1)系统按照一定的流程运行，系统是否能够实现一定的状态；或者不期望的状态不出现。 比如：生产调度计划的验证（按照一定
15、的生产调度计划进行生产，一定的生产任务是否能够完成）（2）要求到达一定的状态，如何确定系统的运行轨迹（流程）。比如：生产调度，如何安排作业顺序？ 死锁关系死锁关系 2 活性活性 在系统中用于检测是否存在死锁。一个系统存在的一个潜在问题是死锁，为了避免死锁， 系统的Petri网模型必须具有活性。 （1）互斥：同时争夺唯一资源 （2）占用且等待 （3）无抢占 （4）循环等待 冲突的实质是竞争资源。 冲突就是指这种两者都有发生权，但在同一时刻只能有一个发 生的关系。 冲突双方谁先发生由系统实际运行环境及状态决定，即谁有优 先权是不确定的。冲突又称为选择（choice）或不确定（nondetermin
16、ism），是对系统性能影响最大的事件类型。 3 有界性有界性 是一个非常重要的特性是一个非常重要的特性, ,它保证系统在运行它保证系统在运行过程中不会需要过程中不会需要无限的资源无限的资源. . 有界性反映有界性反映一个库一个库所在系统运行过程中能所在系统运行过程中能够获得的最大的令牌数够获得的最大的令牌数, ,即所能获得的即所能获得的最大最大资源数资源数, ,它与系统的初始令牌有关它与系统的初始令牌有关. . 在实际系统设计中,必须使网络中的每个库所在任何状态下的令牌数小于库所的容量,这样才能保证系统的正常运行。 4 安全性安全性 （是否会溢出）（是否会溢出） 决定系统中正在执行的操作不会发
17、出请求.若Petri网为1有界,则称此Petri网是安全的.这种网的每一个库所 要么有一个令牌，要么 没有令牌。安全性是有 界性的一种特殊情况 。 5 可逆性和回家状态（主宿状态）可逆性和回家状态（主宿状态） 在制造业系统和过程控制系统中存在着一个重要的问题：错误复原，即系统能否重新回到原来状态(保证系统的循环特性)。 6 守恒性守恒性 在一个Petri网系统中,令牌被用来描述系统资源,对这类Petri网,守恒性是一个重要性质,要使代表资源的令牌在Petri网运行中既不会增加也不会减少,最简单的方法就是网中总令牌数保持恒定。 基本逻辑关系表达：顺序、并发、冲突、异或、死基本逻辑关系表达：顺序、
18、并发、冲突、异或、死锁锁事例与进程，进程的合成事例与进程，进程的合成顺序顺序并发并发 异或异或冲突冲突 死锁死锁 PetriPetri网性能分析网性能分析 覆盖树（Coverability tree）可达图 不变量（Invariation） 覆盖树性能分析法覆盖树性能分析法 1、标识向量m 初始标识m0=(1 1 0 0 0)T 标识m1=(0 0 1 0 0) T m2=(0 0 0 1 1) T kkktokenmmmm),(m)(mp121212；都有：对于任意正数（令牌，托肯）概念。，表示无穷大的再引入一个特别符号。表示为覆盖则标识：若ppP覆盖的数学定义覆盖的数学定义 1、m0作为作
19、为“树根树根”（可作上（可作上new记号）记号）2、对有、对有new记号的标识记号的标识m做以下事情，否则终止；做以下事情，否则终止；3、选择某一、选择某一“new”标识标识m；（1）若）若m与树中间已有的其他标识与树中间已有的其他标识m相同，则将其记为相同，则将其记为“old”，转向其，转向其他他“new”标识；标识；（2）若在）若在m下无变迁使能，则将下无变迁使能，则将m记为记为“dead end”；4、对于、对于m下有使能的所有变迁下有使能的所有变迁t，做以下事情：，做以下事情：（1）激发）激发t，产生标识，产生标识m；（2）若从树根至）若从树根至m的路径上存在一标识的路径上存在一标识m
20、,使得使得m覆盖覆盖m，但，但m 不等不等于于m（mm）,则对于那些使则对于那些使m(p)m(p)成立的成立的p：用：用取代取代m(p);（3）以）以m为一节点，从为一节点，从m到到m画一有向线，将其记为画一有向线，将其记为t，并将，并将m记为记为“new”5、除去、除去m的的“new”标志，回到步骤标志，回到步骤2 当且仅当树中所有节点上均不出现时，PN网是有界的；（可以在树中找出所有库所中最大的托肯数K，称为PN是K有界的） 当且仅当树中所有的节点上仅包含0或1时，则PN网是安全的。否则没有记为的库所是安全的。 在不包含的树中，若给定任何2个节点之间，都存在一有向路径，在该路径上所有变迁都
21、出现，则PN是活的。(包含的树无法确定活性) 在不包含的树中，若从任何节点到根节点之间都存在一有向路径，则PN是可逆的。(包含的树无法确定活性)基本性能分析基本性能分析 基本Petri网：每个库所容量为1，这样库所可称为条件，变迁可称为事件。故又称为条件/事件系统 C/E 低级Petri网：库所容量和权重为=1的任意整数，称为库所/变迁网。简作P/T网 定时Petri网：将各事件的持续时长标在库所旁边，库所中新产生的标记经过一须时间后才加入到网中，或是标在变迁上，经过时间延迟后发生。 高级Petri网：谓词/事件网、染色网、随机网等。PetriPetri网类型网类型 PetriPetri网模型
22、特点网模型特点模拟性：从组织结构的角度，模拟系统的控制和管理，不涉及系统实现所依赖的物理和化学原理；客观性：精确描述事件（变迁）间的依赖（顺序）关系和不依赖（并发）关系。这种关系客观存在，与观察无关；描述性：用统一的语言（网）描述系统结构和系统行为； 流特征：适合描述以有规则的流动为行为特征的系统，包括能量流、物质流和信息流；分析性：网系统具有与应用环境无关的动态行为，是可以独立研究的对象。这样，可按特定方式进行系统性质的分析和验证；基础性：网系统在各个应用领域得到不同的解释，是沟通不同领域的桥梁。网论是这些领域的共同理论基础。 petripetri网的应用领域网的应用领域 (1)通讯协议的验
23、证 通讯协议的验证是Petri网应用最为成功的领域之一最初应用在70年代初期，由于 Petri网以形式语言作为基础，可形式化地 对通信协议进行正确性验证。 (2)计算机通讯网络性能评价及多媒体应用 随着计算机网络技术和信息技术的发展，对网络进行性能分析的需要，不仅出现于企业内部的生产控制的局域总线网，而且出现于光纤局域网或ATM网中。 (3)软件工程 由于产品开发中的竞争和革新需要，导致产品开发者面临巨大压力.在软件工程中Petri网主要用于软件系统的建模和分析，比较成熟的是加色Petri网，可以用于大型软件系统的设计、说明、仿真、确认和实现，在软件开发生命周期的各个阶段，Petri网都可以得
24、到很好的应用。 (4)知识处理 Petri网可用于Al中的知识表达和推理的形式化模型的建立，可以表达各个活动之间的各种关系，如顺序关系、与关系、或关系等，并可在模型基础上通过已知的初始状态和初始条件进行逻辑推理。 (5)FMS的建模、分析和控制 柔性制造系统(FMS)对于现代制造业具有重要作用，Petri网由于其自身优点，在制造系统中应用广泛，如带缓冲区的简单生产线、机床加工中心、自动生产线、柔性制造系统和及时加工系统。 (6)系统可靠性分析 系统的可靠性不仅包括硬件的可靠性、也包括软件可靠性.利用随机Petri网对系统进行可靠性分析，对软件复用、软件可靠性分析。 建模：结构健壮性 逻辑合理性编程流程图Petri net，活动周期法等仿真：系统重现 效果优化JAVA ,C#,C+UG，CAD动态效果Arena，flexsim等