Optimizacion De Redes

Contenido

Introducción 2

OPTIMIZACION DE REDES 3

TERMINOLOGIA 3

PROBLEMA DE LA RUTA MÁS CORTA. REDES CICLICAS Y ACICLICAS 4

ALGORITMO ACICLICO 5

ALGORITMO CICLICO (DE DIJKSTRA) 6

PROBLEMA DEL ARBOL DE MINIMA EXPANSION 8

PROBLEMA DE FLUJO MAXIMO 11

PROBLEMA DE FLUJO DE COSTO MINIMO 14

PROGRAMACION LINEAL EN TEORIA DE REDES 16

USO DE PROGRAMAS DE COMPUTACIÓN 16

BIBLIOGRAFÍA 21

Introducción

Los modelos de redes y los programas de números enteros son aplicables para una gran variedad de modelos decisión. Algunos de estos problemas de decisión son realmente problemas físicos, tales como el transporte o flujo de bienes materiales. Muchos problemas de redes son más que una representación abstracta de procesos o actividades, tales como el camino crítico en las actividades entre las redes de un proyecto gerencial. Estos problemas son ilustrados fácilmente utilizando los arcos de redes, y los nodos.

Los programas lineal estándar asumen que las variables de decisión son continuas. Sin embargo, en muchas aplicaciones, los valores de fracciones podrían ser de poco uso así como es mostrado en algunas aplicaciones útiles.

Optimización de redes es un tipo especial de modelo en programación lineal. Los modelos de redes tienen tres ventajas importantes con respecto a la programación lineal.

Pueden resolverse muy rápidamente. Problemas que con programación lineal tendrían 1000 filas y 30.000 columnas pueden ser resueltos en segundos. Esto permite que los modelos de redes sean usados en muchas aplicaciones (tal como la toma de decisión en tiempo real) para lo cual la programación lineal no es lo ideal.

Requieren en forma natural de soluciones enteras. Al reconocer que un problema puede formularse como algún modelo de red nos permitirá resolver tipos especiales de problemas de programación entera aumentando la eficiencia y reduciendo el tiempo consumido por los algoritmos clásicos de programación lineal.

Son intuitivos. Los modelos de redes proveen un lenguaje para tratar los problemas, mucho más intuitivo que "variables, objetivo, restricciones".

Obviamente los modelos de redes no son capaces de cubrir la amplia gama de problemas que puede resolver la programación lineal. Sin embargo, ellos ocurren con suficiente frecuencia como para ser considerados como una herramienta importante para una real toma de decisiones.

OPTIMIZACION DE REDES

TERMINOLOGIA

Red: conjunto de puntos y líneas que unen ciertos pares de puntos.

Nodos: Puntos (o vértices).

Arcos: Líneas, ligaduras, aristas o ramas. Se etiquetan para dar nombre a los nodos en sus puntos terminales.

Arco dirigido: Si el flujo a través de un arco se permite sólo en una dirección. La dirección se indica agregando una cabeza de flecha al final de la línea que representa el arco.

Arco no dirigido: Si el flujo a través de un arco se permite en ambas direcciones.

Red dirigida: Red que tiene sólo arcos dirigidos.

Red no dirigida: Todos sus arcos son no dirigidos.

Trayectoria: Sucesión de arcos distintos que conectan nodos.

Ciclo: Trayectoria que comienza y termina en el mismo nodo.

Red conexa: Red en la que cada par de nodos esta conectado.

Árbol: Red conexa (para algún subconjunto de n nodos) que no contiene ciclos no dirigidos.

Árbol de expansión: Red conexa para los n nodos que contiene ciclos no dirigidos.

Capacidad del arco: Cantidad máxima de flujo (quizá infinito) que puede circular en un arco dirigido.

Nodo fuente: Nodo origen, tiene la propiedad de que el flujo que sale del nodo excede el flujo que entra a él.

Nodo de demanda: Nodo de destino, donde el flujo que llega excede al que sale de él.

Nodo de trasbordo: Intermedio, satisface la conservación del flujo, es decir, el flujo que entra es igual al que sale.

PROBLEMA DE LA RUTA MÁS CORTA. REDES CICLICAS Y ACICLICAS

En el sentido evidente, el problema de la ruta más corta tiene que ver con la determinación de las ramas conectadas en una red de transporte que contribuyen, en conjunto, la distancia mas corta entre una fuente y un destino. Presentamos otros tipos de aplicaciones que se pueden representar por medio de modelos y resolver como un problema de la ruta mas corta.

EJEMPLO

Una compañía arrendadora de automóviles esta desarrollando un plan de reemplazo de su flotilla para los próximos cinco años. Un automóvil debe estar en servicio cuando menos un año antes de que se considere reemplazado. La tabla que se mostrara a continuación resume el costo de reemplazo por unidad (miles) como función del tiempo y e numero de años en operación. El costo incluye la compra, prima de seguro, operación y mantenimiento.

