MS428

Objetivo: Introduzir modelos de programação linear: minimizar uma função linear sujeita a restrições lineares. Aplicar os conceitos de álgebra Linear ao estudo do problema e desenvolvimento de técnicas de solução. Conteúdo: Formulação de problemas lineares: hipóteses envolvidas na formulação de problemas lineares. Modelos clássicos: problema da dieta, problema de planejamento de produção, problema de transporte, etc. Solução Gráfica. Geometria do Problema Linear: definição de politopos, poliedros, faces, pontos extremos, raios extremos. Teorema de representação de poliedros. Método Simplex: Relação entre pontos extremos e soluções ótimas. Soluções básicas. Caracterização algébrica de pontos extremos e direções extremas. álgebra do método simplex. Métodos para obtenção de solução inicial viável. Simplex revisado, simplex canalizado. Lema de Farkas e condições de otimalidade de Karush-Kuhn-Tucker. Dualidade: formulação do problema dual. Interpretação econômica. Método dual simplex. Análise de sensibilidade. Algoritmos de pontos interiores: breve discussão sobre o histórico de pontos interiores e complexidade de algoritmos. Algoritmos de pontos interiores.