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. / Tesis
| Identifer | oai:union.ndltd.org:PUCP/oai:tesis.pucp.edu.pe:123456789/4538 |
| Date | 13 May 2013 |
| Creators | Arangoitia Fernández Baca, Jorge Víctor |
| Contributors | Kong Moreno, Maynard Jorge |
| Publisher | Pontificia Universidad Católica del Perú |
| Source Sets | Pontificia Universidad Católica del Perú |
| Language | Spanish |
| Detected Language | Spanish |
| Type | info:eu-repo/semantics/bachelorThesis |
| Format | application/pdf |
| Source | Pontificia Universidad Católica del Perú, Repositorio de Tesis - PUCP |
| Rights | Atribución-NoComercial-SinDerivadas 2.5 Perú, info:eu-repo/semantics/openAccess, http://creativecommons.org/licenses/by-nc-nd/2.5/pe/ |
Page generated in 0.0023 seconds