Problemas de otimização linear canalizados e esparsos

• Processo: 00/10605-7
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de novembro de 2000
• Data de Término da vigência: 31 de outubro de 2002
• Área de conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Marcos Nereu Arenales
• Beneficiário: Carla Taviane Lucke da Silva Ghidini
• 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
• Palavra(s)-Chave do Pesquisador: Metodos Do Tipo Simplex | Otimizacao Linear | Sistemas Esparsos

Resumo

A otimização linear tem sido objeto de estudo há décadas, desde o trabalho pioneiro de dantzig em 1947, devido à sua ampla utilidade na resolução de problema práticos. Muito esforço tem sido empregado na busca de algoritmos eficientes e na tentativa de compreender porque o método simplex apresenta desempenho ruim para certas classes de problemas. Em 1984, com o trabalho de karmakar em pontos interiores, este tópico de pesquisa foi ainda mais enfatizado. Neste projeto de pesquisa investigamos o problema de otimização linear na forma geral, isto é, min cx, sujeito a: a<=ax<=b. Este tipo de formulação ocorre com freqüência na prática e tem seu problema dual linear por partes. O método dual simplex, com busca linear por partes, apresenta um desempenho muito bom, quando comparado com os algoritmos do pacote cplex4.0, do ponto de vista de iterações realizadas. Neste trabalho a aluna deverá estender o método dual simplex, com busca linear por partes, para sistemas esparsos e deverá comparar sua implementação com o pacote cplex e outros disponíveis. (AU)

Publicações acadêmicas

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

GHIDINI, Carla Taviane Lucke da Silva. Problemas de otimização linear canalizados e esparsos. 2002. 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.