MAC0325 Otimização Combinatória
OBJETIVOS: Estudo de problemas de otimização com estrutura de grafos.
PROGRAMA: O problema do transporte. Especialização do método simplex para redes. O problema do caminho mais curto: algoritmos de Dijkstra e de Ford. Fluxos em redes: fluxos de valor máximo (teorema de Ford-Fulkerson), fluxos de custo mínimo, e circulações viáveis. O método "out-of-kilter".
PRÉ-REQUISITOS: MAC0122 ou MAC0315.
PRÉ-REQUISITOS NÃO-OFICIAIS: MAC0338 e MAC0328.
CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS: 4 horas, 4 créditos-aula.
CRITÉRIO DE AVALIAÇÃO DA APRENDIZAGEM: Média ponderada de provas e exercícios.
BIBLIOGRAFIA BÁSICA:
- W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver, Combinatorial Optimization, John Wiley, 1998.
- R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.
- C.H. Papadimitrou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, 1982.
- E. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart & Winston, 1976.
- V. Chvátal, Linear Programming, Freeman, New York, 1983.
OBSERVAÇÃO: Disciplina optativa eletiva no currículo do BCC.
[Veja dados da disciplina no JúpiterWeb]