Objetivos

Número de créditos: 8

Docente Responsável: Carlos Humes Jr.

Objetivos: Desenvolvimento de um primeiro curso em nível de mestrado na área de otimização, cobrindo os aspectos fundamentais de Programação Linear, ponto de partida natural para o estudo de Otimização.

Justificativa: O curso cobre caracterização de poliedros por sua relevância em Otimização Combinatória e pela coerência com a visão de convexidade básica para Programaçào Não Linear e Controle Ótimo. A partir destes resultados o algoritmo simplex é apresentado por sua relevância e por permitir uma abordagem simples para a teoria qualitativa (dualidade). Um dos usos apresentados de dualidade é uma breve noção de métodos de trajetória central, importante por si mesmo e por sua polinomialidade. Devido a este aspecto uma breve visão de algoritmos de elipsóides é apresentada, em nível quase que informal e histórico.

Conteúdo: Introdução. Métodos clássicos de otimização. Caracterização de poliedros. Programação linear: teorema fundamental; interpretação geométrica; aplicações; métodos simplex (revisado e tabular); dualidade; métodos dual simplex e primal-dual; análise de sensibilidade. Aplicação da dualidade: teoremas de alternativas e programação linear paramétrica. Método dos elipsóides. Introdução aos métodos de trajetória central. Complexidade.

1. C. Humes Jr. and A.F.P.C. Humes, Programação Linear, SBMAC, Rio de Janeiro, 1986.
2. G.B. Dantzig, Linear Programming and Extensions, University Press, Princeton, 1962.
3. C. Gonzaga, Métodos de Pontos Interiores, IMPA, Rio de Janeiro, 1992.
4. P.F. Bregalda, A.A.F. Oliveira, and C.T. Bornstein, Introdução à Programação Linear, Editora Campus, Rio de Janeiro, 1981.
5. M. Simmonard, Programmation Linéaire, Dunod, Paris, 1962.