Técnicas computacionais para a implementação eficiente e estável de métodos tipo simplex

Autor(es)

Pedro Augusto Munari Junior

• Tipo de documento: Dissertação de Mestrado
• Imprenta: São Carlos.
• Instituição: Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB)
• Data de defesa: 2009-03-06

Membros da banca

Marcos Nereu Arenales; Francisco de Assis Magalhães Gomes Neto; Franklina Maria Bragion de Toledo

• Orientador: Marcos Nereu Arenales

Resumo

Métodos tipo simplex são a base dos principais softwares utilizados na resolução de problemas de otimização linear. A implementação computacional direta destes métodos, assim como são descritos na teoria, leva a resultados indesejáveis na resolução de problemas reais de grande porte. Assim, a utilização de técnicas computacionais adequadas é fundamental para uma implementação eficiente e estável. Neste trabalho, as principais técnicas são discutidas, com enfoque naquelas que buscam proporcionar a estabilidade numérica do método: utilização de tolerâncias, estabilização do teste da razão, mudança de escala e representação da matriz básica. Para este último tópico, são apresentadas duas técnicas, a Forma Produto da Inversa e a Decomposição LU. A análise das abordagens é feita baseando-se na resolução dos problemas da biblioteca Netlib (AU)

• Processo FAPESP: 07/01791-0 - Implementações eficientes de métodos tipo simplex para a resolução de problemas de otimização linear
• Beneficiário: Pedro Augusto Munari Junior
• Modalidade de apoio: Bolsas no Brasil - Mestrado