Algoritmos do tipo Simplex para problemas de fluxo de custo mínimo

Abstract

Os problemas de fluxo de custo mínimo representam uma importante classe de problemas de programação linear. Os algoritmos da família simplex, principal algoritmo utilizado atualmente para resolver problemas de programação linear, apresentam uma deficiência: a dificuldade de se obter uma base inicial viável. Essa deficiência do simplex impulsionou o surgimento do algoritmo criss-cross, que pode caminhar por bases inviáveis e não necessita de uma base inicial viável. A versão finita do criss-cross para problemas de programação linear clássicos utiliza a regra de pivoteamento do menor índice. Implementamos o criss-cross com a regra de menor índice adaptada para problemas de rede, como o problema de fluxo de custo mínimo. Sugerimos algumas modificações na regra do menor índice e conseguimos uma grande melhoria de desempenho no algoritmo. Realizamos testes e comparamos o desempenho das variantes do criss-cross, de uma implementação própria do simplex de rede e da implementação do simplex disponibilizada pela ferramenta CPLEX. Apresentamos detalhes da implementação e discutimos os resultados obtidos.