Problema de Fluxo de Custo Mínimo

O problema do fluxo de custo mínimo (PFCM) é encontrar a maneira mais barata possível de envio de uma certa quantidade de fluxo através de uma rede de fluxo. Aplicações típicas desse problema envolvem encontrar a melhor rota de entrega de uma fábrica para um armazém onde a rede rodoviária tem uma certa capacidade e certos custos associados. O problema do fluxo de custo mínimo é um dos mais fundamentais entre todos os problemas de fluxo e circulação porque a maioria dos outros problemas podem ser expressos como um problema de fluxo de custos mínimos e também podem ser resolvidos de forma muito eficiente usando o algoritmo simplex de rede.

Definição

Dada uma rede de fluxo, isto é, um grafo direcionado ${\displaystyle G=(V,E)}$ com vértice de origem ${\displaystyle s\in V}$ e vértice sumidouro (vértice que possui arestas vindo de todos os outros vértices e não possui nenhuma saindo) ${\displaystyle t\in V}$, onde a aresta ${\displaystyle (u,v)\in E}$ tem capacidade ${\displaystyle c(u,v)>0}$, o fluxo ${\displaystyle f(u,v)\geq 0}$ e custo ${\displaystyle a(u,v)}$ (a maioria dos algoritmos de fluxo de custo mínimo suportam arestas com custos negativos). O custo do envio desse fluxo é ${\displaystyle f(u,v)\cdot a(u,v)}$. Exige-se que se envie uma quantidade de fluxo ${\displaystyle d}$ de ${\displaystyle s}$ até ${\displaystyle t}$.

A definição do problema é minimizar o custo total do fluxo:

${\displaystyle \sum _{(u,v)\in E}a(u,v)\cdot f(u,v)}$

com as restrições

Restrições de capacidade:	${\displaystyle \,f(u,v)\leq c(u,v)}$
Simetria Skew:	${\displaystyle \,f(u,v)=-f(v,u)}$
Conservação de Fluxo:	${\displaystyle \,\sum _{w\in V}f(u,w)=0{\text{ for all }}u\neq s,t}$
Fluxo necessário:	${\displaystyle \,\sum _{w\in V}f(s,w)=d{\text{ and }}\sum _{w\in V}f(w,t)=d}$

Relação com outros problemas

Uma variação desse problema é encontrar um fluxo que é máximo, mas tem o menor custo entre os máximos. Isto poderia ser chamado um problema de fluxo máximo de custo mínimo. Isso é útil para encontrar emparelhamentos máximos de custo mínimo.

Com algumas soluções, encontrando o fluxo máximo de custo mínimo vez é simples. Se não, você pode fazer uma busca binária em ${\displaystyle d}$.

Um problema relacionado é o problema de circulação de custo mínimo, o qual pode ser usado para a solução do fluxo de custo mínimo. Você pode fazer isso definindo o limite inferior em todas as arestas para zero, e em seguida, criar uma aresta extra do vértice sumidouro ${\displaystyle t}$ para o vértice de origem ${\displaystyle s}$, com capacidade ${\displaystyle c(t,s)=d}$ e um limite inferior ${\displaystyle l(t,s)=d}$, forçando o fluxo total de ${\displaystyle s}$ para ${\displaystyle t}$ ser também ${\displaystyle d}$.

O problema pode ser especializado em dois outros problemas:

• Se o limite de capacidade for removido, o problema é reduzido para o problema do menor caminho,
• Se todos os custos forem definidos como sendo zero, o problema é reduzido para o problema do maior fluxo.

Soluções

O problema de fluxo de custo mínimo pode ser resolvido por programação linear, desde que a função linear seja otimizada, e todas as restrições sejam lineares.

Além disso, existem muitos algoritmos combinatórios, para uma pesquisa abrangente, consulte ^[1]. Alguns deles são generalizações do algoritmo de fluxo máximo, outros usam abordagens totalmente diferentes.

Algoritmos fundamentais conhecidos (eles têm muitas variações):

• Ciclo de cancelamento: Um método primal geral.^[2]
• Ciclo de cancelamento de média mínima: Um algoritmo fortemente polinomial simples.^[3]
• Caminho sucessivo mais curto e escalonamento de escala: Métodos duplos, que podem ser vistos como generalizações do algoritmo de Ford–Fulkerson.^[4]
• Custo de escala: Uma abordagem primal-dual, que pode ser visto como a generalização do algoritmo de push-relabel.^[5]
• Rede Simplex: uma versão especializada do método simplex em programação linear , que roda em tempo polinomial.^[6]
• Algoritmo Out-of-kilter de D. R. Fulkerson.

Aplicação

Correspondência bipartida de peso mínimo

Dado um grafo bipartido G = (A ∪ B, E), nós gostaríamos de achar a correspondência máxima de cardinalidade em G que tem o custo mínimo. Deixe w: E → R ser uma função do peso das arestas de E. O problema da correspondência bipartida de peso mínimo ou o problema de atribuição é de encontrar uma correspondência perfeita M ⊆ E, cujo peso total é minimizado. A ideia é reduzir esse problema a um problema de fluxo de rede. Vamos G’ = (V’ = A ∪ B, E’ = E). Atribuir a capacidade de todas as arestas de E’ para 1. Adicione um vértex de origem s e conecte ele a todos os vértices em A’ e adicione um vértex sumidouro t e conecte todos os vértices do grupo B’ a esse vértice. A capacidade de todas as novas arestas é 1 e os seus custos são 0. Está provado que há correspondência bipartida perfeita de custo mínimo em G se e somente se houver um fluxo de custo mínimo em G’. ^[7]

Ver também

• LEMON (biblioteca C ++)

Referências

1. ↑ Ravindra K. Ahuja, Thomas L. Magnanti and James B. Orlin (1993). Network Flows: Theory, Algorithms, and Applications. [S.l.]: Prentice-Hall, Inc. ISBN 0-13-617549-X 
2. ↑ Morton Klein (1967). «A primal method for minimal cost flows with applications to the assignment and transportation problems». Management Science. 14: 205–220. doi:10.1287/mnsc.14.3.205 
3. ↑ Andrew V. Goldberg and Robert E. Tarjan (1989). «Finding minimum-cost circulations by canceling negative cycles». Journal of the ACM. 36 (4): 873–886. doi:10.1145/76359.76368 
4. ↑ Jack Edmonds and Richard M. Karp (1972). «Theoretical improvements in algorithmic efficiency for network flow problems». Journal of the ACM. 19 (2): 248–264. doi:10.1145/321694.321699 
5. ↑ Andrew V. Goldberg and Robert E. Tarjan (1990). «Finding minimum-cost circulations by successive approximation». Math. Oper. Res. 15 (3): 430–466. doi:10.1287/moor.15.3.430 
6. ↑ James B. Orlin (1997). «A polynomial time primal network simplex algorithm for minimum cost flows». Mathematical Programming. 78: 109–129. doi:10.1007/bf02614365 

Ligações externas

• LEMON C++ library with several maximum flow and minimum cost circulation algorithms