Consultar: Faculdade de Engenharia Elétrica e de Computação - FEEC

Título [Principal]: Uma contribuição a solução de problemas de fluxo de custo minimo atraves de metodos de pontos interiores
Autor(es): Rafael Carlos Velez Benito
Palavras-chave [PT]:

Pesquisa operacional , Otimização combinatoria , Pesquisa matematica
Titulação: Doutor em Engenharia Elétrica
Banca:
Christiano Lyra Filho [Orientador]
Resumo:
Resumo: O presente trabalho faz um estudo cuidadoso dos métodos de pontos interiores para obter implementações eficientes na solução de problemas de fluxo de custo mínimo. Tendo em vista que a maior parte do esforço computacional dos algoritmos baseados nos métodos de pontos interiores é dedicado à solução de sistemas do tipo AD* ATY = b, é feita uma análise deste sistema, explorando-se as características da estrutura de redes. Implementa-se especializações dos métodos diretos e dos métodos iterativos. Os métodos diretos são especializações da decomposição de Choleski. Heurísticas do tipo grau mínimo e preenchimento local mínimo são usadas para reordenação das linhas e colunas, procurando conservar a esparsidade da matriz AD* AT. Para a família dos problemas de transportes e atribuição, desenvolve-se um método de ordenação ótima. Os métodos iterativos são do tipo gradiente conjugado pré-condicionado. A estrutura de rede permite agilizar o cálculo das direções, reduzir requisitos de memória e construir pré-condicionadores bem informados. Um pré-condicionador do tipo diagonal é usado nos primeiros passos dos métodos de pontos interiores. Quando a solução se aproxima da otimalidade, constrói-se um outro pré-condicionador, baseado em estimações sobre a base ótima. Desenvolve-se implementações especializadas à problemas de fluxo de custo mínimo dos métodos primal afim, dual afim, primal dual e preditor-corretor. Interpretações baseadas no método de Newton para solução de problemas não lineares levaram a inovações nas implementações dos métodos afins. Estuda-se o problema de falta de volume (ou falta de pontos interiores), aspecto frequente em problemas de fluxo de custo mínimo. Avalia-se suas conseqüências na utilização de métodos de pontos interiores. A partir dos experimentos computacionais com os códigos desenvolvidos, procura-se fazer uma sistematização dos problemas em classes, com indicação das melhores alternativas de solução para cada classe.Finalmente, faz-se extensões das idéias desenvolvidas para a resolução de problemas de fluxos generalizados, através de métodos de pontos interiores.

Abstract: This work is a careful study of the interior point methods looking for eflicient implementations for network flow linear programs. Computational experiments are developed with the primal afline, dual afline, primal dual and predictor-corrector methods looking for the best alternatives for different classes of problems. We discuss Newton's method interpretations of these methods. Since most of the computational time of the interior point methods is spent solving systems of the type (AD* AT)y = b, for different diagonal matrices D* and the same incidence matrix A we take advantage of the structure of such systems for networks. We use the sparse Cholesky factorization with two heuristics: the minimum degree and local minimum fill-in. For the family transportation and assignment problems, it is developed an optimal ordering method. We also use the conjugate gradient method with diagonal and maximum spanning tree preconditioners. We give particular attention to the degenerescency phenomena mainly to the lack of primal and/or dual interior feasible points. We study their consequences to interior point methods. Finally proposes extensions of the main ideas to the generalized network problems.
Data de Defesa: 29-04-1996
Código: vtls000112352
Informações adicionais:
Idioma: Português
Data de Publicação: 1996
Local de Publicação: Campinas, SP
Orientador: Christiano Lyra Filho
Instituição: Universidade Estadual de Campinas . Faculdade de Engenharia Elétrica e de Computação
Nível: Tese (doutorado)
UNICAMP: Programa de Pós-Graduação em Engenharia Elétrica

Dono: admin
Criado: 30-07-2007 14:43
Visitas: 2275
Downloads: 36

ArquivoFormatoTamanhoTempo estimado para download
Velez Benito, Rafael Carlos.pdfDocumento PDF8156 Kb(8351475 bytes)4 minuto(s) (Velocidade de conexão de 56 kb/s)Visualizar/Download