Disciplinas

Otimização Linear e Não Linear

Apresentação

Disciplina: Otimização Linear e Não Linear
Professores: Geraldo Robson Mateus e Alexandre Salles da Cunha

Objetivos

Programação Linear (PL) é uma disciplina básica para a linha de pesquisa em Otimização. Outra área complementar é a Programação Não Linear (PNL). Essas duas áreas são básicas na Programação Matemática. O objetivo é introduzir os conceitos com o devido rigor matemático e formalização. Aspectos práticos e de análise econômica serão enfocados bem como o desenvolvimento de algoritmos e aplicações.
Material Didático de Apoio

1. Introdução

  • O problema de Programação Matemática
  • Variantes e casos particulares
  • Exemplos
  • Notação e Terminologia
  • Funções Convexas

2. Solução Gráfica

  • Geometria da Programação Linear
  • Poliedros, Semiespaços e Hiperplanos
  • Conjuntos Convexos
  • Pontos externos, vértices e soluções básicas
  • Interpretações econômicas
  • Degeneração

3. Método Simplex

  • Direção Viável
  • Custo reduzido
  • Otimalidade
  • Pivoteamento
  • Simplex revisado

4. Dualidade

  • Teorema das Folgas Complementares
  • Aspectos Geométricos
  • Dual Simplex
  • Lema de Farkas

5. Análise de Sensibilidade

  • Par primal-dual
  • Modificações do vetor de custos

6. Otimização de Grande Porte

  • Geração de Colunas
  • Princípio de Decomposição de Dantzig-Wolfe
  • Aplicação em do Princípio em Programação Linear
  • Aplicação de Geração de Colunas e Dantizg-Wolfe em Programação Inteira

7. Programação Não Linear Irrestrita

  • Ótimo Local, local estrito, ótimo global
  • Condições Necessárias de Primeira Ordem
  • Condições Necessárias de Segunda Ordem
  • Condições Suficientes de Otimalidade
  • Problemas Quadráticos
  • Métodos do Tipo Gradiente
  • Método da Seção Áurea
  • Método de Armijo
  • Método de Newton
  • Método das Direções Conjugadas
  • Análise de Convergência

8. Programação Não Linear Sobre Conjuntos Convexos

  • Condições de otimalidade
  • Método de direções viáveis
  • Método de projeção do gradiente

9. Teoria e Métodos Baseados em Multiplicadores de Lagrange

  • Condições necessárias de otimalidade
  • Condições suficientes de otimalidade
  • Condições de Karush-Kuhn-Tucker
  • Método de Barreira
  • Método de Penalidades e Lagrangeano aumentado

Referências Básicas

- D. Bertsimas and J. N. Tsitsiklis. Introduction to Linear Optimization, Athena Scientific, 1997.
- D. Bertsekas. Nonlinear Programming, Athena Scientific, 1999.
- D. G. Luenberger. Introduction to Linear and Nonlinear Programming, Addison-Wesley, London, 1973.
Referências Adicionais
- http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html
- Ravindra K. Ahuja, Thomas L. Magnanti and James B.Orlin. Network Flows: Theory, Algorithms and Applications,Prentice Hall, 1993.
- Mokhtar S. Bazaraa, John J. Jarvis and Hanif D. Sheral’i. Linear Programming and Network Flows, Second Edition, John Wiley & Sons, 1990.
- Paulo F. Bregalda, Antonio A.F. de Oliveira e Cláudio T. Bornstein. Introdução à Programação Linear, Terceira Edição, Ed. Campus, 1988.
- Marcos C. Goldbarg e Henrique P.L. Luna. Programação Linear e Otimização Combinatória: Modelos e Algoritmos, Ed. Campus, 2000.
- Marcos Arenales, Vinicius Armentano, Reinaldo Morabito e Horácio Yanasse. Pesquisa Operacional, Ed. Campus, 2007.
- Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, 1982.
- Robert E. Tarjan. Data Structures and Network Algorithms, volume 44 of Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, Pennsylvania, 1983.
- Robert J. Vanderbei. Linear Programming Foundations and Extensions, Kluwer Academic Publishers, 1996.
- Mokhtar S. Bazaraa and C.M. Shetti. Nonlinear Programming, John Wiley & Sons, New York, 1979
- Geraldo R. Mateus e Henrique P.L. Luna. Programaçao Não Linear, V Escola de Computação, 1986