Algoritmos de tipo ''subasta'' para problemas de flujo en redes.

García Martínez, Alicia
Mateo Collazos, Pedro Mariano (dir.)

Universidad de Zaragoza, CIEN, 2022
Departamento de Métodos Estadísticos, Área de Estadística e Investigación Operativa

Graduado en Matemáticas

Resumen: Los problemas lineales de flujo en redes tienen gran importancia en el área en la que nos centraremos, la Investigación Operativa. Entre los muchos problemas de flujo que nos podemos encontrar vamos a focalizar el trabajo en dos de ellos: el problema de asignación y el problema de flujo a costo mínimo.
Los algoritmos que resuelven estos dos problemas se basan en Teoría de Grafos y hasta finales de los años setenta había fundamentalmente dos tipos de algoritmos que conseguían optimizar los problemas de flujo en redes: el método simplex y el método del simplex-dual .
Más tarde se fueron desarrollando otro tipo de algoritmos que desafiaban a los ya nombrados, tanto desde el punto de vista práctico como desde el punto de vista teórico. En el presente trabajo nos centraremos en uno de ellos, el algoritmo de subasta.
A lo largo de los capítulos, además de explicar detalladamente la casuística de los dos problemas que tratamos, desarrollamos teóricamente el algoritmo de subasta para cada uno de ellos.
Por último, realizamos una implementación en FORTRAN del algoritmo de subasta para el problema de flujo a costo mínimo y hacemos con él un pequeño experimento para analizar su funcionamiento.

Tipo de Trabajo Académico: Trabajo Fin de Grado