cap. 6 modelos de redes.pptx

C A P Í T U LO 6

MODELO DE REDES

OBJETIVOS

• Definir lo que significa una red.

• Ilustrar algunas aplicaciones posibles de redes.

• Analizar las diferentes soluciones para la optimización de redes.

DEFINICIONES PARA REDES

• Consiste en una serie de nodos alcanzados con arcos o ramas.

• La notificación para describir una red es (N,A), donde N es el conjunto de nodos y A es el conjunto de arcos.


• Ejemplo

• N = {1,2,3,4,5}• A = {(1,2),(1,3),(2,3),(2,5),(3,4),(3,5),(4,2),(4,5)}


• Arco dirigido, si permite un flujo positivo en una dirección, y flujo cero en la dirección opuesta.

• Red dirigida, si tiene todos sus arcos dirigidos.

• Ruta, es una sucesión de arcos distintos que unen dos nodos pasando por otros nodos, independientemente de la dirección de flujo en cada arco.

• Una ruta forma un ciclo si conecta un nodo consigo mismo, pasando por otros nodos.

• Un ciclo es dirigido si consiste en una ruta dirigida.


• Ejemplo

• Ciclo dirigido:

(2,3),(3,4),(4,2)


• Red conectada, es aquella en que cada dos nodos distintos están enlazados al menos por una ruta.

• Un árbol, es una red conectada que puede consistir sólo en un subconjunto de todos los nodos en ella, donde no se permiten ciclos.

• Un árbol de expansión es un árbol que enlaza todos los nodos de la red, sin permitir ciclos.


• Ejemplo:

Árbol Árbol de expansión

1 3

2

1 3

2 4

5

APLICACIONES POSIBLES DE REDES

• Diseño de un flujo con costos mínimos de productos petroleros en un oleoducto.

• Determinar el flujo de tráfico de automóviles en carreteras.

• Determinación de la ruta más corta entre dos ciudades, en una red de carreteras.

• Determinación de la capacidad máxima de una red de tuberías.

• Determinación del cronograma de las actividades en la cosntrucción de un proyecto.

ACTIVIDAD

• Realice los numerales 1 y 2 del conjunto de problemas 6.1A

ALGORITMO DE ÁRBOL DE EXPANSIÓN MÍNIMA

• http://www.slideshare.net/adncstell/53-arbol-de-expansin-minima-algoritmo-de-prim

http://www.slideshare.net/adncstell/53-arbol-de-expansin-minima-algoritmo-de-prim

http://www.slideshare.net/adncstell/53-arbol-de-expansin-minima-algoritmo-de-prim

ACTIVIDAD

Desarrollar el ejemplo 6.2-1, comenzando en el nodo 1 y luego en el nodo 5. Demuestre que con el algoritmo se obtiene la misma solución.

EJERCICIO 1

Un centro regional de cómputo, debe instalar líneas especiales para comunicación, a fin de conectar a 5 usuarios con una nueva computadora central, la compañia telefónica local es la que instalará la nueva red de comunicaciones, pero es una operación costosa. Con el propósito de reducir costos, se busca que la longitud total (kms) de éstas líneas sea la menor posible.La red para éste problema es la siguiente:

EJERCICIO 1

1

3

2 5

4

6

20

40

5040

30

40

20

30

30

4010

EJERCICIO 2

La administración del parque necesita determinar los caminos bajo los cuales se deben tender las comunicaciones para conectar todas las estaciones con una longitud total mínima de cable. Seleccionar el nodo A como nodo inicial.

G

F

ED

C

B

A

2

5

2

4

7

1 7

5

4

1

4

3

RUTA MÁS CORTA

EJEMPLO 6.3-1 Reemplazo de Equipo

RentCar está desarrollando un plan de reposición de su flotilla de automóviles para un horizonte de planeación de 4 años, que comienza el 1 de enero de 2001 y termina el 31 de diciembre de 2004. Al iniciar cada año se toma la decisión de si un auto se debe mantener en operación o se debe sustituir. Un automóvil debe estar en servicio durante 1 año como mínimo, y 3 años como máximo. La tabla siguiente muestra el costo de reposición en función del año de adquisición del vehículo y los años que tiene en funcionamiento.

