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 com vértice de origem e vértice sumidouro (vértice que possui arestas vindo de todos os outros vértices e não possui nenhuma saindo) , onde a aresta tem capacidade , o fluxo e custo (a maioria dos algoritmos de fluxo de custo mínimo suportam arestas com custos negativos). O custo do envio desse fluxo é . Exige-se que se envie uma quantidade de fluxo de até .

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

com as restrições

| Restrições de capacidade: || |- | Simetria Skew: || |- | Conservação de Fluxo: || |- | Fluxo necessário: ||

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 .

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 para o vértice de origem , com capacidade e um limite inferior , forçando o fluxo total de para ser também .

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

Aplicação Correspondência bipartida de peso mínimo thumb|Redução de grafo bipartido de peso mínimo correspondente ao problema de fluxo de custo 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’.

Ver também LEMON (biblioteca C ++)

Referências

Ligações externas LEMON C++ library with several maximum flow and minimum cost circulation algorithms

Categoria:Algoritmos de grafos