Equilibrios Dinámicos de Flujo en Redes

Abstract

El tema principal de esta memoria es estudiar características y propiedades de equilibrios, en el contexto de flujos dinámicos en redes. En el caso del modelo de flujo estático, se conocen varios resultados relacionados con equilibrios. El problema del modelo estático es que no contempla las fluctuaciones temporales, que es una característica importante de los problemas de flujos en redes que aparecen en varias aplicaciones, tales como modelos de control de tráfico, sistemas de producción y redes de comunicación. En tales aplicaciones, el flujo que atraviesa los arcos es una cantidad que varía en el tiempo. Más aún, el flujo no atraviesa de forma instantánea la red, sino que requiere una cierta cantidad de tiempo para atravesar cada arco. Los modelos que contemplan estos aspectos son los llamados flujos dinámicos, también denominados flujos a través del tiempo.

En este trabajo estudiamos modelos de flujos dinámicos en tiempo continuo en redes con capacidades, donde se contempla congestión en los arcos, y definimos la noción de equilibrios para este tipo de flujos. Luego estudiamos algunas propiedades de los flujos dinámicos en equilibrio. Uno de los principales aportes de este trabajo son resultados de existencia de equilibrios.

En el caso de determinados tipos de instancias, el resultado de existencia es de carácter algorítmico. El algoritmo encargado de hacer esto tiene que, de forma iterativa, extender a través del tiempo un flujo dinámico en equilibrio. Como parte de este trabajo, describimos algunos resultados en torno a la complejidad computacional de este algoritmo. Otro aporte importante es un resultado relacionado con la unicidad de flujos dinámicos en equilibrio, dentro de una cierta familia de flujos dinámicos.