Detecção de Linhas Redundantes em Problemas de Programação Linear de Grande Porte

Abstract

A presença de linhas redundantes na matriz de restrições não é incomum em problemas reais de grande porte. Se o método de solução a dotado for o simplex, existem procedimentos de fácil implementação que contornam este problema. O mesmo se aplica quando métodos de pontos interiores são adotados e os sistemas lineares resultantes são resolvidos por métodos diretos. No entanto, existem problemas de grande porte cuja única forma possível de solução é resolver os sistemas lineares por métodos iterativos. Nesta situação as linhas redundantes geram uma matriz singular e os métodos iterativos não convergem. A única alternativa viável consiste em detectar tais linhas e eliminá-las antes da aplicação do método. Este trabalho tem como objetivo apresentar um procedimento eficiente de detecção de linhas redundantes.

- Abstract: The presence of dependent rows in the constraint matrix is frequent in real large-scale problems. If the solution method adopted is the simplex method, there are efficient procedures easy to implement that circumvent this problem. The same applies when interior point methods are adopted and the resulting linear systems are solved  for directed methods. However, there are large-scale problems whose only possible approach consists in solving the linear systems by iterative methods. In this situation, the dependent rows create a singular matrix and the iterative method does not converge. The only viable alternative is to find and remove these rows before applying the method. This paper proposes an efficient implementation of a procedure for dependent rows detection.