Flujo maximo

Objetivos
General
* aprender el problema de flujo máximo
Especifico
* aplicar el problema de flujo máximo
* determinar el flujo máximo
* utilizar win QSB para determinar la solución optima
* apropiarse de todos los conceptos sobre el problema de flujo máximo
Introducción
Los modelos de redes son aplicables a una extensa variedad de problemas de decisión, los cuales puedenser modelados como problemas de optimización de redes que pueden ser eficiente y efectivamente resueltos. Algunos de estos problemas de decisión son realmente problemas físicos, tales como el transporte o flujo de bienes materiales. Sin embargo, muchos problemas de redes son más que una representación abstracta de procesos o actividades, tales como el camino critico en las actividades entre lasredes de un proyecto gerencial.
La familia de redes de los problemas de optimización incluye los siguientes prototipos de modelos: Problemas de asignación, camino crítico, flujo máximo, camino más corto, transporte y costo mínimo de flujos. Los problemas son establecidos fácilmente mediante el uso de arcos de redes y de los nodos.
* Que es un Nodo? Es usualmente llamado vértice, o punto. Esusualmente representado por un círculo. En las redes de transporte, estos deberían ser las localidades o las ciudades en un mapa.

* Que es un Arco? Es usualmente llamado borde o flecha. Este podría ser directo o indirecto. La cabeza es el destino, y la cola el origen. La cabeza y la cola son nodos que pueden estar tanto al origen como al final. En las redes de transporte, los arcos podríanser los caminos, los canales de navegación en un rio, o los patrones de vuelo de un avión. Los arcos proporcionan la conectividad entre los nodos. Una calle de una sola dirección podría ser representada por un arco, mientras que una calle de dos direcciones podría representada por un arco sin dirección o por dos arcos que apuntan a direcciones opuestas.

Marco teórico
Problema de flujo máximo:En este tipo de problemas es necesario considerar muchas combinaciones de rutas (flujos asignados a cada ruta) para encontrar las rutas que maximicen el flujo.
En términos generales el problema de flujo máximo se puede describir como sigue:
* se debe considerar una red dirigida.
* Todo flujo a través de una red conexa dirigida se origina en un nodo llamado fuente y termina en otro nodollamado destino.
* Los nodos restantes son nodos de trasbordo y por lo tanto, deben cumplir con la relación de equilibrio, flujo que entra = flujo que sale.
* Se permite el flujo a través de un arco solo en la dirección indicada por la flecha, donde la cantidad máxima del flujo está dada por la cantidad del arco y no debe ser excedida . En la fuente, todos los arcos señalan hacia afuera.En el destino, todos señalan hacia el nodo.
* El objetivo es maximizar la cantidad total de flujo de la fuente al destino. Esta cantidad se mide en cualquiera de las dos, de maneras equivalente, esto es, la cantidad que sale de la fuente o la cantidad que entra al destino.
Ahora se mencionan algunas aplicaciones comunes del problema de flujo máximo:
* Maximizar al flujo a través de lared de distribución de la compañía de sus fábricas a sus clientes.
* Maximizar el flujo a través de la red de suministro de la compañía de los proveedores a las fábricas.
* Maximizar el flujo de petróleo por un sistema de tuberías.
* Maximizar el flujo de agua través de un sistema de acueductos.
* Maximizar el flujo de vehículos por una red de transporte.
Para algunas de estasaplicaciones el flujo a través de la red se puede originar en más de un nodo y también puede terminar en más de un nodo, aunque el problema de flujo máximo puede tener solo un origen y un destino. Por ejemplo una red de distribución de una compañía tiene varias fábricas y múltiples clientes. Se usa una reformulación ingeniosa para ajustar esta situación al problema de flujo máximo. Se trata de...