MAC0325 Otimização Combinatória
Por | EmOBJETIVOS: 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]
Oferecimentos recentes da disciplina: 1998/2, 2000/2.