exercicios21_11

Prévia do material em texto

Questão 1) Considere o problema da mochila abaixo: 
 
a) Determine a solução ótima do problema. 
b) Determine uma solução heurística (Heurística gulosa) . 
c) Compare a qualidade obtida pela solução heurística. 
 
Questão 2) 
 
 
 
b) Determine uma solução heurística para o problema. Explique como obteve. 
 
Questão 3 Uma viatura de uma empresa situada no local “1” necessita entregar encomendas em 2, 3, 4 e 5 
(clientes) e regressar a empresa. Pretende passar uma e somente uma vez em cada vértice e percorrer a menor 
distancia total (km) e retornar a empresa. Qual a rota a fazer? Aplique duas heurísticas (heurística do vizinho 
mais próximo, da inserção do vértice mais próximo, inserção mais barata, das economias e outros), para 
determinar uma solução para o problema do caixeiro viajante dado na questão anterior 
 1 2 3 4 5 
1 - 77 138 133 90 
2 77 - 182 86 69 
3 138 182 - 87 100 
4 133 86 87 - 146 
5 90 69 100 146 - 
 
Questão 4) Pretende-se instalar um número mínimo de centros de saúde para servir 6 povoados. Quantos, e 
em que povoados deverão ser instalados os centros, de forma a que cada povoado não fique a mais do que 
15Km de um centro? A tabela a seguir está as distâncias (em km) dos povoados aos centros. Apresente o 
modelo matemático. Determine uma solução heurística para o problema. 
 P1 P2 P3 P4 P5 P6 
P1 0 10 20 30 30 20 
P2 10 0 25 35 20 10 
P3 20 25 0 15 30 20 
P4 30 35 15 0 15 25 
P5 30 20 30 15 0 14