Problema do transporte

Prévia do material em texto

Problema de Transporte
Raphael Ramos
Raphael Ramos Problema de Transporte 1 / 99
Introdução
O Problema de Transporte consiste em determinar o menor
custo (ou o maior lucro) em transportar produtos de várias
origens onde são estocados para vários destinos onde são
necessários.
Raphael Ramos Problema de Transporte 2 / 99
Introdução
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
maneira especifica.
Raphael Ramos Problema de Transporte 3 / 99
Introdução
Exemplos:
1 Transportar produtos de m fábricas para n estoques;
2 Transportar produtos de m estoques para n lojas.
Raphael Ramos Problema de Transporte 4 / 99
Introdução
Transporte
Conhecemos os custos unitários de transporte de cada origem
para cada destino. Devemos decidir quanto transportar de cada
origem i para cada destino j. Representado por xij
Raphael Ramos Problema de Transporte 5 / 99
Objetivo
Transporte
O objetivo é completar a transferência dos produtos com o
menor custo possível.
Raphael Ramos Problema de Transporte 6 / 99
Exemplo
O modelo generalizado fica:
min Z =
m∑
i=1
n∑
j=1
cijxij
sujeito a :
n∑
j=1
xij = sij disponibilidade
m∑
i=1
xij = dj demanda
xij > 0 (i = 1, ...,m; j = 1, ...n)
(1)
Raphael Ramos Problema de Transporte 7 / 99
Exemplo 1
Raphael Ramos Problema de Transporte 8 / 99
Tabela
Exemplo 1
Essa situação pode ser representada de maneira simples em
uma tabela:
Destinos j D1 D2 DisponibilidadesOrigens i
O1 10 12 50
O2 20 8 100
O3 6 15 120
Necessidades 100 170 270270
Raphael Ramos Problema de Transporte 9 / 99
Modelo Linear
Exemplo 1
min z = 10x11 +12x12 +20x21 +8x22 +6x31 +15x32
sujeito a x11 +x12 = 50
x21 +x22 = 100
x31 +x32 = 120
x11 +x21 +x31 = 100
x12 +x22 +x32 = 170
xij > 0, j = 1,2 e i = 1,2,3
Raphael Ramos Problema de Transporte 10 / 99
Solução básica inicial
Uma solução básica para o problema é um conjunto de valores
a transportar que obedecem a duas condições:
1) Satisfazem as restrições de origem e destino;
2) 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.
Raphael Ramos Problema de Transporte 11 / 99
Método do canto noroeste
Solução básica inicial
A partir da célula superior esquerda transportamos o máximo
possível 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 contígua(à
direita ou abaixo) que tenha disponibilidade de linha e coluna
correspondente.
Raphael Ramos Problema de Transporte 12 / 99
Canto noroeste
Exemplo 1
Essa situação pode ser representada de maneira simples em
uma tabela:
Destinos j D1 D2 DisponibilidadesOrigens i
O1 10 12 50
O2 20 8 100
O3 6 15 120
Necessidades 100 170 270270
Raphael Ramos Problema de Transporte 13 / 99
1a rodada
Canto noroeste
Passos:
1) Selecione a célula x11, localizada no canto superior
esquerdo(noroeste);
2) Capacidade total 1 é 50. Já a demanda é 100. De forma que
o valor máximo a ser alocado nessa célula é o mínimo entre
esses dois valores;
3) O limite máximo de capacidade do fornecedor 1 foi atingido,
de forma que as células correspondentes à mesma linha x12
e x13 devem ser bloqueadas.
Raphael Ramos Problema de Transporte 14 / 99
1a rodada
Canto noroeste
1 2
1 50 x 50/{0}
2 100
3 120
100/{50} 170
Raphael Ramos Problema de Transporte 15 / 99
2a rodada
Canto noroeste
Passos:
1) Dentre as células restantes, selecionar a localizada no canto
noroeste x21
2) A quantidade máxima que poder ser alocada na célula x21 é
50 referente a demanda e 100 referente a origem. Logo x21 =
min 50, 100 = 50;
3) A célula x31 precisa ser bloqueada, já que o limite máximo de
demanda da coluna 1 foi atingido.
Raphael Ramos Problema de Transporte 16 / 99
2a rodada
Canto noroeste
1 2
1 50 x 50/{0}
2 50 100/{50}
3 x 120
100/50/{0} 170
Raphael Ramos Problema de Transporte 17 / 99
3a rodada
Canto noroeste
Passos:
1) Dentre as células restantes, selecionar a localizada no canto
noroeste x22
2) A quantidade máxima que poder ser alocada na célula x22 é
170 referente a demanda e 50 referente a origem. Logo x22 =
min 50, 170 = 50;
3) Nenhuma célula precisa ser bloqueada.
Raphael Ramos Problema de Transporte 18 / 99
3a rodada
Canto noroeste
1 2
1 50 x 50/{0}
2 50 50 100/50/{0}
3 x 120
100/50/{0} 170/{120}
Raphael Ramos Problema de Transporte 19 / 99
4a rodada
Canto noroeste
Passos:
1) Dentre as células restantes, selecionar a localizada no canto
noroeste x32
2) A quantidade máxima que poder ser alocada na célula x32 é
120 referente a demanda e 120 referente a origem. Logo x32
= min 120, 120 = 120;
3) Nenhuma célula precisa ser bloqueada.
Raphael Ramos Problema de Transporte 20 / 99
4a rodada
Canto noroeste
1 2
1 50 x 50/{0}
2 50 50 100/50/{0}
3 x 120 120/{0}
100/50/{0} 170/120/{0}
Raphael Ramos Problema de Transporte 21 / 99
Solução básica inicial
Canto noroeste
A solução básica é, portanto: x11 = 50, x21 = 50, x22 = 50, x32 =
120. Variáveis não básicas: x12 = 0, x31 = 0.
Raphael Ramos Problema de Transporte 22 / 99
Exemplo
Fábricas Depósitos Total1 2 3 4
1 19 30 50 10 7
2 70 30 40 60 9
3 40 8 70 20 18
Total 5 8 7 14 34
Raphael Ramos Problema de Transporte 23 / 99
Exemplo
Canto noroeste
Fábricas Depósitos Total1 2 3 4
1 5 2 x x 7
2 x 6 3 x 9
3 x x 4 14 18
Total 5 8 7 14 34
Raphael Ramos Problema de Transporte 24 / 99
Algoritmo
Método de aproximação de Vogel
Passos:
3 Assim como no método do canto noroeste, aloque o a
maior quantidade possível de produto a essa célula, de
forma que a soma das células correspondentes na mesma
linha e na mesma coluna não ultrapasse a capacidade de
fornecimento total e de demanda total, respectivamente.
4 Analogamente ao método do canto noroeste, a partir da
célula selecionada no Passo anterior, bloqueie as células
correspondentes à mesma linha ou coluna que atingiu o
limite máximo de fornecimento ou demanda,
respectivamente. No caso de utilização do limite máximo,
tanto na linha como na coluna, bloqueie apenas uma delas.
Enquanto restar mais de uma célula não alocada e não
bloqueada, volte para o Passo 1. Caso contrário, vá para o
Passo 5.
Raphael Ramos Problema de Transporte 25 / 99
Algoritmo
Método de aproximação de Vogel
Passos:
5 Aloque a essa última célula a capacidade ou demanda
remanescente.
Raphael Ramos Problema de Transporte 26 / 99
Algoritmo
Método de aproximação de Vogel
Passos:
6 Assim como no método do canto noroeste, aloque o a
maior quantidade possível de produto a essa célula, de
forma que a soma das células correspondentes na mesma
linha e na mesma coluna não ultrapasse a capacidade de
fornecimento total e de demanda total, respectivamente.
Raphael Ramos Problema de Transporte 27 / 99
Exemplo 2
Consumidor
1 2 3 Capacidade Penalidadelinha
Fornecedor
1 12 22 30 100 22 - 12 = 10
2 18 24 32 140 24 - 18 = 6
3 22 15 34 160 22 - 15 = 7
Demanda 120 130 150
Penalidade
coluna 18 - 12 = 6 22 - 15 = 7 32 - 30 = 2
Raphael Ramos Problema de Transporte 28 / 99
1a etapa
Consumidor
1 2 3 Capacidade Penalidadelinha
Fornecedor
1 100 x x 100 22 - 12 = 10
2 140 24 - 18 = 6
3 160 22 - 15 = 7
Demanda 120 130 150
Penalidade
coluna 18 - 12 = 6 22 - 15 = 7 32 - 30 = 2
Raphael Ramos Problema de Transporte 29 / 99
2a etapa
Consumidor
1 2 3 Capacidade Penalidadelinha
Fornecedor
1 100 x x 100 x
2 x 140 24 - 18 = 6
3 130160 22 - 15 = 7
Demanda 120 130 150
Penalidade
coluna 22 - 18 = 4 22 - 15 = 9 34 - 32 = 2
Raphael Ramos Problema de Transporte 30 / 99
3a etapa
Consumidor
1 2 3 Capacidade Penalidadelinha
Fornecedor
1 100 x x 100 x
2 20 x 140 32 - 18 = 14
3 x 130 160 34 - 22 = 12
Demanda 120 130 150
Penalidade
coluna 22 - 18 = 4 x 34 - 32 = 2
Raphael Ramos Problema de Transporte 31 / 99
4a etapa
Consumidor
1 2 3 Capacidade
Fornecedor
1 100 x x 100
2 20 x 120 140
3 x 130 30 160
Demanda 120 130 150
Raphael Ramos Problema de Transporte 32 / 99
Solução básica inicial
A solução básica é portanto, x11 = 100, x21 = 20, x23 = 120, x32 =
130 e x33 = 30 com z = 8.370.
Raphael Ramos Problema de Transporte 33 / 99
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 ser executado realizando operações
sobre uma tabela com a seguinte forma:
Raphael Ramos Problema de Transporte 34 / 99
Exemplo
Algoritmo
Considere a seguinte tabela abaixo:
Raphael Ramos Problema de Transporte 35 / 99
1o Passo: Solução Inicial
Como no Simplex tradicional, 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 ou método de
aproximação de Vogel.
Raphael Ramos Problema de Transporte 36 / 99
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ão
bá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 xi j
é básico: ci j - ui - vj = 0 Essas igualdades compõem um
sistema de m + n - 1 equações com m + n incógnitas. A
solução desse sistema é obtida atribuindo-se um valor
arbitrário a uma das incógnitas e calculando as demais.
Raphael Ramos Problema de Transporte 37 / 99
2o Passo: Critério de Otimalidade
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).
Raphael Ramos Problema de Transporte 38 / 99
2o Passo: Critério de Otimalidade
b) A variável que entra na base é a variável cujo coeficiente
negativo tenha o maior valor absoluto.
b) 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 consequência da
variável que entra será a variável que sai da base.
b) Voltar ao item a) até que a solução seja ótima.
Raphael Ramos Problema de Transporte 39 / 99
Exemplo 2
A Tools Stones Ltda é uma empresa fabricante de autopeças,
cujas sedes estão localizadas em Italva, Itaperuna e Itajara.
Seus clientes encontram-se em Bom Jesus do Itabapoana, Laje
do Muriaé e Miracema. Os custos unitários de transporte de
cada origem para cada destino, assim como a capacidade de
cada fornecedor, encontram-se na tabela abaixo:
Raphael Ramos Problema de Transporte 40 / 99
Exemplo 2
Fornecedor
Custo unitário de transporte
CapacidadeConsumidor
Bom Jesus Laje do Muriaé Miracema
Italva 12 22 30 100
Itaperuna 18 24 32 140
Itajara 22 15 34 160
Demanda 120 130 150
Raphael Ramos Problema de Transporte 41 / 99
Objetivo
Exemplo 2
O objetivo é atender a demanda de cada consumidor final,
respeitando as capacidades de fornecimento, de forma a
minimizar o custo total de transporte.
Raphael Ramos Problema de Transporte 42 / 99
Resolvendo
Exemplo 2
A capacidade de fornecimento é igual á demanda total
consumida - problema de transporte balanceado;
Variáveis de decisão: xij (quant. de peças transportadas do
fornecedor i para o consumidor j), com i=1,2,3 e j=1,2,3;
A capacidade de cada fornecedor será utilizada para
atender a demanda dos consumidores;
A demanda de cada consumidor deve ser atendida.
Raphael Ramos Problema de Transporte 43 / 99
Resolvendo
Exemplo 2
x11 = transporte de Italva para Bom Jesus
x12 = transporte de Italva para Laje do Muriaé
x13 = transporte de Italva para Miracema
x21 = transporte de Itaperuna para Bom Jesus
x22 = transporte de Itaperuna para Laje do Muriaé
x23 = transporte de Itaperuna para Miracema
x31 = transporte de Itajara para Bom Jesus
x32 = transporte de Itajara para Laje do Muriaé
x33 = transporte de Itajara para Miracema
Raphael Ramos Problema de Transporte 44 / 99
Modelo Linear
Exemplo 2
min z = 12x11 +22x12 +30x13 +18x21 +24x22 +32x23 +22x31 +15x32 +34x33
sujeito a x11 +x12 +x13 = 100
x21 +x22 +x23 = 140
x31 +x32 +x33 = 160
x11 +x21 +x31 = 120
x21 +x22 +x32 = 130
x31 +x23 +x33 = 150
xij > 0, j = 1,2 e i = 1,2,3
Raphael Ramos Problema de Transporte 45 / 99
Solução Básica Factível Inicial
Canto Noroeste
Consumidor
1 2 3 Capacidade
Fornecedor
1 100 x x 100
2 20 120 x 140
3 x 10 150 160
Demanda 120 130 150
A solução básica é, portanto: x11 = 100, x21 = 20, x22 = 120, x32
= 10 e x33 = 150 com z = 9.690.
Variáveis não básicas: x12 = 0, x13 = 0, x23 = 0 e x31 = 0;
Raphael Ramos Problema de Transporte 46 / 99
Teste de otimalidade
Exemplo 2
Custos: c11 = 6, c12 = 5, c13 = 8, c21 = 13, c22 = 12, c23 = 1, c31 =
7 , c32 = 9, c33 = 5, c41 = 10, c42 = 6, c43 = 4.
Variáveis básicas:
x11 → c11 - U1 - V1 = 0
x21 → c21 - U2 - V1 = 0
x22 → c22 - U2 - V2 = 0
x32 → c32 - U3 - V2 = 0
x33 → c33 - U3 - V3 = 0
Variáveis não básicas:
x12 → c12 - U1 - V2
x13 → c13 - U1 - V3
x23 → c23 - U2 - V3
x31 → c31 - U3 - V1
Raphael Ramos Problema de Transporte 47 / 99
Critério de otimalidade
Continuação
Atribua um valor para U1. No caso usamos U1 = 0.
U1 = 0 V1 = ?
U2 = ? V2 = ?
U3 = ? V3 = ?
Raphael Ramos Problema de Transporte 48 / 99
Critério de otimalidade
Continuação
Multiplicadores:
U1 = 0 V1 = 12
U2 = 6 V2 = 18
U3 = -3 V3 = 37
Raphael Ramos Problema de Transporte 49 / 99
Critério de otimalidade
Continuação
Custos reduzidos das variáveis não básicas x12 → 4
x13 → -7
x23 → -11
x31 → 13
Com os custos reduzidos das variáveis não básicas x13 e x23
são negativas, há uma solução básica factível adjacente melhor.
A variável não básica que vai entrar na base é x23, , pois tem o
menor custo.
Raphael Ramos Problema de Transporte 50 / 99
Ciclo fechado
Consumidor
1 2 3 Capacidade
Fornecedor
1 100 x x 100
2 20 120 - σ σ 140
3 x 10 + σ 150 - σ 160
Demanda 120 130 150
Raphael Ramos Problema de Transporte 51 / 99
Ciclo fechado
Menor valor da subtração
Consumidor
1 2 3 Capacidade
Fornecedor
1 100 x x 100
2 20 120 - 120 120 140
3 x 10 + 120 150 - 120 160
Demanda 120 130 150
Raphael Ramos Problema de Transporte 52 / 99
Ciclo fechado
Consumidor
1 2 3 Capacidade
Fornecedor
1 100 x x 100
2 20 x 120 140
3 x 130 30 160
Demanda 120 130 150
Raphael Ramos Problema de Transporte 53 / 99
Teste de otimalidade
Exemplo 2
Custos: c11 = 6, c12 = 5, c13 = 8, c21 = 13, c22 = 12, c23 = 1, c31 =
7 , c32 = 9, c33 = 5, c41 = 10, c42 = 6, c43 = 4.
Variáveis básicas:
x11 → c11 - U1 - V1 = 0
x21 → c21 - U2 - V1 = 0
x23 →c23 - U2 - V3 = 0
x32 → c32 - U3 - V2 = 0
x33 → c33 - U3 - V3 = 0
Variáveis não básicas:
x12 → c12 - U1 - V2
x13 → c13 - U1 - V3
x22 → c22 - U2 - V2
x31 → c31 - U3 - V1
Raphael Ramos Problema de Transporte 54 / 99
Critério de otimalidade
Continuação
Multiplicadores:
U1 = 0 V1 = 12
U2 = 6 V2 = 7
U3 = 8 V3 = 26
Raphael Ramos Problema de Transporte 55 / 99
Critério de otimalidade
Continuação
Custos reduzidos das variáveis não básicas x12 → 15
x13 → 4
x22 → 9
x31 → 2
Com os custos reduzidos de todas as variáveis não básicas são
positivos, a solução atual é ótima.
Raphael Ramos Problema de Transporte 56 / 99
Solução
Exemplo 2
Solução básica: x11 = 100, x21 = 20, x23 = 120, x32 = 130 e x33 =
30 com z = 8.370.
Variáveis não básicas: x12 = 0, x22 = 0 e x31 = 0,
Raphael Ramos Problema de Transporte 57 / 99
Exemplo 3
D1 D2 D3
O1 6 5 8 10
O2 13 12 1 20
O3 7 9 5 12
O4 10 6 4 13
8 32 15
Raphael Ramos Problema de Transporte 58 / 99
Exemplo 3
Canto noroeste
D1 D2 D3
O1 8 2 0 10
O2 20 20
O3 10 2 12
O4 13 13
8 32 15
A solução básica é, portanto: x11 = 8, x12 = 2, x22 = 20, x32 = 10,
x33 = 2, x43 = 13. Variáveis não básicas: x13 = 0, x21 = 0, x23 = 0,
x31 = 0, x41 = 0, x42 = 0.
Raphael Ramos Problema de Transporte 59 / 99
Critério de otimalidade
Custos: c11 = 6, c12 = 5, c13 = 8, c21 = 13, c22 = 12, c23 = 1, c31 =
7 , c32 = 9, c33 = 5, c41 = 10, c42 = 6, c43 = 4.
Variáveis básicas:
x11 → c11 - U1 - V1 = 0
x12 → c12 - U1 - V2 = 0
x22 → c22 - U2 - V2 = 0
x32 → c32 - U3 - V2 = 0
x33 → c33 - U3 - V3 = 0
x43 → c43 - U4 - V3 = 0
Variáveis não básicas:
x13 → c13 - U1 - V3
x21 → c21 - U2 - V1
x23 → c23 - U2 - V3
x31 → c31 - U3 - V1
x41 → c41 - U4 - V1
x42 → c42 - U4 - V2
Raphael Ramos Problema de Transporte 60 / 99
Critério de otimalidade
Continuação
Atribua um valor para U1. No caso usamos U1 = 0.
U1 = 0 V1 = ?
U2 = ? V2 = ?
U3 = ? V3 = ?
U4 = ?
Raphael Ramos Problema de Transporte 61 / 99
Critério de otimalidade
Continuação
x11 → c11 - U1 - V1 = 0
U1 = 0
x11 → 6 - 0 - V1 = 0
V1 = 6
Raphael Ramos Problema de Transporte 62 / 99
Critério de otimalidade
Continuação
U1 = 0, V1 = 6, V2 = ?
x12 → c12 - U1 - V2 = 0
x12 → 5 - 0 - V2 = 0
V2 = 5
Raphael Ramos Problema de Transporte 63 / 99
Critério de otimalidade
Continuação
U1 = 0, V1 = 6, U2 = ?, V2 = 5
x22 → c22 - U2 - V2 = 0
x22 → 12 - U2 - 5 = 0
U2 = 7
Raphael Ramos Problema de Transporte 64 / 99
Critério de otimalidade
Continuação
U1 = 0, V1 = 6, U2 = 7, V2 = 5, U3 = ?
x32 → c32 - U3 - V2 = 0
x32 → 9 - U3 - 5 = 0
U3 = 4
Raphael Ramos Problema de Transporte 65 / 99
Critério de otimalidade
Continuação
U1 = 0, V1 = 6, U2 = 7, V2 = 5, U3 = 4, V3 = ?
x33 → c33 - U3 - V3 = 0
x32 → 5 - 4 - V3 = 0
V3 = 1
Raphael Ramos Problema de Transporte 66 / 99
Critério de otimalidade
Continuação
U1 = 0, V1 = 6, U2 = 7, V2 = 5, U3 = 4, V3 = 1, U4 = ?
x43 → c43 - U4 - V3 = 0
x43 → 4 - U4 - 1 = 0
U4 = 3
Raphael Ramos Problema de Transporte 67 / 99
Critério de otimalidade
Variaveis básicas
U1 = 0, V1 = 6, U2 = 7, V2 = 5, U3 = 4, V3 = 1, U4 = 3
Com os valores encontrados, usamos no cálculo das variáveis
não básicas. Em caso de todos coeficientes positivos,
encontramos a solução ótima. Em caso de algum valor
negativo, reiniciamos os algoritmo.
Raphael Ramos Problema de Transporte 68 / 99
Critério de otimalidade
Variaveis não básicas
U1 = 0, V1 = 6, U2 = 7, V2 = 5, U3 = 4, V3 = 1, U4 = 3
Variáveis não básicas:
x13 → c13 - U1 - V3
x21 → c21 - U2 - V1
x23 → c23 - U2 - V3
x31 → c31 - U3 - V1
x41 → c41 - U4 - V1
x42 → c42 - U4 - V2
Raphael Ramos Problema de Transporte 69 / 99
Critério de otimalidade
Variaveis não básicas
U1 = 0, V1 = 6, U2 = 7, V2 = 5, U3 = 4, V3 = 1, U4 = 3
Variáveis não básicas:
x13 → c13 - U1 - V3
x13 → 8 - 0 - 1 = 7
x21 → c21 - U2 - V1
x21 → 13 - 7 - 6 = 0
x23 → c23 - U2 - V3
x23 → 1 - 7 - 1 = -7
Raphael Ramos Problema de Transporte 70 / 99
Critério de otimalidade
Variaveis não básicas
x31 → c31 - U3 - V1
x31 → 7 - 4 - 6 = -3
x41 → c41 - U4 - V1
x41 → 10 - 3 - 6 = 1
x42 → c42 - U4 - V2
x42 → 6 - 3 - 5 = -2
Não temos um solução ótima, pois possuímos valores
negativos, o valor de x23 é o mais negativo. Então, x23 entra na
base.
Raphael Ramos Problema de Transporte 71 / 99
Circuito de compensação
D1 D2 D3
O1 8 2 0 10
O2 20 - σ σ 20
O3 10 + σ 2 - σ 12
O4 13 13
8 32 15
σ entra com valor 2
Raphael Ramos Problema de Transporte 72 / 99
Nova solução
D1 D2 D3
O1 8 2 0 10
O2 18 2 20
O3 12 12
O4 13 13
8 32 15
Raphael Ramos Problema de Transporte 73 / 99
Critério de otimalidade
Custos: c11 = 6, c12 = 5, c13 = 8, c21 = 13, c22 = 12, c23 = 1, c31 =
7 , c32 = 9, c33 = 5, c41 = 10, c42 = 6, c43 = 4.
Variáveis básicas:
x11 → c11 - U1 - V1 = 0
x12 → c12 - U1 - V2 = 0
x22 → c22 - U2 - V2 = 0
x32 → c32 - U3 - V2 = 0
x23 → c23 - U2 - V3 = 0
x43 → c43 - U4 - V3 = 0
Variáveis não básicas:
x13 → c13 - U1 - V3
x21 → c21 - U2 - V1
x31 → c31 - U3 - V1
x33 → c33 - U3 - V3
x41 → c41 - U4 - V1
x42 → c42 - U4 - V2
Raphael Ramos Problema de Transporte 74 / 99
Coeficientes
Variáveis básicas:
U1 = 0, V1 = 6, U2 = 7, V2 = 5,
U3 = 4, V3 = −6, U4 = 10
Variáveis não básicas:
x13 → 14 x21 → 0 x31 → -3 x33
→ 7 x41 → -6 x42 → -9
A solução não é ótima. Entra a variável x42 que possui o
coeficiente negativo de maior valor absoluto.
Raphael Ramos Problema de Transporte 75 / 99
Circuito de compensação
D1 D2 D3
O1 8 2 10
O2 18 - σ 2 + σ 20
O3 12 12
O4 σ 13 - σ 13
8 32 15
σ entra com valor 13
Raphael Ramos Problema de Transporte 76 / 99
Nova solução
D1 D2 D3
O1 8 2 10
O2 5 15 20
O3 12 12
O4 13 13
8 32 15
Raphael Ramos Problema de Transporte 77 / 99
Critério de otimalidade
Custos: c11 = 6, c12 = 5, c13 = 8, c21 = 13, c22 = 12, c23 = 1, c31 =
7 , c32 = 9, c33 = 5, c41 = 10, c42 = 6, c43 = 4.
Variáveis básicas:
x11 → c11 - U1 - V1 = 0
x12 → c12 - U1 - V2 = 0
x22 → c22 - U2 - V2 = 0
x23 → c23 - U2 - V3 = 0
x32 → c32 - U3 - V2 = 0
x42 → c42 - U4 - V2 = 0
Variáveis não básicas:
x13 → c13 - U1 - V3
x21 → c21 - U2 - V1
x31 → c31 - U3 - V1
x33 → c33 - U3 - V3
x41 → c41 - U4 - V1
x43 → c42 - U4 - V3
Raphael Ramos Problema de Transporte 78 / 99
Coeficientes
Variáveis básicas:
U1 = 0, V1 = 6, U2 = 7, V2 = 5,
U3 = 4, V3 = −6, U4 = 1
Variáveis não básicas:
x13 → 14 x21 → 0 x31 → -3 x33
→ 7 x41 → 3 x43 → -9
A solução não é ótima. Entra a variável x31 que possui o
coeficiente negativo de maior valor absoluto.
Raphael Ramos Problema de Transporte 79 / 99
Circuito de compensação
D1 D2 D3
O1 8 - σ 2 + σ 10
O2 5 15 20
O3 σ 12 - σ 12
O4 13 13
8 32 15
σ entra com valor 8
Raphael Ramos Problema de Transporte 80 / 99
Nova solução
D1 D2 D3
O1 10 10
O2 5 15 20
O3 8 4 12
O4 13 13
8 32 15
σ entra com valor 8
Raphael Ramos Problema de Transporte 81 / 99
Critério de otimalidade
Custos: c11 = 6, c12 = 5, c13 = 8, c21 = 13, c22 = 12, c23 = 1, c31 =
7 , c32 = 9, c33 = 5, c41 = 10, c42 = 6, c43 = 4.
Variáveis básicas:
x12 → c12 - U1 - V2 = 0
x22 → c22 - U2 - V2 = 0
x23 → c23 - U2 - V3 = 0
x31 → c31 - U3 - V1 = 0
x32 → c32 - U3 - V2 = 0
x42 → c42 - U4 - V2 = 0
Variáveis não básicas:
x11 → c11 - U1 - V1
x13 → c13 - U1 - V3
x21 → c21 - U2 - V1
x33 → c33 - U3 - V3
x41 → c41 - U4 - V1
x43 → c42 - U4 - V3
Raphael Ramos Problema de Transporte 82 / 99
Coeficientes
Variáveis básicas:
U1 = 0, V1 = 3, U2 = 7, V2 = 5,
U3 = 4, V3 = −6, U4 = 1
Variáveis não básicas:
x11 → 3 x13 → 14 x21 → 3 x33 →
7 x41 → 6 x43 → 9
A solução é ótima. Pois as variáveis não básicas não possuem
coeficientes negativos.
Raphael Ramos Problema de Transporte 83 /99
Solução final
Transportar:
10 unidades da origem 1 ao destino 2;
5 unidades da origem 2 ao destino 2;
15 unidades da origem 2 ao destino 3;
8 unidades da origem 3 ao destino 1;
4 unidades da origem 3 ao destino 2;
13 unidades da origem 4 ao destino 2;
Custo = 10 x 5 + 5 x 12 + 15 x 6 + 8 x 7 + 4 x 9 + 13 x 6 = 370
Raphael Ramos Problema de Transporte 84 / 99
Solução básica inicial
Método de aproximação de Vogel
Início: Representar o problema de transporte na forma tabular
inicial;
Passos:
1 Para cada linha (e coluna), calcule a penalidade que
corresponde à diferença entre os dois menores custos
unitários de transporte na respectiva linha (e coluna). A
penalidade para uma linha (coluna) é calculada enquanto
houver pelo menos duas células ainda não alocadas e não
bloqueadas na mesma linha (coluna).
2 Escolha a linha ou coluna com maior penalidade. Em caso
de empate, escolha qualquer uma delas, aleatoriamente.
Na linha ou coluna selecionada, escolha a célula com
menor custo.
Raphael Ramos Problema de Transporte 85 / 99
Exemplo 4
L1 L2 L3
F1 9 5 3 50
F2 3 7 1 50
F3 7 10 10 50
70 60 20
Raphael Ramos Problema de Transporte 86 / 99
Exemplo 5
Uma companhia enlata ervilhas nas suas unidades “Fábrica de
conservas1, Fábrica de conservas2, Fábrica de conservas3” e
transporta as latas de ervilha por caminhão para os seus
estoques “armazém1, armazém2, armazém3, armazém4”.
Raphael Ramos Problema de Transporte 87 / 99
Exemplo
A tabela abaixo mostra os custos de transporte, a
disponibilidade nas unidades “Fábricas” e as necessidades nos
estoques.
Custo (R$) transporte por caminhão
Armazém - Destino
1 2 3 4 Disponibilidade
Origem
Fábrica 1 464 513 654 867 75
Fábrica 2 352 416 690 791 125
Fábrica 3 995 682 388 685 100
Demanda 80 65 70 85
Raphael Ramos Problema de Transporte 88 / 99
Exemplo
A representação esquemática abaixo ilustra o problema:
Raphael Ramos Problema de Transporte 89 / 99
Exemplo
A função objetivo, a ser minimizada, é:
z = 464x11 + 513x12 + 654x13 + 867x14
+ 352x21 + 416x22 + 690x23 + 791x24
+ 995x31 + 682x32 + 388x33 + 685x34
Raphael Ramos Problema de Transporte 90 / 99
Exemplo
As restrições são:
x11 +x12 +x13 +x14 = 75
+x21 +x22 +x23 +x24 = 125
+x31 +x32 +x33 +x34 = 100
x11 +x21 +x31 = 80
x12 +x22 +x32 = 65
x13 +x23 +x33 = 70
x14 +x24 +x34 = 85
xij > 0, (i = 1,2,3; j = 1,2,3,4)
Raphael Ramos Problema de Transporte 91 / 99
Sistemas não equilibrados
Os modelos descritos anteriormente podem representar
também sistemas de transporte que não obedecem à condição
de equilíbrio entre oferta e demanda.
Raphael Ramos Problema de Transporte 92 / 99
Sistemas não equilibrados
O enquadramento no modelo se faz com a criação de origens
ou destinos auxiliares para receber a diferença entre oferta e
demanda. Os custos unitários para origens ou destinos
auxiliares é zero. Na solução do modelo, as quantidades que
eventualmente sejam transportadas de origens auxiliares ficam
faltando nos destinos. As quantidades que são tranportadas
para destinos auxiliares, na verdade ficam depositadas nas
origens.
Raphael Ramos Problema de Transporte 93 / 99
Exemplo
Sistemas não equilibrados
Tabela: O modelo representado no quadro esta desequilibrado
D1 D2 D3
O1 10 12 9 20
O2 4 9 8 30
O3 6 12 10 10
25 36 5 6066
Raphael Ramos Problema de Transporte 94 / 99
Exemplo
Sistemas não equilibrados
Criando-se uma origem auxiliar para receber a diferença 66-60
= 6, teremos o sistema equilibrado:
Tabela: O modelo representado no quadro está equilibrado
D1 D2 D3
O1 10 12 9 20
O2 4 9 8 30
O3 6 12 10 10
A 0 0 0 6
25 36 5 6666
Raphael Ramos Problema de Transporte 95 / 99
Exemplo
Sistemas não equilibrados
Um solução possível para o problema é mostrada no quadro,
onde o valor das células representa as quantidades
transportadas de cada origem para cada destino.
Tabela: O modelo representado no quadro está equilibrado
D1 D2 D3
O1 20 20
O2 5 25 30
O3 10 10
A 1 5 6
25 36 5
Raphael Ramos Problema de Transporte 96 / 99
Exemplo
Sistemas não equilibrados
As quantidades xA2 = 1 e xA3 = 5 transportadas a partir da
origem auxiliar A, na verdade, ficam faltando nos destinos, isto
é, o destino D2, recebe apenas 35 unidades. O destino D3 não
recebe nenhuma mercadoria.
Raphael Ramos Problema de Transporte 97 / 99
Exercicio
Fábrica Depósito Produção1 2 3
1 8 5 6 120
2 15 10 12 80
3 3 9 10 80
Capacidade 150 70 60 280
Raphael Ramos Problema de Transporte 98 / 99
Resultado
Fábrica Depósito Produção1 2 3
1 70 50 120
2 70 10 80
3 80 80
Capacidade 150 70 60 280
F.O: 10 * 80 + 50 * 6 + 70 * 10 + 10 * 12 + 80 * 3 = 1920
Raphael Ramos Problema de Transporte 99 / 99