Busca avançada
Ano de início
Entree

Métodos de otimização linear

Processo: 99/11528-7
Linha de fomento:Bolsas no Brasil - Doutorado
Vigência (Início): 01 de agosto de 2000
Vigência (Término): 31 de julho de 2004
Área do 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   Métodos de pontos interiores   Problemas de otimização

Resumo

A otimização linear tem sido objeto de intenso estudo desde a publicação do método simplex em 1947, sendo revigorada em 1984 com a publicação de método de pontos interiores, computacionalmente eficiente e com propriedade de convergência polinomial no estudo do pior caso. Nos últimos anos, tem crescido o interesse pela pesquisa rios métodos tipo simplex que sejam mais eficientes. Há uma pergunta subjacente, que talvez seja o maior desafio da atualidade na teoria da otimização linear: "É possível construir um algoritmo tipo simplex com complexidade polinomial?" E ainda, eficiente do ponto de vista computacional? A resposta a esta pergunta não deve ser trivial e talvez seja negativa, restando por enquanto a tarefa árdua da investigação da complexidade, caso a caso, dos métodos propostos. Neste trabalho, pretendemos estudar o comportamento computacional de métodos tipo simplex, baseando em implementações eficientes de grande porte e esparsos; identificar classes de problemas difíceis, e se possível, construir exemplos de complexidade não-polinomial. Contribuindo, assim, para um melhor entendimento do desafio sobre a existência de algoritmos tipo simplex de complexidade polinomial. O comportamento dos métodos tipo simplex serão comparados com o comportamento de métodos de pontos interiores. (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. Métodos tipo dual simplex para problemas de otimização linear canalizados. 2005. Tese de Doutorado - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação São Carlos.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.