MAC-325 OTIMIZAÇÃO COMBINATÓRIA

• OBJETIVOS: Estudo de problemas de otimização com estrutura de grafos. P>
• CONTEÚDO: 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: MAC-122.

• CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS: 4 horas, 4 créditos.

• CRITÉRIO DE AVALIAÇÃO DA APRENDIZAGEM: Média ponderada de provas e exercícios.

• BIBLIOGRAFIA BÁSICA: E. Lawler, COMBINATORIAL OPTIMIZATION: NETWORKS AND MATROIDS, Holt, Rinehart & Winston, 1976 C.H. Papadimitrou, K. Steiglitz, COMBINATORIAL OPTIMIZATION: ALGORITHMS AND COMPLEXITY, Prentice-Hall, 1982 V. Chvátal, LINEAR PROGRAMMING, Freeman, New York, 1983 M.S. Bazaraa, J.J. Jarvis, LINEAR PROGRAMMING AND NETWORK FLOWS, John Wiley, 1977.