Exercício do Problema do Caixeiro Viajante

Prévia do material em texto

UNIVERSIDADE FEDERAL DO AMAZONAS 
FACULDADE DE TECNOLOGIA 
BACHARELADO EM ENGENHARIA DE PRODUÇÃO 
 
Discentes: Jean Sandro Reis de Moraes – 21950535 
 
Disciplina: Pesquisa Operacional – FTL118 
 
CAIXEIRO VIAJANTE 
(EXERCÍCIOS AULA 27) 
 
1) Um vendedor de livros que mora em Basin deve visitar uma vez por mês quatro clientes 
localizados em Wald, Bon, Mena e Kiln. A tabela dá as distâncias em milhas entre as 
diferentes cidades. 
 
 
O objetivo é minimizar a distância total percorrida pelo vendedor. Formule a questão 
como um problema de PLI baseada em designação. (Formular um problema com a teoria 
do caixeiro viajante). 
𝑥𝑖𝑗 = 1, 𝑠𝑒 𝑜 𝑐𝑙𝑖𝑒𝑛𝑡𝑒 𝑑𝑎 𝑐𝑖𝑑𝑎𝑑𝑒 𝑗 𝑓𝑜𝑖 𝑣𝑖𝑠𝑖𝑡𝑎𝑑𝑜 𝑑𝑒𝑝𝑜𝑖𝑠 𝑑𝑎 𝑐𝑖𝑑𝑎𝑑𝑒 𝑖 
0, 𝑠𝑒 𝑜 𝑐𝑙𝑖𝑒𝑛𝑡𝑒 𝑑𝑎 𝑐𝑖𝑑𝑎𝑑𝑒 𝑗 𝑛ã𝑜 𝑓𝑜𝑖 𝑣𝑖𝑠𝑖𝑡𝑎𝑑𝑜 𝑑𝑒𝑝𝑜𝑖𝑠 𝑑𝑎 𝑐𝑖𝑑𝑎𝑑𝑒 𝑖 
 
𝑀𝑖𝑛 𝑧 = 120𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝑊𝑎𝑙𝑑 + 220𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝐵𝑜𝑛 + 150𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝑀𝑒𝑛𝑎 + 210𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝐾𝑖𝑙𝑛
+ 120𝑥𝑊𝑎𝑙𝑑 𝑋 𝐵𝑎𝑠𝑖𝑛 + 80𝑥𝑊𝑎𝑙𝑑 𝑋 𝐵𝑜𝑛 + 110𝑥𝑊𝑎𝑙𝑑 𝑋 𝑀𝑒𝑛𝑎 + 130𝑥𝑊𝑎𝑙𝑑 𝑋 𝐾𝑖𝑙𝑛
+ 220𝑥𝐵𝑜𝑛 𝑋 𝐵𝑎𝑠𝑖𝑛 + 80𝑥𝐵𝑜𝑛 𝑋 𝑊𝑎𝑙𝑑 + 160𝑥𝐵𝑜𝑛 𝑋 𝑀𝑒𝑛𝑎 + 185𝑥𝐵𝑜𝑛 𝑋 𝐾𝑖𝑙𝑛
+ 150𝑥𝑀𝑒𝑛𝑎 𝑋 𝐵𝑎𝑠𝑖𝑛 + 110𝑥𝑀𝑒𝑛𝑎 𝑋 𝑊𝑎𝑙𝑑 + 160𝑥𝑀𝑒𝑛𝑎 𝑋 𝐵𝑜𝑛 + 190𝑥𝑀𝑒𝑛𝑎 𝑋 𝐾𝑖𝑙𝑛
+ 210𝑥𝐾𝑖𝑙𝑛 𝑋 𝐵𝑎𝑠𝑖𝑛 + 130𝑥𝐾𝑖𝑙𝑛 𝑋 𝑊𝑎𝑙𝑑 + 185𝑥𝐾𝑖𝑙𝑛 𝑋 𝐵𝑜𝑛 + 190𝑥𝐾𝑖𝑙𝑛 𝑋 𝑀𝑒𝑛𝑎 
𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎: 
𝑅𝑒𝑠𝑡𝑟𝑖çã𝑜 𝑑𝑒 𝑠𝑎í𝑑𝑎 
𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝑊𝑎𝑙𝑑 + 𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝐵𝑜𝑛 + 𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝑀𝑒𝑛𝑎 + 𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝐾𝑖𝑙𝑛 = 1 
𝑥𝑊𝑎𝑙𝑑 𝑋 𝐵𝑎𝑠𝑖𝑛 + 𝑥𝑊𝑎𝑙𝑑 𝑋 𝐵𝑜𝑛 + 𝑥𝑊𝑎𝑙𝑑 𝑋 𝑀𝑒𝑛𝑎 + 𝑥𝑊𝑎𝑙𝑑 𝑋 𝐾𝑖𝑙𝑛 = 1 
𝑥𝐵𝑜𝑛 𝑋 𝐵𝑎𝑠𝑖𝑛 + 𝑥𝐵𝑜𝑛 𝑋 𝑊𝑎𝑙𝑑 + 𝑥𝐵𝑜𝑛 𝑋 𝑀𝑒𝑛𝑎 + 𝑥𝐵𝑜𝑛 𝑋 𝐾𝑖𝑙𝑛 = 1 
𝑥𝑀𝑒𝑛𝑎 𝑋 𝐵𝑎𝑠𝑖𝑛 + 𝑥𝑀𝑒𝑛𝑎 𝑋 𝑊𝑎𝑙𝑑 + 𝑥𝑀𝑒𝑛𝑎 𝑋 𝐵𝑜𝑛 + 𝑥𝑀𝑒𝑛𝑎 𝑋 𝐾𝑖𝑙𝑛 = 1 
𝑥𝐾𝑖𝑙𝑛 𝑋 𝐵𝑎𝑠𝑖𝑛 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝑊𝑎𝑙𝑑 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝐵𝑜𝑛 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝑀𝑒𝑛𝑎 = 1 
 
