Disciplina Discipline MAP5915
Otimização Linear

Área de Concentração: 45132

Concentration area: 45132

Criação: 17/11/2017

Creation: 17/11/2017

Ativação: 17/11/2017

Activation: 17/11/2017

Nr. de Créditos: 8

Credits: 8

Carga Horária:

Workload:

Teórica

(por semana)

Theory

(weekly)

Prática

(por semana)

Practice

(weekly)

Estudos

(por semana)

Study

(weekly)

Duração Duration Total Total
8 4 8 6 semanas 6 weeks 120 horas 120 hours

Docente Responsável:

Professor:

Gabriel Haeser

Objetivos:

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

Justificativa:

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.

Conteúdo:

1. Introdução: Modelagem de problemas de otimização linear. Representação gráfica e solução gráfica. 2. 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. 3. 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. 4. 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. 5. Análise de sensibilidade.

Forma de Avaliação:

Média ponderada de atividades e provas.

Observação:

Método: Provas e tarefas que podem ou não envolver programação. Critério: Média ponderada de provas e tarefas.

Bibliografia:

M. S. Bazaraa, J. J. Jarvis e H. D. Sherali, Linear programming and Network Flows, 4th edition, Wiley, New York, NY, 2009. D. Bertsimas e 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.