O Problema do Fluxo Mais Rápido

Abstract

Os problemas associados a transmissão de fluxo numa rede aparecem frequentemente em contextos práticos. Neste tipo de problemas, é importante a quantidade de fluxo transmitida mas também é importante o tempo necessário para fazer esta transmissão. Os modelos com fluxo estático (isto é, fluxo que não tem em conta a passagem do tempo) não são adequados para descrever problemas reais. Isto dá origem aos chamados fluxos dinâmicos, onde cada arco tem associado um tempo de transmissão. Seja N = (V;A) uma rede dirigida, com conjunto de nós V e conjunto de arcos A. Cada arco e 2 A tem associada uma capacidade ce e um tempo de transmissão e. O problema do fluxo mais rápido consiste em encontrar na rede N um fluxo dinâmico f, que envie d unidades de fluxo de um nó de origem r para um nó de chegada s, no mínimo tempo possível. O tempo que um fluxo mais rápido de valor d demora a percorrer a rede é designado por tempo de transmissão T (d). Neste trabalho são estudados dois algoritmos propostos em trabalhos anteriores, baseados na relação entre o fluxo mais rápido e o fluxo dinâ- mico máximo. Estes algoritmos são duas variações da pesquisa binária. São apresentados alguns resultados computacionais, de onde se conclui que estes algoritmos são bastante e cientes e podem ser usados para resolver problemas de larga escala.

The problems associated with transmission of flows are very common in practical contexts. In these types of problems is important the amount of flow to be transmitted but also the amount of time needed to transmit this flow. The models with static flows (flows that don't consider time) aren't adequate to describe real life problems. These leads to dynamic flows, where a transmission time is attached to each arc of the network. Let N = (V;A) be a directed network, with set of nodes V and set of arcs A. Each arc e 2 A has a capacity ce and a transmission time e. The quickest flow problem is to find in network N a dynamic flow f, that sends d units of flow from a given source node r to a given sink node s, in minimum possible time. The time that a quickest flow of value d needs to arrive at s is called minimum transmission time T (d). In this work, we study two algorithms that are proposed in previous works and that are based in the relationship between maximum dynamic fows and quickest fows. These algorithms are variations of the usual binary search method. We present some computational results that show that these algorithms are very eficient and can be used to solve large instance problems.