Algoritmos do tipo Simplex para problemas de fluxo de custo mínimo - Oliveira, Lucas Vinicius Amaral de (Brasil, 2015)
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.
Simplex-type algorithms for minimum-cost flow problems
Keywords: CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO; Programação linear; Simplex; Fluxo de custo mínimo; Criss-cross; Regra de pivoteamento; Linear programming; Minimum cost flow; Pivoting rule