Antología de Investigación de Operaciones
Ingeniería en Sistemas Computacionales
de ida. Para cada camino, la dirección del viaje de ida se indica mediante una flecha en la siguiente figura. El número que aparece en la base de la flecha proporciona el límite superior de ese camino en la dirección de salida de la estación. Dados los límites, una solución factible es mandar 7 camiones al día, 5 por la ruta O→B→E→T, 1 por la ruta O→B→C→E→T y 1 por la ruta O→B→C→E→D→T. Esta solución bloquea el uso de cualquier ruta que comience con O→C – por que las capacidades de E→T y E→D están saturadas-. Es sencillo encontrar mejores soluciones factibles. Es necesario considerar muchas combinaciones de rutas – y el número de viajes asignados a cada una – para encontrar la( s) ruta( s) que maximicen el número de viajes al día. Este tipo de problemas se conoce como problemas del flujo máximo.
En términos generales, el problema de flujo máximo se puede describir de la siguiente manera.
1. Todo flujo a través de una red conexa dirigida se origina en un nodo, llamado Fuente, y termina en otro nodo llamado destino – la fuente y el destino en Seervada Park son la entrada en el noo O y el morador en el nodo T, respectivamente-.
2. Los nodos restantes son nodos de trasbordo – en el problema de Seervada Park son los nodos A, B, C, D y E –
3. Se permite el flujo a través de un arco sólo en la dirección indicada por la flecha, donde la cantidad máxima de flujo está dada por la capacidad del arco. En la fuente, todos los arcos señalan hacia afuera. En el destino, todos los arcos señalan hacia el nodo.
4. El objetivo es maximizar la cantidad total de flujo de la fuente al destino. Esta cantidad se mide en cualquiera de las dos maneras equivalentes, esto es, la cantidad que sale de la fuente o la cantidad que entra al destino.
Algunas aplicaciones
A continuación se mencionan algunos tipos de aplicaciones comunes del problema del flujo máximo.
1. Maximizar el flujo a través de la red de distribución de una compañía desde sus fábricas hasta sus clientes.
2. Maximizar el flujo a través de la red de suministros de una compañía de proveedores a las fábricas. 3. Maximizar el flujo de petróleo por un sistema de tuberías. 4. Maximizar el flujo de agua a través de un sistema de acueductos. 5. Maximizar el flujo de vehículos por una red de transporte.
En algunas de estas aplicaciones, 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 uno, aunque en el problema de flujo máximo puede tener sólo un origen y un destino. Por ejemplo, una red de distribución de una compañía tiene varias fábricas y múltiples clientes. En este caso se recurre a una reformulación ingeniosa para ajustar esta situación al problema. Se trata de aumentar la red original para que incluya una fuente ficticia, un destino ficticio y algunos arcos nuevos. La fuente ficticia se maneja como el nodo que da origen a todo el flujo que en realidad se origina en algunos otros nodos. En cada uno de estos otros nodos se inserta un nuevo arco que va desde la fuente ficticia hasta este nodo, donde la capacidad del arco es igual al flujo máximo que puede originar en este nodo. De manera similar, el destino ficticio se trata como al nodo que absorbe todo el flujo que, en realidad, termina en algún otro nodo. Por lo tanto, s coloca un nuevo arco desde cada uno de los otros nodos hasta el destino ficticio con capacidad igual al máximo que en realidad termina en este nodo. Debido a estos
49