ALGORITMO DE LA RUTA MÁS CORTA


Costo de reposición ($) Equipo adquirido para los años en operación al comenzar 1 2 3

2001 4000 5400 98002002 4300 6200 87002003 4800 7100 -2004 4900 - -

RUTA MÁS CORTA


1 2 3 4 54000 4300 4800 4900

5400

9800

7100

6200

8700

Determinar la ruta más corta y calcule el costo total de la política de reposición .

La ruta más corta , es 1 3 5, con un costo de $5400 + $7100 = $12500

RUTA MÁS CORTA

EJEMPLO 6.3-2 Ruta más segura

Smart conduce diariamente hacia su trabajo. Como acaba de

terminar un curso de análisis de redes, puede determinar la

ruta más corta. Desafortunadamente, la ruta seleccionada está

muy patrullada por la policía, y debido a las multas por

manejar a alta velocidad, podría ser que la ruta más corta no

sea la mejor elección. Smart decide entonces escoger una

ruta que maximice la probabilidad de no ser detenido

por la policía.

RUTA MÁS CORTA


La probabilidad de no ser detenido en el trayecto hacia

el trabajo es el producto de las probabilidades

relacionadas con los segmentos sucesivos de la ruta

seleccionada.

La red de la siguiente figura muestra las rutas posibles

para ir y regresar del trabajo, y las probabilidades

correspondientes de no ser detenido en cada segmento.

RUTA MÁS CORTA


La ruta que maximiza probabilidad de que Smart no sea detenido por la policia es: 1 3 5 7 La probabilidad de no recibir una multa en la ruta anterior es: 0.9 x 0.3 x 0.25 = 0.07

1

2

3

4

5

6

7

0.2

0.8

0.9

0.6

0.35

0.10.4

0.30.25

0.5

1

3 5

7

ALGORITMO DE DIJKSTRA

• Nació en Alemania en 1930, su padre era Químico y su madre

Matemática. En 1956, Dijkstra anunció su algoritmo.

Algoritmo de caminos mínimos, propuso el algoritmo del camino

más corto y el algoritmo del árbol generador minimal.

• Se refiere a una red en la que cada arco (i , j) tiene asociado un

número cij que se interpreta como la distancia (costo o tiempo) que

hay entre los vértices i y j. El objetivo consiste en encontrar las rutas

más cortas (económicas, rápidas) entre un nodo específico y todos

los demás nodos de la red.


• Consiste en asignar una etiqueta a cada nodo de la red, la

que luego de sucesivas actualizaciones, contendrá el valor

del camino de valor mínimo que une el nodo inicio de la red

con el nodo considerado y el vértice precedente en dicho

camino.


Supongamos que existen 7 ciudades interconectadas (o sitios cualquiera: barrios en una ciudad, departamentos en una fabrica, etc.), cada línea representa la trayectoria permitida de una ciudad a otra. Las distancias (o costo de transporte) entre ciudades esta representado por un valor sobre la línea. Se pregunta por la secuencia de ciudades que dan la distancia mínima entre la ciudad A y la ciudad G.


1. Etiquetar todos los nodos a donde pueda llegar desde el nodo inicial: Es decir los nodos B, C y D.Etiqueta para el nodo B: Es la distancia desde el nodo que viene, o sea = 4, nombre del nodo que viene = "A“Etiqueta= [4,"A"] , de manera análoga para el nodo C = [5, "A"] y el nodo D = [3, "A"]


2. Evaluar cual de todas las etiquetas temporales, tiene la mínima distancia para que sea convertida en etiqueta permanente. Marquemos como etiqueta permanente, con un asterisco. En nuestro caso hay tres etiquetas temporales, [4,"A"], [5,"A"] y [3,"A"]. La que tiene la menor distancia es [3,"A"] en el nodo D. La convertimos en etiqueta permanente.


