Gabarito da unidade 7

Prévia do material em texto

Disciplina: 
Pesquisa Operacional 
GABARITO DA UNIDADE 7 
 
 
Este documento apresenta as resoluções para os exercícios da Unidade 7 do livro texto da disciplina de Pesquisa Operacional. 
 
Exercício 1 
 
Apenas o Exercício 1 será resolvido com explicações passo a passo. O gabarito dos demais exercícios apresentará apenas os conteúdos 
finais das tabelas de custo mínimo e tabelas auxiliares. 
 
Os passos apresentados neste primeiro exercício podem servir de exemplo para o aluno resolver os demais. Caso ainda haja dúvidas, o 
aluno pode consultar os vídeos disponíveis no AVA para esclarecimentos. 
 
Para resolver este exercício, precisamos criar a tabela de caminhos mínimos e a tabela auxiliar. Na primeira iteração devemos colocar 
o nó de origem na tabela de custos mínimos, anotando um custo zero até ele (afinal de contas, ele é o nó de início e não há custo para ir 
a ele). Em seguida precisamos colocar na tabela auxiliar todos os nós atingidos pelo nó inicial, que neste caso é o nó 1. Isso significa 
que vamos analisar todos os nós cujo o “Anterior” seja o nó 1. 
 
Custos Mínimos Tabela Auxiliar 
Nó Anterior Custo Nó Anterior Custo 
1 - 0 2 1 41 
 3 1 44 
 5 1 50 
 
Após isso, precisamos encontrar o nó não resolvido da tabela auxiliar cujo custo seja o menor de todos e copiá-lo para a tabela de custos 
mínimos. 
 
Custos Mínimos Tabela Auxiliar 
Nó Anterior Custo Nó Anterior Custo 
1 - 0 2 1 41 
2 1 41 3 1 44 
 5 1 50 
 
Agora sabemos que o nó 2 está resolvido, por isso, marcaremos ele com uma cor diferente. Precisamos começar a segunda iteração, 
colocando na tabela auxiliar todos os nós atingidos pelo nó 2. É possível atingir apenas o nó 4 a partir do nó 2. Note que o custo que 
temos até o momento para o nó 2 (veja na tabela de custos mínimos) é 41 e o custo do nó 2 ao 4 é 37 (veja na figura do exercício). Logo, 
o custo que deve ser colocado para se chegar ao nó 4 a partir do nó 2 é de 41 + 37 = 78. 
 
Custos Mínimos Tabela Auxiliar 
Nó Anterior Custo Nó Anterior Custo 
1 - 0 2 1 41 
2 1 41 3 1 44 
 5 1 50 
 4 2 78 
 
Agora precisamos encontrar o nó não resolvido na tabela auxiliar cujo custo seja o menor. Isso ocorre com o nó 3 (a partir do 1) com 
custo 44. Precisamos agora copiá-lo para a tabela de custos mínimos, marcá-lo como um nó resolvido e recomeçar uma nova iteração. 
 
Custos Mínimos Tabela Auxiliar 
Nó Anterior Custo Nó Anterior Custo 
1 - 0 2 1 41 
2 1 41 3 1 44 
3 1 44 5 1 50 
 4 2 78 
 
Agora estamos em uma nova iteração. Vamos copiar todos os nós atingidos pelo nó 3 (que foi o nó que acabou de entrar na tabela de 
custos mínimos) na tabela auxiliar. A partir de 3, podemos atingir apenas o nó 5, com custo 44 + 27 = 71. 
 
Custos Mínimos Tabela Auxiliar 
Nó Anterior Custo Nó Anterior Custo 
1 - 0 2 1 41 
2 1 41 3 1 44 
3 1 44 5 1 50 
 4 2 78 
 5 3 71 
 
Agora precisamos olhar na tabela auxiliar e verificar qual nó não resolvido tem custo mínimo. Isso acontece com o nó 5 (a partir de 1) 
com custo 50. Vamos copiá-lo para a tabela de custos mínimos e marcar o nó 5 como resolvido. 
 
Custos Mínimos Tabela Auxiliar 
Nó Anterior Custo Nó Anterior Custo 
1 - 0 2 1 41 
2 1 41 3 1 44 
3 1 44 5 1 50 
5 1 50 4 2 78 
 5 3 71 
 
É o começo de mais uma iteração. Vamos ver quais nós são atingidos pelo nó 5 (que acabou de entrar na tabela de custos mínimos). A 
partir de 5 podemos ir até 6, com custo 50 + 4 = 54. Vamos colocar isso na tabela auxiliar. 
 
