Pesquisa Operacional - Problemas de Caminho Mínimo em Redes de Transporte

PUCMINAS Engenharia de Produção Pesquisa Operacional Transporte e Sequenciamento Profª Mariana Faleiro Valor 10 pontos Entrega 04062023 Prática 03 Problemas do caminho mínimo 1 Uma fábrica de artigos de decoração localizada em Lambari Minas Gerais deve entregar grande quantidade de peças na cidade de Baependi no mesmo estado A empresa quer saber qual caminho seu caminhão de entregas deve fazer para minimizar a distância total percorrida A Figura 1 abaixo mostra o mapa rodoviário da região do estado em que se situam as duas cidades e a Figura 2 mostra o mapa esquemático e as distâncias entre as cidades na forma de rede utilizando a representação por grafos Figura 01 Mapa rodoviário que liga as cidades de Lambari a Baependi Figura 02 Representação em rede A modelagem do problema terá variáveis binárias do tipo xij indicando o sentido da cidade i para a cidade j Se o valor da variável for igual a 1 significa que aquele trecho deve ser percorrido De forma inversa se o valor da variável for igual a 0 a estrada que liga a cidade i à cidade j não deverá ser utilizada A função objetivo visa minimizar a distância percorrida pelo caminhão Logo se as variáveis de decisão assumem zero ou um a multiplicação destas pelas distâncias entre as respectivas cidades será zero caso a estrada não seja utilizada e igual à distância entre as cidades se ela for utilizada Portanto o somatório desses produtos será a distância percorrida A demanda de Baependi será de um caminhão 1 e a oferta de Lambari será de um caminhão 1 Todas as outras cidades intermediárias terão demanda e oferta iguais a zero A partir disso é possível construir as restrições de fluxo do problema 2 Analise a rede abaixo e faça o que se pede Considere que os números indicados em cada aresta significam o número de quilômetros necessários para um automóvel percorrer a estrada entre duas cidades indicadas pelos nós extremos das arestas observadas Monte o modelo que determine a rota que um automóvel deve seguir para sair de Chapecó e chegar a Porto Alegre percorrendo a menor quantidade de quilômetros possível 0 0 0 xCAXBAEP xLAMBCAX Oferta 1 Demanda 1 0 xLAMBSAOL x3CORSTHL xLAMB3COR xSTHLBAEP xSAOLCAX 3 Você precisa fazer uma viagem de carro para outra cidade que jamais havia estado anteriormente Portanto você está estudando um mapa para determinar a rota mais curta para seu destino Dependendo de qual rota você escolher há cinco outras cidades chamemos estas A B C D E que talvez você passe durante o caminho O mapa mostra a milhagem ao longo de cada estrada que conecta diretamente duas cidades sem qualquer cidade entre elas Esses números são sintetizados na tabela a seguir na qual um traço indica que não há nenhuma estrada conectando diretamente essas duas cidades sem passar por alguma outra cidade Distância em km entre cidades vizinhas Cidade A B C D E Destino Origem 40 60 50 A 10 70 B 20 55 40 C 50 D 10 60 E 80 Questão 1 min 41𝑥12 50𝑥15 44𝑥13 37𝑥24 27𝑥35 45𝑥46 4𝑥56 sa 𝑥12 𝑥13 𝑥15 1 𝑥12 𝑥24 0 𝑥13 𝑥35 0 𝑥24 𝑥46 0 𝑥15 𝑥35 𝑥56 0 𝑥46 𝑥56 1 𝑥𝑖𝑗 0 1 𝑖 𝑗 𝐴𝐺 Questão 2 Considere 1 Chapecó 2 Joacaba 3 Lages 4 Joinvile 5 Caxias do Sul 6 Florianópolis 7 Sombrio 8 Porto Alegre Temos então o seguinte modelo min 400𝑥12 950𝑥13 800𝑥14 1800𝑥25 900𝑥26 1100𝑥35 600𝑥36 600𝑥46 1200𝑥47 400𝑥58 900𝑥65 1300𝑥68 1000𝑥67 600𝑥78 sa 𝑥12 𝑥13 𝑥14 1 𝑥12 𝑥25 𝑥26 0 𝑥13 𝑥35 𝑥36 0 𝑥14 𝑥46 𝑥47 0 𝑥25 𝑥35 𝑥65 𝑥58 0 𝑥26 𝑥36 𝑥46 𝑥65 𝑥68 𝑥67 0 𝑥37 𝑥67 𝑥78 0 𝑥58 𝑥68 𝑥78 1 𝑥𝑖𝑗 0 1 𝑖 𝑗 𝐴𝐺 Questão 3 Considere F Origem G Destino min 40𝑥𝐹𝐴 60𝑥𝐹𝐵 50𝑥𝐹𝐶 10𝑥𝐴𝐵 70𝑥𝐴𝐷 20𝑥𝐵𝐶 55𝑥𝐵𝐷 40𝑥𝐵𝐸 50𝑥𝐶𝐸 10𝑥𝐷𝐸 60𝑥𝐷𝐺 80𝑥𝐸𝐺 sa 𝑥𝐹𝐴 𝑥𝐹𝐵 𝑥𝐹𝐶 1 𝑥𝐹𝐴 𝑥𝐴𝐵 𝑥𝐴𝐷 0 𝑥𝐹𝐵 𝑥𝐵𝐶 𝑥𝐵𝐷 𝑥𝐵𝐸 0 𝑥𝐹𝐶 𝑥𝐶𝐸 0 𝑥𝐴𝐷 𝑥𝐵𝐷 𝑥𝐷𝐸 𝑥𝐷𝐺 0 𝑥𝐷𝐺 𝑥𝐸𝐺 1 𝑥𝑖𝑗 0 1 𝑖 𝑗 𝐴𝐺 Questão 1 min 41 x1250 x1544 x1337 x2427x3545 x464 x56 sa x12x13x151 x12x240 x13x350 x24x460 x15x35x560 x46x561 xij01 i j AG Questão 2 Considere 1 Chapecó 2 Joacaba 3 Lages 4 Joinvile 5 Caxias do Sul 6 Florianópolis 7 Sombrio 8 Porto Alegre Temos então o seguinte modelo min 400 x12950 x13800 x141800 x25900 x261100 x35600x36600 x46 1200 x47400 x58900 x651300 x681000 x67600 x78 sa x12x13x141 x12x25x260 x13x35x360 x14x46x470 x25x35x65x580 x26 x36x46x65x68x670 x37 x67x780 x58x68x781 xij01 i j AG Questão 3 Considere F Origem G Destino min 40 x FA60x FB50x FC10x AB70 x AD20 xBC55x BD40 xBE50 xCE 10 xDE60 x DG80 xEG sa xFAxFBx FC1 xFAxABx AD0 xFBxBCxBDxBE0 xFCxCE0 x ADxBDx DEx DG0 xDGx EG1 xij01 i j AG