𝑅𝑒𝑠𝑡𝑟𝑖çã𝑜 𝑑𝑒 𝑐ℎ𝑒𝑔𝑎𝑑𝑎 
𝑥𝑊𝑎𝑙𝑑 𝑋 𝐵𝑎𝑠𝑖𝑛 + 𝑥𝐵𝑜𝑛 𝑋 𝐵𝑎𝑠𝑖𝑛 + 𝑥𝑀𝑒𝑛𝑎 𝑋 𝐵𝑎𝑠𝑖𝑛 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝐵𝑎𝑠𝑖𝑛 = 1 
𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝑊𝑎𝑙𝑑 + 𝑥𝐵𝑜𝑛 𝑋 𝑊𝑎𝑙𝑑 + 𝑥𝑀𝑒𝑛𝑎 𝑋 𝑊𝑎𝑙𝑑 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝑊𝑎𝑙𝑑 = 1 
𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝐵𝑜𝑛 + 𝑥𝑊𝑎𝑙𝑑 𝑋 𝐵𝑜𝑛 + 𝑥𝑀𝑒𝑛𝑎 𝑋 𝐵𝑜𝑛 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝐵𝑜𝑛 = 1 
𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝑀𝑒𝑛𝑎 + 𝑥𝑊𝑎𝑙𝑑 𝑋 𝑀𝑒𝑛𝑎 + 𝑥𝐵𝑜𝑛 𝑋 𝑀𝑒𝑛𝑎 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝑀𝑒𝑛𝑎 = 1 
𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝐾𝑖𝑙𝑛 + 𝑥𝑊𝑎𝑙𝑑 𝑋 𝐾𝑖𝑙𝑛 + 𝑥𝐵𝑜𝑛 𝑋 𝐾𝑖𝑙𝑛 + 𝑥𝑀𝑒𝑛𝑎 𝑋 𝐾𝑖𝑙𝑛 = 1 
 
