ESTUDO E MODELAGEM DE PROBLEMAS DE FLUXO EM REDES UTILIZANDO SOFTWARES DE PROGRAMAÇÃO MATEMÁTICA

  • Maria Eduarda Barreto Lacerda Gomes
  • Ohana Paula Lopes
  • Fermín Alfredo Tang Montané
Palavras-chave: Otimização Combinatória, Problemas de Fluxo em Redes, Programação Matemática

Resumo

Os problemas de fluxo em redes buscam otimizar a distribuição de produtos originados em pontos de oferta e consumidos em pontos de demanda, inseridos numa rede de interligações possíveis. Os problemas de fluxo se subdividem de acordo com seu objetivo: minimizar custos, maximizar fluxos. Cinco problemas diferentes são objeto de estudo. Detalha-se aqui o problema de fluxo a custo mínimo, que é uma generalização dos outros problemas. Os problemas de fluxo em redes são representados mediante modelos matemáticos, formados por uma função numérica que deve ser otimizada, denominada função objetivo, e desigualdades que representam as restrições do problema. Estes modelos possuem uma estrutura específica, o que permite que equações semelhantes sejam representadas de maneira conjunta. Restrições de conservação de fluxo e de capacidade estão presentes em problemas de fluxo a custo mínimo e podem ser agrupadas. O trabalho de IC visou o estudo dos modelos de fluxo, elaboração de exemplos didáticos e a sua representação mediante as linguagens de modelagem algébrica fornecidas pelos softwares de otimização LINGO e CPLEX. Para que esta solução seja encontrada, após a construção do modelo compacto utilizando a linguagem de modelagem dos softwares LINGO e CPLEX, que calcula a melhor solução para o problema atribuindo valores ótimos para cada variável do modelo. Estes valores foram analisados, e o resultado obtido foi validado. O modo de chegar ao valor ótimo pode variar entre os dois softwares, porém este valor é único em qualquer software que o problema for modelado. O LINGO e o CPLEX retornaram valores iguais para as variáveis na maioria dos problemas, mas os recursos utilizados pelo CPLEX para a apresentação de resultados são notoriamente melhores. Tanto o LINGO como o CPLEX foram ferramentas úteis para a resolução dos modelos, por serem de implementação simples e resultado rápido. Foram modelados os problemas de caminho mínimo, transporte, designação, fluxo máximo e fluxo a custo mínimo, obtendo resultados validados em todos os modelos.
Publicado
05-04-2013