Nível:
Graduação
Nome da disciplina:
Programação Linear
Número de Créditos:
4
Oferecimento:
2º Período Letivo
Pré-requisito:
MA327 + MA211 + MS211
Equivalência:
MS415
Ementa:
Formulação de problemas de programação linear. Resolução Gráfica. Método Simplex. Teoria de dualidade. Análise de sensibilidade e análise paramétrica. Algoritmos de pontos interiores.
Conteúdo / Programa:
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.
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.
Forma de Avaliação:
Por nota e frequência
Referência Bibliográfica:
[1] Marcos Arenales, Vinı́cius Armentano, Reinaldo Morabito, e Horacio Yanasse. Pesquisa Operacional. Campus, 2a ed., 2015.
[2] M. S. Bazaraa, John J. Jarvis, e Hanif D. Sherali. Linear Programming and Network Flows. John Wiley & Sons, 4a ed., 2010.
[3] Marco Cesar Goldbarg e Henrique Pacca Loureiro Luna. Otimização Combinatória e Programação Linear: Modelos e Algoritmos. Campus, 2a ed., 2005.
[4] David G. Luenberger e Yinyu Ye. Linear and Nonlinear Programming. International Series in Operations Research & Management Science: 228. Springer, 4a ed., 2016.
[5] Dimitris Bertsimas e John N. Tsitsiklis. Introduction to Linear Optimization. Athena Scientific Series in Optimization and Neural Computation: 6. Athena Scientific, 1997.