Estudio de flujos multiproducto

Abstract

En este trabajo se estudian problemas de flujo en redes. Tras una introducción a teoría de grafos y optimización, se trata la teoría básica de flujos incluyendo el teorema del flujo máximo y corte mínimo y los algoritmos de Ford-Fulkerson y Edmonds-Karp para resolver problemas de flujo clásico. A continuación, se estudian problemas de flujo multiproducto y se demuestra e implementa un algoritmo de P. Liu (2020) para su resolución.

In this bachelor thesis, flow problems in networks are studied. After a graph theory and optimization introduction, the basic theory of flows is discussed, including the max-flow-min-cut theorem and Ford-Fulkerson and Edmonds-Karp algorithms to solve problems of classical flow. Next, multicommodity flow problems are studied and an algorithm by P. Liu (2020) is demonstrated and implemented to solve them.