Detecção de linhas redundantes em problemas de programação linear de grande porte

Autor(es)

Daniele Costa Silva

• Tipo de documento: Dissertação de Mestrado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Matemática, Estatística e Computação Científica
• Data de defesa: 2010-05-28

Membros da banca

Aurelio Ribeiro Leite de Oliveira; Frederico Ferreira Campos Filho; Francisco de Assis Magalhães Gomes Neto

• Orientador: Aurelio Ribeiro Leite de Oliveira

Resumo

A presença de linhas redundantes na matriz de restrições não é incomum em problemas reais de grande porte. A existência de tais linhas deve ser levada em consideração na solução destes problemas. Se o método de solução adotado for o método simplex, existem procedimentos eficientes e 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 representam uma dificuldade considerável, pois 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 dos métodos de pontos interiores. Este trabalho propõe uma implementação eficiente de um procedimento de detecção de linhas redundantes, que incluímos em uma adaptação própria do PCx que resolve os sistemas lineares por métodos iterativos (AU)

• Processo FAPESP: 07/06188-0 - Detecção de Linhas Redundantes em Problemas de Programação Linear de Grande Porte
• Beneficiário: Daniele Costa Silva
• Modalidade de apoio: Bolsas no Brasil - Mestrado