Otimização Linear e Inteira (2021-1)

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óriosaulas 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:

Plano de Aulas

(Seu browser não suporta imagens vetoriais SVG)

Exercícios

Exercícios Obrigatórios

  • Disponibilizados nos slides utilizados durante as aulas.

Exercícios Opcionais

  • Icon Lista 01: Modelagem (disponibilizada por Haroldo G. Santos).
  • Icon Lista 02: Programação Inteira.
  • Icon 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.