Estructuras Discretas

Tema: Modelos de Redes y Redes de Petrí

Introducción

En el presente trabajo se explicara el Modelo de Redes aplicado específicamente a problemas de trasporte y la maximización de flujos mediante el mismo; se tratara además sobre las Redes de Petrí.

La maximización de flujos es un problema típico de la Investigación de Operaciones, el cual tiene muchas aplicaciones, por ejemplo el flujo vial en una ciudad, una red de aguas negras, una red informática, etc. Si nosotros sobrecargamos una calle, una tubería o un canal que obviamente tiene un limite de capacidad, nos enfrentaremos a un problema, posiblemente un flujo mas lento o una tubería con demasiada presión, ahí es donde el Modelo de Redes es un método o secuencia el cual nos ayuda a tomar una decisión acertada que podría ser mejorar o dar mayor aprovechamiento a los flujos a vías donde que tengan mas capacidad, creando nuevas vías o eliminando algunas antiguas. También nos ayuda a maximizar este flujo de manera eficiente de forma tal que se aprovechen al máximo los recursos.

Por otra parte el objetivo de las Redes de Petrí esta mas enfocado al campo de la computación y este es el de buscar mayor eficiencia y concurrencia en el tratamiento de los datos y que estos no se estanquen o sobrecarguen la capacidad que ellos poseen en un procesador por medio de graficas especiales.

Objetivos

• Exponer de una manera clara los conceptos, teoremas y aplicaciones.

• Encontrar maneras de aplicar la Teoría de Redes a situaciones reales.

• Resolver problemas prácticos.

Modelos de redes

Definición:

Una Red de Transporte es una grafica dirigida, simple, con pesos y que debe cumplir las siguientes:

• Poseer una fuente o vértice fijo que no tiene aristas de entrada.

• Poseer un sumidero o vértice fijo que no tiene arista de salida

• El peso Cij de la arista dirigida de i a j llamado capacidad de “ij” es un numero no negativo.

Este es un ejemplo de una red que parte de un punto a que es un

Muelle y llega a un punto z que es una refinería.

Definición:

Sea “G” una red y sea “Cij” la capacidad de la arista dirigida (ij) se dice que un flujo F en G asigna a cada arista dirigida (ij) un numero no negativo Fij tal que debe cumplir:

• Fij " Cij

• Para todos los vértices que no sea fuente ni sumidero se cumple: ec 8.1.1 (esta es la ecuación de conservación de flujo)

Teorema 1:

Dado un flujo F en una red el flujo de salida de la fuente es igual al flujo de entrada del sumidero.

FLUJO MÁXIMO:

En una red G, el flujo máximo es un flujo máximo. Generalmente existen varios flujos con el mismo valor máximo. Para encontrar el flujo máximo consideraremos un flujo inicial en cada arista igual a cero, después se determina un camino específico de la fuente al sumidero y se incrementa el flujo.

Si una arista esta dirigida hacia la fuente decimos que esta arista esta dirigida en forma impropia, en caso contrario esta dirigida en forma propia.

Si se determina un camino P de la fuente al sumidero en donde cada arista de P esta orientada en forma propia y el flujo en cada arista es menor que la capacidad de la arista, es posible aumentar el valor de flujo.

Es posible incrementar el flujo en ciertos caminos de la fuente al sumidero que tenga aristas orientadas en forma impropia y propia. Sea P un camino de “a” a “z” y sea “x” un vértice en P que no sea “a” ni ”z”

Ambas aristas están orientadas en forma propia, en este caso, si incrementamos el flujo en ", el flujo en la entrada en x seguirá siendo igual al flujo de salida de x.

Si incrementamos el flujo en e2 en ", debemos disminuir el flujo en e1 en " de modo que el flujo de entrada en x siga siendo igual al flujo de salida en x.

Es análogo en el caso b

Disminuimos el flujo en ambas aristas en ". En cada caso las asignaciones resultantes de las aristas dan como resultado un flujo.

Para realizar estas alteraciones debemos tener un flujo menor que la capacidad en una arista orientada en forma propia y un flujo distinto de cero en una arista orientada en forma impropia.

Teorema 2:

Sea P un camino de “a” a ”z” en una red G tal que:

Para cada arista (i,j) de P, orientada en forma propia.

Fij <Cij

Para cada arista (i,j) de P, orientada en forma impropia

0 <Fij

Se define

F'ij =

Si no existieran caminos que concuerden con el teorema 2, el flujo es máximo, entonces se considera el algoritmo:

Iniciar con un flujo

Buscar un camino que satisfaga con las condiciones del teorema 2

Si no existe el camino el flujo es máximo.

Se incrementa el flujo en ", y se regresa a línea 2.

A dicho algoritmo se le llama Algoritmo etiquetado.