Custos Mínimos Tabela Auxiliar 
Nó Anterior Custo Nó Anterior Custo 
1 - 0 2 1 41 
2 1 41 3 1 44 
3 1 44 5 1 50 
5 1 50 4 2 78 
 5 3 71 
 6 5 54 
 
Agora precisamos ver na tabela auxiliar qual nó não resolvido tem menor custo. Isso acontece com o nó 6 (a partir de 5) com custo 54. 
Vamos copiar essa linha para a tabela de custos mínimos e marcá-lo como resolvido. 
 
Custos Mínimos Tabela Auxiliar 
Nó Anterior Custo Nó Anterior Custo 
1 - 0 2 1 41 
2 1 41 3 1 44 
3 1 44 5 1 50 
5 1 50 4 2 78 
6 5 54 5 3 71 
 6 5 54 
 
A partir do nó 6 não é possível ir a nenhum outro nó, então não é necessário acrescentar nenhuma informação à tabela auxiliar. Para 
continuar o algoritmo, agora precisamos escolher o próximo nó não resolvido com custo mínimo. O único nó não resolvido é o nó 4 (a 
partir de 2) com custo 78. Vamos copiá-lo para a tabela de custos mínimos e marcá-lo como resolvido. 
 
Custos Mínimos Tabela Auxiliar 
Nó Anterior Custo Nó Anterior Custo 
1 - 0 2 1 41 
2 1 41 3 1 44 
3 1 44 5 1 50 
5 1 50 4 2 78 
6 5 54 5 3 71 
4 2 78 6 5 54 
 
Neste ponto, podemos ver que todos os nós foram resolvidos. Então podemos parar o algoritmo. A tabela de custos mínimos que 
encontramos é capaz de nos mostrar todos os menores caminhos a partir do nó 1. Portanto, para ir do nó 1 ao 6, precisamos percorrer 1 
– 5 – 6 com custo total de 54. 
 
Exercício 2 
 
Este exercício está com um erro de numeração nos nós. Considere a numeração a seguir como correta: 
 
 
 
Ao final de todas as iterações, as tabelas terão o seguinte conteúdo: 
 
Custos Mínimos Tabela Auxiliar 
Nó Anterior Custo Nó Anterior Custo 
1 - 0 2 1 3 
3 1 2 3 1 2 
2 1 3 4 1 4 
4 1 4 5 3 8 
6 3 5 6 3 5 
5 3 8 5 2 10 
7 6 9 5 4 8 
 6 4 6 
 7 6 9 
 7 5 10 
 
O menor custo para ir de 1 a 7 é percorrendo o trajeto 1 – 3 – 6 – 7 com custo 9 
 
Exercício 3 
 
Para este exercício, considere que a origem é o Nó 1 e o destino final é o Nó 4. 
 
Ao final de todas as iterações, as tabelas terão o seguinte conteúdo: 
 
Custos Mínimos Tabela Auxiliar 
Nó Anterior Custo Nó Anterior Custo 
1 - 0 2 1 2 
2 1 2 5 1 10 
3 2 5 3 2 5 
5 2 9 5 2 9 
4 3 9 4 3 9 
 3 5 17 
 4 5 14 
 
O trajeto para ir do nó 1 ao nó 4 é pelo trajeto 1 – 2 – 3 – 4 com custo total 9 
 
Exercício 4 
 
No enunciado dado no livro, ficou faltando o custo entre os arcos D e F, que é 800. Portanto, considere a figura a seguir para resolver 
este exercício: 
 
 
Ao final de todas as iterações, as tabelas terão o seguinte conteúdo: 
 
Custos Mínimos Tabela Auxiliar 
Nó Anterior Custo Nó Anterior Custo 
A - 0 B A 400 
B A 400 C A 950 
D A 800 D A 800 
C A 950 E B 2200 
F B 1300 F B 1300 
G D 2000 F D 1600 
E C 2050 G D 2000 
H E 2450 E C 2050 
 F C 1550 
 E F 2200 
 G F 2200 
 H F 2600 
 H G 2600 
 H E 2450 
 
Portanto, o melhor caminho para ir de A a F é percorrer A – C – E – H com custo total 2450. 
 
Exercício 5 
 
Neste exercício, o último nó é o Nó F (ao invés do Nó H) 
 
Ao final de todas as iterações, as tabelas terão o seguinte conteúdo: 
Custos Mínimos Tabela Auxiliar 
Nó Anterior Custo Nó Anterior Custo 
A - 0 B A 65 
C A 60 C A 60 
B A 65 D C 95 
E B 80 F C 150 
D C 95 C B 160 
F E 110 D B 110 
 E B 80 
 F E 110 
 E D 135 
 
O menor caminho para ir de A a F é percorrer A – B – E – F com custo 110.