Notícias
Este site contém informações sobre a disciplina PCC174 - Otimização Linear e Inteira, oferecida de forma remota excepcionalmente por conta da crise sanitária do Coronavírus.
Embora bastante informação sobre a disciplina seja disponibilizada aqui, exercícios obrigatórios, aulas práticas e demais atividades serão disponibilizadas exclusivamente por meio da plataforma Moodle.
Slides / Aulas
Importante: o conteúdo das aulas práticas e os vídeos 'extras' (com dicas e resolução de exercícios) serão disponibilizados apenas via Moodle.
Slides e vídeos das aulas teóricas da disciplina:
Aula T-01 - Apresentação
- Aula T-02 - Modelagem e método gráfico
- Aula T-03 - Conceitos básicos e modelagem
- Aula P-01 - Aula prática com resolvedores
- Aula T-04 - Algoritmo Simplex
- Aula P-02 - Aplicando o simplex passo-a-passo
- Aula T-05 - Algoritmo Simplex (2)
- Aula P-03 - Aula prática com resolvedores
- Aula T-06 - Dualidade e análise de sensibilidade
- Aula P-04 - Aula prática com resolvedores
- Aula T-07 - Variáveis inteiras
- Aula P-05 - Modelagem com variáveis inteiras
- Aula T-08 - Limites e branch-and-bound
- Aula P-06 - Aula prática com resolvedores
- Aula T-09 - Desigualdades válidas
- Aula P-07 - Aula prática com resolvedores
- Aula T-10 - Algoritmos de plano de corte
- Aula P-08 - Aula prática com resolvedores
- Aula T-11 - Lifting e matrizes ideais
- Aula P-09 - Aula prática com resolvedores
- Aula T-12 - Geração de colunas
- Aula P-10 - Aula prática com resolvedores
- Aula T-13 - Decomposição de Dantzig-Wolfe
- Aula P-11 - Aula prática com resolvedores
- Aula T-14 - Branch-and-price
- Aula P-12 - Revisão para Prova 02
Plano de Aulas
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.
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étodo 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 (50% da nota)
- Prova 1 (28/04/2021): 25% da nota
- Prova 2 (07/07/2021): 25% da nota
Aulas Práticas (20% da nota)
- Média das notas obtidas com os entregáveis das aulas práticas.
Trabalho Prático (30% da nota)
- Problema deve ser definido em comum acordo entre o aluno e o professor da disciplina até o dia 28/04/2021.
- Resultados do trabalho serão apresentados em um seminário no dia 14/07/2021.
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.
- DANTZIG, George B. Linear programming and extensions. Princeton, N.J.: Princeton University Press 1963.
- 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.