Aula_5_POp5

Prévia do material em texto

Disciplina Pesquisa Operacional 
Aula 5 
Professor Ricardo Zanardini 
 
 
 
Objetivos do Estudo 
Olá! Seja bem-vindo à nossa aula de número 5! 
Veremos como é possível, dentre várias possibilidades, determinar qual é o menor caminho entre dois 
pontos, pois problemas dessa natureza são muito comuns no nosso cotidiano e no cotidiano de muitas 
empresas. 
Aprenderemos também que é possível resolver problemas de roteirização, também conhecidos como 
problemas do caixeiro viajante. 
Acesse o material on-line e assista ao vídeo do professor Ricardo para saber mais detalhes sobre os 
conteúdos e objetivos da nossa aula. 
Basta dar um play e acompanhar! 
 
 
 
Vamos começar com os problemas de caminho mínimo, preparado? 
Para que possamos ter uma ideia inicial sobre o que é um problema de caminho mínimo, é importante 
ver o exemplo que está disponível no material on-line. Boa leitura! 
Deu uma olhada no exemplo do PDF? 
Que tal pensar na solução intuitiva desse problema? Assista ao vídeo do professor Ricardo com atenção, 
porque ele irá nos mostrar quais são as possíveis soluções do problema, bem como uma ótima solução 
para isto! Para isso, acesse o material on-line e confira! 
Bom, agora que já temos uma ideia do que é um problema de caminho mínimo, vamos aprender como é 
possível resolver problemas assim, simples ou mais elaborados, utilizando a pesquisa operacional como 
ferramenta. 
Acesse o material on-line e preste atenção no texto que está disponível! Em seguida, confira o vídeo do 
professor Ricardo sobre os problemas de caminho mínimo, assim ficará muito melhor entender direitinho 
como se faz para resolver! Lá você também poderá ler um artigo muito interessante que envolve 
parâmetros incertos e restrições de tempo. 
Problema do Caixiero Viajante 
Outro tipo muito comum dos problemas de pesquisa operacional é o problema do caixeiro viajante. 
Problemas de caixeiro viajante são comuns em situações onde existe a necessidade de, partindo de uma 
certa origem, passarmos uma única vez por uma série de locais pré-estabelecidos e, em seguida, 
retornarmos ao local de origem, de maneira que o custo total seja o menor possível. 
Esse custo pode ser considerado como o tempo, a distância, o valor... 
Existem problemas dessa natureza com restrições e problemas sem restrições, vamos conferir cada um 
deles! 
O exemplo a seguir nos mostra o que é um problema de caixeiro viajante sem restrições. 
Acesse o material on-line e confira os textos e vídeos que o professor Ricardo preparou para você! 
 
O texto a seguir irá nos mostrar que atualmente a aplicação da roteirização é um importante diferencial 
para as empresas de sucesso. Clique no link para conferir! 
http://www.administradores.com.br/artigos/economia-e-financas/a-aplicacao-da-roteirizacao-de-
transportes-como-diferencial-competitivo/48906/ 
Em seguida, acesse o material on-line novamente para ler um texto que nos mostra um estudo de caso 
que trata da importância do uso de softwares de roteirização na gestão de transportes e os respectivos 
benefícios. 
É interessante dar uma conferida para aprimorar ainda mais seus conhecimentos! 
Lá você também encontrará outro texto sobre diversos sistemas de roteirização e programação de 
veículos que são utilizados atualmente. 
Boa leitura! 
 
 
Sugestão de leituras 
Chegamos ao final de mais uma aula! Esperamos que esses assuntos possam ser úteis a você. 
Para saber mais sobre problemas de caminho mínimo, a sugestão é a leitura da seção 6.3 da obra 
Pesquisa Operacional, Hamdy A. Taha, editora Pearson, que pode ser facilmente encontrada na 
biblioteca virtual. 
No material on-line tem uma excelente alternativa para sabermos mais sobre a teoria, algoritmos e 
problemas envolvendo grafos. 
 
Exercícios 
Contextualização 
A Para fixarmos melhor o que vimos até aqui, vamos resolver os seguintes exercícios sobre caminho 
mínimo e sobre problemas de caixeiro viajante. 
 
Bons Estudos! 
 
 
1. Encontre o menor caminho entre os nós 2 e 11 e entre os nós 3 e 13. 
 
 
 
 
2. Encontre o menor caminho entre os nós 1 e 12 e entre os nós 2 e 12: 
 
 
 
 
3. Uma empresa de logística precisa entregar alguns produtos nas seguintes localidades: Curitiba, 
Florianópolis, São Paulo, Vitória, Belo Horizonte e Macapá. Se a sede da empresa fica no Rio de 
Janeiro, determine qual é a menor rota possível para que o caminhão saia carregado do Rio de 
Janeiro, passe por todas as localidades e retorne à origem. A tabela a seguir apresenta as 
distâncias entre todas as localidades. 
 
 
Rio de 
Janeiro 
Curitiba Florianópolis São Paulo Vitória 
Belo 
Horizonte 
Macapá 
Rio de Janeiro 0 840 1128 429 519 438 7211 
Curitiba 841 0 302 403 1282 979 6986 
Florianópolis 1128 302 0 691 1570 1267 7287 
São Paulo 432 405 693 0 874 584 6826 
Vitória 519 1284 1572 873 0 524 7379 
Belo Horizonte 438 982 1270 584 521 0 6861 
Macapá 7213 6986 7285 6824 7394 6875 0 
 
 
 
4. Determine a rota mais curta para um viajante que, partindo de São Paulo, deverá fazer entregas 
nas seguintes cidades: Salvador, Santos, Paranavaí, São Francisco do Sul, Criciúma e, após as 
entregas, retornar para São Paulo. 
 
 São Paulo Salvador Santos Paranavaí 
São 
Francisco 
do Sul 
Criciúma 
São Paulo 0 1962 74,1 705 569 869 
Salvador 1966 0 2025 2371 2544 2844 
Santos 79,8 2025 0 773 564 864 
Paranavaí 710 2372 772 0 674 975 
São 
Francisco 
do Sul 
572 2549 573 675 0 361 
Criciúma 878 2855 879 981 371 0 
 
 
 
Gabarito 
Exercício 1. 
Menor caminho entre os nós 2 e 11: 2-6-7-11; Distância total: 7 
Menor caminho entre os nós 3 e 13: 3-7-11-13; Distância total: 4 
Exercício 2. 
Menor caminho entre os nós 1 e 12: 1-3-5-9-11-12; Distância total: 1.520 
Menor caminho entre os nós 2 e 12: 2--5-9-11-12; Distância total: 1070 
Exercício 3. 
Rota ótima: Rio de Janeiro – São Paulo – Florianópolis – Curitiba – Macapá – Belo Horizonte – Vitória – 
Rio de Janeiro 
Distância total percorrida: 16.325 km 
 
Exercício 4. 
Rota ótima: São Paulo – Santos – São Francisco do Sul – Criciúma – Paranavaí – Salvador – São Paulo 
Distância total percorrida: 6.318,1 km 
 
Capacidade máxima: 110 kbps