Redes de Petri

Índice

Índice de figuras………………………………..3

Justificación…………………………………….4

Introducción……………………………………4

Marco teórico…………………………………..6

Modelo de redes………………………..6

Red de transporte……………………….7

Flujo máximo……………………………9

Acoplamiento Redes de Petri……………11

Redes de Petri…………………………...12

Grafo de la Red de Petri………………….14

Aplicación……………………………………….15

Conclusión………………………………………19

Referencias……………………..……………….19

Índice de figuras

Fig. 1…………………………………………...7

Fig. 2………………………………………..…8

Fig. 3…………………………………………...9

Fig. 4……………………………………………9

Fig. 5…………………………………………..12

Fig. 6 ………………………………………….14

Fig.7 …………………………………………...15

Fig.8…………………………………………….16

Fig. 9 …………………………………………....17

Fig.10 ……………………………………………18

Fig. 11…………………………………………….18

Fig. 12……………………………………………..18

Justificación

Investigar el origen y aplicación de las redes de Petri, dando a conocer el impacto que puede tener, destacando que este modelo matemático tiene una amplia aplicación abarcando desde la humanidad, industria, en la programación, etc. , por mencionar algunos, desde lo más sencillo hasta lo más complejo; mencionando la importancia de su aplicación, ya que permite agilizar procesos, y optimizar tiempos.

Introducción

Las Redes de Petri surgen en 1962 con el trabajo doctoral de Carl Adam Petri "Kommunikation mit Automaten" (Comunicación con autómatas), en lemania. En su disertación doctoral Petri formuló la base para una teoría de comunicación entre componentes asíncronos de un sistema de cómputo. Las ideas de Petri atrajeron la atención de un grupo de investigadores del Applied Data Research Inc. Dirigido por Anatol Holt y que trabajaban en el proyecto "Information System Theory Project". El grupo, desarrolló la teoría del proyecto conocido como “Systemics”. Este trabajo fue el que proporcionó la teoría primaria, notación y representación de las Redes de Petri.

La teoría de Redes de Petri fue divulgada en 1968 en el reporte final del proyecto "Systemics". 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. El trabajo de Petri, también atrajo la atención del grupo "The Computation Structures Group", bajo la dirección de Jack Dennis, que trabajaban en un proyecto llamado "Project MAC" en el MIT. Este grupo, ha sido una fuente productiva de investigaciones y literatura, publicando varias tesis doctórales, numerosos reportes y memoranda sobre Redes de Petri. Instituto Tecnológico de Morelia Departamento de Sistemas y Computación Redes de Petri como un modelo de especificación formal Carl Adam Petri extendió su teoría original, para incluir conceptos básicos de flujo de información y de la estructura de sistemas concurrentes, estimulando investigaciones en diversos centros de Investigación europeos, particularmente en el "Institut Für Informationssystemforschung of the Gessellschaft Für Mathematik und Datenverarbeitung" en Bonn, Alemania.

Holt continuó con el desarrollo de nuevos conceptos a partir de su trabajo original en "Systemics", se concentró en el desarrollo de herramientas para la representación y análisis de sistemas. Su trabajo lo realizó principalmente en la investigación de aspectos fundamentales de concurrencia y conflicto en sistemas con múltiples partes. En el MIT y muchos otros centros de investigación Americanos, enfocaron inicialmente sus investigaciones sobre Redes de Petri hacia la teoría de autómatas. En la actualidad, existe gran difusión de los avances en Redes de Petri y prácticamente existe una sola corriente entre los investigadores Europeos y los Americanos, ya que la comunicación existente entre todos los grupos beneficia el conocimiento de los nuevos avances. Son Populares porque modelan de forma natural sincronización, eventos asíncronos, concurrencia, compartición de recursos, etc. Útiles en modelado y análisis de sistemas paralelos y concurrentes, de protocolos, evaluación de rendimiento y sistemas tolerantes a fallos. Constan de una multitud de variantes: coloreadas, con tiempo, orientadas a objetos, etc.

Marco Teórico

Modelo de Redes

Consideremos la gráfica mostrada, que representa una red de tuberías de petróleo: El petróleo se descarga en el muelle a y se bombea a través de la red hasta la refinería z.

Los vértices b, c, d y e representan estaciones de bombeo intermedias.

Las aristas dirigidas representan las subtuberías del sistema y muestran la dirección en que el petróleo puede fluir.

Las etiquetas sobre las aristas indican la capacidad de cada subtubería.

Fig.(1)

Red de Transporte

Una red de transporte (o más simple, una red) es una gráfica dirigida, simple, con pesos que satisface:

a) Un vértice fijo, la fuente denotada por a, no tiene aristas de entrada.

b) Un vértice fijo, el sumidero (o destino) denotada por z, no tiene aristas de salida.

c) El peso Cij de la arista dirigida (i, j), llamado la capacidad de (i, j), es un número no negativo.

Ejemplo:

La gráfica es una red de transporte. La fuente es el vértice a y el sumidero es el vértice z. La capacidad de la arista (a,b), Cab es 3, y la capacidad de la arista (b,c), Cbc es 2.

Fig.(2)

Flujo en una Red

Un Flujo en una red asigna un flujo de una arista dirigida que no excede la capacidad de dicha arista.

¿Qué es el Flujo Máximo?

Siendo G una red de trasporte, un flujo máximo es un flujo con valor máximo. En general, habrá varias flujos con el mismo valor máximo. La idea es sencilla: comenzar con cierto flujo inicial e incrementar de forma iterativa hasta que no pueda mejorarse más. El flujo resultante será el máximo. Para aumentar el valor de un flujo dado, debemos determinar un camino de la fuente al sumidero e incrementar el flujo a lo largo de ese camino.

Terminología

Se denotará a G como una red con fuente a, sumidero z y capacidad C. Las aristas se tomarán como no dirigidas, por el momento, y sea:

Fig.(3)

un camino de a a z de esta gráfica.

Si una arista e en P está dirigida de v i-1 ,a v,i, decimos que e está orientada en forma propia (con respecto a P), caso contrario, se dice que e está orientada en forma impropia (con respecto a P).

Fig.(4)

Algoritmo de Flujo Máximo

Si no existen caminos que satisfagan las condiciones del teorema recién mencionado, entonces el flujo es máximo. Así, es posible construir un algoritmo con base a dicho teorema. La idea se centra en:

*Iniciar con un flujo (por ejemplo, uno tal que el flujo en cada arista sea 0).

* Buscar un camino que satisfaga las condiciones del teorema del flujo máximo. Si no existe tal camino, se habrá terminado y el flujo es máximo.

*Se incrementa el flujo en ∆∆∆, donde ∆∆∆ se define como en el teorema, y se regresa al paso 2.

*En el algoritmo formal, se busca un camino que satisfaga las condiciones del teorema, a la vez que

...