Reordenamento Estático na Atualização da Decomposição LU no Método Simplex

Autores

  • D.R. Cantane
  • A.R.L. de Oliveira
  • C. Lyra Filho

DOI:

https://doi.org/10.5540/tema.2007.08.02.0211

Resumo

Neste trabalho são desenvolvidas técnicas de atualização da decomposição LU da base no método Simplex, utilizando um reordenamento estático nas colunas da matriz. Uma simulação do método Simplex, realizando troca de colunas básicas obtidas pelo MINOS e verificando sua esparsidade é implementada. Somente os elementos afetados pela mudança de base são considerados para obter uma atualização da decomposição LU eficaz. As colunas da matriz são reordenadas de acordo com o n´umero de elementos não nulos, em ordem crescente e na forma bloco triangular. Assim, obtém-se uma decomposição esparsa para qualquer base sem esforço computacional para obter a ordem das colunas, pois o reordenamento da matriz é estático e as colunas da base obedecem esta ordem. O objetivo deste trabalho é comparar a simulação desenvolvida que considera a esparsidade da matriz com os resultados obtidos pelo MINOS. Resultados computacionais em Matlab para problemas da Netlib mostram que esta idéia é muito promissora, pois não são necessárias refatorações periódicas como nos métodos de atualização tradicionais.

Referências

[1] R. Bartels, A stabilization of the simplex method, Numer. Math., 16 (1971), 414-434.

G. Bressan, A. Oliveira, Fast iterations for the combined cutting-stock and lot-sizing problems, Anais da IX International Conference on Industrial Enginnering and Operations Management, Arq. TI0601, (2003), 1-8.

G. Bressan, A. Oliveira, Reordenamento eficiente das colunas básicas na programa ção de lotes e cortes, Pesquisa Operacional, 4 (2004), 323-337.

I. Duff, A. Erisman, J. Reid, “Direct methods for sparse matrices”, Clarendon Press, Oxford, 1986.

J.L. Kennington, R.V. Helgason, “Algorithms for Network Programming”, Wiley, New York, 1980.

H. Markowitz, The elimination form of the inverse and its applications to linear programming, Management Science, 3 (1957), 255-269.

I. Maros, “Computational Techniques of the Simplex Method”, Kluwer Academic Publishers, 2003.

S.L. Nonas, A. Thorstenson, A combined cutting-stock and lot-sizing problem, Operations Research, 120 (2000), 327-342.

J. Reid, A sparsity-exploiting variant of the Bartels-Golub decomposition for linear programming bases, Mathematical Programming, 24 (1982), 55-69.

C.T.L. Silva, “Problemas de Otimização Linear Canalizados e Esparsos”, Dissertação de Mestrado, ICMC, USP, São Carlos, 2002.

U. Suhl, L. Suhl, A fast lu update for linear programming, Annals of Operations Research, 43 (1993), 33-47.

Downloads

Publicado

2007-08-13

Como Citar

Cantane, D., de Oliveira, A., & Lyra Filho, C. (2007). Reordenamento Estático na Atualização da Decomposição LU no Método Simplex. Trends in Computational and Applied Mathematics, 8(2), 211–218. https://doi.org/10.5540/tema.2007.08.02.0211

Edição

v. 8 n. 2 (2007)

Seção

Artigo Original

Licença

Direitos Autorais

Autores de artigos publicados no periódico Trends in Computational and Applied Mathematics mantêm os direitos autorais de seus trabalhos. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Os autores concedem ao periódico o direito de primeira publicação.

Propriedade Intelectual e Termos de uso

O conteúdo dos artigos é de responsabilidade exclusiva dos autores. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Esta licença permite que os artigos publicados sejam reutilizados sem permissão para qualquer finalidade, desde que o trabalho original seja corretamente citado.

O periódico encoraja os Autores a autoarquivar seus manuscritos aceitos, publicando-os em blogs pessoais, repositórios institucionais e mídias sociais acadêmicas, bem como postando-os em suas mídias sociais pessoais, desde que seja incluída a citação completa à versão do website da revista.