Baixe o app para aproveitar ainda mais
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.
Compartilhar