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

DATA DE PUBLICAÇÃO

1996

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.

ASSUNTO(S)

pesquisa operacional pesquisa matematica otimização combinatoria

Documentos Relacionados

• Solução de problemas de otimização linear por redes neurais associadas a metodos de pontos interiores
• Sistemas Lineares Aproximados Derivados de Problemas de Fluxo Multiproduto em Métodos de Pontos Interiores
• Problemas de fluxo de custo minimo em redes de custo concavo
• Métodos de pontos interiores para problema de fluxo de potência ótimo DC
• Planejamento do tratamento por radioterapia através de métodos de pontos interiores