ESTUDO E IMPLEMENTAÇÃO DE UM ALGORITMO COM BASE NO MÉTODO SIMPLEX REVISADO PARA PROGRAMAÇÃO LINEAR

Autores

  • Renata Gomes Cordeiro UENF
  • Tiago Carvalho Da Costa UENF
  • Fermín Alfredo Tang Montané UENF

Palavras-chave:

Programação Linear, Método Simplex Revisado, Decomposição LU,

Resumo

O método simplex é um dos algoritmos mais populares para a resolução de problemas de programação linear, que geralmente buscam a distribuição eficiente de recursos limitados para atender um determinado objetivo. O simplex revisado surgiu como uma variante para evitar cálculos desnecessários e consequentemente o desperdício de tempo e espaço computacional. O presente trabalho tem como objetivo desenvolver código próprio com base no método simplex revisado, que fará parte da biblioteca OPTLIB.Neste trabalho foi realizado o estudo do método simplex revisado, através de materiais bibliográficos e testes com problemas pequenos. O método estudado resolve de maneira eficiente sistemas de equações lineares e a cada iteração calcula uma nova solução mais próxima da solução ótima, para isso faz uso de conceitos de álgebra matricial. Foram utilizados os softwares Lingo e Tora para a solução e análise de problemas de teste, realizando-se comparações entre o método revisado e o tabular. O software Scilab foi utilizado para a implementação e validação do algoritmo referente ao método estudado. A segunda parte do projeto consiste na implementação do método na linguagem de programação C++.O método simplex tem como principal característica o fato de a cada iteração se mover para um novo ponto extremo do espaço de soluções, aproximando-se da solução ótima. As implementações eficientes do método simplex evitam o cálculo direto da matriz inversa da base, cálculo considerado caro do ponto de vista computacional, em vez disso, a matriz é atualizada com base em informações da iteração anterior. Uma vez que o simplex realiza um grande número de operações matriciais, a precisão numérica é um fator importante. Durante as pesquisas, foram encontradas diversas variantes do método, como o método Bartels-Golub, que utilizam o método de decomposição LU para tratar da precisão numérica.Neste trabalho, foi observado que o método simplex realiza um grande número de iterações, sendo necessária a adoção de variantes que utilizem o método LU. Na continuação da pesquisa, será escolhida uma variante para implementação visando o melhor desempenho e qualidade dos resultados.

Publicado

18-03-2013