El problema se puede representar mediante la siguiente red.

Cada año est6a representado por un nodo

La longitud de una rama que uno dos nodos es igual al costo de reemplazo que se da en la tabla que se mostrara a continuación

1 2 3 4 5

1 4.0 5.4 9.8 13.7

2 4.3 6.2 8.1

3 4.8 7.9

4 4.9

ALGORITMO ACICLICO

Se dice que una red es acíclica si no tiene lazos; de otra manera, es cíclica. De los dos algoritmos presentados mas adelante, el algoritmo cíclico es mas general, ya que incluye el caso acíclico. El algoritmo acíclico es, sin embargo, más eficiente por que se necesitan hacer menos cálculos.

El algoritmo acíclico se basa en el uso de cálculos recursivos, que son la base para los cálculos de la programación dinámica.

EJEMPLO

Considere la siguiente red

El nodo 1 es le nodo inicial (fuente u origen) y el nodo 7 es el nodo terminal (sumidero o destino). Las distancias d_(ij )entre los nodos i y j se indican directamente sobre cada rama. Por ejemplo, d_12 es igual a 2. La red es acíclica por que no contiene lazos.

u_j = distancia mas corta entre el nodo 1 y el nodo j

Donde: u_1= 0, por definición. Los valores de u_j, j= 1, 2, 3……..n, se calculan en forma recursiva por medio de la formula siguiente:

u_j=min⁡〖 i〗 {█(la distancia u_i mas corta a un nodo i inmediatamente anterior,mas @la distancia d_ij entre l nodo actual j y su predecesor i)┤

= min i {u_j+ d_ij }

La formula recursiva implica que la distancia mas corta u_j al nodo j se puede determinar solo después de que se calcula la distancia mas corta al nodo predecesor i enlazado a j por un arco.

En la solución final del modelo de la ruta mas corta no es suficiente determinar solo la u_j del nodo j. En forma concurrente, debemos identificar también los nodos encontramos a lo largo de la ruta. Para lograr esto usamos un procedimiento de rotulación o bien etiquetado, que asocia el siguiente rotulo o etiqueta al nodo j:

Etiqueta del nodo j = {u_(j ),n}

Donde n es el nodo que precede inmediatamente a j y que da la distancia mas corta u_j, o sea,

u_j = min i {u_j+ d_ij }

= u_(n )+d_nj

Por definición, la etiqueta en el nodo 1 es {0, -}, lo que indica que le nodo 1 es la fuente.

Los cálculos proceden en etapas; cada etapa se identifica con un nodo distinto.

La tabla que se mostrara a continuación proporciona la secuencia de datos que conducen a la solución final. Los cálculos también se pueden resumir directamente en la red.

La ruta óptima se obtiene comenzando en el nodo 7 y procediendo hacia atrás, a través de los nodos, utilizando la información de los nodos. La siguiente secuencia demuestra el procedimiento:

(7) [13, 5] (5) [7, 2] (2) [2,1] (1)

Nodo j Calculo de u_j Etiqueta

1 u_1=0 [0,-]

2 u_2= u_1+ d_12=0+2=2,desde 1

[2,1]

3 u_3 〖=u〗_1+ d_13=0+4=4,desde 1

[4,1]

4 u_4 = min {u_(1 )+ d_(14 ),u_(2 )+ d_24,〖 u〗_3+ d_34 }

=min (0 + 10,2 + 11, 4 + 3)= 7, desde 3 [7,3]

5 u_5 = min {u_(2 )+ d_(25 ),u_(4 )+ d_45 }

=min {2 +5, 7+8}= 7, desde 2 [7,2]

6 u_6= min {u_(3 )+ d_(36 ),u_(4 )+ d_46 }

=min {4 +1, 7+7}= 5, desde 3 [5,3]

7 u_7= min {u_(5 )+ u_(57 ),u_(6 )+ d_57 }

=min {7 +6, 5+9}= 13, desde 5 [13,5]

El algoritmo, de hecho, proporciona la distancia mas corta entre el nodo 1 y cualquier otro nodo de la red.

ALGORITMO CICLICO (DE DIJKSTRA)

El algoritmo acíclico no funciona en forma correcta si la red contiene lazo dirigidos (circuitos). Para demostrar esto, consideremos la siguiente red, donde se forma un circuito con los nodos 2, 3 y 4. De acuerdo con las reglas del algoritmo acíclico es imposible evaluar cualesquiera de los nodos 2, 3 y 4 del lazo, por que el algoritmo necesita que se calcule la u_(i ) de todos los nodos que llegan al nodo j antes de que se puede evaluar u_j.

El algoritmo cíclico difiere del algoritmo acíclico en el sentido que permite tantas oportunidades como sean necesarias para revaluar un nodo. Cuando resulta evidente que se ha alcanzado la distancia mas corta a un nodo, este se excluye de cualquier consideración posterior. El proceso

...