REDES DE PETRI

Teoría de Redes de Petri

Autores:

Prog. Catalina Salvati

Prog. Leandro Cofre

Prog. Francisco Suárez

Base teórica del proyecto final de la carrera de Lic. en Sistemas

Universidad FASTA Bariloche

Índice

INTRODUCCIÓN 1

CONTENIDO 2

DEFINICIONES 3

DEFINICIÓN FORMAL 3

REPRESENTACIÓN 4

REPRESENTACIÓN GRÁFICA 4

REPRESENTACIÓN MATRICIAL 5

EJEMPLO 1 5

MARCADO 7

EVOLUCIÓN DE MARCADO 7

SUBCLASES DE REDES DE PETRI 8

GRAFO DE ESTADOS 8

GRAFO MARCADO 8

RED DE LIBRE ELECCIÓN 8

RED SIMPLE 8

ESTRUCTURAS BÁSICAS 9

SELECCIÓN 9

ATRIBUCIÓN 9

DISTRIBUCIÓN 9

CONJUNCIÓN 10

EJECUCIÓN SECUENCIAL 10

SINCRONIZACIÓN 10

CONCURRENCIA 11

CONFLICTOS 11

PROPIEDADES 12

PROPIEDADES ESTRUCTURALES 12

RDP PURA 12

RED DE PETRI ACOTADA ESTRUCTURALMENTE 12

RED DE PETRI ESTRUCTURALMENTE VIVA 12

RED DE PETRI COMPLETAMENTE CONTROLABLE 12

RED DE PETRI ESTRUCTURALMENTE CONSERVATIVA 12

RED DE PETRI (PARCIALMENTE) REPETITIVA 12

RED DE PETRI (PARCIALMENTE) CONSISTENTE 12

PROPIEDADES DE COMPORTAMIENTO 13

VIVACIDAD 13

CICLICIDAD 14

ACOTAMIENTO 15

CONSERVATIVIDAD 16

ALCANZABILIDAD 16

EXTENSIONES 18

RECURSOS COMPARTIDOS 18

ARCOS INHIBIDORES: 18

VALIDACIÓN 19

MÉTODOS DE ANÁLISIS 19

TÉCNICAS ENUMERATIVAS 19

TÉCNICAS DE TRANSFORMACIÓN 20

TÉCNICAS ESTRUCTURALES 21

TIPOS DE RED 23

RDP CON PESO 23

RDP CON TIEMPO 23

RDP COLOREADAS 23

RDP JERÁRQUICAS 24

ESTOCÁSTICAS (CONCEPTOS REDES PETRI.PDF) 24

REDES DE PETRI ESTOCÁSTICAS GENERALIZADAS 25

EJERCICIOS 26

EJERCICIO Nº 1: 26

EJERCICIO Nº 2: 26

EJERCICIO Nº 3: 27

¿CÓMO MODELARÍA LA SITUACIÓN DE QUE CUANDO NO HAY MÁS BEBIDAS LA MÁQUINA RETORNE LA MONEDA? 27

EJERCICIO Nº 4: 27

EJERCICIO Nº 5: 27

EJERCICIO Nº 6: 28

EJERCICIO 7 28

EJERCICIO 8 28

RESPUESTAS A LOS EJERCICIOS 29

EJERCICIO 1 29

EJERCICIO 2 29

EJERCICIO 3 30

EJERCICIO 4 30

EJERCICIO 5 31

EJERCICIO 6 31

EJERCICIO 7 31

EJERCICIO 8 32

GLOSARIO 33

CONJUNTOS 33

LÓGICA 33

ÍNDICE DE IMÁGENES 34

BIBLIOGRAFÍA 35

Introducción

Las Redes de Petri (RdP) son una teoría matemática postulada por el alemán Carl Adam Petri que proporciona una herramienta gráfica y matemática de modelado para la descripción formal de sistemas cuya dinámica se caracteriza por la concurrencia, sincronización, exclusión mutua y conflictos, las cuales son características típicas de sistemas distribuidos.

La principal aplicación de las redes de Petri es el modelado y el análisis de sistemas con componentes concurrentes que interactúan. Un modelo es una representación de las características más importantes de un sistema de estudio. Manipulando esta representación, se pueden obtener nuevos conocimientos del sistema modelado sin ningún coste o peligro para el sistema real. Sin embargo, el modelado por sí solo sirve de poco, es necesario analizar el sistema modelado.

El sistema se modela primero como una RdP y después, este modelo se analiza. Este análisis nos lleva a una mejor comprensión del comportamiento del sistema modelado. Para realizar el análisis de las propiedades de una red de Petri se han desarrollado diferentes técnicas, que permiten la verificación de las propiedades que el sistema construido posea.

Las RdP se han utilizado en distintas áreas de aplicación como en química, redes informáticas, Inteligencia artificial, tránsito, etc.

Contenido

En este documento, introduciremos los fundamentos de la teoría de redes de Petri.

En la primer parte daremos las definiciones básicas de RdP y los modos de representación.

Luego daremos algunos ejemplos de estructuras básicas que describen el modo de representar algunos casos comunes.

Seguiremos con las propiedades, extensiones y métodos de análisis.

Finalizando luego con una serie de ejercicios para resolver.

Definiciones

Una RdP está formada por lugares y transiciones, unidos alternativamente por arcos dirigidos. Un lugar puede o no contener marcas. El conjunto de marcas asociadas a cada uno de los lugares en un momento dado, constituye un marcado de la RdP. Para la descripción funcional de sistemas concurrentes los marcados representan estados y las transiciones sucesos, que dependen del cumplimiento de determinadas condiciones.

Definición formal

Podemos definir a una red de Petri como una 5-upla:

RdP = (P, T, F, W, M0), donde:

P = {p1, p2, … pm} es un conjunto finito no vacío de lugares

T = {t1, t2, …, tn} es un conjunto finito no vacío de transiciones

P  T = 

F  (P X T) U (T X P) es un conjunto de arcos dirigidos

W: F{1,2,3,…} es una función de pesos

Mi: P{0,1,2,…} es el marcado inicial de la red // define un número inicial de marcas por lugar

Representación

Toda herramienta de modelado tiene una o mas formas de ser representada. En el caso de las RdP, podemos

...