Exemplo de Rede de Transporte e Cálculo de Custos

1 Pesquisa Operacional Modelos de Transportes José Agostinho Baitello EXEMPLO DE UMA REDE DE TRANSPORTE Fábrica 1 Depósito 1 Fábrica 2 Fábrica 3 Depósito 2 Depósito 3 Depósito 4 Custos unitários de transportes C11 C12 C13 C14 C21 C22 C23 C24 C32 C31 C33 C34 X11 Quantidade transportada X21 X31 X12 X22 X32 X13 X23 X33 X14 X24 X34 a1 A empresa deseja saber como distribuir a produção pela rede de modo a 1 Respeitar as capacidades produtivas de cada fábrica 2 Respeitar as demandas de cada depósito 3 Minimizar o custo total de transporte bj Demanda de produtos no depósito j ai Capacidade de produção da fábrica i a2 a3 b1 b2 b3 b4 1 2 2 Problema de transportes Exemplo 1 Uma empresa distribuidora necessita transportar eletrodomésticos produzidos em 3 fábricas distintas para 4 centros de distribuição que atendem o varejo em um estado do país A configuração da malha rodoviária que liga as fábricas aos centros de distribuição implica em custos diferenciados de transporte apresentados no quadro abaixo CENTRO CENTRO CENTRO CENTRO DISTRIB 1 DISTRIB 2 DISTRIB 3 DISTRIB 4 FÁBRICA 1 8 6 10 9 FÁBRICA 2 9 12 13 7 FÁBRICA 3 14 9 16 5 Por outro lado tanto as fábricas como os centros de distribuição apresentam respectivamente capacidades de fabricação e demandas de comercialização diversas entre si conforme apresentado a seguir CAPACIDADES DAS FÁBRICAS DEMANDAS NOS CENTROS DE DISTRIBUIÇÃO FÁBRICA 1 35 CENTRO DE DISTRIB 1 45 FÁBRICA 2 50 CENTRO DE DISTRIB 2 20 FÁBRICA 3 40 CENTRO DE DISTRIB 3 30 CENTRO DE DISTRIB 4 30 Encontre o custo mínimo de transportes para o atendimento das necessidades nos centros de distribuição dos produtos F1 F3 F2 CD4 CD3 CD2 CD1 30 20 45 40 50 35 30 8 10 9 9 12 13 7 14 9 16 5 6 FÁBRICAS ORÍGENS DISTRIBUIDORES DESTINOS Problema de transportes Exemplo 1 Representação gráfica X11 X21 X31 X12 X22 X32 X13 X23 X33 X14 X24 X34 Custos unitários de transportes Variáveis de decisão Quantidade transportada de i para j Produção ou OFERTA Consumo ou DEMANDA 3 4 3 Variáveis de decisão Xij quantidade de produto transportado da fábrica i para o depósito j Função Objetivo MIN 8X11 6X12 10X13 9X14 9X21 12X22 13X23 7X24 14X31 9X32 16X33 5X34 Restrições SUJEITO A RESTRIÇÕES DE CAPACIDADES X11 X12 X13 X14 35 X21 X22 X23 X24 50 X31 X32 X33 X34 40 RESTRIÇOES DE DEMANDAS X11 X21 X31 45 X12 X22 X32 20 X13 X23 X33 30 X14 X24 X34 30 Não negatividade Xij 0 Matriz de coeficientes formada por 0 zero e 1 um Problema de transportes Exemplo 1 Representação matemática Variáveis de decisão Xij quantidade de produto transportado da fábrica i para o depósito j Função Objetivo MIN 8X11 6X12 10X13 9X14 9X21 12X22 13X23 7X24 14X31 9X32 16X33 5X34 Restrições SUJEITO A RESTRIÇÕES DE CAPACIDADES Fabr1 X11 X12 X13 X14 35 Fabr2 X21 X22 X23 X24 50 Fabr3 X31 X32 X33 X34 40 RESTRIÇOES DE DEMANDAS CD1 X11 X21 X31 45 CD2 X12 X22 X32 20 CD3 X13 X23 X33 30 CD4 X14 X24 X34 30 Não negatividade Xij 0 No caso da oferta ser igual à demanda uma vez definidos os atendimentos dos CDs de 1 a 3 a equação do CD4 é redundante pois as quantidades de produtos remanescentes só podem ser deste CD Portanto o numero de equações linearmente independente ou tamanho da base deve ser NÚMERO DE OFERTAS FÁBRICAS NUMERO DE DEMANDAS CDS 1 3 4 1 6 Isto é Em uma solução básica teremos 6 valores de variáveis diferente de zero e as demais todas nulas Problema de transportes Exemplo 1 Representação matemática 5 6 4 Problema de Transportes Exemplo 1 Solução empírica CD1 CD2 CD3 CD4 Oferta Fabr1 X11 X12 X13 X14 35 Fabr2 50 Fabr3 40 Dema nda 45 20 30 30 Sugerir um plano de distribuição para as três fábricas atenderem aos quatro Centros de Distribuição que respeite as capacidades das fábricas e atenda às demandas dos CDs Ver Planilha Auxiliar 7 8 5 MIN 8X11 6X12 10X13 9X14 9X21 12X22 13X23 7X24 14X31 9X32 16X33 5X34 ST Fabr1 X11 X12 X13 X14 35 Fabr2 X21 X22 X23 X24 50 Fabr3 X31 X32 X33 X34 40 CD1 X11 X21 X31 45 CD2 X12 X22 X32 20 CD3 X13 X23 X33 30 CD4 X14 X24 X34 30 END F1 F3 F2 CD4 CD3 CD2 CD1 30 20 45 40 50 35 30 FÁBRICAS ORIGENS DISTRIBUIDORES DESTINOS Problema de transportes Exemplo 1 Modelo para submeter ao sw LINDO Fabr1 Fabr2 Fabr3 CD1 CD2 CD3 CD4 8 10 9 9 12 13 7 14 9 16 5 6 X11 X21 X31 X12 X22 X32 X13 X23 X33 X14 X24 X34 Variáveis de decisão Xij quantidade de produto transportado da fábrica i para o depósito j Função Objetivo MIN 8X11 6X12 10X13 9X14 9X21 12X22 13X23 7X24 14X31 9X32 16X33 5X34 Restrições SUJEITO A RESTRIÇÕES DE CAPACIDADES Fabr1 X11 X12 X13 X14 35 Fabr2 X21 X22 X23 X24 50 Fabr3 X31 X32 X33 X34 40 RESTRIÇOES DE DEMANDAS CD1 X11 X21 X31 45 CD2 X12 X22 X32 20 CD3 X13 X23 X33 30 CD4 X14 X24 X34 30 Não negatividade Xij 0 Problema de transportes Exemplo 1 Representação matemática Oferta total de Produtos 125 unidades Demanda total de Produtos 125 unidades 9 10 7 Demanda Maior que oferta Oferta menor que a Demanda 125 165 Diferença 165 124 40 CD3 folga 40 das 40 que necessitava isto é ficou sem receber qualquer produto Qde de produtos recebidas pelo CD3 13 14 8 Conceito da Álgebra Linear NÚMERO DE OFERTAS FÁBRICAS NUMERO DE DEMANDAS CDS 1 3 4 1 6 Em uma solução básica teremos 6 valores de variáveis diferente de zero e as demais todas nulas Para encontrar a solução ótima de mínimo custo precisamos inicialmente obter uma solução inicial BÁSICA viável e a partir dela buscarmos a solução ótima Solução Básica viável Problema de Transportes Exemplo 1 Solução empírica CD1 CD2 CD3 CD4 Oferta Fabr1 X11 X12 X13 X14 35 Fabr2 50 Fabr3 40 Dema nda 45 20 30 30 Sugerir um plano de distribuição para as três fábricas atenderem aos quatro Centros de Distribuição que respeite as capacidades das fábricas e atenda às demandas dos CDs 15 16 9 Problema de Transportes Forma Tabular NOTAÇÃO CD1 CD2 CD3 CD4 Oferta Fabr1 x11 C11 8 x12 C12 6 x13 C13 10 x14 C14 9 35 Fabr2 x21 C21 9 x22 C22 12 x23 C23 13 x24 C24 7 50 Fabr3 x31 C31 14 x32 C32 9 x33 C33 16 x34 C34 5 40 Dem 45 20 30 30 Custo Total de Transportes CTT 8X11 6X12 10X13 9X14 9X21 12X22 13X23 7X24 14X31 9X32 16X33 5X34 Variáveis na BASE Valor maior ou igual a ZERO xijo Variáveis fora da BASE Valor igual a ZERO xijo Ficam em branco na tabela Problema de Transportes Exemplo 1 Solução empírica básica CD1 CD2 CD3 CD4 Oferta Fabr1 35 Fabr2 50 Fabr3 40 Dema nda 45 20 30 30 Sugerir um plano de distribuição para as três fábricas atenderem aos quatro Centros de Distribuição que respeite as capacidades das fábricas e atenda às demandas dos CDs Solução básica 34 1 6 elementos não nulos 17 18 10 Problema de Transportes Exemplo 1 Solução analítica manual 1 Construir a tabela Inicial de Origens e Destinos 2 Calcular uma solução básica inicial viável Tamanho da Base Numero de Origens Numero de destinos 1 1 Método do canto noroeste 2 Método do Mínimo Custo Unitário de Transporte 3 Método Vogel 3 Calcular a Solução OTIMA Mínimo Custo TOTAL de Transporte 1 Método u x v Problema do Transporte etapas para solução Métodos para obter uma solução básica inicial viável Solução Inicial Pelo Método do CANTO NOROESTE 19 20 11 Problema de Transportes Exemplo 1 Solução Inicial Pelo Método do CANTO NOROESTE CD1 CD2 CD3 CD4 Oferta Fabr1 8 6 10 9 35 Fabr2 9 12 13 7 50 Fabr3 14 9 16 5 40 Dem 45 20 30 30 Este método leva a uma solução BÁSICA mas não leva em conta o custo de transportes CANTO NOROESTE Problema de Transportes Exemplo 1 Solução Inicial Pelo Método do CANTO NOROESTE CD1 CD2 CD3 CD4 Oferta Fabr1 8 6 10 9 35 Fabr2 9 12 13 7 50 Fabr3 14 9 16 5 40 Dem 45 20 30 30 Custo pfabr Custo Total 21 22 12 Problema de Transportes Exemplo 1 Solução Inicial Pelo Método do CANTO NOROESTE CD1 CD2 CD3 CD4 Oferta Fabr1 8 6 10 9 35 Fabr2 9 12 13 7 50 Fabr3 14 9 16 5 40 Dem 45 20 30 30 30 1 2 10 20 20 10 35 3 2 10 20 Problema de Transportes Exemplo 1 Solução Inicial Pelo Método do CANTO NOROESTE CD1 CD2 CD3 CD4 Oferta Fabr1 35 8 6 10 9 35 Fabr2 10 9 20 12 20 13 7 50 Fabr3 14 9 10 16 30 5 40 Dem 45 20 30 30 Custo total de transportes com esta solução R 118000 Ctt 358 109 2012 2013 1016 305 1180 23 24 13 Métodos para obter uma solução básica inicial viável Solução Inicial Pelo MÍNIMO CUSTO UNITÁRIO de Transporte Problema de Transportes Exemplo 1 Solução Inicial Pelo MÍNIMO CUSTO UNITÁRIO CD1 CD2 CD3 CD4 Oferta Fabr1 8 6 10 9 35 Fabr2 9 12 13 7 50 Fabr3 14 9 16 5 40 Dem 45 20 30 30 Custo fabr Custo Total 25 26 14 Problema de Transportes Exemplo 1 Solução Inicial Pelo MÍNIMO CUSTO UNITÁRIO CD1 CD2 CD3 CD4 Oferta Fabr1 8 6 10 9 35 Fabr2 9 12 13 7 50 Fabr3 14 9 16 5 40 Dem 45 20 20 30 30 4 1 20 15 30 20 10 2 3 20 10 15 30 Problema de Transportes Exemplo 1 Solução Inicial Pelo MÍNIMO CUSTO UNITÁRIO Custo fabr 240 530 310 Custo Total 1080 CD1 CD2 CD3 CD4 Oferta Fabr1 15 8 20 6 10 9 35 Fabr2 30 9 12 20 13 7 50 Fabr3 14 9 10 16 30 5 40 Dem 45 20 30 30 Custo total de transportes com esta solução R 108000 Ctt 158 206 309 2013 1016 305 1080 Portanto partimos para a busca de solução ótima partindo de uma posição mais próxima da mesma 27 28 15 Métodos para obter uma solução básica inicial viável Solução Inicial Pelo MÉTODO VOGEL ou das PENALIDADES Problema de Transportes Exemplo 1 Solução Inicial Pelo Método VOGEL ou das Penalidades CD1 CD2 CD3 CD4 Oferta Fabr1 8 6 10 9 35 Fabr2 9 12 13 7 50 Fabr3 14 9 16 5 40 Dem 45 20 30 30 Penalidades 1 PENALIDADE diferença entre o menor custo e o imediatamente superior se os dois menores custos forem iguais considerar a penalidade zero 2 CRITÉRIO escolher a maior penalidade das linhas e colunas e preencher a célula com e menor custo da mesma 29 30 16 Problema de Transportes Exemplo 1 Solução Inicial Pelo Método VOGEL ou das Penalidades CD1 CD2 CD3 CD4 Oferta Fabr1 8 6 10 9 35 Fabr2 9 12 13 7 50 Fabr3 14 9 16 5 40 Dem 45 20 30 30 Penalidades 30 3 1 2 2 4 1 3 3 2 1 25 45 10 10 5 2 2 3 5 1 2 3 1 4 10 25 3 2 1 2 3 4 6 5 Exemplo 1 Problema de Transportes Solução Inicial Pelo Método VOGEL ou das Penalidades CD1 CD2 CD3 CD4 Oferta Fabr1 8 10 6 25 10 9 35 Fabr2 45 9 12 5 13 7 50 Fabr3 14 10 9 16 30 5 40 Dem 45 20 30 30 3 3 3 3 3 3 6 1 1 1 1 2 4 5 2 3 3 4 2 2 2 2 Penalidades 31 32 17 Problema de Transportes Exemplo 1 Solução Inicial Pelo Método VOGEL ou das Penalidades CD1 CD2 CD3 CD4 Oferta Fabr1 8 10 6 25 10 9 35 Fabr2 45 9 12 5 13 7 50 Fabr3 14 10 9 16 30 5 40 Dem 45 20 30 30 Custo total de transportes com esta solução R 102000 Ctt 106 2510 459 513 109 305 1020 Este método fornece uma solução inicial muito próxima do ótimo e em problemas pequenos é comum ele já fornecer a solução ótima Como neste caso Métodos para obter uma solução ÓTIMA MÉTODO U x V Verificação de otimalidade e busca interativa da solução ótima 33 34 18 Verificação de Otimalidade Como comprovamos que estamos na solução ótima Como melhorar a solução inicial até chegar à ótima Métodou X v Células da Base Linha i Coluna j ui vj Células Fora da Base Linha i Coluna j vj cij cij cij Xij Para as células básicas cálculo dos ui e dos vj Inicialmente atribuir u1 0 e para o primeiro elemento da base da linha 1 calcular o valor do vj correspondente segundo a fórmula abaixo Com os valores encontrados calcular todos os ui e vj remanescentes utilizando apenas os componentes da base cij ui vj Para as células fora da base calcular todos os cij cij cij ui vj ui Problema de Transportes Exemplo 1 Busca da Solução Ótima Pelo Método u X v Partindo de uma solução inicial pelo Método do Mínimo Custo Unitário CD1 CD2 CD3 CD4 Oferta Fabr1 8 6 10 9 35 Fabr2 9 12 13 7 50 Fabr3 14 9 16 5 40 Dem 45 20 30 30 Início u1 0 u2 u3 v1 v2 v3 v4 Cálculo dos u e v 35 36 19 Problema de Transportes Exemplo 1 Busca da Solução Ótima Pelo Método u X v Partindo de uma solução inicial pelo Método do Mínimo Custo Unitário CD1 CD2 CD3 CD4 Oferta Fabr1 15 8 20 6 10 9 35 Fabr2 30 9 12 20 13 7 50 Fabr3 14 9 10 16 30 5 40 Dem 45 20 30 30 Células básicas cij ui vj c11 u1 v1 8 0 v1 Início u1 0 u2 u3 v1 v2 v3 v4 Cálculo dos u e v v1 8 v2 6 v3 12 v4 1 u2 1 u3 4 Para as células não básicas cij cij ui vj c32 c32 u3 v2 c32 9 4 6 1 1 5 5 2 8 2 2 Problema de Transportes Exemplo 1 Busca da Solução Ótima Pelo Método u X v Partindo de uma solução inicial pelo Método do Mínimo Custo Unitário CD1 CD2 CD3 CD4 Oferta Fabr1 15 8 20 6 10 9 35 2 8 Fabr2 30 9 12 20 13 7 50 5 5 Fabr3 14 9 10 16 30 5 40 2 1 Dem 45 20 30 30 Início u1 0 u2 1 u3 4 v1 8 v2 6 v3 12 v4 1 Cálculo dos u e v Remanejar as remessas efetuadas pela Fabr1 do CD1 para o CD3 reduzirá o custo total de transporte em 2 por unidade remanejada 37 38 20 Problema de Transportes Exemplo 1 Busca da Solução Ótima Pelo Método u X v CD1 CD2 CD3 CD4 Oferta Fabr1 15 8 20 6 10 9 35 2 8 Fabr2 30 9 12 20 13 7 50 5 5 Fabr3 14 9 10 16 30 5 40 2 1 Dem 45 20 30 30 Início u1 0 u2 1 u3 4 v1 8 v2 6 v3 12 v4 1 Cálculo dos u e v θ θ θ θ θ15 θ15 θ θθ θθ θ θθ θθ θ θ Problema de Transportes Exemplo 1 Busca da Solução Ótima Pelo Método u X v CD1 CD2 CD3 CD4 Oferta Fabr1 15 8 20 6 θ15 10 9 35θθ 2 8 Fabr2 30 9 12 20 13 7 50θθ 5 5 Fabr3 14 9 10 16 30 5 40 2 1 Dem 45θθ 20 30θθ 30 u1 0 u2 1 u3 4 v1 8 v2 6 v3 12 v4 1 θ θ θ θ Custo total de transporte 15x8 20x6 30x9 20x13 10x16 30x5 1080 É Possível remanejar no máximo 15 unidades pois ao subtrairmos θ não pode restar uma quantidade negativa na célula A redução de custo devido ao remanejamento será portanto de 15x2 30 será reduzido para 1050 Remanejar as remessas efetuadas pela Fabr1 do CD1 para o CD3 reduzirá o custo total de transporte em 2 por unidade remanejada 39 40 21 Problema de Transportes Exemplo 1 Busca da Solução Ótima Pelo Método u X v CD1 CD2 CD3 CD4 Oferta Fabr1 8 20 6 15 10 9 35 Fabr2 45 9 12 5 13 7 50 Fabr3 14 9 10 16 30 5 40 Dem 45 20 30 30 u1 0 u2 u3 v1 v2 v3 v4 Custo total de transporte 20x6 15x10 45x9 5x13 10x16 30x5 1050 Problema de Transportes Exemplo 1 Busca da Solução Ótima Pelo Método u X v CD1 CD2 CD3 CD4 Oferta Fabr1 8 20 6 15 10 9 35 Fabr2 45 9 12 5 13 7 50 Fabr3 14 9 10 16 30 5 40 Dem 45 20 30 30 u1 0 u2 u3 v1 v2 v3 v4 É Possível remanejar no máximo 10 unidades pois ao subtrairmos θ não pode restar uma quantidade negativa na célula A redução de custo devido ao remanejamento será portanto de 10x3 30 sera reduzido para 1020 6 3 1 10 6 6 Custo total de transporte 20x6 15x10 45x9 5x13 10x16 30x5 1050 2 10 3 5 2 3 3 41 42 22 Problema de Transportes Exemplo 1 Busca da Solução Ótima Pelo Método u X v CD1 CD2 CD3 CD4 Oferta Fabr1 8 20 6 15 10 9 35θθ 2 10 Fabr2 45 9 12 5 13 7 50 3 5 Fabr3 14 9 10 16 30 5 40θθ 2 3 Dem 45 20θθ 30θθ 30 u1 0 u2 3 u3 6 v1 6 v2 6 v3 10 v4 1 θ θ θ θ É Possível remanejar no máximo 10 unidades pois ao subtrairmos θ não pode restar uma quantidade negativa na célula A redução de custo devido ao remanejamento será portanto de 10x3 30 será reduzido para 1020 θ10 Custo total de transporte 20x6 15x10 45x9 5x13 10x16 30x5 1050 Problema de Transportes Exemplo 1 Busca da Solução Ótima Pelo Método u X v CD1 CD2 CD3 CD4 Oferta Fabr1 8 10 6 25 10 9 35 Fabr2 45 9 12 5 13 7 50 Fabr3 14 10 9 16 30 5 40 Dem 45 20 30 30 u1 0 u2 u3 v1 v2 v3 v4 Todos os cij são positivos significando que encontramos a solução ótima Custo total de transporte 10x6 25x10 45x9 5x13 10x9 30x5 1020 Resposta X110 X1210 X1325 X140 X2145 X220 X235 X240 X310 X3210 X330 X3430 6 10 3 3 2 6 2 7 3 2 5 3 43 44 23 Problema de Transportes Exemplo 1 Busca da Solução Ótima Pelo Método u X v Partindo de uma solução inicial pelo Método Vogel ou das Penalidades CD1 CD2 CD3 CD4 Oferta Fabr1 8 10 6 25 10 9 35 Fabr2 45 9 12 5 13 7 50 Fabr3 14 10 9 16 30 5 40 Dem 45 20 30 30 Células básicas cij ui vj c12 u1 v2 6 0 v2 Início u1 0 u2 u3 v1 v2 v3 v4 Para as células não básicas cij cij ui vj Cálculo dos u e v Problema de Transportes Exemplo 1 Busca da Solução Ótima Pelo Método u X v Partindo de uma solução inicial pelo Método Vogel ou das Penalidades CD1 CD2 CD3 CD4 Oferta Fabr1 8 10 6 25 10 9 35 2 7 Fabr2 45 9 12 5 13 7 50 3 2 Fabr3 14 10 9 16 30 5 40 5 3 Dem 45 20 30 30 u1 0 u2 3 u3 3 v1 6 v2 6 v3 10 v4 2 Todos os cij são positivos significando que encontramos a solução ótima Custo total de transporte 10x6 25x10 45x9 5x13 10x9 30x5 1020 Resposta X110 X1210 X1325 X140 X2145 X220 X235 X240 X310 X3210 X330 X3430 45 46 24 Significado do cij cij Problema de Transportes Exemplo 1 Solução analítica manual 1 Construir a tabela Inicial de Origens e Destinos 2 Calcular uma solução básica inicial viável Tamanho da Base Numero de Origens Numero de destinos 1 1 Método do canto noroeste 2 Método do Mínimo Custo Unitário de Transporte 3 Método Vogel 3 Calcular a Solução OTIMA Mínimo Custo TOTAL de Transporte 1 Método u x v Algorítmo do Transporte etapas 47 48