𝑅𝑒𝑠𝑡𝑟𝑖çã𝑜 𝑑𝑒 𝑆𝑢𝑏 − 𝑅𝑜𝑡𝑎𝑠 (𝑑𝑢𝑎𝑠 𝑐𝑖𝑑𝑎𝑑𝑒𝑠): 𝐶5,2 =
5!
2!(5−2)!
= 10 
𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝑊𝑎𝑙𝑑 + 𝑥𝑊𝑎𝑙𝑑 𝑋 𝐵𝑎𝑠𝑖𝑛 ≤ 1 
𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝐵𝑜𝑛 + 𝑥𝐵𝑜𝑛 𝑋 𝐵𝑎𝑠𝑖𝑛 ≤ 1 
𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝑀𝑒𝑛𝑎 + 𝑥𝑀𝑒𝑛𝑎 𝑋 𝐵𝑎𝑠𝑖𝑛 ≤ 1 
𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝐾𝑖𝑙𝑛 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝐵𝑎𝑠𝑖𝑛 ≤ 1 
𝑥𝑊𝑎𝑙𝑑 𝑋 𝐵𝑜𝑛 + 𝑥𝐵𝑜𝑛 𝑋 𝑊𝑎𝑙𝑑 ≤ 1 
𝑥𝑊𝑎𝑙𝑑 𝑋 𝑀𝑒𝑛𝑎 + 𝑥𝑀𝑒𝑛𝑎 𝑋 𝑊𝑎𝑙𝑑 ≤ 1 
𝑥𝑊𝑎𝑙𝑑 𝑋 𝐾𝑖𝑙𝑛 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝑊𝑎𝑙𝑑 ≤ 1 
𝑥𝐵𝑜𝑛 𝑋 𝑀𝑒𝑛𝑎 + 𝑥𝑀𝑒𝑛𝑎 𝑋 𝐵𝑜𝑛 ≤ 1 
𝑥𝐵𝑜𝑛 𝑋 𝐾𝑖𝑙𝑛 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝐵𝑜𝑛 ≤ 1 
𝑥𝑀𝑒𝑛𝑎 𝑋 𝐾𝑖𝑙𝑛 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝑀𝑒𝑛𝑎 ≤ 1 
 
𝑅𝑒𝑠𝑡𝑟𝑖çã𝑜 𝑑𝑒 𝑆𝑢𝑏 − 𝑅𝑜𝑡𝑎𝑠 (𝑡𝑟ê𝑠 𝑐𝑖𝑑𝑎𝑑𝑒𝑠): 𝐶5,3 =
5!
3!(5−3)!
= 10 
𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝑊𝑎𝑙𝑑 + 𝑥𝑊𝑎𝑙𝑑 𝑋 𝐵𝑜𝑛 + 𝑥𝑊𝑎𝑙𝑑 𝑋 𝐵𝑎𝑠𝑖𝑛 ≤ 2 
𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝑊𝑎𝑙𝑑 + 𝑥𝑊𝑎𝑙𝑑 𝑋 𝑀𝑒𝑛𝑎 + 𝑥𝑀𝑒𝑛𝑎 𝑋 𝐵𝑎𝑠𝑖𝑛 ≤ 2 
𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝑊𝑎𝑙𝑑 + 𝑥𝑊𝑎𝑙𝑑 𝑋 𝐾𝑖𝑙𝑛 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝐵𝑎𝑠𝑖𝑛 ≤ 2 
𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝐵𝑜𝑛 + 𝑥𝐵𝑜𝑛 𝑋 𝑀𝑒𝑛𝑎 + 𝑥𝑀𝑒𝑛𝑎 𝑋 𝐵𝑎𝑠𝑖𝑛 ≤ 2 
𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝐵𝑜𝑛 + 𝑥𝐵𝑜𝑛 𝑋 𝐾𝑖𝑙𝑛 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝐵𝑎𝑠𝑖𝑛 ≤ 2 
𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝑀𝑒𝑛𝑎 + 𝑥𝑀𝑒𝑛𝑎 𝑋 𝐾𝑖𝑙𝑛 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝐵𝑎𝑠𝑖𝑛 ≤ 2 
𝑥𝑊𝑎𝑙𝑑 𝑋 𝐵𝑜𝑛 + 𝑥𝐵𝑜𝑛 𝑋 𝑀𝑒𝑛𝑎 + 𝑥𝑀𝑒𝑛𝑎 𝑋 𝑊𝑎𝑙𝑑 ≤ 2 
𝑥𝑊𝑎𝑙𝑑 𝑋 𝑀𝑒𝑛𝑎 + 𝑥𝑀𝑒𝑛𝑎 𝑋 𝐾𝑖𝑙𝑛 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝑊𝑎𝑙𝑑 ≤ 2 
𝑥𝑊𝑎𝑙𝑑 𝑋 𝐵𝑜𝑛 + 𝑥𝐵𝑜𝑛 𝑋 𝐾𝑖𝑙𝑛 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝑊𝑎𝑙𝑑 ≤ 2 
𝑥𝐵𝑜𝑛 𝑋 𝑀𝑒𝑛𝑎 + 𝑥𝑀𝑒𝑛𝑎 𝑋 𝐾𝑖𝑙𝑛 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝐵𝑜𝑛 ≤ 2 
 
