(LACHTERMACHER, 2009) Uma fábrica de tecidos sediada em Lambari, MG, deve transportar uma grande quantidade de peças para Baependi, MG. Considere a...

(a) As variáveis de decisão são as possíveis rotas que a fábrica pode seguir para chegar a Baependi. Podemos representar cada rota por uma variável binária, onde 1 indica que a rota é escolhida e 0 indica que não é escolhida. Seja xi a variável que representa a escolha da rota i, onde i = 1, 2, 3, 4, 5. A função objetivo é minimizar a distância total percorrida, que pode ser representada por: min Z = 41x1 + 44x2 + 50x3 + 4x4 + 45x5 + 37x6 As restrições são que a fábrica deve sair de Lambari e chegar a Baependi, ou seja: x1 + x2 + x3 + x4 + x5 + x6 = 1 Além disso, cada rota só pode ser escolhida uma vez, ou seja: x1 + x2 ≤ 1 x1 + x3 ≤ 1 x2 + x3 + x4 ≤ 1 x2 + x5 ≤ 1 x3 + x6 ≤ 1 x4 + x5 + x6 ≤ 1 (b) Usando o algoritmo de Dijkstra, a rota mais curta é Lambari - Caxambu - Baependi, com distância total de 91 km.