Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/306870
Type: TESE
Title: Metodo primal-dual de pontos interiores aplicado ao problema de multifluxo
Author: Podestá, Valéria Abrão de, 1953-
Advisor: Perin Filho, Clovis, 1947-
Filho, Clovis Perin
Abstract: Resumo: O problema de Multifluxo (Fluxo de Multiproduto) em uma rede é um modelo de Programação Matemática com muitas aplicações práticas. Neste trabalho, apresentamos um estudo computacional do Método Primal-Dual de Pontos Interiores aplicado ao problema de Multifluxo. Destacamos a resolução do sistema linear das direções, onde é utilizado o método dos Gradientes Conjugados com uma combinação dos precondicionadores Diagonal e Floresta Geradora Máxima. Vários experimentos computacionais foram realizados, incluindo duas regras de atualização do parâmetro de centragem, três pontos iniciais e critérios de parada no Gradiente Conjugado, entre outros. Apresentamos ainda a caracterização da base de Multifluxo, uma heurística para a obtenção de uma base ótima a partir de uma solução interior "quase-ótima" fornecida pelo Método Primal-Dual e um estudo sobre a degenerescência

Abstract: The Multicommodity Flow Problem is a model of Mathematical Programming defined on a network that has many important applications. In this work, we perform a computational study of a Primal-Dual Interior Point Method applied to this problem. We solve the linear system of iterate displacements using the Conjugate Gradient Method with a combination of the preconditioned Diagonal and Maximum Spanning Forest. Several computational experiments were performed, considering different starting points, different rules of the centering parameter update and different stopping criterion for the Conjugate Gradient. We present a characterization of the Multiflow basis, a heuristic for constructing an optimal basis from an interior "quasi-optimal" solution given by the Primal-Dual Method as well as a study about degeneracy
Subject: Sistemas lineares
Programação (Matemática)
Programação linear
Language: Português
Editor: [s.n.]
Date Issue: 1999
Appears in Collections:IMECC - Dissertação e Tese

Files in This Item:
File SizeFormat 
Podesta_ValeriaAbraode_D.pdf3.58 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.