Problema de Transporte

Objectivo Geral: Resolver o problema de transporte, usando alguns métodos como o Canto Noroeste.

Fundamentação Teórica

Temos que transportar produtos das várias origens onde estão estocados para vários destinos onde são necessários. Conhecemos os custos unitários de transporte de cada origem para cada destino (Cij - custo unitário de transporte da origem i para o destino j). Devemos decidir quanto transportar de cada origem para cada destino (Xij- quantidade a ser transportada da origem I para o destino j.

Definição: O problema de transporte é uma classe especial de problemas de programação linear que trata do envio de uma mercadoria, de origens  para destinos.

Tem como objectivos:

(1) Determinar uma programação que minimize o custo total de expedição e ao mesmo tempo, satisfazer os limites de fornecimento e demanda.

(2) Completar a transferência dos produtos com o menor custo possível.

Obs.: O problema de transporte pode ser equilibrado ou não. O problema de transporte não equilibrado ou tem sistemas não equilibrados acontece quando a necessidade a ser transportada é diferente da necessidade do destino, o que é muito comum acontecer, neste caso cria-se uma linha fantasma representando a quantidade excedente ou faltante. Caso contrário é equilibrado.

                                 Modelagem do Problema de Transporte

                                        Origens         C₁₁ - x₁₁      Destinos

a₁ →                                         →b₁

 

a₂ →                                         →b₂

.

 

a_n →                                         →b_n

Nesta figura há m origens e n destinos, cada um representado por um nó. Os arcos representam as rotas que ligam as origens aos destinos. O arco (i,j), que liga a origem i ao destino j, nos dá duas informações: 1) o custo de transporte por unidade, c_ij; e 2) a quantidade enviada, x_ij. A quantidade de suprimento na origem i é a_i e a quantidade de demanda no destino j é b_j.

O objectivo do problema é determinar as incógnitas xij que minimizarão o custo total de transporte e, ao mesmo tempo, satisfarão todas as restrições de suprimento e demanda.

 Solução para o problema do transporte

A solução do problema do transporte, como todo problema representado por um modelo de programação linear, pode ser obtida por um método especifico. Entretanto, devido as suas características especiais do problema de transporte, podemos descrever e utilizar um método que, tem os cálculos simplificados.

Uma solução básica para o problema é um conjunto de valores a transportar que obedecem a duas condições:

v  Satisfazem as restrições de origem e destino;

v  Não apresentam circuitos entre as variáveis básicas. Por circuitos devemos entender uma poligonal fechada construída no sentido das linhas ou colunas, ligando variáveis básicas.

Para achar a solução básica inicial, dentre vários métodos utilizaremos o método do Canto Noroeste e a análise das variáveis básicas será feita com recurso ao método de Stepping Stone.

 Método do canto noroeste

A partir da célula superior esquerda transportamos o máximo possíveI da origem ao destino correspondente. Esse procedimento zera a disponibilidade da linha ou da coluna da célula. O próximo transporte será feito na célula contigua (à direita ou abaixo) que tenha disponibilidade de linha e coluna correspondente. O método do canto noroeste garante a não-formação de circuitos entre as variáveis básicas, além de satisfazer as condições de contorno (restrições de origem e destino).

Exemplo:

A LK Cimentos, Ld  tem três fábricas de cimentos: uma em Benguela, uma no Kwanza Sul e outra em Luanda, e duas grandes centrais de distribuição: uma no Huambo e a outra no Bié. As capacidades das três fábricas por dia são de 1000, 1500 e 1200 sacos de cimento. As demandas diárias nas duas centrais de distribuição são de 2300 e 1400 sacos de cimentos. O mapa de distâncias entre as fábricas e as centrais de distribuição é dado na seguinte tabela:

	Huambo	Bie
Benguela	1000	2690
Kwanza Sul	1250	1350
Luanda	1275	850

A empresa transportadora encarregada no transporte dos sacos de cimento cobra 8 centavos por saco. Os custos de transporte por carro nas diferentes rotas, arredondadas para o valor mais próximo, contam na seguinte tabela:

	Huambo	Bie
Benguela	80	215
KwanzaSul	100	108
Luanda	102	68

Rede de Transporte

                                   Origens                                        Destinos

1000 →                                                                    →2300

 

1500 →                                                                    →1400

.

 

1200 →                                       

Tabela de Transporte ou Matriz de Transporte

	Huambo	Bie
Benguela	80 X11	215 X12	1000
Kwanza Sul	100 X21	108 X22	1500
Luanda	102 X31	68 X32	1200
	2300	1400

Passos para a resolução do problema de transporte:

1- Analisar se o problema é balanceado ou não, isto é, total do fornecimento = total da demanda ou diferentes.

2- Se for balanceado achar a solução básica inicial, tendo como número de variáveis básicas m + n - 1, onde m é o total de fornecimento e n o total da demanda. Caso não seja balanceado, introduzir um fornecimento fictício ou uma demanda fictícia, conforme o caso, para que o problema se torne balanceado. A solução básica inial é achada tendo em conta  o Método do canto noroeste;

3- Achar a solução óptima pelo método stepping stone ou pelo método dos multiplicadores.

Solução:

m+n-1=3+2-1=4; fornecimento = demanda → 3700=3700

Tabela Inicial (método do canto noroeste)

	Huambo	Bie
Benguela	80 1000	215 0	1000
Kwanza Sul	100 1300	108 200	1500
Luanda	102 0	68 1200	1200
	2300	1400

Método Stepping Stone

Tabela Inicial (método do canto noroeste)

	Dever	Miami
Los Angeles	80 1000	215 0	1000
Detroit	100 1300	108 200	1500
Nova Orleans	102 0	68 1200	1200
	2300	1400

X₁₂ = 215-80+100-108 = 127

X₃₁ = 102-68+108-100= 42       Todas as variáveis não básicas são positivas, logo, esta é solução óptima.

Solução:

Custo_mim = 80x1000+1300x100+200x108+1200x68=313.200

Rede de transporte do cimento da empresa Lk.

                                   Origens                                        Destinos

1000 →                                      1000                      →2300              2300

1300

1500 →                                       200                       →1400             1400

.

1200                                       

           1200 →

BIBLIOGRAFIA

1. Goldbarg, M.C. Luna, H.P.L. (2005) Otimização Combinatória e Programação Linear. Modelos e Algoritmos. 2ª Edição. Editora Campus.

2.  Hillier F. S., Lieberman G. J. (2010) Introdução à Pesquisa Operacional. 8ª Edição. Editoras Mc Graw Hill e bookman.

3. Taha, Hamdy A. (2008) Pesquisa Operacional: Uma Visão Geral. 8ª Edição. São Paulo. Pearson Prentice Hall.

4. Ramalhete, Manuel;  Guerreiro, Jorge; Magalhães, Alípio – Programação Linear, Volume 1. Alfragide: McGraw-Hill, 1984.

5. Tavares, L. Valadares; Oliveira, R. Carvalho; Themido, I. Hall; Correia, F. Nunes – Investigação Operacional.  Alfragide: McGraw-Hill, 1997.