Please use this identifier to cite or link to this item:
https://hdl.handle.net/10316/99581
Title: | O Problema do Fluxo Mais Rápido | Authors: | Batalha, Adriana Pratas | Orientador: | Santos, José Luis | Keywords: | Fluxo dinâmico; fluxo máximo; fluxo mais rápido; pesquisa binária | Issue Date: | Jun-2013 | Place of publication or event: | Coimbra | 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. |
URI: | https://hdl.handle.net/10316/99581 | Rights: | openAccess |
Appears in Collections: | FCTUC Matemática - Teses de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Tese_AdrianaBatalha.pdf | 989.32 kB | Adobe PDF | View/Open |
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.