Problema 1:

Para este ejemplo hemos usado una parte de la flota de la empresa multinacional ESSO.

La planta de ESSO-Texaco para el aeropuerto internacional de El Salvador posee dos tanques que son capaces de contener 180,000 galones de combustible para avion jet. Ambas distribuidoras depositan combustible en los mismos tanques, la ESSO esta encargada de depositar en los tanques de las 23:30 a las 6:00 y de las 6:00 en adelante se recibe producto de Texaco. Los camiones de la ESSO salen de la base hacia la refinería a cargar combustible o si ya están cargados, se dirigen directamente hacia la planta del aeropuerto a descargarlo. La siguiente red representa las posibles rutas que pueden tomar los camiones y sus respectivos tiempos:

Por medio del diagrama nos podemos dar cuenta que un camión que no esta cargado de combustible no puede partir mas tarde de las 23:30 y cargar combustible ya que llegaría después de las 5:00 y un camión tarda una hora en descargar todo su combustible, lo cual provocaría que chocaran los horarios de los camiones ESSO con los horarios de los camiones de Texaco. Un camión ya cargado puede salir lo mas tarde a las 3:30 de la mañana para llegar exactamente a las 5:00. Estas restricciones de tiempo se deben a que todos los camiones de ESSO tienen un limite de velocidad por seguridad que es de 70 kmh y los tiempos ya están medidos.

Problema 2:

El problema dos que escogimos esta enfocado siempre a los camiones de la empresa ESSO, pero en este caso enfocado a la longitud de los trayectos. Para tener una idea más amplia de lo que se habla, colocamos el siguiente mapa:

El tiempo que se recorre en cada uno de los trayectos y los trayectos mismos se representan en la siguiente red:

Es evidente que el camino 2 es el mas adecuado por el tiempo que utiliza que es de 30 minutos menos que el camino 1.

Teorema de flujo máximo y corte mínimo

Tenemos una red G y tiene un flujo F al concluir nuestro algoritmo esto significa que algunos vértices están etiquetados y otros no. Sea P el conjunto de vértices Etiquetados y (
no complementados) entonces la fuente a no esta en P y el sumidero z esta
. El conjunto s de aristas (v,w) con v que pertenece a P y w que pertenece a
, es un corte y la suma de las capacidades de las aristas s es la capacidad de cortes.

Para el caso G es una red con una fuente a y un sumidero z luego la capacidad de las aristas i,j es Cij

Un corte (P,
) donde el complemento de P es
en G consta de un conjunto P de vértices y de complementos a
, donde a pertenece a P y z pertenece a
.

Teorema 3

Sea F un flujo en G y teniendo (P,
) un corte en G entonces la capacidad de este es mayor o igual que el valor de F; es decir

Teorema 4

Siendo F un flujo en G sea (P,
) Un corte en G, si la igualdad se cumple en Un corte (P,
) donde el complemento de P es
en G consta de un conjunto P de vértices y de complementos a
, donde a pertenece a P y z pertenece a
. Entonces se dice que el flujo es máximo y el corte es mínimo. La igualdad se cumple sí y solo sí:

Fij =Cij Para i que pertenece a P, j pertenece a
.

Fij = 0 Para i que pertenece a
, j pertenece a P.

Teorema 5

Cuando se concluye un algoritmo se produce un flujo máximo, si P (respectivamente,
) es el conjunto de vértices etiquetados (respectivamente, no etiquetados) al concluir el algoritmo el corte (P,
) es mínimo.

Redes de Petri

Son graficas del procesamiento concurrente, es un método para modelar y estudiar el procesamiento concurrente.

Una red de Petrí   es un grafo dirigido bipartito, con un estado inicial, llamado marcación inicial. Los dos componentes principales de la red de Petrí son los sitios  (también conocidos como estados) y las transiciones. Gráficamente, los sitios son dibujados como círculos y las transiciones como barras o rectángulos. Las aristas del grafo son conocidas como arcos. Estos tienen un peso específico, el cual es indicado por un número entero positivo, y van de sitio a transición y viceversa. Por simplicidad, el peso de los arcos no se indica cuando éste es igual a 1. Un arco que esté etiquetado con k puede ser interpretado como k arcos paralelos.

Ejemplo de una Red de Petrí

Es una grafica dirigida G = (V, E) donde V = P U T y P "T = Ø, cualquier arista e en E es incidente en un miembro de P y un miembro de T, el conjunto P es el conjunto de lugares y el conjunto T es en conjunto de Transiciones.

Un marcado de una Red de Petrí asigna a cada lugar un entero no negativo, una red de Petrí con un marcado es una Red de Petrí Marcada (o simplemente una Red de Petrí).

Con un marcado se asigna al valor no negativo n al lugar p, decimos que existen n elementos en p, mediante los elementos a representar son los puntos.

