Plano de Ensino
Disciplina: DCC033 - FLUXO EM REDES
Horas Aula: 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
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.
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.
- 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)
Não informado
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
- 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