Notícias
12/08/2019
-
Notas finais disponíveis.
- As aulas teóricas ocorrerão na Sala 204 do Pavilhão de Aulas a partir das 10h10.
- As aulas prática ocorrerão no Laboratório COM30 do ICEB.
- Disponibilizado o plano de aulas da disciplina, contendo o cronograma do semestre.
- Consulte, no site, os objetivos e a ementa da disciplina, a bibliografia recomendada e os critérios utilizados na avaliação dos alunos.
Slides / Aulas
Apresentação do Curso- Aula 02: Introdução.
- Aula 03: Método gráfico e conceitos.
- Aula 04: Modelagem e Python-MIP (código: exemplo_1.py e exemplo_2.py).
- Aula 05: Algoritmo Simplex (Parte 1).
- Aula 06: Modelagem e Python-MIP (código: exemplo_1.py).
- Aula 07: Algoritmo Simplex (Parte 2).
- Aula 08: Dualidade (código: exemplo_1.py).
- Aula 09: Análise de sensibilidade.
- Aula 10: Revisão (apresentação extra com exemplos de modelagem).
Aula 11: Prova 01.- Aula 12: Modelagem e variáveis inteiras.
- Aula 13: Branch-and-bound.
- Aula 14: Aula prática sobre branch-and-bound.
- Aula 15: Desigualdades válidas.
- Aula 16: -
- Aula 17: Planos de corte.
- Aula 18: Aula prática sobre planos de corte.
- Aula 19: Lifting e matrizes ideais.
- Aula 20: Aula prática sobre modelagem e planos de corte.
- Aula 21: Revisão.
- Aula 22: Prova 02.
- Aula 23: Formulações com número exponencial de variáveis.
- Aula 24: Geração de colunas.
- Aula 25: Decomposição de Dantzig-Wolfe.
- Aula 26: Aula prática: implementação de geração de colunas.
- Aula 27: Branch-and-price.
- Aula 28: Aula prática sobre branch-and-price.
- Aula 29: Decomposições.
- Aula 30: Revisão.
- Aula 31: Prova 03.
- Aula 32: Aula de exercícios e correção da Prova 03.
- Aula 33: Apresentação do Trabalho Prático.
- Aula 34: Apresentação do Trabalho Prático.
- Aula 35: Apresentação do Trabalho Prático.
- Aula 36: Apresentação do Trabalho Prático.
Código / Práticas
- Prática de B&B: mochila_bnb.py, mochila.csv
- Prática de Planos de Corte: mochila.csv
- Prática de Planos de Corte e Modelagem: tsp.py (usando callbacks: tsp_callback.py)
- Prática de Geração de Colunas: cg.py
- Prática de Branch-and-price: pag.py
Exercícios
Exercícios Obrigatórios
- Disponibilizados nos slides utilizados durante as aulas.
Exercícios Opcionais
- Lista 01: Modelagem (disponibilizada por Haroldo G. Santos).
- Lista 02: Programação Inteira.
- Lista 03: Geração de colunas e branch-and-price.
Plano de Aulas
- Aula 01 - Introdução ao curso
- Aula 02 - Modelagem em programação linear
- Aula 03 - Método gráfico e conceitos
- Aula 04 - Formulações e exemplos
- Aula 05 - Algoritmo Simplex
- Aula 06 - Resolvedores de programação linear
- Aula 07 - Algoritmo Simplex (Parte 2)
- Aula 08 - Dualidade
- Aula 09 - Análise de sensibilidade
- Aula 10 - Aula de exercícios e revisão
- Aula 11 - Prova 01
- Aula 12 - Programação inteira
- Aula 13 - Modelagem em programação inteira
- Aula 14 - Aula prática com resolvedores
- Aula 15 - Limites e enumeração implícita
- Aula 16 - Formulações fortes e fracas
- Aula 17 - Desigualdades válidas
- Aula 18 - Algoritmos de planos de corte
- Aula 19 - Aula prática com resolvedores
- Aula 20 - Aula de exercícios e revisão
- Aula 21 - Prova 02
- Aula 22 - Limites e relaxações
- Aula 23 - Formulações com número exponencial de variáveis
- Aula 24 - Geração de colunas
- Aula 25 - Decomposição de Dantzig-Wolfe
- Aula 26 - Formulações e exemplos
- Aula 27 - Aula prática com resolvedores
- Aula 28 - Branch-and-price
- Aula 29 - Outras decomposições
- Aula 30 - Aula de exercícios e revisão
- Aula 31 - Prova 03
- Aula 32 - Apresentação de trabalho prático
- Aula 33 - Apresentação de trabalho prático
- Aula 34 - Apresentação de trabalho prático
- Aula 35 - Apresentação de trabalho prático
- Aula 36 - Apresentação de trabalho prático
- Aula 37 - Exames substitutivos
Objetivos / Ementa
Objetivo Geral
- Apresentar ao aluno diversos aspectos práticos e teóricos de otimização linear e inteira.
- Ensinar as técnicas de modelagem de problemas em diversas áreas de aplicação.
- Apresentar os métodos de resolução e os programas computacionais para problemas lineares e inteiros.
Ementa
- Modelagem em Programação Linear
- Algoritmo Simplex
- Dualidade
- Análise de sensibilidade
- Geração de colunas
- Métodos de decomposição de Dantzig-Wolfe
- Modelagem em Programação Inteira
- Enumeração Implícita
- Planos de Corte
- Limites e Relaxações
Avaliação
Provas (60% da nota)
- Prova 1 (17/09/2019): 20% da nota
- Prova 2 (22/10/2019): 20% da nota
- Prova 3 (26/11/2019): 20% da nota
Trabalhos Práticos (40% da nota)
- Problema deve ser definido em comum acordo entre o aluno e o professor da disciplina até o dia 19/10/2019.
- Apresentação de resultados no final do semestre (relatório e aulas de seminário).
Bibliografia
Bibliografia Básica
- MACULAN, Nelson; FAMPA, Marcia H. C. Otimização linear. Brasília, DF: Ed. UnB, 2006. 310 p. ISBN 8523009272.
- WOLSEY, Laurence A. Integer programming. New York: John Wiley & Sons 1998. xviii, 264 p. (Wiley-interscience series in discrete mathematics and optimization). ISBN 0471283665
- CHVATAL, Vasek. Linear programming. New York: W. H. Freeman c1983. xiii, 478 p. (A series of books in the mathematical sciences). ISBN 0716715872
Bibliografia Complementar
- JÜNGER, M. 50 years of integer programming, 1958-2008: the early years and state-of-the-art surveys. Heidelberg: Springer 2010. 803 p.
- DANTZIG, George B. Linear programming and extensions. Princeton, N.J.: Princeton University Press 1963. xvi, 632 p.
- KARLOF, John K. Integer programming: theory and practice. Boca Raton, Fla.: London: CRC, 2006. 316 p. (The Operations Research Series). ISBN 9780849319143
- GOLDBARG, Marco Cesar; LUNA, Henrique Pacca L. Otimização combinatória e programação linear: modelos e algoritmos. Rio de Janeiro: Campus c2000. 649p ISBN 8535205411
- LEE, Jon. A first course in combinatorial optimization. Cambridge, UK: New York: Cambridge University Press 2004. 211 p. (Cambridge texts in applied mathematics). ISBN 0521811511.
- DASGUPTA, Sanjoy; PAPADIMITRIOU, Christos H.; VAZIRANI, Umesh Virkumar. Algoritmos. Sao Paulo: McGraw-Hill, 2009. 320 p. ISBN 9788577260324.