Trasporte De Flujo De Redes

TRANSPORTE
FLUJO 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 todas aquellassituaciones 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.
Cuando se trata deencontrar el camino más corto entre un origen y un destino, la técnica, algoritmo o el modelo adecuado es el de la ruta más corta; aunque existen otros modelos de redes como el árbol de expansión mínima, flujo máximo y flujo de costo mínimo cada uno abarca un problema en particular. En este trabajo se mencionan los modelos de redes existentes y los problemas que abarca cada uno de ellos, ademásse describen losalgoritmos que aplican estos modelos para encontrar la solución optima al problema. Utilizando la terminología utilizada para representarlos como una red.

Problema de Transporte

Considere el siguiente problema de limpieza de nieve: la ciudad está dividida en comunas. Después de una tormenta de nieve, se debe sacar la nieve y botarla en un lugar conveniente. En Helsinki (laciudad del problema), esos lugares son grandes esplanadas con un sistema de secado artificial. Cada una de esos "destinos" tiene una capacidad. El objetivo es minimizar la distancia recorrida para transportar  la nieve. 
Este problema es un ejemplo de un problema de transporte. En tales problemas, existe un conjunto de nodos llamados fuentes y un conjunto de nodos llamados destinos. Todos los arcosvan desde el origen al destino. Existe un costo unitario (por unidad) asociado a cada arco. Cada fuente tiene un concepto de abastecimiento y cada destino maneja el concepto de demanda. Se asume que la cantidad total a abastecer es exactamente igual a la cantidad demandada. Para el problema de la nieve la red puede ser como se muestra en la figura  1.4.
   
Figura 1.4:Red de Transporte de NieveUn problema que corresponde al modelo de transporte puede ser el asignar clientes a un negocio para poder satisfacer las demandas. En tal caso los almacenes son las fuentes, los clientes son los destinos y los costos representan los costos de transporte por unidad.
Otro ejemplo sería:
Uno de los principales productos de la Compañía P&T son los duraznos en conserva. Los duraznos sonpreparados en 3 enlatadoras (Washington, Oregon y Minnesota) y luego se despachan en camiones para distribuirlos en tres supermercados en California, Utah, South Dakota, Nuevo México. Debido a que los costos de transporte han aumentado, la administración ha decidido hacer un estudio sobre ellos. Para la próxima estación se ha estimado el número de tarros de conserva generado en cada enlatadora, y lacantidad que requerirá cada almacén para satisfacer a sus clientes. Los costos de trasnporte desde la enlatadora a los almacenes se resume en la siguiente tabla.
 
veamos cuál sería el modelo de programación lineal para este problema. Sea   el número de camiones cargados que van desde la enlatadora i al almacén j, el problema sería:

Este es un ejemplo de modelo de transporte. Este problema tieneuna estructura interesante. Todos los coeficientes son 1 y cada variable aparece exactamente en 2 restricciones. Es esta estructura que hace que el algoritmo simplex sea extremadamente eficiente al resolverlo.
¿Qué define a un modelo de transporte?. En general el modelo de transporte tiene que ver con distribuir desde un grupo de centros de abastecimiento, llamados fuentes a un grupo de centros...