O Problema do Fluxo Máximo (PFM) é um dos modelos de otimização de rede que trata de maximizar o fluxo que passa pelos arcos de um nó de origem (oferta) até um nó de destino (demanda/escoadouro). Nesse trajeto, do nó de origem até o destino, o fluxo passa por nós intermediários chamados de nós transshipment. O fluxo através de um arco é permitido apenas na direção indicada pela seta, e a quantidade máxima de fluxo é determinada pela capacidade daquele arco.
O objetivo do PFM é maximizar a quantidade total de fluxo da origem para o escoadouro de forma que não fique sobrando, ou seja, não seja desperdiçado nada nos nós de transshipment. Portanto, a quantidade que sai da origem tem que ser igual a quantidade que chega no escoadouro, respeitando a capacidade de fluxo de cada arco.
Algumas aplicações típicas do PFM são:
- Maximizar o fluxo através da rede de distribuição de uma empresa partindo de suas fábricas para chegar aos clientes;
- Maximizar o fluxo de petróleo através de um sistema de tubulação;
- Maximizar o fluxo de veículos através de uma rede de transporte.
Pelo fato de o problema do fluxo máximo poder ser formulado como um problema de programação linear, ele pode ser resolvido pelo método simplex, de forma que qualquer um dos pacotes de software de programação linear possa ser usado
Em geral, o PFM pode ser modelado da seguinte forma:
- N − Conjunto de vértices
- A − Conjunto de arestas
- Xij - Quantidade de Fluxo existente na aresta i → j
- uij - Capacidade máxima da aresta i → j;
Objetivo:
Restrições:
Podemos ver abaixo um exemplo do PFM em uma companhia de saneamento que transporta água potável por meio de uma malha de aquedutos. A companhia busca determinar o fluxo máximo de água (em m³/s) que pode ser transportado na rede da Figura 1. A rede tem como nó de origem (O) uma estação no Norte de Minas e como nó de destino (T) um consumidor final localizado na região central do estado de São Paulo. Os valores nos arcos representam as capacidades máximas em cada arco (em m³/s).
Para resolver esse problema, primeiro definimos as variáveis de decisão do modelo:
Xij = fluxo de água no arco (i,j), ∀ i,j
Assim, temos 8 variáveis de decisão, cada uma representando um arco, como por exemplo Xoa que é o fluxo da estação de origem até a estação A.
A função objetivo busca maximizar o fluxo total de saída da estação de origem O, ou maximizar o fluxo total de chegada na estação final T:
- max z = Xoa + Xob
- max z = Xct + Xdt
As restrições do modelo são:
1. O fluxo de entrada em T é igual ao fluxo de saída em O:
Xct + Xdt = Xoa + Xob
2. Existe uma conservação de fluxo de saída e entrada em cada nó de transshipment, pois não pode restar nada nesses nós:
Xoa = Xac + Xad
Xob = Xbc + Xbd
Xac + Xbc = Xct
Xad + Xbd = Xdt
3. A capacidade máxima em cada arco:
Xoa ≤ 50 m³/s
Xob ≤ 60 m³/s
Xac ≤ 40 m³/s
Xad ≤ 60 m³/s
Xbc ≤ 80 m³/s
Xbd ≤ 60 m³/s
Xct ≤ 50 m³/s
Xdt ≤ 70 m³/s
4. Restrição de não negatividade:
Xoa, Xob, Xac, Xad, Xbc, Xbd, Xct, Xdt ≥ 0
Resolvendo esse PFM por meio de qualquer solver como simplex, ou por meio do código desenvolvido pelo trabalho, foi encontrado a solução ótima de Z = 110 m³/s.
Foi requisitado que construíssemos um problema que resolva o PFM modelado como Problema de Fluxo de Custo Mínimo (PFCM). Para realizar a transformação do PFM no formato do PFCM foram necessárias três alterações:
1. Custo do arco (Cij) com valor igual a zero para todos os arcos existentes de modo a refletir a ausência de custos no PFM.
2. Selecionar um limite superior (F) seguro sobre o fluxo viável máximo da rede, para servir de parâmetro aos nós de suprimento e demanda.
3. Criar um arco de ligação entre o nó de suprimento (origem) e o nó de demanda (escoadouro), com o custo unitário grande (M).
Em razão de criarmos esse custo unitário positivo para o arco de ligação e atribuirmos o custo unitário zero para todos os demais, o PFCM enviará o fluxo viável máximo através dos arcos de transshipment, o que faz alcançar o objetivo do PFM. Na Figura 2 podemos observar uma rede do Seervada Park, como exemplo, antes da aplicação dessas transformações, e na Figura 3 observamos a mesma após as transformações.
O código foi desenvolvido na linguagem Python, usando o ambiente Spyder do Anaconda 3. A versão do Python utilizada foi a 3.7. O algoritmo se encontra no arquivo “PFM.py” anexado e para rodá-lo é necessário fazer as seguintes importações no Prompt do Anaconda, ou no terminal do Sistema Operacional:
- $ sudo apt-get install python3
- $ sudo apt-get install python3-pip
- $ pip install --upgrade --user ortools
- $ pip install python-igraph
- $ pip install pycairo
Caso esteja no linux, é necessário instalar o python 3 e pip usando as duas primeiras chamadas de função no terminal.
A terceira importação é referente ao pacote de programação linear OR-Tools, disponível pelo Google, cuja referência está anexada no sétimo tópico ‘Bibliografia’. As outras importações são referentes aos pacotes necessários para visualização do grafo.
O objetivo do trabalho foi alcançado, em ordem o algoritmo lê: o número de vértices, número de arcos, índice da origem, índice do escoadouro, e os dados de cada arco (direção e custo). A saída do algoritmo exibe na tela a solução ótima do PFM e também os grafos utilizados e seus fluxos.
Nas figuras abaixo temos dois exemplos de execução do algoritmo.
- HILLIER, Frederick S; LIEBERMAN, Gerald J.; GRIESI, Ariovaldo. Introdução à pesquisa operacional. 9.ed. Porto Alegre: AMGH,, 2013. 1005p. ISBN: 9788580551181.
- Referência do pacote de programação linear OR-Tools
- Referência do pacote igraph
- Referência Glop Linear Solver