AULA 004 - O PROBLEMA DO FLUXO MAXIMO

Prévia do material em texto

PESQUISA OPERACIONAL 
Otimização de Redes e Filas e Simulação 
Fernando Tadeu Pongelupe Nogueira 
fernando.nogueira@prof.una.br 
PESQUISA OPERACIONAL 
Otimização de Redes e Filas e Simulação 
I – MODELOS DE OTIMIZAÇÃO DE REDES 
Voltando ao nosso exemplo (Seervada Park), 
agora um número de pessoas deseja utilizar o 
serviço de transporte do parque do que pode 
ser atendido durante a época de pico da 
visitação. Para evitar maiores transtornos à 
ecologia, fauna e flora da região, foi imposta 
uma limitação rigorosa do número de viagens 
que os carrinhos podem fazer diariamente 
por estas estradas. 
O Problema do Fluxo Máximo 
• Portanto durante o pico várias rotas 
poderiam ser seguidas, independente da 
distância, visando aumentar o número de 
viagens que poderiam ser feitas todos os 
dias. A questão é, quais rotas escolher para 
as diversas viagens de modo a maximizar o 
número delas que poderiam ser feitas sem 
violar os limites das estradas 
individualmente ??? 
O Problema do Fluxo Máximo 
Terminologia 
Direção da viagem no sentido de se 
afastar da entrada do parque 
Número máximo de 
viagens permitidas / 
dia 
• Todo fluxo através de uma rede direcionada e 
conectada origina-se de um nó, denominado 
origem e termina em um outro nó, chamado 
escoadouro. 
• Todos os nós restantes são nós de transbordo. 
• O fluxo através de um arco é permitido apenas 
na direção indicada pela seta, em que o fluxo 
máximo é indicado pela capacidade do arco. 
• O objetivo é maximizar a quantidade total de 
fluxo da origem para o escoadouro. 
Em termos gerais: 
 
• Maximizar o fluxo pela rede de distribuição de uma 
empresa, partindo de suas fábricas para chegar a seus 
clientes. 
• Maximizar o fluxo pela rede de distribuição de uma 
empresa, partindo de seus fornecedores para chegar nas 
suas fábricas. 
• Maximizar o fluxo de petróleo por um sistema de 
tubulações. 
• Maximizar o fluxo de água por um sistema de aquedutos. 
• Maximizar o fluxo de veículos por uma rede de transportes. 
Algumas Aplicações 
• Após alguns fluxos serem designados aos arcos, a rede 
residual mostra as capacidades dos arcos remanescentes 
(chamadas capacidades residuais) para designar fluxos 
adicionais. 
O algoritmo 
• Para um fluxo = 5, a capacidade residual 
deste arco é igual a  7-5=2. 
O algoritmo 
O algoritmo 
• Um caminho aumentado é um caminho 
direcionado da origem para o 
escoadouro na rede residual de modo 
que todo arco nele tenha capacidade 
residual estritamente positiva. 
O algoritmo 
• Identifique um caminho aumentado encontrando algum 
caminho direcionado da origem para o escoadouro na rede 
residual tal que cada arco desse caminho tenha capacidade 
residual estritamente positiva (se não existir um caminho, os 
fluxos já constituem um padrão de fluxo ótimo). 
 
• Identifique a capacidade residual c* desse caminho aumentado 
encontrando o mínimo das capacidades residuais dos arcos 
nesse caminho. Aumente o fluxo nesse caminho de c* . 
 
• Diminua de c* a capacidade residual de cada arco nesse caminho 
aumentado. Aumente de c* a capacidade residual de cada arco 
na direção oposta nesse caminho aumentado. Retorne a etapa1. 
O algoritmo do caminho aumentado 
Aplicação: Passo 1. 
Aplicação: Passo 2. 
Capacidade residual de min{7,5,6}=5 
Fluxo de + 5 
Aplicação: Passo 2. 
Capacidade residual de min{7,5,6}=5 
Fluxo de + 5 
Aplicação: Passo 3. 
7-5=2 
0+5=5 
Aplicação: Iteração 2 – Passo 1 
Aplicação: Iteração 2 – Passo 1 
Aplicação: Iteração 2 – Passo 2 
Capacidade residual de min{5,3,9}=3 
Fluxo de + 3 
= 8 
Aplicação: Iteração 2 – Passo 3 
Aplicação: Iteração 3 – Passo 1 
Aplicação: Iteração 3 – Passo 1 
Aplicação: Iteração 3 – Passo 2 
Capacidade residual de min{2,1,4,6}=1 
Fluxo de + 1 
= 9 
Aplicação: Iteração 3 – Passo 3 
9 
9 1 
4 
0 
1 
3 1 
5 
4 
Aplicação: Iteração 4 – Passo 1 
9 
9 1 
4 
0 
1 
3 1 
5 
4 
Aplicação: Iteração 4 – Passo 1 
9 
9 1 
4 
0 
1 
3 1 
5 
4 
Aplicação: Iteração 4 – Passo 2 
9 
9 1 
4 
0 
1 
3 1 
5 
4 
Capacidade residual de min{2,3,5}=2 
Fluxo de + 2 
= 11 
Aplicação: Iteração 4 – Passo 3 
Aplicação: Iteração 5 – Passo 1 
Aplicação: Iteração 5 – Passo 1 
Aplicação: Iteração 5 – Passo 2 
Capacidade residual de min{4,4,1,1}=1 
Fluxo de + 1 
= 12 
Aplicação: Iteração 5 – Passo 3 
12 
3 
1 
3 1 
0 
1 
2 
7 
Aplicação: Iteração 6 – Passo 1 
12 
12 
3 
1 
3 1 
0 
1 
Aplicação: Iteração 6 – Passo 1 
12 
12 
3 
1 
3 1 
0 
1 
Aplicação: Iteração 6 – Passo 2 
12 
12 
3 
1 
3 1 
0 
1 
Capacidade residual de min{3,3,1}=1 
Fluxo de + 1 
= 13 
Aplicação: Iteração 7 – Passo 1 
Aplicação: Iteração 7 – Passo 1 
Aplicação: Iteração 7 – Passo 2 
Capacidade residual de min{2,2,5,1,2}=1 
Fluxo de + 1 
= 14 
Aplicação: Iteração 7 – Passo 3 
Aplicação: FIM 
Agradecimento 
 
 
• Agradeço à Profa. Alaine Cardoso Silva (Msc) 
pelas orientações e materiais que serviram de 
base para elaboração deste power point. 
Bibliografia 
 
 
HILLIER, Frederick S. e LIEBERMAN, Gerald J. 
Introdução à Pesquisa Operacional. 9ª 
edição. Porto Alegre: AMGH Editora Ltda 
(McGraw Hill), 2013. Capitulo 9 – pg. 341-
403.