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

...