Problemas Lineares Especiais Problema de Transportes-2020-1

13 Problemas Lineares Especiais – Problema de Transportes © 2020 Prof. Sérgio F. Mayerle 13 Problemas Lineares Especiais – Problema de Transportes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 2 of 14  Descrição do problema de transportes  Obtenção de uma solução inicial viável  Algoritmo das alpondras  Exemplo numérico  Exemplo prático 13 Problemas Lineares Especiais – Problema de Transportes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 3 of 14 Descrição do Problema de Transportes O Problema de Transportes consiste em determinar as quantidades de um determinado produto que deverão ser transportadas de m origens para n destinos, dadas as restrições de oferta máxima ( i O ) associadas a cada origem e as restrições de demanda ( j D ) associadas a cada destino. Formalmente, pode ser equacionado como: 1 1 1 1 . : 1,.., 1,.., 0 1,..., 1,..., (1.a) (1.b) (1.c) (1.d) m n ij ij i j n ij i j m ij j i ij Min z c x s a x O i m x D j n x i m j n                    ijc ijx j D Oi 13 Problemas Lineares Especiais – Problema de Transportes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 4 of 14 Obtenção de uma Solução Inicial Viável Para obter uma solução inicial viável, deve-se realizar o equilíbrio entre a oferta total e a demanda total. Ito garante que sempre haverá uma solução viável para o problema de transportes.  No caso da demanda total ser maior que a oferta total, adiciona-se uma origem fictícia de modo a igualar oferta e demanda. A oferta fictícia representa a falta de produto no mercado, e os transportes realizados a partir desta origem serão interpretados como uma demanda não atendida  No caso da oferta total ser maior que demanda total, deverá ser acrescentado um destino fictício. Neste caso os transportes realizados para este destino fictício serão interpretados como um excesso de oferta não transportado. Nestes casos, os custos de transportes entre qualquer origem ou destino fictícios serão nulos, já que o transporte efetivamente não se realiza. Três métodos são utilizados para obter uma solução inicial viável, a depender da escolha da célula (fluxo) a ser incrementada. Efetuada a escolha, a máxima quantidade possível será alocada. Efetuada a alocação, elimina-se a linha (ou coluna) da matriz na qual se atingiu a oferta (ou demanda), e procede-se a escolha de uma outra célula, até que não existam mais sobras de oferta e demanda. Método do Canto Noroeste: a célula escolhida para alocação é que se situa mais ao noroeste possível e que ainda dispõe de oferta e de demanda. Método do Custo Mínimo: a célula escolhida para alocação é a de menor custo unitário de transporte que ainda disponha de oferta e demanda. Método de Vogel: consiste em alocar fluxo na célula cuja penalidade pela não-escolha é máxima. Penalidades, associadas às linhas (colunas), são calculadas pela diferença entre os dois menores custos da linha (coluna). Na linha ou coluna de maior penalidade será escolhida a célula na qual a alocação é efetuada. 13 Problemas Lineares Especiais – Problema de Transportes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 5 of 14 Algoritmo das Alpondras P0 Obtenha uma solução inicial. Para tanto, utilize um dos métodos citados anteriormente (Canto Noroeste, Custo Mínimo ou Vogel); P1 Determine valores dos iu e dos jv , de modo que para toda célula alocada seja satisfeita a condição 0 ij ij i j c c u v      . Para tanto, arbitre apenas um valor de iu ou jv . No caso de existirem menos que 1 m  n  células alocadas, haverá necessidade de serem realizadas alocações com zeros explícitos para completar este número de células alocadas (). P2 Determine, para cada célula não alocada, o valor ij ij i j c c u v     . Se todos os ijc forem positivos ou nulos, então PARE. A solução corrente é ótima. Em caso contrário determine a célula que possui o menor ijc . Assinale esta célula com o sinal (+). Partindo da célula já assinalada, busque, alternadamente, sobre linhas e colunas da matriz de alocações, células alocadas. Marque estas células, alternadamente, com sinais (+) e (-), até retornar a primeira célula assinalada. P3 Determine a célula assinalada com (-) que possui a menor alocação. Subtraia esta quantia de todas as células assinaladas com (-) e adicione esta mesma quantia a todas células assinaladas com (+), e retorne ao passo P1. 13 Problemas Lineares Especiais – Problema de Transportes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 6 of 14 Exemplo Numérico Determinar a distribuição de produtos, considerando as ofertas e demandas apresentadas no quadro abaixo, e de modo a minimizar o custo total de transporte. Custos de Transportes (R$/unid) Destino 01 Destino 02 Destino 03 Oferta (unid/dia) 01 10,00 7,00 8,00 200 02 9,00 8,00 6,00 190 Origem 03 12,00 9,00 11,00 140 Demanda (unid/dia) 150 180 160 13 Problemas Lineares Especiais – Problema de Transportes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 7 of 14 Usando o Método do Canto Noroeste para obtenção de uma solução básica viável tem-se: Oferta 10 7 8 0 150 50 - - 9 8 6 0 - 130 60 - 12 9 11 0 - - 100 40 Demanda Destino 1 Destino 2 Destino 3 Destino Fic. Origem 1 Origem 2 Origem 3 200 190 140 150 180 160 40 CT = 10  150 + 7  50 + 8  130 + 6  60 + 11  100 + 0  40 = 4350 13 Problemas Lineares Especiais – Problema de Transportes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 8 of 14 Usando o Método do Custo Mínimo para obtenção de uma solução básica viável, tem-se: Oferta 10 7 8 0 - 160 - 40 9 8 6 0 10 20 160 - 12 9 11 0 140 - - - Demanda Destino 1 Destino 2 Destino 3 Destino Fic. Origem 1 Origem 2 Origem 3 200 190 140 150 180 160 40 CT = 7  160 + 0  40 + 9  10 + 8  20 + 6  160 + 12  140 = 4010 13 Problemas Lineares Especiais – Problema de Transportes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 9 of 14 Usando o Método de Vogel para obtenção de uma solução básica viável, tem-se: Oferta Penalidades 10 7 8 0 7 1 3 20 180 - - 9 8 6 0 6 2 1 30 - 160 - 12 9 11 0 9 2 3 100 - - 40 Demanda Penalidades 1 1 2 0 Destino 1 Destino 2 Destino 3 Destino Fic. Origem 1 Origem 2 Origem 3 200 190 140 150 180 160 40 CT = 10  20 + 7  180 + 9  30 + 6  160 + 12  100 + 0  40 = 3890 13 Problemas Lineares Especiais – Problema de Transportes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 10 of 14 Em geral, para problemas de pequeno porte, o método de Vogel apresenta a melhor solução inicial. Neste caso, como veremos, este método obtém a solução ótima do problema. Porém, usando a solução inicial obtida pelo método do Custo Mínimo tem-se: Oferta Ui 2 10 7 3 8 0 -1 - + 160 - - 40 9 8 6 -1 0 0 + 10 - 20 160 - 12 -2 9 2 11 -4 0 3 - 140 - - + - Demanda Vj 9 8 6 1 Destino 1 Destino 2 Destino 3 Destino Fic. Origem 1 Origem 2 Origem 3 200 190 140 150 180 160 40 13 Problemas Lineares Especiais – Problema de Transportes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 11 of 14 Oferta Ui -2 10 7 -1 8 0 0 + - 180 - - 20 9 4 8 6 3 0 -3 30 - 160 - 12 2 9 2 11 0 0 - 120 - - + 20 Demanda Vj 12 7 9 0 Destino 1 Destino 2 Destino 3 Destino Fic. Origem 1 Origem 2 Origem 3 200 190 140 150 180 160 40 Oferta Ui 10 7 1 8 2 0 10 20 180 - - 9 2 8 6 3 0 9 30 - 160 - 12 0 9 2 11 0 12 100 - - 40 Demanda Vj 0 -3 -3 -12 Destino 1 Destino 2 Destino 3 Destino Fic. Origem 1 Origem 2 Origem 3 200 190 140 150 180 160 40 13 Problemas Lineares Especiais – Problema de Transportes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 12 of 14 Portanto, esta solução é ótima, visto que todos os custos marginais são positivos, e consequentemente não é possível reduzir o custo total. Portanto, a solução é a seguinte: Origem Destino Quantidade Custo Unitário Custo Total O1 D1 20 10 200 O1 D2 180 7 1260 O2 D1 30 9 270 O2 D3 160 6 960 O3 D1 100 12 1200 O3 Fic 40 0 0 Custo Total 3890 13 Problemas Lineares Especiais – Problema de Transportes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 13 of 14 Exemplo Prático A sorveteria XYZ produz sorvetes artesanais. Dado a sazonalidade da demanda, e a baixa capacidade instalada, o Sr. MacIce, gerente da empresa, está estudando a possibilidade de antecipar o início da produção, armazenando o produto em câmaras frias até os meses de maior consumo. No quadro abaixo encontram-se as médias históricas das demandas e dos preços de armazenagem, os quais são negociados para todo o período de armazenagem no instante em que o produto dá entrada no frigorífico. O gerente do frigirífico prometeu descontos especiais de 10%, 18% ou 24% para o caso da armazenagem ocorrer, respectivamente, por 2, 3 ou 4 (ou mais) meses. Set Out Nov Dez Jan Fev Mar Demanda (ton/mês) 120 150 180 210 270 210 170 Armazenagem (R$/ton.mês) 1.800 1.700 1.400 1.400 1.300 1.200 1.100 A atual capacidade nominal de produção é de 160 ton/mês. Com horas extras, esta capacidade poderá ser aumentada em até 25%, a um custo adicional de R$ 300,00 por tonelada. O Sr. MacIce sabe que, dada a margem de lucro que o sorvete apresenta, interessa a oportunidade de atender toda a demanda. Ajude-o a resolver este problema, programando a produção e a contratação de armazenagem para o período Set/Mar. 13 Problemas Lineares Especiais – Problema de Transportes EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 14 of 14 F I M (© 2020 Prof. Sérgio Mayerle)