UNIVERSIDADE FEDERAL DE SANTA CATARINA

CENTRO DE CIÊNCIAS FÍSICAS E MATEMÁTICAS

DEPARTAMENTO DE MATEMÁTICA

PROGRAMA DE MTM 5412 – OTIMIZAÇÃO I

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

No DE HORAS-AULAS SEMANAIS: 08

No TOTAL DE HORAS-SULAS: 144

EMENTA: Conceito de otimização. Tipos de problemas. Algorítmos iterativos e convergência. Programação linear: propriedades básicas o método simplex, análise de sensibilidade, dualidade, algorítmo de Karmarkar, problemas de transporte e fluxos em redes. Problemas de localização. Programação inteira: conceituação, técnicas de corte, técnicas de branch-and-bound. Programação Dinâmica.

OBJETIVOS: Propiciar aos alunos a compreensão dos conceitos básicos de otimização e suas implicações no contexto geral no Curso de Matemática e Computação Científica.

CONTEÚDO PROGRAMÁTICO:

  1. O Conceito de Otimização

    1. Definição de problemas de otimização

    2. Classificação de problemas de otimização

    3. Problemas de programação não linear

  2. Elementos de álgebra linear e cálculo multidimensional.

    1. Decomposições e Sistemas lineares

    2. Métodos iterativos, teorema de taylor e notação de ordem

    3. Taxa de convergência de seqüências iterativas

  3. Programação Linear – Propriedades Básicas

    1. Exemplos de problemas de programação linear

    2. Soluções básicas

    3. O teorema fundamental da programação linear

    4. Relações com convexidade

  4. O método simplex

    1. Pivotamento e pontos extremos adjacentes

    2. Determinação de uma solução básica factível

    3. Os procedimentos do método simplex

    4. Variáveis artificiais e variáveis limitadas

    5. A forma matricial do método simplex-decomposições

  5. Teoria da Dualidade

    1. O problema dual

    2. O teorema da dualidade

    3. As relações com o simplex

    4. Sensibilidade e complementaridade

    5. O método dual simplex

    6. Algoritmos primais-duais

  6. Introdução aos métodos de pontos interiores

    1. Complexidade

    2. O método afim-escalar

    3. O método de Karmarkar

  7. Os problemas de Fluxos em Redes e de transporte e Programação dinâmica

    1. O problema de custo mínimo de fluxos em redes.

    2. Teoria dos grafos

    3. O método simplex para Problemas de fluxos em redes

    4. Os problemas de transporte e designação

    5. O método simplex para o problema de transporte

    6. Programação inteira

    7. Programação dinâmica

Referencias Bibliográficas

  1. Linear Programming and Network Flows. M. S. Bazara, J. J. Jarvis and H. D. Sherali, 1990 2nd edition. John Wiley & San.

  2. Linear and Nonlinear programming. D. G. Luenberger 2nd edition 1986 – Addison-Wesley Co.

  3. Gonzaga, C. C. Algoritmos de pontos interiores para programação linear. 17o Colóquio Brasileiro de Matemática. RJ, IMPA SMB 1989.

  4. Primal-Dual Interior-Point Methods. S. J. Wrignt – SIAM Philadelphia-1997.

  5. Introdução à Programação Linear. P. F. Bregalda, A. F. Oliveira E C. T. Bornstein. Editora Campus – RJ – 1981.

  6. Linear Programming and Extensions. G. Dontzig – 1963 – Rond Corporation – Princeton University Press