...

Problema do Fluxo Máximo

by user

on
Category: Documents
1

views

Report

Comments

Transcript

Problema do Fluxo Máximo
Problema
do
Fluxo Máximo
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• capacidade de transporte
• problema de corte
• rede R=(V,A,s,t)
–fonte ilimitada de fluxo
–terminal com consumo infinito
–restantes: conservação de fluxo
–arcos com capacidades máxima
–maximizar fluxo
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• problemas dinâmicos
– aplicação em logística (militar), transporte de
bens e equipamentos;
– primeiras aplicações em problemas de trânsito
ferroviário;
– aplicação em problemas de evacuação em situações
de catástrofe.
• modelagem do estacionamento
• escalonamento de viaturas
• planeamento com janelas temporais
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• escalonamento de viaturas
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• escalonamento de viaturas
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• planeamento com janelas temporais
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• planeamento com janelas temporais
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• fluxos:
• fluxo na rede
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• cortes
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• cortes
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• cortes
• problema do corte é resolvido através
do problema do fluxo máximo
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• formulação PL
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• formulação PL
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
rotulação é ordem O(n)
aumento de uma unidade fluxo
regra FIFO para examinar vértices
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s}
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s, v1 }
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s, v1, v2 }
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s, v1, v2 , v3 }
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s, v1, v2 , v3 , v4 }
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s, v1, v2 , v3 , v4 }
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s, v1, v2 , v3 , v4 , t }
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s, v1, v2 , v3 , v4 , t }
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s, v1, v2 , v3 , v4 , t }
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s}
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s , v1}
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s, v1, v2}
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s, v1, v2 , v3}
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s, v1, v2 , v3 , v4}
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s, v1, v2 , v3 , v4}
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s, v1, v2 , v3 , v4}
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s, v1, v2 , v3 , v4 , t }
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
2, 2
1, 1
1, 3
X={s, v1, v2 , v3 , v4 , t }
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s}
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s, v2}
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s, v2 , v4}
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s, v2 , v4 , t, v1 }
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s, v2 , v4 , t, v1 }
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s}
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s, v2}
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
X={s, v2}
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
FLUXO MÁXIMO = 4
X={s, v2}
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
x
x
CORTE MÍNIMO = 4
X={s, v2}
J.A.Oliveira – DPS – U.Minho
Problema do Fluxo Máximo
• algoritmo de Ford-Fulkerson
• casos especiais:
J.A.Oliveira – DPS – U.Minho
Fly UP