Análisis, diseño e implementación de un software que determine la solución al problema del flujo máximo aplicando el algoritmo de Ford-Fulkerson

Abstract

El presente proyecto de fin carrera esboza una solución informática al problema del flujo máximo, para lo cual se ha optado por utilizar el algoritmo de Ford-Fulkerson, al ser este el más conocido y difundido, y que permite llegar a una solución exacta del problema en un tiempo relativamente corto. Dicho problema tiene una amplia gama de aplicaciones, que van desde cálculo de rutas disjuntas para redes de comunicaciones, circulación con capacidad, programación de líneas aéreas, selección de proyectos, entre otras. El problema del flujo máximo fundamentalmente consiste en: dado una red (o grafo) de arcos y nodos, cada arco con una capacidad determinada, y con un nodo fuente y otro sumidero, se trata de hallar la cantidad máxima de material (flujo) que puede circular desde el nodo fuente hasta el nodo sumidero, de manera que el flujo individual que va por cada arco no supere la capacidad de dicho arco; esto último es conocido como restricción de capacidad del arco. Como se verá en la memoria descriptiva, este problema se reduce a uno de investigación de operaciones, es decir, un problema de maximización de una expresión dependiente de una serie de variables, las cuales están sujetas a un conjunto de restricciones. El algoritmo elegido para la implementación de la solución es el de Ford-Fulkerson, el cual fue propuesto en 1956 en un artículo científico por los matemáticos estadounidenses Lester Randolph Ford Jr. y Delbert Ray Fulkerson, quienes establecieron y demostraron el teorema del flujo máximo - corte mínimo, fundamental para la justificación del algoritmo como proveedor de la solución. Como se dijo en el párrafo inicial del resumen, existe una vasta y variada cantidad de contextos que pueden modelarse como un problema de flujo máximo, las principales serán brevemente explicadas en la memoria descriptiva, y se deja como trabajo futuro la particularización de esta solución a alguna de las mencionadas situaciones.