Problema de Fluxo de Custo Mínimo

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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:

Soluções[editar | editar código-fonte]

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):

Aplicação[editar | editar código-fonte]

Correspondência bipartida de peso mínimo[editar | editar código-fonte]

Redução de grafo bipartido de peso mínimo correspondente ao problema de fluxo de custo mínimo

Dado um grafo bipartido G = (AB, E), nós gostaríamos de achar a correspondência máxima de cardinalidade em G que tem o custo mínimo. Deixe w: ER 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 ME, cujo peso total é minimizado. A ideia é reduzir esse problema a um problema de fluxo de rede. Vamos G’ = (V’ = AB, 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[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  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[editar | editar código-fonte]