Problemas de Redes Otimização de Fluxo e Caminho Mínimo com Solver

5º Aula Redes Objetivos de aprendizagem Ao término desta aula vocês serão capazes de aprender sobre os problemas de rede e sua forma de resolução entender e resolver os problemas de caminho mínimo compreender e resolver os problemas de fluxo máximo entender como modelar os problemas de rede e resolver no Excel Solver Prezadosas alunosas Nesta quinta aula focaremos em um ramo bem específico da Pesquisa Operacional que são as redes Esta aula se assemelha a aula 4 referente ao problema do transporte e suas variantes com a diferença de que aqui temos a adição de múltiplas fontes consumidoras fornecedoras e de intermediários Será dado o foco na modelagem e resolução via Excel Solver Bons estudos 42 Pesquisa Operacional Seções de estudo 1 O problema de redes 2 Caminho mínimo 3 Problema do fl uxo máximo 1 O problema de redes De acordo com Lachtermacher 2016 problemas que consideram múltiplas fontes centros consumidores e locais intermediários por onde os produtos simplesmente passam são denominados problemas de rede de distribuição Os problemas de transporte podem ser considerados uma simplifi cação do problema de rede de distribuição de custo mínimo em que as localizações intermediárias não existem O exemplo a seguir baseado em Lachtermacher 2016 ilustra um típico caso de problema de rede de distribuição 11 Exemplo de problema de redes Caso LCL Carros Brasil Ltda A montadora de veículos LCL Carros Brasil Ltda está iniciando suas operações no país com duas fábricas uma na Bahia e outra em São Paulo A LCL está estudando uma forma de distribuição de seus carros para as diversas revendas localizadas nos estados de Goiás Rio de Janeiro Minas Gerais Paraná Santa Catarina e Rio Grande do Sul de modo a minimizar o custo total de distribuição Figura 1 As capacidades instaladas de cada uma das fábricas as demandas das revendas bem como os custos unitários de transporte entre fábricas e revendas são mostrados no diagrama da Figura 2 Figura 1 Localização das fábricas e distribuidores da LCL Carros Brasil Fonte Lachtermacher 2016 Figura 2 Diagrama da rede do caso LCL Carros Brasil Fonte Lachtermacher 2016 Em uma primeira e rápida análise concluímos facilmente que as variáveis de decisão do modelo serão as quantidades de veículos enviadas de cada fábrica a cada distribuidor e a funçãoobjetivo será a minimização do custo total de transporte No entanto o problema apresenta dois detalhes especiais o número de carros demandados é maior do que a capacidade de produção da empresa e alguns distribuidores de Minas Gerais e de Santa Catarina também podem enviar carros que receberam das fábricas para outros distribuidores possivelmente suas fi liais LACHTERMACHER 2016 Existem duas maneiras básicas de resolver esse tipo de problema A primeira consiste em inserir uma unidade dummy que iguale a oferta e a demanda totais Se a oferta for maior que a demanda a variável dummy será colocada como uma unidade de demanda ligada às unidades de oferta De forma inversa se a demanda for maior que a oferta a variável dummy representará um novo ponto de oferta para atender à demanda excedente Em ambos os casos todas as restrições serão consideradas igualdades A segunda forma de resolver problemas de distribuição é seguir a regra do fl uxo balanceado para cada nó unidade da rede Por essa regra não há necessidade da inserção de variáveis do tipo dummy o desequilíbrio entre a oferta total e a demanda total é tratado por meio de restrições de maior ou igual ou de menor ou igual A Tabela 1 resume a forma de aplicação da regra do fl uxo balanceado Tabela 1 Regra do fl uxo balanceado Hipótese do problema Tipo de restrição para cada nó Oferta Demanda Entradas Saídas Oferta ou demanda Oferta Demanda Entradas Saídas Oferta ou demanda Oferta Demanda Entradas Saídas Oferta ou demanda Fonte Elaborado pelo autor Resolveremos o caso da LCL Carros Brasil pelos dois métodos A Figura 2 mostra a diferença entre a capacidade de produção da empresa oferta e o número de carros requeridos pelos estados demanda Nesse caso há uma oferta de 1100 veículos e uma demanda de 1400 Assim o primeiro passo para resolver esse problema pela primeira alternativa é inserir uma unidade de oferta dummy com disponibilidade de 300 veículos e conectada a todos os nós de demanda com custo zero de transporte Figura 3 Figura 3 Diagrama de rede do caso LCL Carros Brasil 1ª alternativa Fonte Lachtermacher 2016 43 De acordo com esse primeiro método de modelagem o problema que será inserido na planilha Excel tem os parâmetros a seguir Variáveis de decisão x13 número de carros enviados da BA para MG x14 número de carros enviados da BA para o RJ x15 número de carros enviados da BA para GO x23 número de carros enviados de SP para MG x24 número de carros enviados de SP para o RJ x26 número de carros enviados de SP para o PR x27 número de carros enviados de SP para SC x28 número de carros enviados de SP para o RS x34 número de carros enviados de MG para o RJ x35 número de carros enviados de MG para GO x78 número de carros enviados de SC para o RS x93 número de carros que MG deixará de receber x94 número de carros que o RJ deixará de receber x95 número de carros que GO deixará de receber x96 número de carros que o PR deixará de receber x97 número de carros que SC deixará de receber x98 número de carros que o RS deixará de receber Funçãoobjetivo Min 25x13 30x14 40x15 20x23 15x24 20x26 35x27 50x28 20x34 20x35 20x78 Montaremos as restrições conforme a seguinte lógica o número de carros que chegam ao nó menos o montante que sai deve ser igual à oferta negativa ou à demanda positiva do nó Restrições de fluxo x13 x14 x15 500 nó 1 x23 x24 x26 x27 x28 600 nó 2 x13 x23 x93 x34 x35 200 nó 3 x14 x24 x34 x94 350 nó 4 x15 x35 x95 150 nó 5 x26 x96 300 nó 6 x27 x97 x78 150 nó 7 x28 x78 x98 250 nó 8 2x93 x94 x95 x96 x97 x98 300 nó 9 A Figura 4 mostra uma das maneiras de o problema ser modelado no Excel Para inserir a condição de que o fluxo líquido de cada nó quantidade que chega menos quantidade que sai deve ser igual à respectiva demanda positiva ou oferta negativa utilizaremos a função SomaSe do Excel ou SumIf em inglês Essa função serve para somar as células especificadas por determinado critério que pode ser um número uma expressão 100 por exemplo ou um texto No nosso problema a função SomaSe nos ajudará a calcular o fluxo líquido de cada nó com base em seus critérios de identificação Na Figura 4 a célula I16 representa a funçãoobjetivo e as células E4 a E20 as variáveis de decisão do modelo As células H4 a H12 representam os LHS das restrições de fluxo e as células I4 a I12 os RHS lado direito da equação de restrição das células A Tabela 2 mostra as fórmulas utilizadas nas células que representam cada LHS lado esquerdo da equação das restrições e na célula que denota a função objetivo Figura 4 Modelagem da rede do caso LCL Carros Brasil 1o método Fonte Lachtermacher 2016 Tabela 2 Fórmulas utilizadas nas restrições do problema de redes de distribuição Funçãoobjetivo Célula Fórmula referente a função objetivo z I16 SOMARPRODUTOD4D14E14E14 Restrição Célula Resultado da restrição Nó 1 H4 SOMASEC4C20G4E4E20 SOMASEB4B20G4E4E20 Nó2 H5 SOMASEC4C20G5E4E20 SOMASEB4B20G5E4E20 Nó 3 H6 SOMASEC4C20G6E4E20 SOMASEB4B20G6E4E20 Nó 4 H7 SOMASEC4C20G7E4E20 SOMASEB4B20G7E4E20 Nó 5 H8 SOMASEC4C20G8E4E20 SOMASEB4B20G8E4E20 Nó 6 H9 SOMASEC4C20G9E4E20 SOMASEB4B20G9E4E20 Nó 7 H10 SOMASEC4C20G10E4E20 SOMASEB4B20G10E4E20 Nó 8 H11 SOMASEC4C20G11E4E20 SOMASEB4B20G11E4E20 Nó 9 H12 SOMASEC4C20G12E4E20 SOMASEB4B20G12E4E20 Fonte Elaborado pelo autor Uma vez feita a modelagem devemos estabelecer os parâmetros e as opções do Solver Figura 5 e otimizálo A Figura 6 apresenta a solução ótima do problema Nela verificamos que a forma mais econômica de a LCL Carros Brasil atender a seus distribuidores é enviando 200 carros da fábrica da Bahia para Minas Gerais 150 da Bahia para o Rio de Janeiro 150 da Bahia para Goiás 200 de São Paulo para o Rio de Janeiro 300 de São Paulo para o Paraná e 100 de São Paulo para Santa Catarina De acordo com Lachtermacher 2016 nem todos os distribuidores poderiam ter suas demandas completamente atendidas pois a demanda total é maior do que a capacidade de produção da companhia Os distribuidores que não devem 44 Pesquisa Operacional ter sua demanda total suprida de acordo com a solução ótima apresentada pelo Solver são os dos estados de Santa Catarina e do Rio Grande do Sul Santa Catarina deixará de receber 50 carros e o Rio Grande do Sul 250 carros Figura 5 Condições do Solver para o caso LCL Carros Brasil 1a alternativa Fonte Elaborado pelo autor Figura 6 Solução ótima para o caso LCL Carros Brasil 1ª alternativa Fonte Lachtermacher 2016 Para resolver o problema da montadora de veículos LCL Carros Brasil pela outra forma sem inclusão de variáveis dummy modelaremos o problema tratando as restrições como de menor ou igual já que a oferta total é menor do que a demanda total A modelagem do problema portanto será a seguinte Variáveis de decisão x13 número de carros enviados da BA para MG x14 número de carros enviados da BA para o RJ x15 número de carros enviados da BA para GO x23 número de carros enviados de SP para MG x24 número de carros enviados de SP para o RJ x26 número de carros enviados de SP para o PR x27 número de carros enviados de SP para SC x28 número de carros enviados de SP para o RS x34 número de carros enviados de MG para o RJ x35 número de carros enviados de MG para GO x78 número de carros enviados de SC para o RS Funçãoobjetivo Min 25x13 30x14 40x15 20x23 15x24 20x26 35x27 50x28 20x34 20x35 20x78 A montagem das restrições segue a lógica utilizada na modelagem anterior e elas serão do tipo menor ou igual representadas abaixo x13 x14 x15 500 nó 1 x23 x24 x26 x27 x28 600 nó 2 x13 x23 x34 x35 200 nó 3 x14 x24 x34 350 nó 4 x15 x35 150 nó 5 x26 300 nó 6 x27 x78 150 nó 7 x28 x78 250 nó 8 A Figura 7 mostra o problema de transporte da LCL Carros Brasil modelado de acordo com a 2a alternativa A célula I16 representa a funçãoobjetivo e as células E4 a E14 as variáveis de decisão do modelo As células H4 a H11 representam os LHS das restrições de fl uxo e as células I4 a I11 os RHS das células A Tabela 3 mostra as fórmulas utilizadas nas células que representam os LHS das restrições e na célula que denota a funçãoobjetivo A Figura 8 representa os parâmetros e as opções do Solver utilizados no problema Figura 7 Modelagem do caso LCL Carros Brasil 2a alternativa Fonte Lachtermacher 2016 Tabela 3 Fórmulas utilizadas nas restrições do problema de redes de distribuição 2a alternativa Funçãoobjetivo Célula Fórmula referente a função objetivo z I16 SOMARPRODUTOD4D14E14E14 Restrição Célula Resultado da restrição Nó 1 H4 SOMASEC4C14G4E4E14 SOMASEB4B14G4E4E14 Nó2 H5 SOMASEC4C14G5E4E14 SOMASEB4B14G5E4E14 Nó 3 H6 SOMASEC4C14G6E4E14 SOMASEB4B14G6E4E14 Nó 4 H7 SOMASEC4C14G7E4E14 SOMASEB4B14G7E4E14 45 Nó 5 H8 SOMASEC4C14G8E4E14 SOMASEB4B14G8E4E14 Nó 6 H9 SOMASEC4C14G9E4E14 SOMASEB4B14G9E4E14 Nó 7 H10 SOMASEC4C14 G10E4E14SOMASEB4B14 G10E4E14 Nó 8 H11 SOMASEC4C14 G11E4E14SOMASEB4B14 G11E4E14 Fonte Elaborado pelo autor Figura 8 Condições do Solver para o caso LCL Carros Brasil 2a alternativa Fonte Elaborado pelo autor Observando a Figura 9 que mostra o resultado da otimização do problema notamos que a solução ótima apresentada pelo Solver nesse modelo é exatamente igual à solução da modelagem anterior que incluía a variável dummy É indiferente utilizarmos um ou outro método de modelagem o modelador deve escolher o que mais lhe convém No caso de soluções múltiplas os resultados poderiam até ser diferentes isto é um método poderia chegar a uma solução ótima e o método alternativo a outra solução porém ambas apresentando o mesmo valor ótimo Figura 9 Solução ótima para o caso LCL Carros Brasil 2ª alternativa Fonte Lachtermacher 2016 2 Caminho mínimo O problema do caminho mínimo representa um caso especial de problemas de rede em que os arcos signifi cam a distância entre dois pontos nós Quando desejamos achar a rota que une esses pontos com a menor distância entre as possíveis temos um problema do tipo menor caminho Esse tipo de problema pode ser generalizado e aplicado à distribuição de energia elétrica GPS entre outros Em problemas de menor caminho haverá sempre dois tipos de nós especiais chamados de origem e destino Entre um nó de origem e um nó de destino geralmente existem nós intermediários que podem representar cidades que conectam rodovias subestações com problemas de distribuição de energia e assim por diante Para exemplifi car vamos estudar o caso da Dourados Adornos Tecidos A fábrica de artigos de decoração Dourados Adornos Tecidos 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 10 mostra o mapa rodoviário da região do estado em que se situam as duas cidades e a Figura 528 mostra o mapa esquemático e as distâncias entre as cidades na forma de rede Figura 10 Mapa rodoviário que liga as cidades de Lambari a Baependi Fonte Lachtermacher 2016 Figura 11 Representação em rede do caso Dourados Adornos Tecidos Fonte Lachtermacher 2016 46 Pesquisa Operacional 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 um signifi ca que aquele trecho deve ser percorrido De forma inversa se o valor da variável for igual a zero a estrada que liga a cidade i à cidade j não deverá ser utilizada Variáveis de decisão x12 trecho Lambari 1 Três Corações 2 x13 trecho Lambari 1 São Lourenço 3 x15 trecho Lambari 1 Caxambu 5 x24 trecho Três Corações 2 São Thomé das Letras 4 x35 trecho São Lourenço 3 Caxambu 5 x46 trecho São Thomé das Letras 4 Baependi 6 x56 trecho Caxambu 5 Baependi 6 De acordo com Lachtermacher 2016 a funçãoobjetivo 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 isto é a funçãoobjetivo que matematicamente pode ser representada por Min Z 41x12 44x13 50x15 37x24 27x35 45x46 4x56 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 Dessa forma as restrições de fl uxo podem ser matematicamente representadas por x12 x13 x15 1 nó 1 x12 x24 0 nó 2 x13 x35 0 nó 3 x24 x46 0 nó 4 x15 x35 x56 0 nó 5 x46 x56 1 nó 6 Uma das possíveis modelagens desse problema na planilha Excel é mostrada na Figura 12 A célula E12 representa a funçãoobjetivo e as células E4 a E10 as variáveis de decisão do modelo As células H4 a H9 representam os LHS das restrições de fl uxo e as células I4 a I9 os RHS das células A Tabela 4 mostra as fórmulas utilizadas nos LHS das restrições e na célula que denota a funçãoobjetivo Figura 12 Modelagem do caso da Dourados Adornos Tecidos Fonte Elaborado pelo autor Tabela 4 Fórmulas utilizadas no caso da Dourados Adornos Tecidos Funçãoobjetivo Célula Fórmula referente à função objetivo z E12 SOMARPRODUTOD4D10E4E10 Restrição Célula Resultado da restrição Nó 1 H4 SOMASEC4C10G4E4E10 SOMASEB4B10G4E4E10 Nó2 H5 SOMASEC4C10G5E4E10 SOMASEB4B10G5E4E10 Nó 3 H6 SOMASEC4C10G6E4E10 SOMASEB4B10G6E4E10 Nó 4 H7 SOMASEC4C10G7E4E10 SOMASEB4B10G7E4E10 Nó 5 H8 SOMASEC4C10G8E4E10 SOMASEB4B10G8E4E10 Nó 6 H9 SOMASEC4C10G9E4E10 SOMASEB4B10G9E4E10 Fonte Elaborado pelo autor Figura 13 Modelagem no solver Fonte Elaborado pelo autor Figura 14 Solução do exemplo Fonte Elaborado pelo autor As condições especifi cadas para os parâmetros e as opções do Solver estão evidenciadas na Figura 13 A Figura 14 47 mostra a solução ótima do problema Segundo ela o caminho pela malha rodoviária da região que resulta na menor distância entre as cidades de Lambari e Baependi é o que passa pelo município de Caxambu Dessa forma o caminhão de entregas da LCL Adornos Tecidos deve sair de Lambari seguir a estrada que leva até Caxambu x15 1 e de lá partir para Baependi x56 1 percorrendo uma distância total de 54 quilômetros 50 km de Lambari a Caxambu e mais 4 km de Caxambu a Baependi 3 Problema do fl uxo máximo O tipo de problema de fl uxo máximo é utilizado quando queremos maximizar a quantidade de fl uxo de um ponto de origem para um ponto de destino e estamos sujeitos a restrições de capacidade de fl uxo nos arcos Esses problemas geralmente envolvem o fl uxo de materiais como água óleo gás energia por uma rede de tubos ou cabos mas também podem representar o fl uxo máximo de carros em uma malha rodoviária de produtos em linhas de produção e assim por diante Para exemplifi car tomemos o exemplo da empresa distribuidora de gás GasoBras Ltda deseja determinar a quantidade máxima de metros cúbicos por segundo de gás que pode bombear da estação de Campos para o centro consumidor do Rio de Janeiro pela rede de gasodutos existentes A Figura 15 ilustra a estrutura da rede de distribuição e apresenta a capacidade de fl uxo máximo nos trechos em metros cúbicos por segundo Figura 15 Redes de gasodutos que ligam Campos ao Rio de Janeiro Fonte Lachtermacher 2016 Figura 16 Rede com inclusão do arco artifi cial Fonte Lachtermacher 2016 De acordo com Lachtermacher 2016 para resolver esse problema utilizaremos um pequeno artifício adicionaremos um arco virtual ligando o nó B ao nó A Figura 16 A função objetivo portanto será a maximização do fl uxo de gás que passa de B para A Como o fl uxo de B para A na realidade não existe o valor do fl uxo no arco artifi cial representará o total de gás que pode chegar ao Rio de Janeiro vindo de Campos por mais de um caminho simultaneamente Variáveis de decisão xA1 m3s de gás que saem de A e chegam à Estação 1 xA2 m3s de gás que saem de A e chegam à Estação 2 x13 m3s de gás que saem da Estação 1 e chegam à Estação 3 x14 m3s de gás que saem da Estação 1 e chegam à Estação 4 x24 m3s de gás que saem da Estação 2 e chegam à Estação 4 x3B m3s de gás que saem da Estação 3 e chegam em B x4B m3s de gás que saem da Estação 4 e chegam em B xBA m3s de gás que saem de B e chegam em A arco artifi cial Funçãoobjetivo Max xBA A composição das restrições seguirá as seguintes condições O fl uxo em cada arco deverá ser maior ou igual a zero O fl uxo em cada arco deverá ser menor ou igual à capacidade do arco O fl uxo que chega a cada nó deverá ser igual ao fl uxo que sai dele O fl uxo do arco artifi cial desconhecido deve ser grande o bastante para assumir qualquer valor possível já que este será maximizado Restrições de capacidade xA1 40 xA2 30 x13 30 x14 20 x24 30 x3B 20 x4B 40 xBA 9999 Restrições de fl uxo xBA xA1 xA2 0 nó A xA1 x13 x14 0 nó 1 xA2 x24 0 nó 2 x13 x3B 0 nó 3 x14 x24 x4B 0 nó 4 x3B x4B xBA 0 nó B Uma das possíveis modelagens desse problema na planilha Excel é mostrada na Figura 17 A célula E13 representa a funçãoobjetivo e as células E4 a E11 as variáveis de decisão do modelo As células H4 a H9 representam os LHS das restrições de fl uxo e as células I4 a I9 os RHS das células A Tabela 5 mostra as fórmulas utilizadas nos LHS das restrições e na célula que denota a funçãoobjetivo As condições especifi cadas para os parâmetros e as opções do Solver estão evidenciadas na Figura 18 48 Pesquisa Operacional Figura 17 Modelagem no caso da GasoBras Fonte Lachtermacher 2016 Figura 18 Estratégia com o Solver no caso da GasoBras Fonte Elaborado pelo autor Tabela 5 Fórmulas utilizadas no caso da GasoBrass Funçãoobjetivo Célula Fórmula referente à função objetivo Max xBA E13 E11 Restrição Célula Resultado da restrição Nó 1 H4 SOMASEC4C11G4E4E11SO MASEB4B11G4E4E11 Nó2 H5 SOMASEC4C11G5E4E11SO MASEB4B11G5E4E11 Nó 3 H6 SOMASEC4C11G6E4E11SO MASEB4B11G6E4E11 Nó 4 H7 SOMASEC4C11G7E4E11SO MASEB4B11G7E4E11 Nó 5 H8 SOMASEC4C11G8E4E11SO MASEB4B11G8E4E11 Nó 6 H9 SOMASEC4C11G9E4E11SO MASEB4B11G9E4E11 Fonte Elaborado pelo autor Figura 19 Solução do problema da GasoBras Fonte Lachtermacher 2016 A Figura 19 evidencia a solução ótima apresentada pelo Solver para o problema da GasoBras Como podemos observar em função dos limites de fl uxos dos gasodutos o fl uxo máximo que pode chegar ao Rio de Janeiro é de 60 metros cúbicos de gás por segundo Ao chegar ao fi nal da quinta aula vamos recordar o que aprendemos Retomando a aula 1 O problema de redes Nessa seção fomos apresentados ao problema de redes que pode ser considerado um problema de transporte mais complexo com inúmeros fornecedores transbordos e destinos fi nais sendo por essas características que é necessário ser estudado separadamente 2 Caminho mínimo Nessa segunda parte de nosso estudo vimos uma aplicação clássica de problema de redes que é o problema do caminho mínimo Vimos exemplo de como resolver esse problema através do Excel bem em linha com a realidade do dia a dia de um engenheiro 3 Problema do fl uxo máximo Finalmente na última etapa vimos o problema do fl uxo máximo que pode ser entendido como o inverso do problema do caminho mínimo da segunda seção Nessa seção também foi apresentado uma maneira de resolução através do Microsoft Excel Hillier FS e Lieberman GJ Introdução à Pesquisa Operacional 8ª edição São Paulo McGrawHill 2006 Lachtermacher G Pesquisa operacional na tomada de decisões 5ª edição São Paulo Prentice Hall 2016 Taha H A Pesquisa Operacional 8ª edição São Paulo Pearson 2008 Vale a pena ler Vale a pena