Problema de fluxo de rede - Network flow problem

Na otimização combinatória , os problemas de fluxo de rede são uma classe de problemas computacionais em que a entrada é uma rede de fluxo (um gráfico com capacidades numéricas em suas bordas), e o objetivo é construir um fluxo , valores numéricos em cada borda que respeitem a capacidade restrições e que têm fluxo de entrada igual ao fluxo de saída em todos os vértices, exceto para certos terminais designados.

Tipos específicos de problemas de fluxo de rede incluem:

  • O problema de fluxo máximo , em que o objetivo é maximizar a quantidade total de fluxo fora dos terminais de origem e para os terminais coletor
  • O problema de fluxo de custo mínimo , em que as bordas têm custos e também capacidades e o objetivo é atingir uma determinada quantidade de fluxo (ou um fluxo máximo) que tenha o custo mínimo possível
  • O problema do fluxo de múltiplas mercadorias , em que se deve construir fluxos múltiplos para diferentes mercadorias cujos valores totais de fluxo em conjunto respeitam as capacidades
  • Fluxo em lugar nenhum , um tipo de fluxo estudado em combinatória em que os valores de fluxo são restritos a um conjunto finito de valores diferentes de zero

O teorema do corte mínimo do fluxo máximo iguala o valor de um fluxo máximo ao valor de um corte mínimo , uma partição dos vértices da rede de fluxo que minimiza a capacidade total das bordas que cruzam de um lado da partição para o outro. Teoremas aproximados de fluxo máximo de corte mínimo fornecem uma extensão desse resultado para problemas de fluxo de mercadorias múltiplas. A árvore Gomory-Hu de uma rede de fluxo não direcionada fornece uma representação concisa de todos os cortes mínimos entre diferentes pares de vértices terminais.

Algoritmos para a construção de fluxos incluem

Caso contrário, o problema pode ser formulado como um programa linear mais convencional ou semelhante e resolvido usando um solucionador de otimização de propósito geral.