O problema de fluxo máximo

Prévia do material em texto

O problema de fluxo máximo • Escolha de caminho que permita o maior fluxo de transporte, dado dois nós origem e destino. • Vejamos as definições aplicadas a um problema de exemplo: – Rede de tubulações de transporte de petróleo entre poços e refinarias. – A solução requer equipar a rede com uma única origem e um único sorvedouro (destino final) com arcos unidirecionais (tracejados), de capacidades infinitas (figura). – Enumeração de cortes – define um conjunto de arcos que, quando eliminado da rede, causará um rompimento total do fluxo entre o nó de origem e o nó sorvedouro -> é igual à soma das capacidades dos seus arcos. O corte de menor capacidade dá o fluxo máximo da rede como solução.
• Considere outro exemplo (fig. abaixo). As capacidades bidirecionais são mostradas nos respectivos arcos. Abaixo está a tabela de corte.
Defina Xij como quantidade de fluxo no arco (i, j) com capacidade Cij. • O objetivo é determinar Xij para todo i e j que maximizará o fluxo entre o nó inicial (s) e o terminal (t) sujeito às restrições de fluxo (fluxo entrada = fluxo saída) em todos os nós, exceto nos nós s e t. • Exemplo da rede entre s=1 e t=5: Função objetivo: Max. fluxo no nó de entrada, ou, max. fluxo no nó de saída (são equivalentes). Restrições: Para todos os nós individuais, exceto 1 e 5 (nós origem e destino, respectivamente); e, para as capacidades das arestas.