Uma implementação de pontos interiores para fluxo em redes lineares por partes

Problemas de Fluxo em Redes Lineares por Partes constituem uma importante \'area de aplica\c{c}\~ao, onde s\~ao estudados modelos que tratam da minimiza\c{c}\~ao de uma fun\c{c}\~ao objetivo convexa, separ\'avel e linear por partes, sujeita a um sistema de equa\c{c}\~oes lineares que expressam a conserva\c{c}\~ao de fluxo sobre uma rede conectada. Este problema pode ser transformado em um programa linear equivalente de tamanho maior. Neste trabalho apresentamos e comparamos duas implementa\c{c}\~oes do m\'etodo primal-dual para redes: uma para problemas lineares e outra para problemas lineares por partes. Ambas as implementa\c{c}\~oes utilizam estruturas de dados especiais visando diminuir o gasto com mem\'oria e tempo. A estrutura utilizada para redes lineares por partes pode ser considerada uma extens\~ao daquela utilizada em redes lineares. Cabe observar que o esfor\c{c}o computacional de cada itera\c{c}\~ao est\'a concentrado na constru\c{c}\~ao e resolu\c{c}\~ao de um sistema linear quadrado, sim\'etrico e definido positivo, resolvido por um m\'etodo de gradientes conjugados precondicionado. Al\'em disto, a matriz do sistema n\~ao \'e constru\'{\i}da explicitamente.Neste trabalho estudamos as vantagens advindas do uso de estrutura de dados especial para redes lineares por partes, em uma implementa\c{c}\~ao do m\'etodo primal-dual de pontos interiores especializada para redes cujo esfor\c{c}o computacional maior de cada itera\c{c}\~ao reside na solu\c{c}\~ao impl\'{\i}cita de um sistema quadrado sim\'etrico e definido positivo ao qual \'e aplicado o m\'etodo dos gradientes conjugados pr\'e-condicionado.Foram realizados diversos testes computacionais que permitem concluir afirmativamente a respeito da vantagem computacional da segunda implementa\c{c}\~ao.