Atividade de Pesquisa Operacional 2

2 crédito PESQUISA OPERACIONAL II PROFESSOR LEONARDO Questões de 1 a 12 tem peso 1 Questões do capítulo do livro Modelagem e Análise de Decisão tem peso 4 Q33 e Casos 51 a 54 1 4 Suponha que no problema 2 os nós 3 e 4 tivessem uma demanda de 20 e 30 itens respectivamente Agora desenvolva o problema de transbordo 5 A partir do Problema de Transbordo Bavarian Motor Company estudado em sala altere as seguintes informações e desenvolva o problema de transbordo RICHMOND APRESENTA OFERTA DE 50 ITENS ATLANTA TEM DEMANDA DE 200 ITENS COLUMBUS E MOBILE TEM DEMANDA DE 100ITENS CADA A rede da Figura 510 mostra as rotas de expedição de carros de três fábricas nós 1 2 e 3 para as três revendedoras nós 6 a 8 passando por duas centrais de distribuição nós 4 e 5 Os custos de expedição por carro em 100 são mostrados nos arcos a Resolva a questão como um problema de transbordo b Ache a nova solução ótima considerando que a Central de Distribuição 4 possa vender 240 carros diretamente a clientes Uma empresa fabrica um determinado produto em três cidades P1 P2 e P3 o produto destinase a quatro centros de consumo C1 C2 C3 e C4 O custo estimado de transportar o produto das fábricas para os centros consumidores assim como a demanda de cada centro e a oferta de cada fábrica é dado na tabela a seguir Destino Origem C1 C2 C3 C4 Oferta P1 10 7 6 5 9 P2 2 8 9 1 10 P3 11 12 8 4 8 Demanda 7 6 10 4 Formule o modelo de transporte para se determinar o programa que torna mínimo o custo total de transporte entre as quatro cidades e os três centros consumidores Um dado produto é produzido em diferentes fábricas do país com capacidades de produção limitadas e deve ser levado a centros de distribuição depósitos em regiões onde há demandas a serem satisfeitas O custo de transporte de cada fábrica a cada depósito é proporcional à quantidade transportada A tabela a seguir fornece os custos unitários de transporte de cada fábrica para cada depósito bem como as demandas em cada depósito e as produções de cada fábrica Depósitos Fábricas Florianópolis Rio de Jane iro Salvador Manaus Produções Curitiba 1 08 3 45 470 São Paulo 15 06 25 3 400 Aracaju 6 5 12 28 400 Demanda 350 300 300 120 Faça a modelagem do problema Uma rede de depósitos de material de construção tem 4 lojas que devem ser abastecidas com 50 m³ L1 80 m³ L2 40 m³ L3 100 m³ L4 de areia grossa Essa areia pode ser encarregada em 3 portos P1 P2 e P3 cujas distâncias às lojas estão no quadro em km L1 L2 L3 L4 P1 30 20 24 18 P2 12 36 30 24 P3 8 15 25 20 O caminhão pode transportar 10 m³ por viagem Os portos tem areia para suprir qualquer demanda Estabelecer um plano de transporte que minimize a distância total percorrida entre os portos e as lojas e supra as necessidades das lojas Construa o modelo linear do problema 12 Formule e resolva o problema de transporte de modo que os clientes 1 2 e 3 sejam atendidos QUESTÃO 1 A questão apresentada é um problema de transporte em duas etapas das montadoras P1 e P2 para as centrais de distribuição T1 e T2 e das centrais de distribuição para os revendedores D1 D2 e D3 Vamos resolver o problema utilizando um método de programação linear Oferta P1 1000 unidades P2 1200 unidades Demanda D1 800 unidades D2 900 unidades D3 500 unidades Custos Fase 1 Montadoras para Centrais P1 para T1 300 P1 para T2 400 P2 para T1 200 P2 para T2 500 Fase 2 Centrais para Revendedores T1 para D1 800 T1 para D2 600 T1 para D3 não disponível T2 para D1 não disponível T2 para D2 400 T2 para D3 900 Variáveis de decisão xP1 T 1 Quantidade enviada de P1 para T1 xP1 T 2 Quantidade enviada de P1 para T2 xP2 T 1 Quantidade enviada de P2 para T1 xP2 T 2 Quantidade enviada de P2 para T2 xT 1 D1 Quantidade enviada de T1 para D1 xT 1 D2 Quantidade enviada de T1 para D2 xT 2 D2 Quantidade enviada de T2 para D2 xT 2 D3 Quantidade enviada de T2 para D3 Restrições Restrições de oferta nas montadoras xP1 T 1 xP1T 21000 xP2 T 1xP2T 21200 Restrições de demanda nas centrais de distribuição xT 1 D1xT 2 D2xP1 T 1xP2T 1 xT 2 D2xT 2 D3x P1T 2xP2 T 2 Restrições de demanda nos revendedores xT 1 D1800 xT 1 D2xT 2 D2900 xT 2 D3500 Todas as variáveis x devem ser maiores ou iguais a zero Função Objetivo Minimizar o custo total Z300 xP1T 1400 xP1T 2200 xP 2 T 1500 xP2T 2800xT 1 D 1600 xT 1 D2400xT 2D 2900xT 2D 3 A solução do problema é Quantidade transportada de P1 para T1 0 unidades Quantidade transportada de P1 para T2 1000 unidades Quantidade transportada de P2 para T1 800 unidades Quantidade transportada de P2 para T2 400 unidades Quantidade transportada de T1 para D1 0 unidades Quantidade transportada de T1 para D2 800 unidades Quantidade transportada de T2 para D2 900 unidades Quantidade transportada de T2 para D3 500 unidades O custo total mínimo é de 2050000 Na construção de uma rodovia empregamse jazidas de rochas para obtenção de pedra britada É conveniente transportar este material de jazidas em pedreiras localizadas nas proximidades para alguns pontos preestabelecidos ao longo do caminho em que passará a estrada Esquema para m4 pedreiras e n3 depósitos A tabela a seguir contém os dados do problema Os custos e demandas são dados por tonelada de pedra britada Depósitos Pedreiras 1 2 3 Oferta 1 30 13 21 433 2 12 40 26 215 3 27 15 35 782 4 37 25 19 300 demanda 697 421 612 QUESTÃO 2 a Desenvolva o problema de transbordo correspondente O problema de transbordo é um tipo de problema de fluxo em rede onde há nós de origem nós de destino e nós de transbordo O objetivo é determinar a rota mais econômica para transportar mercadorias das origens para os destinos respeitando a capacidade dos nós e os custos de transporte Origens Nós 1 e 2 oferecem respectivamente 100 e 200 itens Destinos Nós 5 e 6 com demandas de 150 itens cada Nós de transbordo Nós 3 e 4 Definindo variáveis de decisão Seja xij o número de itens transportados do nó i para o nó j Os arcos com os respectivos custos unitários são dados na imagem A seguir estão as variáveis com os respectivos custos x13 Custo 1 x14 Custo 3 x15 Custo 6 x23 Custo 2 x24 Custo 4 x26 Custo 5 x35 Custo 5 x36 Custo 1 x46 Custo 8 Restrições Oferta total do nó 1 x13x14x15100 Oferta total do nó 2 x23x24x26200 Demanda total do nó 5 x15x35150 Demanda total do nó 6 x26 x36x46150 Além disso os nós de transbordo nós 3 e 4 têm o balanço de fluxo Fluxo no nó 3 x13x23x35x36 Fluxo no nó 4 x14x24x46 O objetivo é minimizar o custo total de transporte Z1x133 x146x152 x234 x245 x265 x351 x368 x46 b Resolver o problema Considerando as informações da letra a temse Solução de transporte Do nó 1 Envia 100 itens para o nó 3 x13 100 Do nó 2 Envia 50 itens diretamente para o nó 6 x26 50 Envia 150 itens para o nó 4 x24 150 Do nó 3 Envia 100 itens para o nó 5 x35 100 Do nó 4 Envia 150 itens para o nó 6 x46 150 Custos totais O custo total do transporte é calculado com base nos fluxos encontrados Z110041505100815055010060050012002502650 O custo total mínimo de transporte é 2650 com os embarques roteados conforme descrito abaixo Nó 1 envia 100 itens para o nó 3 Nó 2 envia 50 itens diretamente para o nó 6 e 150 itens para o nó 4 Nó 3 envia 100 itens para o nó 5 Nó 4 envia 150 itens para o nó 6 QUESTÃO 3 Se adiciona uma nova ligação entre os nós 1 e 2 com um custo de expedição de 1 Além disso a expedição do nó 1 para o nó 3 sofre um aumento de 5 no custo A função objetivo deve ser ajustada para considerar o novo custo entre os nós 1 e 2 e o aumento no custo de transporte entre os nós 1 e 3 A nova função objetivo é Z6 x133 x146 x151 x122 x234 x245 x265 x351 x368 x46 Restrições As restrições de oferta demanda e transbordo permanecem as mesmas com a adição da nova variável x12 que representa o número de unidades transportadas do nó 1 para o nó 2 x14x15100 Oferta nos nós de origem Nó 1 x12x13x14x15100 Nó 2 x23x24x26200x12 Demanda nos nós de destino Nó 5 x15x35150 Nó 6 x26 x36x46150 Fluxo nos nós de transbordo Nó 3 x13x23x35x36 Nó 4 x14x24x46 Distribuição de fluxo Do nó 1 Envia 50 itens diretamente para o nó 2 x1250 Envia 50 itens para o nó 3 x1350 Do nó 2 Envia 50 itens diretamente para o nó 6 x2650 Envia 100 itens para o nó 4 x24100 Do nó 3 Envia 50 itens para o nó 5 x3550 Do nó 4 Envia 100 itens para o nó 6 x46100 Atualizando a função custo Z65015041005508100550 Z300504002508002502050 Com a nova rota entre os nós 1 e 2 e o aumento no custo de transporte do nó 1 para o nó 3 o custo total mínimo de transporte é 2050 Os embarques são roteados da seguinte forma Nó 1 envia 50 itens para o nó 2 e 50 itens para o nó 3 Nó 2 envia 50 itens diretamente para o nó 6 e 100 itens para o nó 4 Nó 3 envia 50 itens para o nó 5 Nó 4 envia 100 itens para o nó 6 QUESTÃO 4 Considerouse uma nova demanda para os nós 3 e 4 com demandas de 20 e 30 itens respectivamente Precisamos agora ajustar o problema de transbordo para incorporar essas novas demandas e resolver o problema com as novas restrições O nó 3 tem agora uma demanda de 20 itens O nó 4 tem agora uma demanda de 30 itens Além das demandas nos nós 5 e 6 agora também precisamos atender às demandas dos nós 3 e 4 Demanda no nó 3 x13x2320 Demanda no nó 4 x14x2430 Demanda no nó 5 x15x35150 Demanda no nó 6 x26 x36x46150 As restrições de oferta continuam as mesmas com o nó 1 ofertando 100 itens e o nó 2 ofertando 200 itens Oferta nos nós 1 e 2 Nó 1 x13x14x15100 Nó 2 x23x24x26200 A função objetivo continua sendo a minimização do custo total de transporte Z1x133 x146x152 x234 x245 x265 x351 x368 x46 Distribuição de fluxo Do nó 1 Envia 10 itens para o nó 3 x1310 Envia 30 itens para o nó 4 x1430 Envia 60 itens para o nó 5 x1560 Do nó 2 Envia 10 itens para o nó 3 x2310 Envia 0 itens para o nó 4 x240 Envia 130 itens diretamente para o nó 6 x26130 Do nó 3 Envia 50 itens para o nó 5 x3550 Do nó 4 Envia 20 itens para o nó 6 x4620 Agora calculamos o custo total utilizando os fluxos encontrados Z11033066021051305508201090360206502501601540 Com as novas demandas nos nós 3 e 4 20 e 30 itens respectivamente o custo total mínimo de transporte é 1540 Os embarques são roteados da seguinte forma Nó 1 envia 10 itens para o nó 3 30 itens para o nó 4 e 60 itens para o nó 5 Nó 2 envia 10 itens para o nó 3 e 130 itens diretamente para o nó 6 Nó 3 envia 50 itens para o nó 5 Nó 4 envia 20 itens para o nó 6 QUESTÃO 5 Richmond tem uma oferta de 50 itens Atlanta tem uma demanda de 200 itens Columbus e Mobile têm uma demanda de 100 itens cada Portanto as cidades de Richmond origem e Atlanta demanda e Columbus e Mobile demanda formam os nós de um novo problema de transbordo Devemos resolver este problema otimizando os custos de transporte Definição dos nós Nó 1 Richmond Oferta 50 itens Nó 2 Atlanta Demanda 200 itens Nó 3 Columbus Demanda 100 itens Nó 4 Mobile Demanda 100 itens A formulação do problema de transbordo incluirá a oferta em Richmond e as demandas nas outras cidades Devemos definir as rotas e os custos de transporte entre os nós sem detalhes explícitos sobre os custos que podem ser arbitrariamente definidos para representar rotas diretas ou intermediárias Suponha que as variáveis xij representem o número de itens transportados do nó i para o nó j Assim a função objetivo seria minimizar o custo total de transporte Zc12x12c13 x13c14 x14c23 x23c24 x24c34x34 Onde cij são os custos unitários de transporte entre os nós i e j xij são as variáveis de decisão que representam o número de itens transportados entre os nós Restrições Oferta Nó 1 Richmond x12x13x1450 Demanda Nó 2 Atlanta x12x23x24200 Nó 3 Columbus x13x23100 Nó 4 Mobile x14x24x34100 Fluxo de transbordo Se houver rota intermediária como entre Columbus e Mobile nó 3 e nó 4 temse também x34x43 respeitando o equilíbrio de fluxos entre cidades De Richmond Nó 1 como há uma oferta limitada de 50 itens ele pode enviar parte para Atlanta e o restante para Columbus e Mobile Atlanta Nó 2 precisará receber itens de Richmond ou de outras cidades próximas Columbus e Mobile Nó 3 e Nó 4 podem trocar itens entre si ou receber diretamente de Richmond e Atlanta Distribuição de fluxo hipotética Richmond envia 20 itens para Atlanta x1220 Richmond envia 30 itens para Columbus x1330 Atlanta envia 80 itens para Columbus x2380 Atlanta envia 100 itens para Mobile x24100 Columbus envia 20 itens para Mobile x3420 Supondo que temos os seguintes custos de transporte entre os nós c125c134 c148c233 c246c342 Z5204 303806100220100120240600401100 Neste cenário o custo total mínimo de transporte para atender às demandas de Atlanta Columbus e Mobile é 1100 Os itens são roteados da seguinte forma Richmond envia 20 itens para Atlanta e 30 itens para Columbus Atlanta envia 80 itens para Columbus e 100 itens para Mobile Columbus envia 20 itens para Mobile QUESTÃO 6 a Resolva a questão como um problema de transbordo Os nós de origem são as fábricas nós intermediários são as centrais de distribuição e nós de destino são os revendedores Vamos definir as variáveis de decisão e a função objetivo Variáveis de decisão xij quantidade de carros enviados do nó i para o nó j i 12345 para as fábricas e centrais de distribuição j 4567 8 para os pontos de destino Função objetivo Minimizamos o custo total de transporte Z i j cijxij onde cij é o custo de transporte entre os nós i e j dado na rede Restrições Oferta e demanda Cada fábrica nós 1 2 3 tem uma capacidade de produção específica Cada revendedor nós 6 7 8 tem uma demanda específica Conservação de fluxo nos nós intermediários nós 4 e 5 O total de carros que entra em um nó intermediário deve ser igual ao total de carros que sai desse nó O custo total deve ser minimizado Z04 x1405 x1503x2405 x2503 x3402x3504 x4603 x4703 x4805x5603 x5702x58 Onde os custos são multiplicados pelas variáveis que representam a quantidade de carros enviados entre os nós Capacidades de produção das fábricas nós 1 2 3 x14x15900 x24x251200 x34x351100 Capacidade de fluxo nos nós intermediários 4 e 5 x14x24x34x46x47x48 x15x25x35x56x57x58 Demandas nos revendedores nós 6 7 8 x46x561100 x47x571200 x48x58900 O custo total Z minimizando os custos de transporte com base nos custos unitários fornecidos nos arcos será Z03600059004311004650019500 Z180450473023009508610 O custo total Z é 8610 em 100 dólares b Ache a nova solução ótima considerando que a Central de Distribuição 4 possa vender 240 carros diretamente a clientes Com a nova restrição de que o nó 4 pode vender diretamente até 240 carros adicionase uma nova variável x4cpara representar a quantidade de carros vendidos diretamente do nó 4 para os revendedores com a restrição x4c 240 Nesta parte ajustamos a solução permitindo que a central 4 envie 240 carros diretamente para os clientes Isso reduz o fluxo que precisa passar pelos revendedores e centros de distribuição A nova restrição será x46x47 x48240 Cálculo ajustado 1 Fluxo da central 4 para os clientes diretamente 240custo zero0 supondo que o custo seja zero para o transporte direto conforme o enunciado da questão sugere 2 Ajuste do restante O restante do fluxo se ajustará conforme as capacidades e demandas dos outros nós Usaremos a mesma fórmula que calculamos anteriormente mas retirando a parte do fluxo direto de 240 carros Portanto o novo custo Z será Z03600059004311004650024019500 Z180450473046260950 Z180450473011969507506 Isso resulta em uma redução do custo total em relação à situação inicial QUESTÃO 7 Neste problema temos jazidas pedreiras que devem fornecer pedra britada para depósitos ao longo da estrada O objetivo é minimizar os custos de transporte respeitando as capacidades das pedreiras e as demandas dos depósitos Variáveis de decisão xij quantidade de pedra britada transportada da pedreira i para o depósito j Função objetivo Minimizamos o custo total de transporte Z i1 m j1 n cijxij onde cij é o custo por tonelada de transporte da pedreira i para o depósito j conforme fornecido na tabela Z30 x1131x1221x1332x2125 x2226 x2327 x3115 x3235 x3318 x4119x4223 x43 Restrições Oferta A quantidade total transportada de cada pedreira não pode exceder a sua capacidade Oferta das pedreiras x11x12x13 433 x21x22x23215 x31x32 x33782 x41 x42x43 300 Demanda Cada depósito deve receber a quantidade necessária para atender sua demanda Demanda dos depósitos x11x21x31x41697 x12x22x32x42421 x13x23x33x43612 QUESTÃO 8 Esse problema envolve uma empresa que transporta produtos de fábricas para centros de consumo Vamos modelar o problema de transporte para minimizar os custos Variáveis de decisão xij quantidade de produto transportada da fábrica Pi para o centro de consumo C j Função objetivo Minimizamos o custo total de transporte Z i1 3 j1 4 cijxij onde cij é o custo de transporte da fábrica i para o centro j Restrições Oferta A quantidade total transportada de cada fábrica não pode exceder a sua capacidade Demanda Cada centro de consumo deve receber a quantidade necessária para atender sua demanda Função objetivo Z10 x117 x126 x139x147 x219x225 x2310 x2411 x3112 x328 x336 x34 Restrições Oferta das fábricas x11x12x13x149 x21x22x23x24 10 x31x32 x33x348 Demanda dos centros de consumo x11x21x317 x12x22x326 x13x23x3310 x14x24x344 QUESTÃO 9 Esse problema é similar aos anteriores envolvendo a produção e distribuição de um produto para diversos centros Vamos modelálo de forma a minimizar o custo Variáveis de decisão xij quantidade de produto transportada da fábrica i para o depósito j Função objetivo Minimizamos o custo total de transporte Z i1 3 j1 4 cijxij onde cij é o custo de transporte da fábrica i para o depósito j conforme a tabela Z2x115 x123x134 x1415x214 5 x223x231x246 x315x3225 x3328 x34 Restrições Oferta A quantidade total transportada de cada fábrica não pode exceder a capacidade de produção de cada uma Oferta das fábricas x11x12x13x14470 x21x22x23x24 800 x31x32 x33x34 400 Demanda Cada depósito deve receber a quantidade necessária para atender sua demanda Demanda dos depósitos x11x21x31350 x12x22x32300 x13x23x33300 x14x24x34120 QUESTÃO 10 Minimizar a distância total percorrida dada por Z30 x1120x1224 x1318x1412 x2136 x2230 x2324 x248 x3115 x3225 x3320x34 Restrições de Demanda Loja1 L1 x11x21x3150 Loja2 L2 x12x22x3280 Loja3 L3x13x23x3340 Loja 4 L4 x14x24x34100 Restrições de Oferta Assumindo que cada porto tem capacidade ilimitada pois não foi especificado xIJ 0 i j QUESTÃO 11 Função Objetivo Minimizar o custo total de transporte Z0081000 x112690 x121250 x211350 x221275 x31850x32 Restrições Capacidade das Fábricas x11x121000Los Angeles x21x221500Detroit x31x321200NovaOrleans Demanda dos Centros de Distribuição x11x21x312300Denver x12x22x321400Miami QUESTÃO 12 Temse um problema de transporte envolvendo duas plantas Planta 1 e Planta 2 dois centros de distribuição CD1 e CD2 e três clientes C1 C2 e C3 Função Objetivo Minimizar o custo total de transporte entre plantas e clientes via centros de distribuição CD1 e CD2 Restrições Capacidade das plantas e demanda dos clientes são configuradas conforme o gráfico Minimizar o custo total de transporte Z5 xP1CD 14 xP1 CD20 xP2 CD12 xP2CD 23xCD 1C 13 xCD 1C 23 xCD2C 14 xCD2C 21 xCD 1C 32 xCD2C 3 Restrições 1 Capacidade das plantas xP1 CD1xP1CD 2 xP2 CD1xP2 CD260000 2 Capacidade dos CDs xCD1 C 1xCD 1C 2 xCD 1C 3x P1CD 1x P2CD1 xCD2 C 1xCD 2C 2xCD 2C 3x P1CD 2x P2CD 2 3 Atender a demanda dos clientes xCD1 C 1xCD 1C 250000 xCD1 C 2xCD 2C 2100000 xCD1 C 3xCD 2C 350000 A função objetivo Z será Z5500004600002400000500003100000150000 Z25000024000080000030000050000920000