UNIVERSIDADE FEDERAL DE SANTA CATARINA
CENTRO DE CIÊNCIAS FÍSICAS E MATEMÁTICAS
DEPARTAMENTO DE MATEMÁTICA
PROGRAMA DE MTM 5875 – PROGRAMAÇÃO LINEAR
PRÉ-REQUISITO(S): MTM 5863 e MTM 5872
Nº DE HORAS-AULA SEMANAIS: 6
Nº TOTAL DE HORAS-AULA: 108
SEMESTRE: 2004-2
CURSO(S): Matemática , habilitação: Bacharelado em Matemática e Computação Científica
EMENTA:
Formulação de problemas de programação linear. Método simplex. Teoria de dualidade. Análise de sensibilidade paramétrica. Métodos de pontos interiores.
OBJETIVOS ESPECÍFICOS: Propiciar aos alunos condições de:
a) Adquirir base teórica sobre otimização irrestrita e com restrições lineares.
b) Entender e programar os algoritmos de Cauchy e Newton.
c) Entender a teoria e programar o método simplex para programação linear.
d) Entender e programar algoritmos básicos de pontos interiores para programação linear.
OBJETIVOS GERAIS
I - Propiciar ao aluno condições de:
1. Desenvolver sua capacidade de dedução;
2. Desenvolver sua capacidade de raciocínio lógico e organizado;
3. Desenvolver sua capacidade de formulação de algoritmos e suas implementações em computador;
4. Desenvolver seu espírito crítico e criativo;
5. Perceber e compreender o interrelacionamento das diversas áreas da Matemática apresentadas ao longo do curso;
6. Organizar, comparar e aplicar os conhecimentos adquiridos.
II - Incentivar o aluno ao uso da Biblioteca.
CONTEÚDO PROGRAMÁTICO:
1 – Formulação e classificação de problemas de otimização em Rn.
2 – Minimização de funções na reta real
Algoritmo de seção áurea
Algoritmo de Armijo
Programação e testes desses algoritmos
3 – Métodos de otimização irrestrita em Rn
a. Condições necessárias de otimalidade em Rn
b. Algoritmo de Cauchy com buscas de Armijo e seção áurea
c. Algoritmo de Newton puro e com buscas unidirecionais
d. Programação e testes desses algoritmos
4 – O problema de otimização com restrições lineares
a. Conjuntos convexos, subespaços afins e cones em Rn
b. Poliedros: caracterização, vértices, arestas, faces
c. Problemas de programação linear: formulação, exemplos e resolução gráfica.
d. Vértices e bases em um problema de programação linear
5– Condições de otimalidade
a. Lema de Farkas
b. Condições de Karush-Kuhn-Tucker para problemas com restrições lineares
c. Dualidade: problemas primal e dual e condições de otimalidade primais-duais para
programação linear
6 – O método simplex
a. Descrição do algoritmo clássico, usando dicionários
b. Descrição e desenvolvimento teórico do método simplex usando matrizes
c. Programação do algoritmo matricial, exemplos e testes
7 – Métodos de pontos interiores
a. O elipsóide de Dikin e o algoritmo afim-escala
b. A função barreira logarítmica, centro analítico e trajetória central primal
c. Algoritmo de trajetória central primal
BIBLIOGRAFIA
Bazaraa, M. S. and Jarvis, J.J., Linear Programming and Network Flows, John Wiley and Sons, New York, 1977.
Bazaraa, M. S., Sheraly H.D., and Shetty C. M., Nonlinear Programming: theory and algorithms, 2nd Ed., John Wiley and Sons, New York, 1993.
Bregalda, P.F., Oliveira, A.A.F., e Bornstein, C.T., Introdução à Programação Linear, Editora Campus, 1988.
Chvátal, V. , Linear Programming, W. H. Freeman and Company, New York, 1983.
Friedlander, A., Elementos de Programação não linear, Editora da Unicamp, 1994.
Murty, K. C., Linear Programming, John Wiley and Sons, New York, 1983.
Vanderbei, R. , Linear Programming – Foundations and Extensions, Kluwer, Boston 1996.