3. Ahora, con base en la última etiqueta permanente (la del nodo D), se etiquetan todos los nodos a los que se pueda llegar desde el Nodo D (el de la última etiqueta permanente). En nuestro caso, son los Nodos C y F. La etiqueta para el Nodo F es [3+7=10, "D"], es decir [10, D], para el Nodo C, se puede colocar la etiqueta [3+2, "D"] = [ 5 ,"D"]. Da igual dejar la etiqueta actual, que tiene una distancia de 5, que cambiarla por esta última, así que dejemos la que tiene actualmente.


4. De nuevo se evalúa de todas las etiquetas temporales, cual es la que tiene la distancia más pequeña:[4,"A"], [5,"A"] y [10,"A"]. El nodo B que tiene la etiqueta temporal con la distancia más pequeña, se pasa a tener una etiqueta permanente.


5. Etiquetar todos los nodos a los que se puede llegar desde el nodo con la última etiqueta permanente, es decir el B. Estos nodos son el C y el E. La etiqueta probable para el nodo C sería [4+3, "B"]= [7,"B"], pero como ya tiene una etiqueta temporal de [5,"A"], que tiene una distancia menor, no se cambia. Miremos el Nodo E. La etiqueta para el Nodo E es [4+6, "B"] = [10, "B"]


6. Evaluar de todas las etiquetas temporales, cual es la que tiene la distancia más corta: [10,"B"], [5,"A"] y [10,"D"]. La de menor distancia es la [5,"A"]. Se marca como etiqueta permanente. Ahora etiquetar todos los nodos a los que se puede llegar desde el Nodo C y que no tengan ya, una etiqueta permanente. Son los nodos E, F y G. Para el Nodo E la etiqueta sería [5+4,"C"] =[9,"C"], que nos da una distancia menor que la que tiene ([10,"B"]). Por lo tanto la cambiamos. Para el Nodo F nos da [5+5,"C"]=[10,"C"], como ya tiene una etiqueta con 10, nos es indiferente y no la cambiamos. Para el Nodo G la etiqueta es [5+25, "C"]=[30,"C"].


7. Evaluar cual de las etiquetas temporales tiene la distancia más corta: [9,"C"], [10, "D"] y [30,"C"]. Gana el nodo E. Se marca como etiqueta permanente y desde él evaluamos para rotular a todos los nodos a los que pueda llegar, con etiquetas temporales: F y G. Para el Nodo F, lo dejamos como esta por que la distancia nos da 9+6 = 15 que es mayor que el que tiene actualmente 10, pero para el Nodo G el rotulo es [9+7,"E"] = [16, "E"].Quedan como rótulos temporales el del nodo F y G. El menor es el del Nodo F, se marca como permanente... no hay más rótulos temporales excepto el del Nodo G y el Nodo G quedaría como [10+8, "G"]=[18,"G"] que es mayor que el que ya tiene, así que mejor dejémoslo así y por último marquémoslo como etiqueta permanente.


La trayectoria que da una mínima distancia: G-E-C-A, con una distancia mínima de 16.

EJERCICIO

• El valor del arco entre D y G es 7

ALGORITMO DE FLUJO MÁXIMO

• En algunas redes circula por los arcos un flujo (envío o circulación de unidades homogéneas de algún producto: automóviles en una red de carreteras, litros de petróleo en un oleoducto, bits por un cable de fibra óptica) desde el origen o fuente al destino.

• Los arcos tienen una capacidad máxima de flujo, y se trata de enviar desde la fuente al destino la mayor cantidad posible de flujo, de tal manera que:

ALGORITMO DE FLUJO MÁXIMO

• El flujo es siempre positivo y con unidades enteras.

• El flujo a través de un arco es menor o igual que la capacidad.

• El flujo que entra en un nodo es igual al que sale de él.

ALGORITMO DE FORD-FULKERSON

• El algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar el flujo, hasta que se alcance el flujo máximo.

• La idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos origen y destino.


http://www.youtube.com/watch?v=bu1BnW9H9V0




Ejercicio. Encuentre el flujo máximo utilizando el algortimo de Ford Fulkerson

cap. 6 modelos de redes.pptx

Documents