Problemas de Menor Caminho em Redes de Distribuição

Capítulo 5 Problemas de Rede Pesquisa Operacional na Tomada de Decisões Gerson Lachtermacher 2005 Adaptação Ademir Martins PROBLEMAS DE MENOR CAMINHO Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problemas de Menor Caminho Se considerarmos uma rede na qual o arco signifique a distância entre dois pontos nós e desejarmos achar a rota que une estes pontos com distância mínima teremos um problema do tipo do Menor caminho Este tipo de problema pode ser generalizado e aplicado a distribuição de produtos entre outros Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problemas de Menor Caminho Considere a rede abaixo que representa a ligação rodoviária entre duas cidades A e B O tamanho dos arcos representa a distância entre pontos da malha rodoviária entre as cidades A B 4 3 2 1 40 30 30 30 20 20 20 Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problemas de Menor Caminho Este problema pode ser visto como um problema de rede de distribuição com um ponto de oferta de um caminhão A 1 um ponto de demanda de um caminhão B 1 os demais pontos da malha sem demanda ou oferta 0 1 1 A B 4 3 2 1 40 30 30 30 20 20 20 Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problemas de Menor Caminho A B 4 3 2 1 40 30 30 30 20 20 20 Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 EXCEL Função SOMASE SOMASE intervalobusca critérios intervalosoma Essa função pesquisa por células que atendam aos critérios Se encontrar usa o índice atual do intervalobusca para pegar os valores correspondentes no intervalosoma e soma esses valores Ex SOMASEB1B6 João C1C6 irá retornar 243 15 82 340 A B C 1 Visa Marcos 45 2 Elo João 243 3 Credicard Henrique 165 4 Elo João 15 5 Elo João 82 6 Visa Laércio 99 Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problemas de Menor Caminho SOMASEC3C9 F3 E3E9 SOMASEB3B9 F3 E3E9 TEntradas TSaidas Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problemas de Menor Caminho SOMASEC3C9 F3 E3E9 SOMASEB3B9 F3 E3E9 TEntradas TSaidas Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problemas de Menor Caminho A B 4 3 2 1 40 30 30 30 20 20 20 Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problemas de Menor Caminho A B 4 3 2 1 40 30 30 30 20 20 20 PROBLEMAS DE FLUXO MÁXIMO Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problemas de Fluxo Máximo Nesse tipo de problema temse uma rede de nós e arcos e desejase que o maior fluxo de uma grandeza possa fluir de um determinado nó para outro Nesse tipo de problema mais de um caminho pode ser utilizado simultaneamente Aplicações Rede de distribuição de Água Luz Gás Tráfego na internet Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problemas de Fluxo Máximo Como resolver o problema Adicionar um arco artificial ligando o ponto de saída A ao ponto de chegada B Maximizar o fluxo no arco artificial criado fluxo grande Utilizar a regra de balanceamento de redes As grandezas associadas aos arcos são o fluxo máximo em cada trecho da rede portanto restrições no modelo O Valor de OfertaDemanda em cada nó é igual a zero Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema do Fluxo Máximo A B 4 3 2 1 40 30 30 30 20 20 20 valor grande Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema do Fluxo Máximo Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema do Fluxo Máximo Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema do Fluxo Máximo Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema do Fluxo Máximo Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema do Fluxo Máximo Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema do Fluxo Máximo 30 30 A B 4 3 2 1 40 30 20 20 40 40 20 20 20 20 20 40 60 PROBLEMAS DE REDE DE DISTRIBUIÇÃO Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Rede de Distribuição A Frod Brasil terá duas fábricas no Brasil uma na Bahia outra em São Paulo A empresa está estudando a forma de distribuição de seus carros para as diversas revendas de Minas Gerais A seguir é apresentada a possível rede de distribuição dos veículos seus custos de transporte unitários demandas por revenda e as capacidades das fábricas Formule o Problema de Programação Linear que resolva as rotas que devem ser seguidas a partir das fábricas para atender as diversas revendas Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Rede de Distribuição SP 1 BA 2 3 4 5 6 7 500 600 200 300 250 350 350 40 20 20 25 25 35 40 10 10 10 10 10 15 Ofertas Demandas Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Rede de Distribuição Variáveis de Decisão Uma para cada arco ligação entre nós x13 x14 x15 x23 x24 x27 x36 x45 x47 x56 x65 x67 x76 Função Objetivo somarproduto variáveis custos 76 65 67 56 47 45 36 27 24 23 15 13 14 10 10 10 15 25 35 25 40 20 10 40 20 10 X X X X X X X X X X X X X Min Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Rede de Distribuição Restrições Temse Oferta 500 600 1100 Demanda 200 300 250 350 350 1450 Como a oferta total é que a demanda total devemos utilizar a seguinte restrição em todos os nós Entradas Saídas Oferta Demanda no nó Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Rede de Distribuição 76 65 67 56 47 45 36 27 24 23 15 13 14 10 10 10 15 25 35 25 40 20 10 40 20 10 X X X X X X X X X X X X X Min Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Rede de Distribuição SOMASEC3C15 F3 E3E15 SOMASEB3B15 F3 E3E15 Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Rede de Distribuição Configuração do Solver Entradas Saídas Oferta Demanda no nó Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Rede de Distribuição Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Rede de Distribuição SP 1 BA 2 3 4 5 6 7 500 600 200 300 250 350 350 200 350 50 500 550 De Para Cust Unid 1 3 20 1 4 10 500 1 5 40 2 3 10 550 2 4 20 2 7 40 50 3 6 25 350 4 5 35 4 7 25 200 5 6 15 6 5 10 6 7 10 7 6 10 Capítulo 5 Problemas de Rede Pesquisa Operacional na Tomada de Decisões Gerson Lachtermacher 2005 Adaptação Ademir Martins A ser continuado