Buscar

Problema de Fluxo Máximo em Redes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Fluxo Máximo 
 
Um problema de fluxo máximo consiste em determinarmos a capacidade 
máxima de transporte de uma rede formada por arcos e nós, com dois nós 
especiais: um nó representando a origem e um nó representando o final da rede. 
As aplicações de problemas de fluxo máximo ocorrem nas mais diversas áreas. 
Podemos determinar, por exemplo, a capacidade máxima de distribuição de gás, 
petróleo ou água em uma rede formada por tubulações e estações intermediárias 
que muitas vezes servem para impulsionar o fluxo. Podemos também determinar a 
capacidade máxima de transporte de passageiros em uma rede de ônibus, trens ou 
metrôs. Também é possível determinarmos a capacidade máxima de uma linha de 
produção ou a capacidade máxima de atendimento de pessoas em um hospital ou 
repartição. Um problema de fluxo máximo é um caso particular de um problema de 
programação linear e pode ser resolvido pelo método simplex. Mas, devido às 
características do problema, existem algoritmos mais eficientes para a solução de 
problemas de fluxo máximo, tais como o algoritmo do caminho aumentado e o 
algoritmo dos caminhos parciais. 
Para que possamos entender melhor o que é um problema de fluxo máximo, 
vamos considerar um problema de uma empresa que precisa transportar gás 
natural. O nó A indica a origem da rede e o nó E indica o final. Os nós B, C e D são 
estações intermediárias. A capacidade máxima das tubulações (arcos), em bilhões 
de litros por dia, pode ser vista na figura a seguir. 
 
 
 
 O objetivo é determinar qual é a capacidade máxima de transporte de gás 
natural da rede. Observe que, mesmo que a capacidade inicial (arcos AB e AC) seja 
de 38 bilhões de litros por dia, a quantidade que chega ao destino nem sempre é a 
mesma. Isso ocorre pois muitas vezes há uma redução da capacidade de 
transmissão ao longo da rede. É como se uma avenida com quatro pistas, em um 
determinado momento, tiver uma redução para duas pistas. O número de 
automóveis que circulam, em um determinado intervalo de tempo, no trecho de 
quatro pistas muitas vezes não será o mesmo que conseguirá circular no trecho de 
duas pistas. 
 Veremos adiante como é possível resolver o problema de fluxo máximo 
utilizando o WinQSB.

Outros materiais

Materiais relacionados

Perguntas relacionadas

Perguntas Recentes