MAC0325  Otimização Combinatória

OBJETIVOS:  Ensinar técnicas para o tratamento de problemas de otimização combinatória, em especial aqueles que podem ser formulados como problemas em grafos.

PROGRAMA:  O escopo da otimização combinatória e programação inteira. Modelagem de vários problemas usando variáveis 0/1. O problema do transporte. Especialização do método simplex para redes. Aplicações: teorema de Hall, teorema de König, teorema de Dilworth. O problema do transporte capacitado: o método primal-dual. Algoritmos para fluxos máximos em redes. Fluxos de custo mínimo e circulações viáveis: o método "out-of-kilter". Estudo aprofundado de poliedros de alguns problemas não-unimodulares bem resolvidos (emparelhamentos, branchings, etc.).

PRÉ-REQUISITOS:  MAC0121 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]