Modelos de Programação Linear: Fluxo em Redes

Muitos problemas de otimização combinatória podem ser modelados como problemas de fluxo em rede. Revisando um pouco, uma rede de fluxo é um grafo direcionado onde cada aresta tem uma capacidade e um fluxo associados. O fluxo na aresta não pode ultrapassar sua capacidade. Além disso, um fluxo deve satisfazer a restrição de conservação de fluxo, ou seja, a quantidade de fluxo que entra em um vértice é a mesma que sai, com exceção de um nó fonte (denotado por s), de onde só sai fluxo e um nó sorvedouro (denotado por t) de aonde só entra fluxo. Vamos apresentar um modelo que representa essas restrições. A cada aresta (ij), associamos uma variável representando o fluxo que passa por ela. Seja sua capacidade.

Rede com capacidades não-inteiras

 

(1) Para cada nó v do grafo que não a fonte ou o sorvedouro,

(2) Para cada aresta (ij),

(3) Para cada aresta (ij),

O lado esquerdo da igualdade (1) representa o somatório do fluxo de todas as arestas que entram em v e o lado direito o somatório do fluxo de todas as arestas que saem de v. Em outras palavras, é a restrição de conservação de fluxo. A desigualdade (2) é a restrição da capacidade do fluxo e (3) é para mostrar que o fluxo não pode ser negativo.

Analogia com dutos: capacidade e conservação de fluxo

Existe uma versão mais eficiente do algoritmo Simplex para resolver fluxos em rede (network simplex). Além disso, alguns dos problemas que podem ser modelados como fluxo em rede possuem algoritmos combinatórios (ou seja, algoritmos específicos para resolvê-los de maneira mais eficiente do que através de programação linear). A seguir vou apresentar dois exemplos para os quais foram desenvolvidos algoritmos combinatórios: o problema do fluxo máximo e o problema do fluxo máximo de custo mínimo.

Fluxo Máximo

Se adicionarmos uma função objetivo para maximizar a quantidade total de fluxo que sai da fonte (que por sinal é o mesmo que chega no sorvedouro), ou seja,

(4)

Temos o modelo linear do problema do fluxo máximo. O algoritmo mais simples para resolvê-lo é o ford-fulkerson, com complexidade , onde |f| é o valor do fluxo máximo (ou seja, esse algoritmo é pseudo-polinomial) e um dos mais eficientes é um baseado numa técnica chamada Push-relabel, com complexidade .

Fluxo Máximo de Custo Mínimo

Se além da capacidade, as arestas tiverem custo associado , podemos considerar a seguinte função objetivo:

(5)

Porém, se os custos forem positivos, obviamente a melhor solução seria não passar nenhum fluxo. Por isso, temos que fixar que o fluxo que passa pela rede tenha um valor fixo d,

(6)

Tal problema é chamado de fluxo de custo mínimo. No caso em que d é o maior valor de fluxo possível, temos o problema do fluxo máximo de custo mínimo. Para este problema existe o algoritmo por cancelamento de ciclos, com complexidade , onde U e C são respectivamente a capacidade máxima e o custo máximo de alguma aresta, sendo este portanto um algoritmo pseudo-polinomial. O mais eficiente algoritmo até hoje é de o duplo-escalanamento (escalonamento de custo e capacidade) que é , sendo assim fortemente polinomial [2].

Conclusão

Esses modelos em particular possuem a propriedade de que se as capacidades da rede forem inteiras, o fluxo máximo também será. Ou seja, mesmo que x possa assumir valores reais, na solução ótima ela será inteira. Desta forma, a solução ótima do PLI (x inteira) e do PL (x real) coincidem. Assim, esse é um típico caso em que um PLI pode ser resolvido em tempo polinomial.

Para uma referência mais abrangente, consulte o livro do Ahuja, Magnanti e Orlin [1].

Referências:

[1] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin (1993). Network Flows: Theory, Algorithms, and Applications.
[2] Advanced Algorithms MIT – Minimum cost maximum flow, Minimum cost circulation, Cost/Capacity scaling

2 respostas a Modelos de Programação Linear: Fluxo em Redes

  1. Alguma sugestão de algoritmo paralelo para fluxo em redes com múltiplas fontes e sorvedouros?

%d bloggers like this: