A09 - Transporte

Prévia do material em texto

OTIMIZAÇÃO I
Problemas de Transporte
Maurílio Alves Martins da Costa
maurilioamc@gmail.com
2021/22
O Problema de Transporte
O problema de transporte aparece quando há a necessidade de distribuição
de bens e serviços de várias fontes de suprimentos para várias localizações
de demanda. Em geral são quantidades fixas ou delimitadas.
Neste caso há um problema de decisão envolvendo rotas e custos de
transportes entre as fontes e os destinos. É preciso determinar quanto se
deve enviar de cada fonte a cada destino de modo a satisfazer as
demandas e minimizar o custo total de transporte.
O problema do transporte é um caso especial de aplicação PPL.
O Problema de Transporte
Um problema prático de operação no cotidiano das empresas é a análise de
decisões que se preocupa exatamente com a avaliação de alternativas para
"escolher a melhor solução dentre as finitas maneiras de realizá-la", ou
seja, enumerar as soluções possíveis e escolher a melhor.
Fonte
Destino
O caminho entre a fonte e o destino é denominada de rota.
O Problema de Transporte
Matematicamente, o problema de transporte pode ser representado
graficamente por meio de uma rede, onde de um lado indicamos os pontos
de origem dos produtos ou mercadorias que devem ser expedidos, e do
outro lado indicamos os destinos desses produtos ou mercadorias. Os
pontos de origem e destino são ligados por meio de arcos orientados, cada
qual contendo duas informações: o custo de transporte por unidade de
produto e a quantidade de produto a ser transportada.
O Problema de Transporte
No Problema de Transporte, temos como dados conhecidos o custo de
transporte de cada item (Cij), as quantidades de itens disponíveis em cada
origem (ai) e as demandas de cada destino (bj).
Como variáveis de decisão, temos as quantidades de itens a serem
transportados de cada uma das origens i para os destinos j (Xij). Sendo
assim, a função objetivo do modelo matemático deste tipo de problema pode
ser, genericamente, assim escrita:
onde,
m é o número de origens (fábricas);
n é o número de destinos (depósitos
ou centros de consumo);
Cij é o custo por unidade transportada
da origem i para o destino j;
Xij é a quantidade de itens transportados
da origem i para o destino j.
O Problema de Transporte
Um exemplo de Problema de Transporte modelado como um PPL. 
Existem três fontes de suprimento de um dado produto, as quais serão
indicadas por F1, F2 e F3, com as seguintes capacidades mensais de
produção:
F1: 10000 unidades
F2: 15000 unidades
F3: 5000 unidades
Perfazendo um total de 30.000 unidades disponíveis por mês.
O Problema de Transporte
Essas três fontes devem suprir as necessidades de quatro armazéns
(destinos), indicados por D1, D2, D3 e D4, com as seguintes demandas do
produto por mês:
D1: 8000 unidades
D2: 4000 unidades
D3: 7000 unidades
D4: 11000 unidades
Chegando, portanto, a um total de 30.000 unidades de produto demandados
por mês.
O Problema de Transporte
A situação descrita pode ser representada por meio de uma rede, como
mostrado na figura abaixo.
F1
F2
F3
D1
D2
D3
D4
10.000
15.000
5.000
8.000
4.000
7.000
11.000
O Problema de Transporte
Nesta, os círculos representam as fontes de suprimento e os destinos das
demandas. Ao lado dos círculos, anotou-se a capacidade de produção de
cada fonte de suprimento e o valor da demanda de cada um dos destinos. As
linhas que unem os círculos representam as diversas rotas de transporte.
O Problema de Transporte
Suponha que os custos de transporte em unidades monetárias por unidade
nas várias rotas variem segundo a tabela abaixo.
D1 D2 D3 D4
F1 13 8 9 12
F2 12 9 10 14
F3 8 8 9 6
Cada rota possui custos diferentes. Assim, é preciso determinar quanto deve
ser enviado da fonte para o destino de modo a satisfazer as demandas
desejadas e minimizar o custo da rota.
O Problema de Transporte
Denominando de xij ao número de unidades do produto despachado da
fonte i (i={1,2,3} para o destino j (j={1,2,3,4}, pode-se fazer uma matriz
de transporte, que é a síntese entre a quantidade produzida, a quantidade
armazenável e os custos de cada unidade do produto para cada rota.
D1 D2 D3 D4 Fone
F1 13 8 9 12 10.000
F2 12 9 10 14 15.000
F3 8 8 9 6 5.000
Demanda 8.000 4.000 7.000 11.000 30.000D1 D2 D3 D4
F1 13 8 9 12
F2 12 9 10 14
F3 8 8 9 6
O Problema de Transporte
As variáveis xij são as variáveis de decisão, ou seja, as quantidades que
devem ser transportadas de cada fonte a cada destino. São ao todo 12
variáveis de decisão. A última coluna à direita da matriz de transporte
fornece a capacidade de suprimento de cada fonte, e a linha mais abaixo
fornece a demanda de cada um dos destinos.
D1 D2 D3 D4 Fonte
F1 (13)
X11
(8)
X12
(9)
X13
(12)
X14
10.000
F2 (12)
X21
(9)
X22
(10)
X23
(14)
X24
15.000
F3 (8)
X31
(8)
X32
(9)
X33
(6)
X34
5.000
Demanda 8.000 4.000 7.000 11.000 30.000
O Problema de Transporte
Restrições relativas às fontes de produção:
x11 + x22 + x13 + x14 ≤ 10.000
x21 + x22 + x23 + x24 ≤ 15.000
x31 + x32 + x33 + x34 ≤ 5.000
Restrições relativas às demandas dos destinos:
x11 + x12 + x13 = 8.000
x12 + x22 + x31 = 4.000
x13 + x32 + x33 = 7.000
x14 + x24 + x34 = 11.000 xij >= 0
Desta forma, tem-se um problema com 12 variáveis de decisão e sete
restrições. Este exemplo ilustra a modelagem matemática de um problema
do transporte. Para resolvê-lo aplica-se o Método Simplex.
O Problema de Transporte
Tem-se então a seguinte solução para o problema proposto:
FO: Z = 300.000
D1 D2 D3 D4 Fonte
F1 13
x11
0
8
x12
0
9
x13
4.000
12
x14
6.000
10.000
F2 12
x21
8.000
9
x22
4.000
10
x23
3.000
14
x24
0
15.000
F3 8
x31
0
8
x32
0
9
x33
0
6
x34
5.000
5.000
Demanda 8.000 4.000 7.000 11.000 30.000
Restrições do Problema de Transporte
As restrições do Problema de Transporte implicam em que as origens
(fábricas) não podem produzir mais do que suas capacidades e os destinos
(depósitos ou centros de consumo) não podem receber quantidades de itens
superiores às suas demandas.
Na modelagem das restrições, podemos nos deparar com três situações
distintas:
1. As quantidades ofertadas pelas origens são iguais às quantidades
demandadas pelos destinos;
2. As quantidades ofertadas pelas origens são maiores que as
quantidades demandadas pelos destinos;
3. As quantidades ofertadas pelas origens são menores que as
quantidades demandadas pelos destinos.
O Problema de Transporte
Situação 1: há um equilíbrio entre oferta e demanda, assim, as restrições
podem ser escritas diretamente por meio de equações (igualdades).
Situação 2: a oferta é maior que a demanda, logo, deve-se introduzir no
modelo um destino fantasma (dummy), com o custo de transporte igual
a zero e a demanda igual à diferença entre o total ofertado e o total
demandado. Assim, o modelo ficará artificialmente equilibrado, a oferta será
igual à demanda, e pode-se escrever as restrições como igualdades.
Situação 3: a oferta é menor que a demanda, devemos introduzir uma
origem fantasma (dummy) que terá como custo de transporte igual a
zero e capacidade de produção igual à diferença entre o total ofertado pelas
origens e o total demandado pelos destinos.
E assim também podemos escrever as restrições por meio de equações, já
que a oferta e a demanda foram artificialmente igualadas.
Aplicação
A empresa TCOMP, fabricante de computadores, possui duas fábricas
localizadas em São Paulo e Curitiba. Os computadores produzidos por essas
fábricas devem ser enviados para os centros de consumo localizados em
Natal, Recife e Salvador. Sabendo-se que as quantidades ofertadas pelas
fábricas e as quantidades demandadas pelos centros de consumo, assim
como os custos de transporte por unidade de computador, estão
representados na tabela a seguir, determine as quantidades que devem ser
enviadas por fábrica para cada centro de consumo, de maneira a minimizar
os custos de transporte.
Aplicação
Observando o cenário, podemos perceber que o total demandado pelos
centros consumidores é de 3.300 unidades de computadores.Por outro
lado, a capacidade produtiva das fábricas é de 2.800 computadores. Dessa
forma, temos uma quantidade demandada superior à quantidade ofertada,
sendo assim, devemos introduzir no modelo uma origem fantasma (dummy)
com capacidade produtiva igual à diferença entre o total demandado e o
total ofertado, que neste caso é de 500 unidades (3.300 - 2.800). Caso a
situação fosse inversa, ou seja, se a oferta fosse maior que a demanda,
deveríamos então introduzir um destino artificial (dummy) ao invés de uma
origem artificial.
Aplicação
A representação gráfica do problema da empresa TCOMP é apresentada na
figura a seguir:
Aplicação
Analisando o cenário, podemos destacar os seguintes dados:
Variáveis de decisão:
X11 - Nº de computadores a enviar de São Paulo para Natal;
X12 - Nº de computadores a enviar de São Paulo para Recife;
X13 - Nº de computadores a enviar de São Paulo para Salvador;
X21 - Nº de computadores a enviar de Curitiba para Natal;
X22 - Nº de computadores a enviar de Curitiba para Recife;
X23 - Nº de computadores a enviar de Curitiba para Salvador;•
X31 - Nº de computadores a enviar de dummy para Natal;
X32 - Nº de computadores a enviar de dummy para Recife;
X33 - Nº de computadores a enviar de dummy para Salvador.
Aplicação
Analisando o cenário, podemos destacar os seguintes dados:
Parâmetros:
C11=45 - Custo do transporte por unidade entre São Paulo e Natal;
C12=17 - Custo do transporte por unidade entre São Paulo e Recife;
C13=21 - Custo do transporte por unidade entre São Paulo e Salvador;
C21=14 - Custo do transporte por unidade entre Curitiba e Natal;
C22=18 - Custo do transporte por unidade entre Curitiba e Recife;
C23=19 - Custo do transporte por unidade entre Curitiba e Salvador;
C31=0 - Custo do transporte por unidade entre dummy e Natal;
C32=0 - Custo do transporte por unidade entre dummy e Recife;
C33=0 - Custo do transporte por unidade entre dummy e Salvador.
Aplicação
Analisando o cenário, podemos destacar os seguintes dados:
Restrições:
a1=1500 - Capacidade produtiva (oferta) da fábrica de São Paulo;
a2=1300 - Capacidade produtiva (oferta) da fábrica de Curitiba;
a3=500 - Capacidade produtiva (oferta) de dummy;
b1=1200 - Demanda do centro consumidor de Natal;
b2=1400 - Demanda do centro consumidor de Recife;
b3=700 - Demanda do centro consumidor de Salvador.
Aplicação
Analisando o cenário, podemos destacar os seguintes dados:
Modelo Matemático:
Minimizar Z=45X11 + 17X12 + 21X13 + 14X21 + 18X22 + 19X23
Sujeito a:
X11 + X12 + X13 = 1500 (restrição de oferta - São Paulo)
X21 + X22 + X23 = 1300 (restrição de oferta - Curitiba)
X31 + X32 + X33 = 500 (restrição de oferta - dummy)
X11 + X21 + X31 = 1200 (restrição de demanda - Natal)
X12 + X22 + X32 = 1400 (restrição de demanda - Recife)
X13 + X23 + X33 = 700 (restrição de demanda - Salvador)
Xij ≥ 0 , para i=1,2,3 e j=1,2,3 (não negatividade)
Exercício 1
A Docelar é fábrica de fogões domésticos, com escritórios centrais em São
Paulo e fábricas em Londrina , Salvador e São Paulo. Atualmente, um dos
modelos mais conceituados da Docelar é o Brasileirinho, um fogão de seis
bocas. Apesar de contar com uma rede de revendedores, a Docelar
pretende agora trabalhar com três armazéns próprios, localizados em
Bauru, Porto Alegre e Campo Grande. Londrina é capaz de produzir 5.000
unidades mensais do Brasileirinho, enquanto a fábrica de São Paulo
consegue produzir 30.000 mensais . Já Salvador tem uma capacidade
intermediária de produção de 10.000 unidades por mês. Por outro lado, os
armazéns que devem ser reabastecidos têm as seguintes demandas:
• Bauru: 15.000 unidades por mês. 
• Porto Alegre: 20.000 unidades por mês. 
• Campo Grande: 10.000 unidades por mês. 
Exercício 1
Os custos unitários de transporte, de cada fábrica a cada um dos armazéns,
são mostrados na tabela a seguir:
Pede-se: determinar as quantidades que devem ser despachadas de cada
fábrica para cada armazém, de forma a minimizar o custo total de
transporte. Calcular também quanto vale o custo mínimo de transporte.
Exercício 2
Pede-se: determinar as quantidades que devem ser despachadas de cada
fábrica para cada armazém, de forma a minimizar o custo total de
transporte para cada situação:
Suponha que os custos de transporte em unidades monetárias por unidade
nas várias rotas variem segundo a tabela abaixo.
D1 D2 D3 D4
F1 13 8 9 12
F2 12 9 10 14
F3 8 8 9 6
Exercício 2
a) A demanda total dos destinos é menor que a oferta total das fontes.
F1
F2
F3
D1
D2
D3
D4
12.000
15.000
9.000
8.000
4.000
7.000
11.000
Exercício 2
b) A demanda total dos destinos é maior que a oferta total das fontes.
F1
F2
F3
D1
D2
D3
D4
10.000
15.000
5.000
8.000
4.000
11.000
13.000