MAC0315  Otimização Linear

Por | Em

Até 2016 se chamou MAC0315 Programação Linear.

OBJETIVOS:  Apresentar os conceitos básicos, teóricos e algorítmicos, da resolução de problemas de otimização linear.

PROGRAMA RESUMIDO:  O problema de otimização linear consiste em encontrar valores que minimizem uma função linear dada dentre aqueles valores que satisfazem um conjunto de restrições lineares dadas. Nesta disciplina são estudadas aplicações, teoria e algoritmos de otimização linear.

PROGRAMA:  Introdução: Modelagem de problemas de otimização linear. Representação gráfica e solução gráfica. Geometria de otimização linear: Poliedros e conjuntos convexos. Pontos extremos, vértices e soluções viáveis básicas. Poliedros no formato padrão. Degenerescência. Existência de pontos extremos. Otimalidade de pontos extremos. O método Simplex: Condições de otimalidade. Desenvolvimento do método Simplex. Implementação do método Simplex (implementação trivial, Simplex Revisado e tableau). Anti-ciclagem: ordem lexicográfica e regra de Brand. Encontrando uma solução viável básica inicial. Dualidade: O problema dual. O teorema de dualidade. Variáveis duais ótimas como custos marginais. Problemas no formato padrão e o método Simplex Dual. Análise de sensibilidade.

RESPONSÁVEIS:  Ernesto Julián Goldberg Birgin, Gabriel Haeser, Júlio Michael Stern, Leônidas de Oliveira Brandão, Marcelo Queiroz, Walter Figueiredo Mascarenhas.

PRÉ-REQUISITOS:  MAT0122  ou MAT3211.

CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS:  4 horas, 4 créditos-aula.

CRITÉRIO DE AVALIAÇÃO DA APRENDIZAGEM: 
Método: Provas e tarefas que podem ou não envolver programação.
Critério: Média ponderada de provas e tarefas.
Norma de recuperação: Média ponderada da nota final e de provas e/ou tarefas de recuperação.

BIBLIOGRAFIA BÁSICA: 

  • M.S. Bazaraa, J.J. Jarvis, H.D. Sherali, Linear programming and Network Flows, 4th edition, Wiley, New York, NY, 2009.
  • D. Bertsimas, J.N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, Belmont, MA, 1997.
  • V. Chvátal, Linear Programming, W.H. Freeman, New York, NY, 1983.
  • G.B. Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, NJ, 1963.

OBSERVAÇÃO:  Disciplina optativa eletiva no currículo do BCC. Disciplina obrigatória nos currículos do BMA e BMAC.

 

[Veja dados da disciplina no JúpiterWeb: para o BCC, para o BMA, para o BMAC]

Oferecimentos recentes da disciplina: 2002/1, 1999/1.