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.
Dada uma rede de fluxo, isto é, um grafo direcionado G = ( V , E ) {\displaystyle G=(V,E)} com vértice de origem s ∈ V {\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) t ∈ V {\displaystyle t\in V} , onde a aresta ( u , v ) ∈ E {\displaystyle (u,v)\in E} tem capacidade c ( u , v ) > 0 {\displaystyle c(u,v)>0} , o fluxo f ( u , v ) ≥ 0 {\displaystyle f(u,v)\geq 0} e custo a ( u , v ) {\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 é f ( u , v ) ⋅ a ( u , v ) {\displaystyle f(u,v)\cdot a(u,v)} . Exige-se que se envie uma quantidade de fluxo d {\displaystyle d} de s {\displaystyle s} até t {\displaystyle t} . A definição do problema é minimizar o custo total do fluxo:
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 d {\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 t {\displaystyle t} para o vértice de origem s {\displaystyle s} , com capacidade c ( t , s ) = d {\displaystyle c(t,s)=d} e um limite inferior l ( t , s ) = d {\displaystyle l(t,s)=d} , forçando o fluxo total de s {\displaystyle s} para t {\displaystyle t} ser também d {\displaystyle d} .
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 . 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):
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’.
