[pt] Este trabalho busca desenvolver o método Simplex para
Redes na solução de
problemas de Fluxo de Custo Mínimo. Este método consiste
em uma adaptação do
método Simplex primal em que são exploradas as
características específicas da rede
subjacente ao problema ao se buscar a solução ótima em um
número finito de árvores
geradoras. A árvore geradora ótima será obtida
iterativamente através de sucessivas
melhorias na estrutura de cada árvore formada. A maior
eficiência do Simplex para Redes
se dá tanto no menor número de iterações necessárias para
se atingir o ótimo, quanto na
maior velocidade destas iterações, trata-se, portanto, de
um método bastante poderoso na
resolução de problemas de Fluxo de Custo Mínimo. Serão,
também, abordados aspectos
práticos da implementação do algoritmo além da aplicação
deste algoritmo implementado
em VBA (Visual Basic for Applications) em um problema
prático a título de
exemplificação. / [en] The current work intends to develop a Network Simplex
Method for solving
Minimum Cost Flow problems. Such method consists of a
primal Simplex Method
adaptation in which specific characteristics of the network
underlying the problem are
investigated by searching for the optimal solution within a
finite number of spanning
trees. The optimal spanning tree is iteratively obtained
through successive structure
improvements in each formed tree. The higher efficiency of
Network Simplex lies both in
fewer iterations necessary to achieve the optimum and in
the higher speed of these
iterations. Therefore, it is a powerful method for solving
Minimum Cost Flow Problems.
Practical aspects of implementing the algorithm will be
discussed, as well as the
algorithm´s implementation in VBA (Visual Basic for
Applications) through a practical
instance.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:13219 |
| Date | 01 April 2009 |
| Creators | JOAQUIM PEDRO DE V CORDEIRO |
| Contributors | JOSE EUGENIO LEAL |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | English |
| Type | TEXTO |
Page generated in 0.0019 seconds