Estudos em otimização linear

• Processo: 98/02003-5
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de agosto de 1998
• Data de Término da vigência: 31 de julho de 2000
• Área de conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Marcos Nereu Arenales
• Beneficiário: Ricardo Silveira Sousa
• Instituição Sede: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil
• Assunto(s): Métodos numéricos de otimização Programação linear Método simplex Algoritmos Métodos de pontos interiores
• Palavra(s)-Chave do Pesquisador: Complexidade De Algoritmos | Metodos Tipo Simplex | Otimizacao Linear

Resumo

A otimização linear tem sido objeto de intensa pesquisa desde os trabalhos de Dantzig em 1947, quando publicou o método simplex e mais recentemente com o trabalho de Karmarkar em 1984, apresentando um algoritmo polinomial de pontos interiores cujo desempenho computacional para problemas de grande porte mostrou-se superior ao método simplex. Como o método simplex e muitos de seus variantes foram mostrados que não são polinomiais, provocou uma questão teórica na otimização linear sobre a existência ou não de métodos do tipo simplex (que percorrem soluções básicas, factíveis ou não) de complexidade polinomial. O objetivo principal deste trabalho será o de estudar e implementar alguns variantes do método simplex publicados mais recentemente e observar seus desempenhos computacionais. Pretende-se também uma introdução à questão da complexidade, sem pretender responder a questão teórica acima. (AU)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

SOUSA, Ricardo Silveira. Estudos em Otimização Linear. 2000. Dissertação de Mestrado - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) São Carlos.