AULA 002 - O PROBLEMA DO CAMINHO MAIS CURTO

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 
 O Seervada Park foi reservado recentemente para visitação e 
excursões limitadas (mochileiros). Não se permite o ingresso de carros no 
parque, porém, há um sistema de estradinhas estreitas e tortuosas por 
onde podem trafegar pequenos carros elétricos e jipes dirigidos pelos 
guardas florestais. Esse sistema de estradinhas é mostrado (sem as 
curvas) na Figura 9.1, na qual o local “O” é a entrada do parque. Outras 
letras designam os locais de postos de guardas florestais (e outras 
instalações limitadas). Os números fornecem as distâncias em milhas 
dessas estradinhas tortuosas. 
 O parque tem uma vista panorâmica de destaque no posto T. Um 
pequeno número de carrinhos é usado para levar e trazer visitantes da 
entrada do parque até esse posto. 
 A gerência do parque está se deparando atualmente com três 
problemas. Um é determinar que rota da entrada até o posto T tem a 
menor distância total para a operação dos carrinhos. (Esse é um exemplo 
do problema do caminho mais curto a ser discutido na Seção 9.3.). 
O Problema do Caminho Mais Curto 
O Problema do Caminho Mais Curto 
Figura 9.1: Sistema de pequenas estradas par o Seervada Park. 
Terminologia de Redes 
Rede Proposta para 
o problema exemplo 
“Seervada Park” 
Algoritmo para o problema do 
caminho mais curto 
• Objetivo da n-ésima iteração: encontrar o 
nó mais próximo da origem. 
• Entrada para a n-ésima iteração: n-1 nós 
mais próximos da origem, inclusive sua 
distância da origem e caminho mais curtos. 
(Os nós além da origem serão chamados de 
nós solucionados, os demais serão os nós 
não solucionados. 
Algoritmo para o problema do 
caminho mais curto 
• Candidatos ao n-ésimo nó mais 
próximo: cada solucionado que é 
conectado diretamente por uma ligação a 
um ou mais nós não solucionados fornece 
um candidato – o nó não solucionado com 
a ligação de conexão mais curta. 
(Empates fornecem candidatos 
adicionais). 
Algoritmo para o problema do 
caminho mais curto 
• Cálculo do n-ésimo nó mais próximo: 
para cada nó assim solucionado e seu 
candidato, acrescente a distância entre 
eles e a distância do caminho mais curto 
da origem até esse nó solucionado. O 
candidato com a menor distância total é o 
n-ésimo nó mais próximo e seu caminho 
mais curto é aquele gerando essa 
distância. (Empates fornecem candidatos 
adicionais). 
Aplicação do algoritmo proposto ao 
problema do Seervada Park 
Aplicação do algoritmo proposto ao 
problema do Seervada Park 
Solucionado 
Candidatos 
Aplicação do algoritmo proposto ao 
problema do Seervada Park 
n Nós 
solucionados 
diretamente 
conectados a 
nós não 
solucionados 
Nó não 
solucionado 
com conexão 
mais próxima 
Distância 
Total 
envolvida 
N-ésimo 
nó mais 
próximo 
Distân
cia 
mínima 
Última 
conexão 
1 O 
O 
O 
A 
B 
C 
2 
5 
4 
A 2 OA 
Aplicação do algoritmo proposto ao 
problema do Seervada Park 
Solucionado 
Candidatos 
Empate ????? O que fazer ???? 
n Nós 
solucionados 
diretamente 
conectados a 
nós não 
solucionados 
Nó não 
solucionado 
com conexão 
mais próxima 
Distância 
Total 
envolvida 
N-ésimo 
nó mais 
próximo 
Distân
cia 
mínima 
Última 
conexão 
1 O 
O 
O 
A 
B 
C 
2 
5 
4 
A 2 OA 
2,3 O 
A 
O 
A 
C 
B 
B 
D 
4 
2+2 = 4 
5 
2+7=9 
C 
B 
 
4 
4 
 
OC 
AB 
4 A 
B 
C 
B 
D 
E 
E 
D 
2+7 = 9 
4+3 = 7 
4+4 = 8 
4+4 = 8 
 
E 
 
7 
 
BE 
Aplicação do algoritmo proposto ao 
problema do Seervada Park 
Solucionado 
Candidatos 
Empate !!!!!! 
n Nós 
solucionados 
diretamente 
conectados a nós 
não solucionados 
Nó não 
solucionado 
com conexão 
mais próxima 
Distância 
Total 
envolvida 
N-
ésimo 
nó mais 
próxim
o 
Distân
cia 
mínima 
Última 
conexão 
1 O 
O 
O 
A 
B 
C 
2 
5 
4 
A 2 OA 
2,3 O 
A 
O 
A 
C 
B 
B 
D 
4 
2+2 = 4 
5 
2+7=9 
C 
B 
4 
4 
OC 
AB 
4 A 
B 
C 
B 
D 
E 
E 
D 
2+7 = 9 
4+3 = 7 
4+4 = 8 
4+4 = 8 
 
E 
 
7 
 
BE 
5,6 A 
B 
E 
E 
D 
D 
D 
T 
2+7 = 9 
4+4 = 8 
7+1 = 8 
2+2+3+7=14 
 
D 
D 
 
8 
8 
 
BD 
ED 
Aplicação do algoritmo proposto ao 
problema do Seervada Park 
Solucionado 
Candidatos 
n Nós 
solucionados 
diretamente 
conectados a 
nós não 
solucionados 
Nó não 
solucionado 
com conexão 
mais próxima 
Distância 
Total 
envolvida 
N-ésimo 
nó mais 
próximo 
Distân
cia 
mínima 
Última 
conexão 
1 O 
O 
O 
A 
B 
C 
2 
5 
4 
A 2 OA 
2,3 O 
A 
O 
A 
C 
B 
B 
D 
4 
2+2 = 4 
5 
2+7=9 
C 
B 
4 
4 
OC 
AB 
4 A 
B 
C 
B 
D 
E 
E 
D 
2+7 = 9 
4+3 = 7 
4+4 = 8 
4+4 = 8 
 
E 
 
7 
 
BE 
5,6 A 
B 
E 
D 
D 
D 
2+7 = 9 
4+4 = 8 
7+1 = 8 
 
D 
D 
 
8 
8 
 
BD 
ED 
7 D 
E 
T 
T 
8+5 =13 
7+7 =14 
T 13 DT 
Aplicação do algoritmo proposto ao 
problema do Seervada Park 
Solução final !!! 
Outras Aplicações 
 
 
• Nem todas as aplicações do problema do 
caminho mais curto envolvem minimizar a 
distância percorrida da origem ao destino. 
Outras Aplicações 
• Segundo HILLIER (2013, p. 350), são possíveis 
mais três categorias de aplicações: 
 
– Minimizar a distância total percorrida, como no 
exemplo do Seervada Park; 
– Minimizar o custo total de uma sequência de 
atividades (Problema 9.3-3 é desse tipo.); 
– Minimizar o tempo total de uma sequência de 
atividades (Problema 9.3-6 e 9.3-7 são desse tipo.) 
Outras Aplicações 
• Observação: É até mesmo possível para todas as 
três categorias surgirem na mesma aplicação. 
 
• Observação: Muitas aplicações requerem 
encontrar o caminho direcionado mais curto da 
origem ao destino por uma rede direcionada. 
Basta pequenas alterações no algoritmo para, 
com facilidade, lidar apenas com caminhos 
direcionados. 
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.