Ingeniería en SoftwareMatemáticas Discretas Alumno: Paul Vega Rodríguez Facilitador: Luis Miguel Venegas Hernández Redes de Petri Modelo de Redes • • • • • • • • • • • REDES DE PETRI Definición Historia Estructuras básicas Ventajas Desventajas Aplicaciones Propiedades Subclases Métodos de análisis Conclusiones Bibliografía Las redes de Petri son representaciones graficas que permiten modelar sistemas con flujo de información, mostrando la información importante sobre su estructura y comportamiento dinámico. Pueden considerarse como generadores de lenguaje o autómatas formales asociados a la teoría de grafos. Por sus características, son de gran utilidad para el diseño, especificación y simulación de sistemas de hardware o software; permiten representar procesos concurrentes y modelamiento matemático del sistema. DEFINICION en Alemania. notación y representación de las Redes de Petri. en el artículo titulado "Events and Conditions". El trabajo del proyecto “Systemics” proporcionó la teoría primaria. Holt y Commoner muestran como las Redes de Petri pueden aplicarse al modelado y análisis de sistemas con componentes concurrentes. publicado en 1970. existe gran difusión de los avances en Redes de Petri y prácticamente existe una sola corriente entre los investigadores . Petri formuló la base para una teoría de comunicación entre componentes asíncronos de un sistema de cómputo. En la actualidad. Posteriormente.HISTORIA Surgen en 1962 con el trabajo doctoral de Carl Adam Petri "Kommunikation mit Automaten" (Comunicación con autómatas). Contienen arcos o flechas y marcas o Tokens que se ubican en las plazas o lugares de la red y definen su ejecución. .Estructuras Básicas Las redes de Petri tienen dos tipos de nodos: lugares (representados mediante circunferencias) y transiciones (representados por segmentos rectos verticales). dicha transición se considera sensibilizada. Por otra parte. La transición estará validada cuando ocurra un evento relacionado con esta. Los componentes se pueden relacionar de múltiples formas. tanto los lugares como las transiciones pueden ser origen y destino de varias transiciones o lugares. cuando todos los lugares de una transición están marcados. Cada lugar tiene asociada una acción o salida y los que contienen marcas se consideran lugares activos. Proporcionan un modelamiento más exacto que los diagramas de estados para problemas complejos. .VENTAJAS Facilidad de interpretación del sistema pues el esquema es gráfico e ilustrativo. Permiten modelar procesos concurrentes. Se pueden sintetizar de forma bottom-up o topdown. Permiten modelar sistemas donde un recurso es compartido por dos procesos diferentes. Permiten tratar procesos independientes de forma individual. Para un mayor alcance en el modelamiento. Pueden presentarse problemas de análisis de acuerdo a la complejidad del sistema modelado. Existen muchas subclases del modelo general de redes de Petri generadas para diferentes problemas específicos. .DESVENTAJAS Las redes de Petri generales no pueden modelar ciertas situaciones de prioridad. el tiempo y el consumo de espacio aumentan considerablemente. que permiten modelar ambientes industriales de producción.APLICACIONES Modelamiento de sistemas o aplicaciones que se ejecutan en tiempo real. . Hardware y Software de computadores Redes de libre elección. Diagramas de Flujo de Datos (DFD) Protocolos de Comunicación Bases de Datos. Sistemas operativos y compiladores. .REDES DE PETRI: PROPIEDADES Las propiedades de las redes de Petri nos permiten detectar fenómenos de interés o errores de funcionamiento en el sistema que modelan. CUALES SON SUS PROPIEDADES • • • • • • Vivacidad Ciclicidad Limitación Conservación Conflictividad Exclusión mutua . Una RdP marcada es viva si cada una de sus transiciones es viva. .VIVACIDAD La propiedad de vivacidad es muy importante porque sirve para caracterizar el bloqueo total o parcial de un sistema. .CICLICIDAD Una RdP para un marcado inicial M0 se dice que posee un comportamiento globalmente cíclico. si existe una secuencia de disparos que permite alcanzar el marcado inicial M0 a partir de cualquier marcado Mi sucesor de M0. Desde un punto de vista práctico.LIMITACIÓN El interés de la limitación de una red es que garantiza la finitud de sus marcados alcanzables. . una red k-limitada puede implementarse con un conjunto de recursos finitos. que no puede variar durante la ejecución de la red de Petri. . Sin embargo.CONSERVACION El concepto de conservación está relacionado con el número de recursos disponibles. La manera más simple de conseguirlo es requerir que el número total de testigos en la red permanezca constante. la conservación estricta es una relación muy fuerte y normalmente conviene hablar de conservación con respecto a un vector peso. CONFLICTIVIDAD Se dice que en una RdP existe un conflicto estructural cuando un lugar posee más de una transición de salida. Si al dispararse ti (tj) el marcado que se obtiene no habilita a tj (ti). Se dice que dos transiciones ti y tj están en conflicto efectivo para M0 si: Existe un marcado alcanzable desde M0 que sensibiliza simultáneamente a ti y tj. . Se dice que dos plazas de una red de Petri están en exclusión mutua para un marcado M0 si no pueden estar marcadas simultáneamente en los marcados alcanzables a partir de M0. . se deshabilitan. i j.EXCLUSIÓN MUTUA Un conjunto de transiciones Te T se dice que son mutuamente exclusivas si el disparo de cualquier transición ti Te genera un marcado en el cual todas las demás transiciones tj Te. a pesar de basarse en unas reglas bastante simples. se puedan utilizar procedimientos de análisis simples. y se han estudiado sus propiedades. al menos para los problemas de interés. Como consecuencia.REDES DE PETRI: SUBCLASES Las redes de Petri. El objetivo que se persigue al definir una subclase de red de Petri es que pueda modelar una gran variedad de sistemas y que. pueden exhibir comportamientos muy complicados. se han introducido clases restringidas de redes de Petri. que son más fáciles de analizar. . SUBCLASES DE REDES DE PETRI • Grafos de estados (GE) o máquinas de estados (ME) • Grafo marcado (GM) o grafo de sincronización • Red de libre elección (RLE) • Red de Petri simple (RS) . Puede representar conflictos o alternativas.GE O ME • Son RdP en las que cada transición ha de tener exactamente una entrada y una salida. . Una máquina de estados es estrictamente conservativa y muy sencilla de analizar. pero tiene un interés muy limitado debido a su escasa potencia de modelado. concurrencia ni sincronización. pero no paralelismo. GM • Es una RdP en la que cada plaza tiene exactamente una entrada y una salida. pero no conflicto o decisiones dependientes de datos. concurrencia y sincronización. . Los grafos marcados pueden representar paralelismo. pero de una manera más restringida que en el modelo general. es la única entrada de estas transiciones. Esta subclase permite el modelado de concurrencia y conflicto. o bien todas estas transiciones conflictivas están simultáneamente habilitadas o ninguna de ellas lo está. si una plaza es la entrada de varias transiciones (conflicto potencial).RLE Es aquella en la que cada plaza p es o bien la única plaza de entrada de una transición o hay como mucho una transición que tiene p como una plaza de entrada. Por tanto. Según la definición de las redes de Petri libres de elección. . RS Es aquella en la que cada transición tiene como máximo una plaza de entrada compartida con otra transición. . .MÉTODOS DE ANÁLISIS Las basadas en el árbol de alcanzabilidad Las basadas en las ecuaciones matriciales o de estado. La principal desventaja es que el árbol de alcanzabilidad puede hacerse complejo. para verificar la corrección de un diseño. grande e inmanejable. para elegir la mejor entre varias propuestas o para predecir el comportamiento del sistema. El análisis del árbol de alcanzabilidad se puede utilizar para determinar si la red de Petri es una representación válida del sistema modelado.ANÁLISIS A PARTIR DEL ÁRBOL DE ALCANZABILIDAD Analizando el árbol de alcanzabilidad se puede obtener una información detallada del comportamiento del sistema modelado. . Sólo informa de qué transiciones se disparan y cuántas veces. no refleja totalmente la estructura de la red.ANÁLISIS MATRICIAL DE UNA RED DE PETRI El análisis de las redes de Petri mediante técnicas matriciales es muy prometedor. por sí sola. . La matriz C. pero presenta también severos problemas. El vector de disparo no da información sobre el orden en que se lleva a cabo el disparo de las transiciones. puede ocurrir que la solución encontrada no se corresponda con ninguna secuencia de disparos permitida. . para que el marcado sea alcanzable.Además. pero no suficiente. el que exista solución para la ecuación M’=M +f(σ ) • C es una condición necesaria. MODELO DE REDES • • • • DEFINICION CONCEPTOS BÁSICOS TIPOS DE MODELOS DE REDES MODELO DE RUTA MAS CORTA (MRC) EJEMPLO • MODELO DE ÁRBOL DE EXPANSIÓN MÍNIMA (AEM) EJEMPLO • MODELO DE RED DE FLUJO MÁXIMO EJEMPLO • MODELO GENERALDE FLUJO DE COSTO MINIMO EJEMPLO CONCLUSIONES BIBLIOGRAFIA . redes eléctricas o de comunicación. en marketing. .DEFINICIÓN • Los modelos de administración de redes se aplican a numerosos casos de la ciencia de a administración. recursos humanos y finanzas. en particular relacionados con la optimización de redes de transporte. logística. pero también en programación y seguimiento de procesos. CONCEPTOS BÁSICOS Arista Nodo Capacidad Sumidero (z) Fuente (a) Red . .ARISTA Segmento de recta dirigido de un punto a otro. NODO Es el punto de intersección de dos o más aristas. . es la capacidad máxima de una arista cualquiera.CAPACIDAD En una red. . SUMIDERO (Z) Es el punto de llegada del flujo total de una red. . FUENTE Punto de partida del flujo total de la red. . un sumidero. . aristas y nodos.RED Es un grafo dirigido formado por una fuente. la trayectoria con la minima distancia total. es decir. El objetivo del analisis es encontrar la ruta mas corta.MODELO DE RUTA MAS CORTA (RMC) Los problemas de la ruta RMC se considera una red conexa y no dirigida con 2 nodos especiales. . A cada una de las ligaduras (arcos no dirigidos) se asocia una distancia no negativa. llamados origen y destino. que va del origen al destino. EJEMPLO RCM . simplemente este proceso se repite hasta que se hayan conectado todos los nodos. La resolución de este problema consiste en elegir. Se trata de crear un árbol de expansión.). etc. . costo. problema útil en la planeación de redes de transporte que no se transitaran mucho y en las que la inquietud principal es proporcionar alguna trayectoria entre todos los pares de nodos de la manera mas económica.MODELO DE ÁRBOL DE EXPANSIÓN MÍNIMA (AEM) Los problemas de AEM se considera una red conexa y no dirigida. desde cualquier nodo la rama mas corta posible a otro nodo. Cada ligadura esta unida a una medida de longitud positiva (distancia. EJEMPLO AEM . teniendo en cuanta las capacidades máximas por unidad de tiempo de cada tramo. .MODELO DE RED DE FLUJO MÁXIMO Su objetivo es maximizar el flujo por unidad de tiempo entre el nodo origen y el destino. • El Flujo Total Es 14 . .MODELO GENERALDE FLUJO DE COSTO MINIMO • El objetivo del modelo es minimizar el costo total de transportar los recursos disponibles en los nodos de origen a través de la red para abastecer la demanda en los nodos de tipo destino. Ejemplo Flujo de Costo Mínimo . en el modelado de sistemas complejos. A pesar de la gran cantidad de publicaciones existentes. su divulgación en el ámbito es muy limitada. . Este trabajo permite generar conciencia en el lector sobre el impacto de las mismas en el diseño e implementación de algoritmos de control para controladores lógicos programables.CONCLUSIONES Las RDP han demostrado desde hace mas de 45 anos su utilidad practica en muchas áreas y en especial. shtml http://webdiis.monografias.uhu.es/diego.mx/~fmorales/Sis DisII/aRedesPetri01.com/ma/enwiki/es/Petr i_net .lopez/AI/auto_trans -tema3.worldlingo.com/trabajos14/red esdepetri/redesdepetri.pdf http://www.itmorelia.BIBLIOGRAFÍA http://antares.PDF http://www.p df http://www.unizar.es/~joseluis/TPN&RT.edu. su divulgación en el ámbito es muy limitada. A pesar de la gran cantidad de publicaciones existentes. Este trabajo permite generar conciencia en el lector sobre el impacto de las mismas en el diseño e implementación de algoritmos de control para controladores lógicos programables. en el modelado de sistemas complejos. .CONCLUSIONES Las RDP han demostrado desde hace mas de 45 anos su utilidad practica en muchas áreas y en especial. itmorelia.unizar.p df http://www.mx/~fmorales/Sis DisII/aRedesPetri01.com/trabajos14/red esdepetri/redesdepetri.es/~joseluis/TPN&RT.worldlingo.PDF http://www.uhu.es/diego.BIBLIOGRAFÍA http://antares.lopez/AI/auto_trans -tema3.edu.monografias.com/ma/enwiki/es/Petr i_net .shtml http://webdiis.pdf http://www.