Problemasdetransporte
PESQUISA OPERACIONAL – Profa. Vânia Gayer PROBLEMAS DE TRANSPORTE INTRODUÇAO: O Problema de transporte é de forma geral o problema de determinar o carregamento de uma rede de transporte que liga várias fontes a vários destinos, de forma que o custo total do transporte seja mínimo. É encontrado em empresas que têm unidades produtoras em algumas cidades e depósitos em outras. Uma variação desta situação é o caso em que o produto não vai direto da fonte para outros destinos ante e c 1 oriá transportes com tran to view nut*ge HISTÓRICO: outras fontes e nal. ? o modelo de Em 1975, os professores Leonid Kantarovich (URSS) e jalling C. Koopmans (USA) receberam o prêmio Nobel de Ciências Econômicas por suas contribuições para a teoria da alocação ótima de recursos. Estes professores investigaram uma grande variedade de problemas de otimização. É interessante notar que ambos estão associados a vários dos primeiros trabalhos descrevendo problemas de fluxo em redes.
Em 1939, Kantarowch discutiu uma classe de modelos de otimização com exemplos específicos. A ideia de cada exemplo era a busca da mais alta produção possível com uma utilização ótima dos recursos xistentes. Um destes exemplos envolveu a distribuição de transporte de carga entre diferentes rotas de uma rede de modo a satisfazer as necessidades e restrições de capacidade nas rotas enquanto enquanto otimizava o gasto de combustível.
A discussão deu- se na URSS e não foi conhecida pelo ocidente antes de 1950. Enquanto isso, nos EUA, trabalhando independente, Koopmans formulou o mesmo problema. Devido a isso, o problema de transporte é frequentemente chamado de Problema de transporte de Kantarovich-Koopmans. Em 1956, Alex Orben propôs uma generalização do modelo de transporte no qual ontos de transcarregamento eram alocados. A formulação é conhecida hoje como um problema de transporte com transbordo. l.
O PROBLEMA CLÁSSICO DE TRANSPORTES A modelagem de um problema clásslco de transportes com m fontes e n destinos pode ser assim expressa: Min para i-l para 1—1, onde: ci] é o custo de transportar uma unidade da fonte i para o destino xij é a quantidade (un) que deve ser transportada da fonte i para o destino j ai é a capacidade da fonte i bj é a capacidade de absorção do destino j EXEMPLO 1: Suponha um problema de 2 fontes e 3 destinos, onde a capacidade das fontes sejam respectivamente 15 e 25 e a apacidade de absorção pelos destinos sejam 20, 10 e 10, respectivamente.
Os custos de transportar uma unidade da fonte 1 para o destino 1 seja 10, da fonte 1 fonte 1 para o destino 3 s ra o destino 2 seja 3 e da ente, suponha que os Para facilitar o entendimento, podemos fazer um esquema utilizando nós e arcos, de tal forma que teremos 2 nós fontes e 3 nós destinos e 6 arcos que correspondem as rotas que ligam as fontes aos destinos. 5 15 10 IO 20 Note que no problema clássico, existe a suposição que a soma das capacidades das fontes é igual a capacidade de absorção dos destinos: al+a2- bl+b2+b3-40 Para fazermos a modelagem do problema acima precisamos perceber que o objetivo é transportar todas as unidades das fontes para os destinos ao menor custo possível. Desse modo precisamos encontrar o valor das variáveis do problema que minimizam este custo, ou seja, quanto deverá ser transportado da fonte para o destino j.
As variáveis deste problema são: XII, x12, x13, x21, x22 e x23 Sabendo que os custos unitários de transporte da fonte i para o destino j são: Cl 1=10, Cl 2=3, C13=5, C21=12, C22=7, C23=9 A função objetivo é expressa por: Min IOXII + 5X13+ PAGF + 9X23 problema modelado como um problema de programação linear nteira: Min + 3×12+ + 12×21+ 7×22 s. a. XII +x13- 15 x21 x22 + x23 25 XI 1+ X21 = 20 xl 2+ x22 10 X13 + X23 com O e INTEIRAS USANDO O SOLVER DO EXCEL 9X23 1) Entrar com a tabela dos custos unitários de transporte.
Linha/Coluna I Destino 1 Destino 2 | Destino 3 | 2 Fonte 1 1 1013151 3 Fonte 2 1217 91 2) Montar com a tabela de saída com as ofertas das fontes, demandas dos destinos e custo total do transporte. A IBICIDIEIF 51 1 Destino 1 Destino 2 Destino 31 Soma Oferta 61 Fonte 1 | 15 7 Fonte 2 | 8 soma I 9 Demanda120 110 10 3) Abrir a ferramenta Solver e informar os parâmetros: a. Célula de destino: E8 b. Selecionar Igual a: Mínimo c.
Células variáveis: B6: Soma I Oferta Fonte 1 1015 10 11515 Fonte 2 120 15 IO 125 soma IO 10 5 | Demanda | 20 10 1011 Resposta: Para minimizar o custo total do transporte em $ 340,00 deve-se transportar: da fonte 1 : 5 unidades para o destino 2 e 10 unidades para o destino 3; da fonte 2 : IO unidades para o destino 2 e 5 unidades para o destino 3. Note que, somando os valores de cada variável na saída das fontes, todas as unidades estão sendo transportadas.
O mesmo ocorre somando as quantidades que chegam aos destinos, todos estão recebendo as unidades de acordo com a capacidade de bsorção, satisfazendo todas as restrições do problema. Observação: esta não é a única solução que minimiza o custo total de transporte, no entanto, a ferramenta Solver não apresenta a tabela de custos marginals que nos permitlriam verificar a existência de múltiplas soluções para o problema apresentado. A solução (colocada na forma esquemática) é: 12(20) 2.
VARIAÇÕES NA FORMULAÇÃO DO PROBLEMA: 2. 1. OFERTA TOTAL DIFER NDA TOTAL. caso em produtos de outros fornecedores para atender a demanda que é maior que a oferta ou no caso de destinos fict(cios, um novo mercado para absorver o excesso de oferta. O método é utilizado da mesma forma que no caso clássico. Loglcamente os destinos que estiverem recebendo unidades da fonte fictícia não receberão estas unidades, bem como as fontes que estiverem enviando unidades para destinos fictícios, não estarão enviando estas unidades.
Os custos unitários de transporte associados ? fonte/destino fictícios são zero, já que estas unidades não serão transportadas. EXEMPLO 2: Suponha que no exemplo 1 a demanda do destino 3 seja alterada para 15 unidades. Então a demanda total (20+10+15=45) é superior à oferta total (25+15=40). Logo, precisamos incluir uma FONTE FICTíClA com oferta de 5 unidades para igualarmos oferta total e demanda total e associarmos custo ZERO de transporte desta fonte fictícia para os 3 destinos. 1) Tabela dos custos unitários de transporte.
A IBICIDI 21 Fonte 1 1 1013 151 1217 g I 4 Fonte Fictícia O IO 10 2) Tabela com as ofertas das fontes, demandas dos destinos e custo total do transporte. 5 | Destino 1 61 ponte 1 8 Fonte Fictícia Destino 2 Destino 31 Soma Oferta -soma g7:D7 25 I 25 | I 15 1 9 Soma I =somarproduto(32:D4;B6:D8) 10 Demanda | 20 | 10 | 15 3) Parâmetros do Solver: g. Célula de destino: E9 h. Selecionar Igual a: Mínimo i. Células variáveis: B6:D8 j. Restrições: BIO*IO B6:D8 NÚMERO (é esta restrição que impõe que a solução só conterá números INTEIROS) k.
Opções: selecionar Presumir Modelo Linear e Presumir Não negativos l. Resolver 4) Saída do Solver Destino 1 | Destino 2 Destlno 3 Soma ponte 1 IO 110 115 Fonte 2 1510 10 25 125 1 ponte fictícia 15 IO 15 15 1 Soma 120 110 15 325 Demandal 20 10 11511 Oferta Solução: Para obtermos o custo total mínimo do transporte de $ 325,00 deve-se transportar: da fonte 1: 10 unidades para o destino 2 e 5 unidades para o da fonte 2 : 15 unidades para o destino 1 e 10 unidades para o Veia que o destino 1 “está unidades da fonte enviar e receber, bem como todos os destinos.
Isto é, cada nó pode ser uma fonte elou destino simultaneamente. Neste caso a dimensão do problema aumenta consideravelmente. Alguma modificação é necessária para a resolução. Se o problema apresenta m fontes e n destinos originais, no caso de transbordo teremos m+n fontes e m+n destinos. Também precisamos adicionar o total de unidades que precisam ser transportadas a todas as capacidades das fontes e dos destinos antes de entrar com os dados do problema. Os custos unitários de transporte de ma fonte ou destino para ele mesmo (diagonal) normalmente são zero.
Neste caso, os valores apresentados na diagonal da solução devem ser desconsiderados, já que não estão sendo transportados. (Há situações nas quais as duas variações ocorrem no mesmo problema: demanda total diferente da oferta total e possibilidade de transporte com transbordo). EXEMPLO 3: Suponha que no exemplo 1 aceitemos que o transporte possa ser feito com transbordo. Temos então um problema com 5 fontes e 5 destinos. Precisamos então conhecer 25 custos unitários de transporte. Considere que os custos unitários de transporte de ma fonte ou destino para ele mesmo sejam zero.
Considere ainda que os custos, de ida e volta, sejam os mesmos e que tenhamos os seguintes custos unitários de transporte adicionais: Fonte 1 para fonte 2 = fonte 2 para fonte 1 = 2 Destino 1 para destin02 = destino 2 para destino 1 = 6 Destino 1 para destino 3 = destino 3 para destino 1 – g destino 2 para destino 1 —6 Destino 2 para destino 3 destino 3 para destino 2 – 5 1) Tabela de custos: A IBICIDIEIFI 3 4 6 I Fontel Fonte 2 Fonte 1 1012 1 10 I Fonte 2 | 2 0112 1110 112 Destino Destino 213 7 16 Destino 315 9 | g 13151 17191 016 91 10151 15101
Observação: As células contendo os dados referentes aos custos unitários de transporte do problema resolvido pelo modelo clássico estão em cinza só para destacar o aumento da dimensão do problema. Para ajustarmos a oferta e a demanda, precisamos somar o valor mínimo de 40 (total de unidades a serem transportadas) na oferta de cada fonte e na demanda de cada destino. A entrada de dados do nosso problema então fica: I Fonte 1 Fonte 2 | Destino 1 Destino 2 | 8 Soma I OFERTA Destino 3 | 9 11 12 13 14 Fonte 1 Fonte 2 Destinol Destino 2 Destino 3 soma I | 55 | I 65 -soma B13:F13) 40 14 soma 15 DEMANDA 140 140 160 50 150 1 .
Célula de destino: G 14 c. Células variáveis: B9:F13 d. Restrições: B9:F13 NUMERO e. Opções: selecionar Presumir Modelo Linear e Presumir Não f. Resolver Fontel I Fonte 2 Destino 1 | Destino 2 Destino 3 | OFERTA 1510 0130 110 Fonte 2 25 140 IO Destinol IO 140 Destino 21 0 0 20 Destino 310 Somal 40 40 60 DEMANDAI 40 40 | 60 | 50 Soma OIO 010 20 IO o | 40 50 | 50 55 155 1 65 65 | ao 40 | 40 40 | 310 50 Resposta: para obter o custo total mínimo do transporte de $ 310,00 deve-se transportar Fonte 1: 30 unidades para o destino 2 e IO unidades para o Fonte 2: 25 unidades para a fonte 1 Destino 2: 20 unidades pa