UFJF - Universidade Federal de Juiz de Fora

Plano de ensino

Disciplina: DCC033 - FLUXO EM REDES

Créditos: 4

Departamento: DEPTO DE CIENCIA DA COMPUTACAO /ICE

Ementa 1. Problemas do Caminho Mínimo
2. Problema de Fluxo Máximo
3. Problema de fluxo compatível a custo mínimo
4. Problemas de Atribuição e Problema de Transporte
Conteúdo 1) Problemas do Caminho Mínimo
O Modelo de Caminho Mínimo. Algoritmo de Dijkstra, Ford e Dantzig. Algoritmo de Floyd e Cascata. Interpretação segundo Programação Linear. Análise de Complexidade.

2) Problema de Fluxo Máximo
O Modelo de Fluxo. Algoritmo de Caminhos de Fluxo. Algoritmo de Ford-Fulkerson-Rotulação. Algoritmo DMKM. Interpretação segundo programação linear. Análise de Complexidade.

3) Problema de fluxo compatível a custo mínimo
Definições básicas. Método simplex para o problema de redes. Algoritmo Out-of-Kilter. Problema de Multi-Fluxos-Decomposição. Análise de Complexidade.

4) Problemas de Atribuição e Problema de Transporte
Definições Básicas. Método Simplex para o problema de transporte. O problema de atribuição. Algoritmo Hungariano. Análise de Complexidade.
Bibliografia - AHUJA, R. K. Network flows - Theory, algorithms and applications. Prentice Hall. 1993.
- BAZARAA, M.S. e JARVIS, J.J. Linear Programming and Networks Flows, John Wiley & Sons, New York, 2010, 4a Edition.
- NEWMAN, M.E.J. Networks - Oxford, 2010.
Bibliografia (continuação)
Bibliografia complementar - NEMAHUSER, G. L.; Wolsey, L. Integer and combinatorial optimization. John Wiley. 1999.
- TAHA, H. A. Pesquisa Operacional, Pearson. 8a. Edição. 2008
- GOLDBARG, M. e GOLDBARG, E. Grafos - Conceitos, Algoritmos e Aplicações. Campus Elservier. 1ed. 2012.
- SIERKSMA, GERARD. Linear and integer programming: Theory and Practice, Marcel Dekker, New York, 2002, 2nd, Edition.
- GROSS, J. L., YELLEN, J. Graph Theory and Its Applications, Second Edition, 2010
Voltar