Redes De Petri

Transcript

Ingeniería en Software Matemáticas Discretas Alumno: Paul Vega Rodríguez Facilitador: Luis Miguel Mig uel Venegas Hernández Redes de Petri Modelo de Redes 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 DEFINICION de Petri son Las redes 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. HISTORIA Surgen en 1962 con el trabajo doctoral de Carl Adam Petri "Kommunikation mit Automaten" (Comunicación con autómatas), en Alemania. Petri formuló la base para una teoría de comunicación entre componentes asíncronos de un sistema de cómputo. El trabajo del proyecto “Systemics” proporcionó la teoría primaria, notación y representación de las Redes de Petri. Posteriormente, en el artículo titulado "Events and Conditions", publicado en 1970, Holt y Commoner muestran como las Redes de Petri pueden aplicarse al modelado y análisis de sistemas con componentes concurrentes. En la actualidad, existe gran difusión de los avances en Redes de Petri y prácticamente existe una sola corriente entre los investigadores Estructuras Básicas Las redes de Petri tienen dos tipos de nodos: lugares (representados mediante circunferencias) y transiciones (representados por segmentos rectos verticales). Contienen arcos o flechas y marcas o Tokens que se ubican en las plazas o lugares de la red y definen su ejecución. 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. Cada lugar tiene asociada una acción o salida y los que contienen marcas se consideran lugares activos. Por otra parte, cuando todos los lugares de una transición están marcados, dicha transición se considera sensibilizada. La transición estará validada cuando ocurra un evento relacionado con esta. VENTAJAS Facilidad de interpretación del sistema pues el esquema es gráfico e ilustrativo. Permiten tratar procesos independientes de forma individual. Proporcionan un modelamiento más exacto que los diagramas de estados para problemas complejos. Permiten modelar sistemas donde un recurso es compartido por dos procesos diferentes. Se pueden sintetizar de forma bottom-up o topdown. Permiten modelar procesos concurrentes. DESVENTAJAS Las redes de Petri generales no pueden modelar  ciertas situaciones de prioridad. Pueden presentarse problemas de análisis de acuerdo a la complejidad del sistema modelado. Para un mayor alcance en el modelamiento, el tiempo y el consumo de espacio aumentan considerablemente. Existen muchas subclases del modelo general de redes de Petri generadas para diferentes problemas específicos. APLICACIONES Modelamiento de sistemas o aplicaciones que se ejecutan en tiempo real. Sistemas operativos y compiladores. Hardware y Software de computadores Redes de libre elección, que permiten modelar  ambientes industriales de producción. Diagramas de Flujo de Datos (DFD) Protocolos de Comunicación Bases de Datos. 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 VIVACIDAD La propiedad de vivacidad es muy importante porque sirve para caracterizar el bloqueo total o parcial de un sistema. Una RdP marcada es viva si cada una de sus transiciones es viva. 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. LIMITACIÓN El interés de la limitación de una red es que garantiza la finitud de sus marcados alcanzables. Desde un punto de vista práctico, una red k-limitada puede implementarse con un conjunto de recursos finitos. CONSERVACION El concepto de conservación está relacionado con el número de recursos disponibles, que no puede variar durante la ejecución de la red de Petri. La manera más simple de conseguirlo es requerir que el número total de testigos en la red permanezca constante. Sin embargo, 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. 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. Si al dispararse ti (tj) el marcado que se obtiene no habilita a tj (ti). 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, i j, se deshabilitan. 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. REDES DE PETRI: SUBCLASES Las redes de Petri, a pesar de basarse en unas reglas bastante simples, pueden exhibir comportamientos muy complicados. Como consecuencia, se han introducido clases restringidas de redes de Petri, que son más fáciles de analizar, y se han estudiado sus propiedades. El objetivo que se persigue al definir una subclase de red de Petri es que pueda modelar una gran variedad de sistemas y que, al menos para los problemas de interés, se puedan utilizar procedimientos de análisis simples. 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) 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. Puede representar conflictos o alternativas, pero no paralelismo, concurrencia ni sincronización. GM • Es una RdP en la que cada plaza tiene exactamente una entrada y una salida. Los grafos marcados pueden representar  paralelismo, concurrencia y sincronización, pero no conflicto o decisiones dependientes de datos. 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. Esta subclase permite el modelado de concurrencia y conflicto, pero de una manera más restringida que en el modelo general. Según la definición de las redes de Petri libres de elección, si una plaza es la entrada de varias transiciones (conflicto potencial), es la única entrada de estas transiciones. Por tanto, o bien todas estas transiciones conflictivas están simultáneamente habilitadas o ninguna de ellas lo está. 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. 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. 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, para verificar la corrección de un diseño, para elegir la mejor entre varias propuestas o para predecir el comportamiento del sistema. La principal desventaja es que el árbol de alcanzabilidad puede hacerse complejo, grande e inmanejable. ANÁLISIS MATRICIAL DE UNA RED DE PETRI El análisis de las redes de Petri mediante técnicas matriciales es muy prometedor, pero presenta también severos problemas. La matriz C, por sí sola, no refleja totalmente la estructura de la red. El vector de disparo no da información sobre el orden en que se lleva a cabo el disparo de las transiciones. Sólo informa de qué transiciones se disparan y cuántas veces.  Además, el que exista solución para la ecuación M’=M +f(σ ) • C es una condición necesaria, pero no suficiente, para que el marcado sea alcanzable; puede ocurrir que la solución encontrada no se corresponda con ninguna secuencia de disparos permitida. 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 DEFINICIÓN • Los modelos de administración de redes se aplican a numerosos casos de la ciencia de a administración, en particular  relacionados con la optimización de redes de transporte, logística, redes eléctricas o de comunicación, pero también en programación y seguimiento de procesos, en marketing, recursos humanos y finanzas. 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. CAPACIDAD En una red, es la capacidad máxima de una arista cualquiera. SUMIDERO (Z) Es el punto de llegada del flujo total de una red. FUENTE Punto de partida del flujo total de la red. RED Es un grafo dirigido formado por una fuente, un sumidero, aristas y nodos. MODELO DE RUTA MAS CORTA (RMC) Los problemas de la ruta RMC se considera una red conexa y no dirigida con 2 nodos especiales, llamados origen y destino. A cada una de las ligaduras (arcos no dirigidos) se asocia una distancia no negativa. El objetivo del analisis es encontrar la ruta mas corta, es decir, la trayectoria con la minima distancia total, que va del origen al destino. EJEMPLO RCM MODELO DE ÁRBOL DE EXPANSIÓN MÍNIMA (AEM) Los problemas de AEM se considera una red conexa y no dirigida. Cada ligadura esta unida a una medida de longitud positiva (distancia, costo, etc.). Se trata de crear un árbol de expansión, 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. La resolución de este problema consiste en elegir, desde cualquier nodo la rama mas corta posible a otro nodo, simplemente este proceso se repite hasta que se hayan conectado todos los nodos. EJEMPLO AEM MODELO DE RED DE FLUJO MÁXIMO Su objetivo es maximizar el flujo por unidad de tiempo entre el nodo origen y el destino, teniendo en cuanta las capacidades máximas por unidad de tiempo de cada tramo. • 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 CONCLUSIONES Las RDP han demostrado desde hace mas de 45 anos su utilidad practica en muchas áreas y en especial, 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. BIBLIOGRAFÍA http://antares.itmorelia.edu.mx/~fmorales/Sis DisII/aRedesPetri01.pdf  http://www.uhu.es/diego.lopez/AI/auto_trans -tema3.PDF http://www.monografias.com/trabajos14/red esdepetri/redesdepetri.shtml http://webdiis.unizar.es/~joseluis/TPN&RT.p df  http://www.worldlingo.com/ma/enwiki/es/Petr  i_net CONCLUSIONES Las RDP han demostrado desde hace mas de 45 anos su utilidad practica en muchas áreas y en especial, 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.