Capítulo 5: Problemas de Rede em Pesquisa Operacional

Capítulo 5 Problemas de Rede Pesquisa Operacional na Tomada de Decisões Gerson Lachtermacher 2005 Adaptação Ademir Martins Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Conteúdos do Capítulo 5 Problemas de Transporte Problemas de Rede de Distribuição Problemas do Menor Caminho Problemas de Fluxo Máximo Problemas de Designação Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema de Transporte Caso LCL Bicicletas Dados do Problema A LCL Bicicletas possui 3 fábricas localizadas no Rio São Paulo e Belo Horizonte A produção deve ser entregue em Recife Salvador e Manaus Considerando os custos de transporte unitários as capacidades de produção das fábricas e as demandas dos centros consumidores que estão especificados na tabela a seguir determine quanto deve ser produzido e entregue por cada fábrica em cada centro consumidor de forma a minimizar os custos de transporte Fábrica Centro Consumidor Capacidade Recife Salvador Manaus Rio 25 20 30 2000 São Paulo 30 25 25 1500 BHorizonte 20 15 23 1500 Demanda 2000 2000 1000 Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema de Transporte Caso LCL Bicicletas Variáveis de Decisão 3 Fábricas x 3 Centros consumidores 9 Variáveis RIO SP BHZ REC SSA MAN x11 x12 x13 x21 x22 x23 x31 x32 x33 Fábr Centro Consumidor REC SSA MAN Rio x11 x12 x13 SP x21 x22 x23 BH x31 x32 x33 Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema de Transporte Caso LCL Bicicletas Preparação de Tabelas 1 Tabela de Custos Tabela de Variáveis Fábrica Centro Consumidor REC SSA MAN Cap RIO 25 20 30 2000 SP 30 25 25 1500 BHZ 20 15 23 1500 Demanda 2000 2000 1000 Fábr Centro Consumidor REC SSA MAN Rio x11 x12 x13 SP x21 x22 x23 BH x31 x32 x33 Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema de Transporte Caso LCL Bicicletas Preparação de Tabelas 2 Fábrica Centro Consumidor REC SSA MAN RIO 25 20 30 SP 30 25 25 BHZ 20 15 23 Fábrica Centro Consumidor Cap REC SSA MAN Rio x11 x12 x13 2000 SP x21 x22 x23 1500 BHZ x31 x32 x33 1500 Demanda 2000 2000 1000 Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema de Transporte Caso LCL Bicicletas Função Objetivo Função Objetivo Fábrica Centro Consumidor REC SSA MAN RIO 25 20 30 SP 30 25 25 BHZ 20 15 23 Fábrica Centro Consumidor Cap REC SSA MAN Rio x11 x12 x13 2000 SP x21 x22 x23 1500 BHZ x31 x32 x33 1500 Demanda 2000 2000 1000 Min Z 25x11 20x12 30x13 15x32 23x33 Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema de Transporte Caso LCL Bicicletas Modelagem do Problema 0 1000 2000 2000 1500 1500 2000 st 23 15 20 25 25 30 30 20 25 33 23 13 32 22 12 31 21 11 33 32 31 23 22 21 13 12 11 33 32 31 23 22 21 13 12 11 ijx x x x x x x x x x x x x x x x x x x x x x x x x x x x Min Por Linha Por Coluna Func Obj Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problemas de Transporte Propriedades Soluções Inteiras Para problemas de transporte onde os valores das ofertas e demandas sejam números inteiros todos os valores das variáveis das soluções básicas viáveis incluindo a solução ótima também serão inteiros A condição necessária e suficiente para um problema de transporte com n fábricas e m centros consumidores tenha solução é dada por Total da Capacidade Total da demanda Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema de Transporte Oferta Diferente da Demanda Uso de variáveis fantasma Dummy Se Oferta Demanda introduzir uma demanda fantasma Se Demanda Oferta introduzir uma oferta fantasma Todos os custos relacionados às variáveis fantasma serão nulos O valor da oferta ou demanda fantasma será dada pela diferença entre o total ofertado e total demandado Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema de Transporte Caso LCL Bicicletas Desequilibrando o problema Modificando a oferta de São Paulo de 1500 para 3000 Demanda total 5000 menor que a Oferta total 6500 Centro Consumidor Capacidade Fábrica Recife Salvador Manaus oferta Rio 25 20 30 2000 São Paulo 30 25 25 3000 BHorizonte 20 15 23 1500 Demanda 2000 2000 1000 Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema de Transporte Caso LCL Bicicletas Inserindo um elemento Dummy para equilibrar Criase um consumidor Dummy Valor da demanda do consumidor Dummy 6500 Total da Oferta 5000 Total da Demanda 1500 Centro Consumidor Fábrica Recife Salvador Manaus Dummy Capacidade Rio 25 20 30 0 2000 São Paulo 30 25 25 0 3000 BHorizonte 20 15 23 0 1500 Demanda 2000 2000 1000 1500 Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema de Transporte Caso LCL Bicicletas Préentendimento do uso do Excel Incluir Coluna de somas de Produção e Linha de somas de Entregas Centro Consumidor Fábrica REC SSA MAN Dummy Produção Cap RIO x11 x12 x13 x14 SOMA 2000 SP x21 x22 x23 x24 SOMA 3000 BHZ x31 x32 x33 x34 SOMA 1500 Entrega SOMA SOMA SOMA SOMA Demanda 2000 2000 1000 1500 Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema de Transporte Caso LCL Bicicletas Resolvendo no Excel SOMAB10E10 SOMARPRODUTOB4E6B10E13 Problema de Transporte Caso LCL Bicicletas Parâmetros e Opções do Solver Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema de Transporte Caso LCL Bicicletas Resolvendo no Excel Resultado Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problemas de Transporte Solução Alternativa As Variáveis Dummy não são obrigatórias apenas facilitam a interpretação do resultado da otimização Oferta Demanda Interpretação capacidade ociosa Criação de consumidor dummy Alternativa restrições de oferta com sinal Demanda Oferta Interpretação demanda não atendida Criação de fábrica dummy Alternativa restrições de demanda com sinal Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema de Transporte Caso LCL Bicicletas Modelo sem Fantasma Todas as fórmulas são idênticas Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema de Transporte Caso LCL Bicicletas Modelo sem Fantasma no Excel As restrições de oferta estão com sinal Com a diferença de Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema de Transporte Caso LCL Bicicletas Modelo sem Fantasma Resultado Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Problema de Transporte Caso LCL Bicicletas Comparação de Resultados com e sem Dummy Com DUMMY Sem DUMMY Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Solver no Google Planilhas Digite solver na caixa de busca da página de extensões Selecione Solver da Frontline Systems Inc Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Solver no Google Planilhas Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Solver no Google Planilhas Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Solver no Google Planilhas Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Solver no Google Planilhas Extensões Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Solver no Google Planilhas Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Solver no Google Planilhas Objetivo Variáveis Restrições Método Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Solver no Google Planilhas Necessário Gerson Lachtermacher2005 Adaptação Ademir Martins 2020 Solver no Google Planilhas Capítulo 5 Problemas de Rede Pesquisa Operacional na Tomada de Decisões Gerson Lachtermacher 2005 Adaptação Ademir Martins A ser continuado