Texto completo
| |
| Autor(es): |
Daniela Renata Cantane
Número total de Autores: 1
|
| Tipo de documento: | Tese de Doutorado |
| Imprenta: | Campinas, SP. |
| Instituição: | Universidade Estadual de Campinas (UNICAMP). Faculdade de Engenharia Elétrica e de Computação |
| Data de defesa: | 2009-08-17 |
| Membros da banca: |
Aurelio Ribeiro Leite de Oliveira;
Frederico Ferreira Campos Filho;
Marcon Nereu Arenales;
Paulo Augusto Valente Ferreira;
Akebo Yamakami
|
| Orientador: | Christiano Lyra Filho; Aurelio Ribeiro Leite de Oliveira |
| Resumo | |
A solução eficiente de sistemas lineares é fundamental em problemas de otimização linear e o primeiro método a obter êxito nesta classe de problemas foi o método Simplex. Com o objetivo de desenvolver alternativas eficientes para sua implementação, são apresentadas nesta tese técnicas de atualização da decomposição LU da base para aperfeiçoar a solução dos sistemas lineares oriundos do método Simplex, utilizando um reordenamento estático nas colunas da matriz. Uma simulação do método Simplex é implementada, realizando troca de bases obtidas pelo MINOS e verificando sua esparsidade. Somente os elementos afetados pela mudança de base são considerados para obter uma atualização da decomposição LU eficaz. As colunas da matriz são reordenadas de acordo com três estratégias: mínimo grau; forma bloco triangular e estratégia de Björck. Assim, obtém-se uma decomposição esparsa para qualquer base sem esforço computacional para obter a ordem das colunas, pois o reordenamento da matriz é estático e as colunas da base obedecem esta ordem. A forma bloco triangular obteve os melhores resultados, para os maiores problemas testados, em relação ao mínimo grau e a estratégia de Björck. Resultados computacionais para problemas da Netlib mostram a robustez e um bom desempenho computacional do método de atualização da decomposição LU proposto, pois não são necessárias refatorações periódicas da base como nos métodos de atualização tradicionais. O método proposto obteve uma redução do número de elementos não nulos da base em relação ao MINOS. Esta abordagem foi aplicada em problemas de corte de estoque e a atualização da decomposição LU proposta obteve uma redução do tempo computacional na solução destes problemas em relação ao GPLK. (AU) | |
| Processo FAPESP: | 03/12580-0 - Atualização eficiente da decomposição Lu da base no método simplex aplicação a problemas de corte e empacotamento |
| Beneficiário: | Daniela Renata Cantane |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado |