Metodo De Programacion Lineal Para Acortamiento De Redes

METODO DE PROGRAMACION LINEAL PARA ACORTAMIENTO DE REDES.
INTRODUCCION
Las técnicas de flujo de redes están orientadas a optimizar situaciones vinculadas a las redes de transporte, redes de comunicación, sistema de vuelos de los aeropuertos, rutas de navegación de los cruceros, estaciones de bombeo que transportan fluidos a través de tuberías, rutas entre ciudades, redes de conductos y todasaquellas situaciones que puedan representarse mediante una red donde los nodos representan las estaciones o las ciudades, los arcos los caminos, las líneas aéreas, los cables, las tuberías y el flujo lo representan los camiones, mensajes y fluidos que pasan por la red. Con el objetivo de encontrar la ruta mas corta si es una red de caminos o enviar el máximo fluido si es una red de tuberías.VISTA GENERAL DE ALGUNAS APLICACIONES PRÁCTICAS DE LA OPTIMIZACIÓN DE REDES
1. Diseño de redes de telecomunicación (redes de fibra óptica, de computadores, telefónicas, de televisión por cable, etc.)
2. Diseño de redes de transporte para minimizar el costo total de proporcionar las ligaduras (vías ferroviarias, carreteras, etc.)
3. Diseño de una red de líneas de transmisión de energíaeléctrica de alto voltaje.
4. Diseño de una red de cableado en equipo eléctrico (como sistemas de computo) para minimizar la longitud total del cable.
5. Diseño de una red de tuberías para conectar varias localidades.
6. Diseño de una red de tuberías de gas natural mar adentro que conecta fuentes del golfo de México con un punto de entrega en tierra con el objetivo de minimizar el costo deconstrucción.
7. Determinación de la ruta más corta que une dos ciudades en una red de caminos existentes.
8. Determinar la capacidad anual de máxima en toneladas de una red de conductos de pasta aguada de carbón que enlaza las minas carboneras de Wyoming con las plantas generadoras de electricidad Houston. (Los conductos de pasta aguada de carbón transportan éste bombeando agua a travésde tubos adecuadamente diseñados que operan entre las minas de carbón y el destino deseado.)
9. Determinación del programa de costo mínimo de los campos petrolíferos a refinerías y finalmente a los campos de distribución. Se pueden enviar petróleo crudo y productos derivados de la gasolina en buques tanque, oleoductos y/o camiones. Además de la disponibilidad de la oferta máxima en los campospetrolíferos y los requisitos de demanda mínima en los centros de distribución, deben tomarse en cuenta restricciones sobre la capacidad de las refinerías y los modos de transporte.
MODELOS DE REDES
Los problemas de optimización de redes se pueden representar en términos generales a través de uno de estos cuatro modelos:
* Modelo de minimización de redes (Problema del árbol de mínimaexpansión).
* Modelo de la ruta más corta.
* Modelo del flujo máximo.
* Modelo del flujo del costo mínimo.
Modelo de minimización de redes
El modelo de minimización de redes o problema del árbol de mínima expansión tiene que ver con la determinación de los ramales que pueden unir todos los nodos de una red, tal que minimice la suma de las longitudes de los ramales escogidos. No se debenincluir ciclos en al solución del problema.
Para crear el árbol de expansión mínima tiene las siguientes características:
1. Se tienen los nodos de una red pero no las ligaduras. En su lugar se proporcionan las ligaduras potenciales y la longitud positiva para cada una si se inserta en la red. (Las medidas alternativas para la longitud de una ligadura incluyen distancia, costo y tiempo.)
2. Sedesea diseñar la red con suficientes ligaduras para satisfacer el requisito de que haya un camino entre cada par de nodos.
3. El objetivo es satisfacer este requisito de manera que se minimice la longitud total de las ligaduras insertadas en la red.
Una red con n nodos requiere sólo (n-1) ligaduras para proporcionar una trayectoria entre cada par de nodos. Las (n-1) ligaduras deben...