Nível:
Graduação
Nome da disciplina:
Fluxos em Redes
Número de Créditos:
4
Oferecimento:
A Critério da Unidade
Pré-requisito:
MS428
Ementa:
Terminologia de redes: problema de transporte e designação; problema de fluxo máximo; problema de fluxo com custo mínimo; método simplex. Fluxo em rede generalizada. Fluxo com restrições adicionais. Fluxo de multiprodutos.
Conteúdo / Programa:
Objetivo:
Estudo de problemas de otimização envolvendo redes. Modelagem de problemas práticos de otimização contínua e discreta utilizando conceitos de teoria de grafos e programação linear. Apresentação e comparação de algoritmos para resolver os problemas resultantes.
Conteúdo:
Noções de teoria dos grafos: Definições e terminologia, tipos de representação, matrizes de adjacência e incidência, listas de adjacência; métodos de busca: em profundidade e em largura; noções de complexidade de algoritmos.
Problema da árvore geradora mínima: Caracterizações equivalentes; algoritmos gulosos: Kruskal, Prim e Boruvka/Sollin. Problema de caminho mínimo: Algoritmos de Dijkstra e Floyd-Warshall. Problema de transporte. Problema de designação: algoritmo húngaro e algoritmo polinomial baseado em caminhos mínimos.
Problema de fluxo máximo: Teorema do fluxo máximo e capacidade de corte mínimo; algoritmo de caminhos aumentantes e algoritmo preflow-push. Problema de fluxo de custo mínimo: simplex para rede.
Objetivo:
Estudo de problemas de otimização envolvendo redes. Modelagem de problemas práticos de otimização contínua e discreta utilizando conceitos de teoria de grafos e programação linear. Apresentação e comparação de algoritmos para resolver os problemas resultantes.
Forma de Avaliação:
Por nota e frequência
Referência Bibliográfica:
[1] Ravindra K. Ahuja, Thomas L. Magnanti, e James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, 1993.
[2] M. S. Bazaraa, John J. Jarvis, e Hanif D. Sherali. Linear Programming and Network Flows. John Wiley & Sons, 4 a ed., 2010.
[3] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, e Cliford Stein. Algoritmos: Teoria e Prática. Elsevier, 2012.