Problema del Flujo Máximo (I)

Recuérdese que el tercer problema al que se enfrenta el administrador de Seervada Park (véase la sección 10.1) durante la temporada pico es determinar las rutas de algunos viajes de tranvía desde la entrada del parque (estación O en la figura 10.1) al mirador (estación T), de manera que el número de viajes diarios sea mínimo. (Cada tranvía regresará por la misma ruta que tomó de ida, por lo que el análisis se hará sólo sobre los viajes de ida.) Se impusieron límites superiores estrictos sobre el número de viajes de ida permitidos en cada dirección para cada ruta individual. Los límites se muestran en la figura 10.5, en la que los números que aparecen al lado de cada estación sobre los caminos dan el límite superior para ese camino en la dirección de salida de la estación. Por ejemplo, sólo se permite un viaje al día de la estación A a la estación B, pero también se permite otro de la estación B a la estación A. Dados los límites, una solución factible es mandar siete tranvias al día, cinco por la ruta O→ B→ E→ T, uno por la ruta O→ B→ C→ E→ T y otro por O→ B→ C→ E→ D→ T. Pero esta solución bloquea el uso de cualquier ruta que comience con O→ C (porque las capacidades de E→ T y E→ D están saturadas) Es sencillo encontrar mejores soluciones factibles. Es necesario considerar muchas combinaciones o rutas (y el número de viajes asignados a cada una) para encontrarla o las que maximicen.

Con la terminología que se introdujo en la sección 10.2, el problema del flujo máximo se puede describir formalmente como sigue. Considérese una red dirigida y conexa que tiene un solo nodo fuente y un solo nodo destino, y el resto son nodos de trasbordo. Dada la capacidad en los arcos, el objetivo es determinar el patrón factible que fluye a través de la red que maximiza el flujo total, desde el nodo fuente al nodo destino.