PLANO DE ENSINO

DISCIPLINA: Programação Linear

CÓDIGO: MTM 5875

PRÉ-REQUISITO(S): MTM 5863 e MTM 5872

Nº DE HORAS-AULA SEMANAIS: 6

Nº TOTAL DE HORAS-AULA: 108

SEMESTRE: 2006-2

CURSO: Matemática habilitação: Bacharelado em Matemática e Computação Científica

EMENTA:

Programação Linear: 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:

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 – Minimização de funções na reta real

d. Programação e testes desses algoritmos

4 – 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

5 – 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

6 – 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

7 – 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

8 – 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

METODOLOGIA: Aulas expositivas dialogadas e aulas em laboratório de computação.

AVALIAÇÃO: O aluno será avaliado através de três notas: duas notas correspondentes a duas provas escritas obrigatórias e uma nota correspondente a um conjunto de trabalhos de casa distribuídos ao longo do semestre. Será consideado aprovado o aluno com frequência suficiente que obtiver média igual ou superior a 6,0 nessas três avaliações.

PROVA FINAL: De acordo com o artigo 70 da Resolução 17/CUn/97, o aluno com frequência suficiente e média das avaliações acima entre 3,0 e 5,5 terá direito a uma nova avaliação, no final do semestre, com todo o conteúdo programático. A nota final desse aluno será calculada através da media aritmética entre a média das avaliações anteriores e a nota da nova avaliação.

BIBLIOGRAFIA

1) Gonzaga, C., Notas de aula de Programação Linear, UFSC, 2004

2) Chvátal, V., Linear Programming, W. H. Freeman and Company, N. York, 1983

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

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

Florianópolis, 11 de setembro de 2006

Prof. Mario Cesar Zambaldi

Coordenador da disciplina.