La Media

Problema de
Transporte
(Redes)

O Problema de Transporte consiste em determinar o menor
custo (ou o maior lucro) em transportar produtos de várias
origens para vários destinos.

Aplicação direta em Logística.

O Problema de Transporte é também um problema de P.L.,
porém devido a sua importância e ao mau desempenho do
Simplex para este tipo de problema, este será estudado de
maneiraespecifica.

Exemplos:
1) Transportar produtos de m fábricas para n estoques;
2) Transportar produtos de m estoques para n lojas.

Outro Exemplo
Uma companhia enlata ervilhas nas suas unidades “Cannery1,
Cannery2, Cannery3” e transporta as latas de ervilha por
caminhão para os seus estoques “Warehouse1, Warehouse2,
Warehouse3, Warehouse4”.

A tabela abaixo mostra os custos detransporte, a disponibilidade
nas unidades “Cannery” e as necessidades nos estoques.

A representação esquemática abaixo ilustra o problema

A função objetivo, a ser minimizada, é:

Z = 464x11 + 513x12 + 654x13 + 867 x14
+ 352x 21 + 416x 22 + 690x 23 + 791x 24
+ 995x 31 + 682x 32 + 388x 33 + 685x 34

As restrições são:
x11 + x12 + x13 + x14
x21

+ x22 + x23 + x24
x31

+ x21

x11+ x31
+ x22

x12

+ x32
+ x23

x13
x14

+ x33
+ x24

com

x ij ≥ 0

+ x32 + x33 + x34

(i = 1,2,3; j = 1,2,3,4)

+ x34

= 75
= 125
= 100
=
=
=
=

80
65
70
85

O modelo generalizado fica:
mn

min Z = ∑ ∑ cij x ij
i =1 j=1

sujeito a:

n

∑ x ij = s i

j=1

disponibilidade

m

∑ x ij = d j

i =1

x ij ≥ 0

demanda

(i = 1,..., m; j =1,...n )

Algoritmo
Como o Problema de Transporte é um problema de P.L., o Simplex
pode ser utilizado. Porém, devido as características específicas do
Problema de Transporte, uma versão modificada do Simplex,
denominado, “Método Simplex de Transporte” torna a resolução
deste tipo de problema muito mais eficiente, quando comparado ao
Simplex tradicional.
O algoritmo todo pode serexecutado realizando operações sobre
uma tabela com a seguinte forma:

cij é o custo de transporte da origem i para o destino j;
xij é a quantidade transportada da origem i para o destino j;
dj é a demanda do destino j;
si é a oferta da origem i;
m é o número de origens e n é o número de destinos.

Exemplo
Considere a seguinte tabela abaixo:

1o Passo: Solução Inicial
Como no Simplextradicional, faz-se necessário achar uma solução
viável inicial. A maneira mais simples para esta tarefa é através do
Método do Canto Noroeste.

2o Passo: Critério de Otimalidade
Como no Simplex tradicional, uma solução é analisada se pode ou
não ser melhorada observando-se os coeficientes das variáveis
não básicas na função-objetivo.
a) Escrever a função-objetivo em termos das variáveis nãobásicas.
Multiplicar cada restrição de linha pelo número –ui e cada
restrição de coluna pelo número –vj e somar as novas linhas e
colunas na função-objetivo de tal maneira que os coeficientes
das variáveis básicas sejam todos nulos.
Se xij é básico: cij - ui - vj = 0
Essas igualdades compõem um sistema de m + n – 1 equações
com m + n incógintas. A solução desse sistema é obtidaatribuindo-se um valor arbitrário a uma das incógnitas e
calculando as demais.

De posse desses valores, calcula-se os coeficientes das
variáveis não-básicas:
Se xij é não-básico: coeficiente = cij - ui - vj
Se todos esses valores forem não-negativos a solução é ótima.
Se houver coeficientes negativos, implica que a solução poderá
ser melhorada (minimizada).
b) A variável que entra na base é avariável cujo coeficiente
negativo tenha o maior valor absoluto.
c) A introdução de uma nova variável na base ocasiona uma reação
em cadeia para compensar as restrições de linha (oferta) e
coluna (demanda).
O valor da variável que entra deve ser o maior valor possível,
sem tornar nenhuma variável básica negativa. A variável básica
que tiver seu valor anulado em conseqüência da variável que...