MODELOS DE REDES
-
Upload
eduardo-n-tenorio -
Category
Documents
-
view
44 -
download
0
Transcript of MODELOS DE REDES
5/13/2018 MODELOS DE REDES - slidepdf.com
http://slidepdf.com/reader/full/modelos-de-redes-55a754353c50e 1/17
MODELOS DE REDES
En un modelo de redes el objetivo consiste en maximizar el
flujo del muelle a la refinería y calcular el valor de este flujo
máximo.
5/13/2018 MODELOS DE REDES - slidepdf.com
http://slidepdf.com/reader/full/modelos-de-redes-55a754353c50e 2/17
INTRODUCCIÓN
En este capitulo se estudian los modelos de redes, que usan
gráficas dirigidas, en esta sección aprenderemos a maximizar el
flujo a través de una red. La red podría ser una red de transporte
por la que fluyen bienes, una red de tuberías a través de la cual
fluye el petróleo, una red de computadoras a través de la cual fluyenlos datos, etc. En cada caso el problema consiste en determinar el
flujo máximo. La maximización del flujo en una red es un problema
que pertenece a la teoría de gráficas como a la investigación de
operaciones. Las redes de Petri modelan sistemas en los que el
procesamiento puede ocurrir de manera concurrente. El modelo
proporciona un marco de referencia para tratar cuestiones como laposible operación de estancamiento en un sistema o el hecho de
exceder la capacidad de los componentes de un sistema.
5/13/2018 MODELOS DE REDES - slidepdf.com
http://slidepdf.com/reader/full/modelos-de-redes-55a754353c50e 3/17
RED DE TRANSPORTE
Considerando la siguiente gráfica dirigida (red de transporte), que representa una
tubería de petróleo. El petróleo se descarga en el muelle a y se bombea por toda la
red de la refinería z . Los vértices b,c,d y e representan estaciones de bombeo
intermedias. Las aristas dirigidas representan subtuberías del sistema y muestran la
dirección en que puede fluir el petróleo. Las etiquetas de las aristas indican las
capacidades de las subtuberías. El problema es encontrar la manera de maximizar elflujo del muelle a la refinería y calcular el valor de este flujo máximo.
5/13/2018 MODELOS DE REDES - slidepdf.com
http://slidepdf.com/reader/full/modelos-de-redes-55a754353c50e 4/17
Una red de transporte es una grafica dirigida, simple con pesos que
satisface:
a) Un vértice fijo, designado como el origen o fuente, no tiene aristas de
entrada.
b) Un vértice, designado como destino o sumidero, no tiene aristassalientes.
c) El peso Cij de la arista dirigida (i, j) llamada capacidad de (i, j) es un
numero no negativo.
Si observamos la gráfica, el origen es el vértice a y el destino es el vértices
z. La capacidad de la arista (a, b), C_{a, b} es 3 y la capacidad de la arista
(b, c), C_{b, c} es 2. Un flujo en una red asigna un flujo a cada aristadirigida que no excede la capacidad de esa arista. Más aun, si se supone
que el flujo que entra a un vértice v, que no es el origen y el destino, es
igual al flujo que sale de v.
5/13/2018 MODELOS DE REDES - slidepdf.com
http://slidepdf.com/reader/full/modelos-de-redes-55a754353c50e 5/17
Ejemplo de red de transporte
Tomado con referencia la gráfica
5/13/2018 MODELOS DE REDES - slidepdf.com
http://slidepdf.com/reader/full/modelos-de-redes-55a754353c50e 6/17
Sea G una red de transporte. Sea C_{ij} la capacidad de la arista dirigida (i,
j) . Un flujo F en G asigna a cada arista dirigida (i, j) un numero no negativo
F _{ij} tal que:
a. F _{ij} C_{ij}
b. Para cada vértice j, que no es la fuente ni el destino.
Conservación de flujo b
Conservación de flujo
F _{ij} recibe el nombre de flujo en la arista (i, j). Para cualquier vértice j,
5/13/2018 MODELOS DE REDES - slidepdf.com
http://slidepdf.com/reader/full/modelos-de-redes-55a754353c50e 7/17
Se llama flujo que entra a j y
Se llama flujo que sale de j.Conservación de flujo significa para el ejemplo,
que el petróleo no se usa ni se suministra en las estaciones de bombeo b,
c, d y e.
Ahora, vamos a definir un flujo para la red del ejemplo asignando los
valores: F _{ab} = 2, F _{bc} = 2, F _{cz} = 3; F _{ad} = 3, F _{dc} = 1, F _{de} = 2,
F _{ez} = 2
La gráfica quedaría,
5/13/2018 MODELOS DE REDES - slidepdf.com
http://slidepdf.com/reader/full/modelos-de-redes-55a754353c50e 8/17
Analizando, El flujo que entra al vértice d F _{ad} = 3 y es el mismo que sale
del vértice d,
F _{dc} + F _{de} = 1 + 2 = 3
Se debe considerar que una arista e se etiqueta ³x, y´ si la capacidad de e
es x y el flujo en e es y.
Observemos que el flujo que sale del origen (a) Fab + Fad, es igual al flujo
que entra al destino (z) Fcz + Fez F _{ab} + F _{ad} = 2 + 3 = 5
F _{cz} + F _{ez} = 3 + 2 = 5
Ambos valores son iguales a 5; a este valor lo denominamos valor del flujo
F.
Sea F un flujo en una red G. el valor
Se llama el valor del flujo F.
5/13/2018 MODELOS DE REDES - slidepdf.com
http://slidepdf.com/reader/full/modelos-de-redes-55a754353c50e 9/17
ALGORITMO DE FLUJO MÁXIMO
Si G es una red de transporte, un flujo máximo en G es un flujo con valor
máximo.
Diseñar un algoritmo para determinar un valor máximo, consiste en iniciar
con cierto flujo inicial e incrementar de manera interactiva el valor del flujo
hasta que no pueda mejorarse mas.
Podemos considerar un flujo inicial aquel en el que el flujo en cada arista es
igual a cero.
Para incrementar el valor de un flujo dado, debemos determinar un camino
del origen al destino e incrementar el flujo a lo largo de este camino.
5/13/2018 MODELOS DE REDES - slidepdf.com
http://slidepdf.com/reader/full/modelos-de-redes-55a754353c50e 10/17
Notación
G denota una red con origen a, destino z y capacidad C
En principio denotaremos aristas no dirigidas
(Camino) P = (V0, V1,«««««., Vn) Vo = a, V = z
Si una arista e en P esta dirigida de Vi-1 a Vi decimos que esta orientada
en forma propia.
5/13/2018 MODELOS DE REDES - slidepdf.com
http://slidepdf.com/reader/full/modelos-de-redes-55a754353c50e 11/17
Si podemos determinar un camino P de la forma del origen al destino en
donde cada arista 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 del
flujo.
5/13/2018 MODELOS DE REDES - slidepdf.com
http://slidepdf.com/reader/full/modelos-de-redes-55a754353c50e 12/17
Uso del algoritmo 8.2.4 para determinar el flujo máximo.
Dada la siguiente red de transporte:
Determinar un flujo máximo en la red, mediante el algoritmo 8.2.4
5/13/2018 MODELOS DE REDES - slidepdf.com
http://slidepdf.com/reader/full/modelos-de-redes-55a754353c50e 13/17
Desarrollo:
Las líneas 1 y 2 del algoritmo, nos permite inicializar el flujo con 0 para
cada una de las aristas de la red.
5/13/2018 MODELOS DE REDES - slidepdf.com
http://slidepdf.com/reader/full/modelos-de-redes-55a754353c50e 14/17
Las líneas 5 al 9 del algoritmo, permiten etiquetar los vértices como
NULOS.
Las líneas 10 y 11 del algoritmo permite etiquetar el vértice a como (-,)
que es un par o dupla de valores, donde el primer elemento identifica el
vértice ³predecesor o anterior´ y el segundo valor es el mínimo entre el
incremento (¨) y la diferencia dada por Cvw - Fvw, donde la red resultante
es:
5/13/2018 MODELOS DE REDES - slidepdf.com
http://slidepdf.com/reader/full/modelos-de-redes-55a754353c50e 15/17
En la línea 12 al conjunto U le añadimos el vértice a en este caso (vértice
fuente o inicial).
A continuación la línea 13, da inicio al ciclo WHILE, que permite etiquetar
los vértices que conectan las aristas que salen de a y al mismo tiempo
elimina el vértice a de U, para nuestro caso las aristas (a, b) y (a, d)
controlando que los vértices b y d no estén etiquetados. Luego de etiquetar
los vértices anteriores, regresamos a la línea 13 y repetimos el ciclo
WHILE, pero esta vez tomamos el vértice b y nos dirigimos a etiquetar el
vértice c que se conecta con la arista (b, c) y c no esta etiquetado, se
elimina el vértice b y se añade el vértice c a U. Regresamos a la línea 13 y
repetimos el ciclo WHILE, como el vértice z no está etiquetado, tomamos
cualquiera de los vértices que se encuentran en U pero observando quecon los vértices que se conecta no se encuentren etiquetados, para nuestro
caso tomamos el vértice c y cumplimos los requisitos que nos pide el
algoritmo en las líneas que hagamos referencia, para nuestro caso c se
conecta con z y z no está etiquetado, dando como resultado lo siguiente:
5/13/2018 MODELOS DE REDES - slidepdf.com
http://slidepdf.com/reader/full/modelos-de-redes-55a754353c50e 16/17
Regresamos a la línea 13, ciclo WHILE, pero como z está etiquetado,
saltamos a la línea 35, donde las líneas que le siguen nos permite
determinar el conjunto P con el camino de los vértices comenzando
desde z hacia atrás hasta llegar a a, donde el camino está dado por:
P = (a, b, c, z)En la línea 43 del algoritmo hacemos ¨ = val(z) y asignamos el flujo a
todas las aristas del camino identificado, conforme lo señalan las
líneas del algoritmo que están a continuación de la línea 43.
La red con estos nuevos datos es la siguiente:
5/13/2018 MODELOS DE REDES - slidepdf.com
http://slidepdf.com/reader/full/modelos-de-redes-55a754353c50e 17/17
Luego de obtener este primer camino, regresamos al inicio del algoritmo o
sea a la línea 3 y volvemos a ejecutar las instrucciones como se lo hizo al
inicio, con esto se determina otro camino y los flujos respectivos; pero hay
que considerar que ahora algunas de las aristas ya tienen un flujo asignado
por el anterior proceso. Este procedimiento continua hasta cuando el
conjunto U este vacío, que se controla en la línea 15 y se puede dar por terminado el algoritmo.