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

  1. Algoritmo de seção áurea

  2. Algoritmo de Armijo

  3. 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


  1. Bazaraa, M. S. and Jarvis, J.J., Linear Programming and Network Flows, John Wiley and Sons, New York, 1977.

  2. Bazaraa, M. S., Sheraly H.D., and Shetty C. M., Nonlinear Programming: theory and algorithms, 2nd Ed., John Wiley and Sons, New York, 1993.

  3. Bregalda, P.F., Oliveira, A.A.F., e Bornstein, C.T., Introdução à Programação Linear, Editora Campus, 1988.

  4. Chvátal, V. , Linear Programming, W. H. Freeman and Company, New York, 1983.

  5. Friedlander, A., Elementos de Programação não linear, Editora da Unicamp, 1994.

  6. Murty, K. C., Linear Programming, John Wiley and Sons, New York, 1983.

  7. Vanderbei, R. , Linear Programming – Foundations and Extensions, Kluwer, Boston 1996.