Los lugares representan condiciones, las transiciones representan eventos, y la presencia de al menos un elemento en un lugar (condición) indica que tal condición se cumple.

Si una arista va del lugar p a la transición t, decimos que p es un lugar de entrada para la transición t. Un lugar de salida se define de manera análoga, si cada lugar de entrada de una transición t tiene al menos un elemento, decimos que t esta activada.

La descarga de una transición elimina un elemento de cada lugar de entrada y agrega un elemento a cada lugar de salida. Una serie de descargas transforma un marcado M, en un marcado M', decimos que M' es alcanzable desde M.

Un evento puede ocurrir si y solo si se cumplen todas las condiciones para su ejecución; es decir, la transición se puede descargar solo si esta activada.

Entre las propiedades más comunes de Redes de Petrí tenemos la Supervivencia y la Seguridad. La Supervivencia se refiere a la ausencia de estancamientos, y la Seguridad se relaciona con la capacidad limitada de la memoria.

Un marcado M de una red de Petrí esta Vivo si, partiendo de M, sin importar la serie de descargas realizadas, es posible descargar cualquier transición dada mediante alguna secuencia de descargas adicionales. Si un marcado M esta vivo para una Red de Petrí P, entonces, sin importar la serie de descargas de transiciones, P nunca se estancara. De hecho, podemos descargar cualquier transición mediante cierta secuencia de descargas adicionales. Un marcado M para una red de Petrí esta acotado si existe algún entero positivo n con la propiedad de que, en cualquier secuencia de descarga, ningún lugar recibe mas de n elementos. Si un marcado M, esta acotado y en cualquier secuencia de descarga ningún lugar recibe mas de un elemento, decimos que M es un marcado Seguro.

Si cada lugar representa un registro capaz de guardar una palabra de computadora y si un marcado inicial es seguro, tenemos garantizado que no se excederá la capacidad de memoria de los registros.

Problema 1:

Este es un ejercicio aplicado a casi cualquier tipo de fila donde existe una sola línea para atender a 100 personas o más. Los tiempos de llegada de los clientes serán valores sucesivos de la variable aleatoria ta, los tiempos de servicio están dados por la variable aleatoria ts, y N es el número de servidores. Este modelo en su estado inicial tiene la cola vacía y todos los servidores en estado de espera.

La red de Petrí para este escenario se muestra en la siguiente figura:

  

Los estados están etiquetados con letras mayúsculas y las transiciones con minúsculas. Las etiquetas de los sitios también serán usadas como las variables de cuyos valores son los tokens

Las aristas tienen etiquetas que podrían representar las funciones de transición, las cuales especifican el número de tokens eliminados o agregados cuando una transición es activada.

El estado A inicialmente contiene la llegada de 100 clientes; el sitio B evita que los clientes entren más de una vez; el sitio Q es la fila que realizan los clientes cuando tienen que esperar a que se les atienda. El estado S es donde los servidores ociosos esperan la oportunidad para trabajar, y el sitio E cuenta el número de clientes que abandonan el sistema. El estado inicial implica que los sitios tengan los siguientes valores:

• A = 100

• B = 1

• Q = 0

• S = N

• E = 0

La transición a sirve para modelar a los clientes que entran al sistema y la transición b modela a los clientes cuando están siendo atendidos.

Problema 2:

La evaluación de expresiones aritméticas puede ser descrita de forma sencilla desde redes de Petrí. Ponemos un ejemplo practico con la expresión (a+b)X(c+d) puede ser caracterizada por la siguiente red de Petrí, en la que los lugares representan operandos, las transiciones operadores y la existencia de un toen en un lugar denota la disponibilidad del valor del operando:

Problema 3:

El proceso de préstamo de libros en la UAE también puede representarse con una Red de Petrí de la siguiente manera:

Podemos notar que el lugar de libro disponible es el que delimita la cantidad de libros disponibles, por ejemplo si se tienen 5 ejemplares, lo marcaríamos con 5.

Conceptos

• Red:

Es un grafo dirigido formado por una fuente, un sumidero, aristas y nodos.

• 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 (a):

Punto de partida del flujo total de la red.

Conclusiones

• El modelo de redes posee una gran aplicabilidad en muchos problemas de la vida cotidiana, en nuestra sociedad moderna es casi imprescindible para lograr una mayor eficiencia en casi cualquier tipo de flujo.

• Las Redes de Petrí están mas enfocadas a la optimización de procesos que pueden depender de otros al operar.

• En general puede observarse la importancia de los modelos matemáticos para encontrar la solución de infinidad de problemas.

Bibliografía:

-Johnsonbaugh, Richard, Matemáticas Discretas 4ª edición, PRENTICE may, México, 1999.

-Selecciones varias en Internet.