Métodos de otimização linear

• Processo: 99/11528-7
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de agosto de 2000
• Data de Término da vigência: 31 de julho de 2004
• Á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 Métodos de pontos interiores Problemas de otimização
• Palavra(s)-Chave do Pesquisador: Complexidade Polinomial | Metodos De Pontos Interiores | Metodos Tipo Simplex | Otimizacao Linear

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 (ICMC/SB) São Carlos.