Linear and Integer Programming (2019-2) - Portuguese only *

Notícias

12/08/2019

  • 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

Código / Práticas

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.

Plano de Aulas

(Seu browser não suporta imagens vetoriais SVG)

  • 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.