𝑅𝑒𝑠𝑡𝑟𝑖çã𝑜 𝑑𝑒 𝑆𝑢𝑏 − 𝑅𝑜𝑡𝑎𝑠 (𝑞𝑢𝑎𝑡𝑟𝑜 𝑐𝑖𝑑𝑎𝑑𝑒𝑠): 𝐶5,4 =
5!
4!(5−4)!
= 5 
𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝑊𝑎𝑙𝑑 + 𝑥𝑊𝑎𝑙𝑑 𝑋 𝐵𝑜𝑛 + 𝑥𝐵𝑜𝑛 𝑋 𝑀𝑒𝑛𝑎 + 𝑥𝑀𝑒𝑛𝑎 𝑋 𝐵𝑎𝑠𝑖𝑛 ≤ 3 
𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝑊𝑎𝑙𝑑 + 𝑥𝑊𝑎𝑙𝑑 𝑋 𝐵𝑜𝑛 + 𝑥𝐵𝑜𝑛 𝑋 𝐾𝑖𝑙𝑛 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝐵𝑎𝑠𝑖𝑛 ≤ 3 
𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝑊𝑎𝑙𝑑 + 𝑥𝑊𝑎𝑙𝑑 𝑋 𝑀𝑒𝑛𝑎 + 𝑥𝑀𝑒𝑛𝑎 𝑋 𝐾𝑖𝑙𝑛 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝐵𝑎𝑠𝑖𝑛 ≤ 3 
𝑥𝐵𝑎𝑠𝑖𝑛 𝑋 𝐵𝑜𝑛 + 𝑥𝐵𝑜𝑛 𝑋 𝑀𝑒𝑛𝑎 + 𝑥𝑀𝑒𝑛𝑎 𝑋 𝐾𝑖𝑙𝑛 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝐵𝑎𝑠𝑖𝑛 ≤ 3 
𝑥𝑊𝑎𝑙𝑑 𝑋 𝐵𝑜𝑛 + 𝑥𝐵𝑜𝑛 𝑋 𝑀𝑒𝑛𝑎 + 𝑥𝑀𝑒𝑛𝑎 𝑋 𝐾𝑖𝑙𝑛 + 𝑥𝐾𝑖𝑙𝑛 𝑋 𝑊𝑎𝑙𝑑 ≤ 3 
 
 
 
 
Milha entre as cidades 
 Basin Wald Bon Mena Kiln 
Basin 0 0 1 0 
Wald 1 0 0 0 
Bon 0 1 0 0 
Mena 0 0 0 1 
Kiln 0 0 1 0 
 
FO 725 
 
 
 
 
 
 
 
 
 
 
 
 
 
Logo, o melhor trajeto que o vendedor de livros terá que fazer para ter a mínima 
distância percorrida, obedecerá a seguinte ordem: 
1º Basin a Mena (150 milhas) 
2º Mena a Kiln (190 milhas) 
3º Kiln a Bon (185 milhas) 
4º Bon a Wald (80 milhas) 
5º Wald a Basin (120 milhas) 
Com esse trajeto ele percorrerá 725 milhas. 
Restrições de saída Restrição Sub-Rotas (quatro cidades)
Basin 1 = 1 1 3 <= 3
Wald 1 = 1 2 3 <= 3
Bom 1 = 1 3 1 <= 3
Mena 1 = 1 4 0 <= 3
Kiln 1 = 1 5 1 <= 3
Restrição de chegada
Basin 1 = 1
Wald 1 = 1
Bom 1 = 1
Mena 1 = 1
Kiln 1 = 1
Restrição Sub-Rotas (duas cidades)
1 1 <= 1
2 0 <= 1
3 1 <= 1
4 0 <= 1
5 1 <= 1
6 0 <= 1
7 0 <= 1
8 0 <= 1
9 1 <= 1
10 1 <= 1
Restrição Sub-Rotas (três cidades)
1 1 <= 2
2 2 <= 2
3 1 <= 2
4 1 <= 2
5 1 <= 2
6 0 <= 2
7 1 <= 2
8 0 <= 2
9 2 <= 2
10 0 <= 2