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

• Processo: 07/06188-0
• Linha de fomento: Bolsas no Brasil - Mestrado
• Vigência (Início): 01 de março de 2008
• Vigência (Término): 28 de fevereiro de 2010
• Área do conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Aurelio Ribeiro Leite de Oliveira
• Beneficiário: Daniele Costa Silva
• Instituição-sede: Instituto de Matemática, Estatística e Computação Científica (IMECC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Matrizes esparsas Métodos de pontos interiores Programação linear

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 simplex, existem procedimentos eficientes e de fácil implementação que contornam este problema. O mesmo se aplica quando métodos de pontosinteriores são adotados e os sistemas lineares resultantes são resolvidos por métodos diretos. No entanto, existem problemas de grande portecuja única forma possível de solução é resolver os sistemas lineares oriundos dos métodos de pontos interiores 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 do método.Este projeto tem como objetivo implementar um procedimento eficiente de detecção de linhas redundantes e integrar esta implementação a umaadaptação própria do PCx que resolve os sistemas lineares por métodos iterativos.

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

SILVA, Daniele Costa. Detecção de linhas redundantes em problemas de programação linear de grande porte. 2010. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Matemática, Estatística e Computação Científica.