[pt] O problema do fluxo máximo multiterminal é uma extensão do conhecido
problema de fluxo máximo entre um nó origem e um nó destino de uma rede. Este
problema surge no contexto de fluxos em redes, tema que possui diversas
aplicações, especialmente nos campos de transporte, telecomunicações e energia.
No caso multiterminal, o fluxo máximo é calculado entre todos os pares de nós da
rede. No referente a uma rede simétrica, este problema pode ser resolvido,
obviamente, pela execução do algoritmo de fluxo máximo n(n − 1) 2 vezes, onde
n é o número de nós da rede. Os tradicionais métodos encontrados na literatura o
conseguem com apenas n − 1. O presente trabalho busca elaborar um algoritmo
capaz de resolver o problema multiterminal com uma complexidade menor do que
os métodos da literatura. A recente teoria da análise de sensibilidade, em que se
estuda a influência da variação de capacidade de uma aresta nos fluxos máximos
multiterminais, é utilizada para a construção do algoritmo. Técnicas dos
tradicionais métodos, como a de contração de nós, também compõem o método.
Ao final, o algoritmo é testado computacionalmente com todas as suas variações e
heurísticas adicionadas. Para um determinado caso, o algoritmo se mostrou com
eficiência semelhante a dos métodos tradicionais. Novas variações e heurísticas
são listadas para futuras pesquisas. / [en] The multi-terminal maximum flow problem is an extension of the well
known single source-single terminal maximum flow problem. These problems
arise in the context of network flows, theme which has various applications,
especially in the fields of transport, telecommunications and energy. In the multiterminal
case, the maximum flow is calculated between all pairs of nodes. Clearly,
this problem can be solved, in a symmetric network, by computing the maximum
flow algorithm n(n − 1) 2 times, where n is the number of nodes of the network,
but the traditional methods found in the literature can do it with only n − 1
computations. This paper seeks to elaborate an algorithm able to solve the multiterminal
problem with a complexity lower than the methods of the literature. The
recent theory of sensitivity analysis, which studies the influence of an edge
capacity variation on multi-terminals maximum flows, is employed on the
construction of the algorithm. Techniques of the traditional methods, such as the
contraction of nodes, are also part of the method. Finally, the algorithm is
computationally tested with all its variations and added heuristics. For a given
case, the algorithm showed an efficiency very close to the ones of traditional
methods. New variations and heuristics are listed for future research.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:18109 |
| Date | 19 August 2011 |
| Creators | JOAO PAULO DE FREITAS ARAUJO |
| Contributors | MADIAGNE DIALLO, MADIAGNE DIALLO, MADIAGNE DIALLO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0021 seconds