Aula 9

Prévia do material em texto

PESQUISA OPERACIONAL
AULA 9 – O PROBLEMA DE TRANSPORTE
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
Conteúdo Programático
1. Problemas de Rede
2. Problema de Transporte
3. Modelo de Transporte
4. Formulação do Modelo de 
Transporte
5. Observações sobre o Modelo
6. Casos
7. Exemplos
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
Definição
Rede é um conjunto de vértices ou nós ligados entre si 
por um conjunto de arcos.
PROBLEMAS DE REDE
Nós Arcos
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
PROBLEMAS DE REDE
Tipos de Problemas de Redes
➢Problema de transporte e rede de distribuição
➢Problema do menor caminho
➢Problema de fluxo máximo
Exemplos:
distribuição logística, energia, comunicações, 
dentre outros.
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
PROBLEMAS DE REDE
PROBLEMA
Nós Arcos
Modelo de Rede
modelos especiais de 
Problemas de 
Programação Linear
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
O Problema de Transporte consiste em determinar, dentre 
as diversas maneiras de distribuição de um produto, a que 
resulta no menor custo de transporte entre as várias 
origens e os vários destinos.
PROBLEMA DE TRANSPORTE
origem destino
Rota de transporte
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
PROBLEMA DE TRANSPORTE
Notação
➢Origem i
➢Destino j
➢Custo unitário de transporte da origem i para o 
destino j cij
➢Quantidade a ser transportada da origem i para o 
destino j Xij
➢Rota de transporte da origem i para o destino j cijxij
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
EXEMPLO
Origens - Ofertas Destinos - Demandas
Fabr 1
Fabr 2
Fabr 3
Destino 1
Destino 2
Destino 3
50
40
60
40
100
10
Total 150Total 150
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
QUADRO
Destino 1 Destino 2 Destino 3 Oferta
Fabr 1 10 15 20 40
Fabr 2 12 25 18 100
Fabr 3 16 14 24 10
Demanda 50 40 60
i
j
150
150
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
MODELO DO TRANSPORTE
Função-objetivo
Conjunto de restrições
Condição de não-negatividade
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
MODELO DO TRANSPORTE
→
ij
x
Variável de decisão: 
quantidade de produtos 
transportados da origem i 
para o destino j
Objetivo: minimizar o custo do transporte
Função -objetivo
Min C = c11x11 + c12x12 + c13x13 + c21x21 + c22x22 + c23x23 +
+ c31x31 + c32x32 + c34x33
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
FUNÇÃO - OBJETIVO
Min C = 10x11 + 15x12 + 20x13 + 12x21 + 25x22 + 18x23 +
+ 16x31 + 14x32 + 24x33
Quantidade a ser transportada 
da fábrica 1 para o destino 1
Custo unitário do transporte 
da fábrica 1 para o destino 1 
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
RESTRIÇÕES
Restrições com relação as ofertas:
D1 D2 D3 O
Fabr 1 10 15 20 40
Fabr 2 12 25 18 100
Fabr 3 16 14 24 10
D 50 40 60
x11 + x12 + x13 = 40
x21 + x22 + x23 =100
x31 + x32 + x33 =10
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
Restrições com relação as demandas:
D1 D2 D3 O
Fabr 1 10 15 20 40
Fabr 2 12 25 18 100
Fabr 3 16 14 24 10
D 50 40 60
x13 + x23 + x33 = 60
x12 + x22 + x32 = 40
x11 + x21 + x31 = 50
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
MODELO DO TRANSPORTE
Min C = 10x11 + 15x12 + 20x13 + 12x21 + 25x22 + 18x23 +
+ 16x31 + 14x32 + 24x33
Sujeito a:
x11 + x12 + x13 = 40
x21 + x22 + x23 =100
x31 + x32 + x33 =10
x11 + x21 + x31 = 50
x12 + x22 + x32 = 40
x13 + x23 + x33 = 60
Xij ≥ 0 para i = 1, 2, 3 e j = 1, 2, 3
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
FORMULAÇÃO DO MODELO DE TRANSPORTE 
( )
njemix
njdx
miox
asujeito
xcxcxcxczMinimizar
ij
j
m
i
ij
i
n
j
ij
m
i
n
j
m
i
ininiiiiijij
,,1,,10
,,1
,,1
:
1
1
1 1 1
2211




==
==
==
+++==


 
=
=
= = =
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
OBSERVAÇÕES SOBRE O MODELO DE TRANSPORTE 
➢A letra m indica o número de origens
➢A letra n indica o número de destinos (centros 
consumidores)
Restrições
➢As origens não podem produzir mais do que as suas
capacidades instaladas.
➢Os centros consumidores não desejam receber
volumes acima de suas demandas.
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
➢O problema de transporte deve obedecer à condição 
de equilíbrio entre a oferta e a demanda.
➢montante ofertado deve ser igual ao demandado.
somatório das 
capacidades das fábricas
somatório das demandas dos 
centros consumidores
=

==
=
n
i
j
m
i
i
do
11
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
➢Introduzimos um destino ( demanda ) fantasma – que 
tenha custos de transporte unitário de todas as origens 
para este destino iguais a zero. 
➢Demanda deste centro consumidor = total ofertado –
total demandado
CASO 1 - OFERTA > DEMANDA
10 15 20 100
12 25 18 80
16 14 24 30
100 50 50
10 15 20 0 100
12 25 18 0 80
16 14 24 0 30
100 50 50 10
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
10 15 20 100
12 25 18 80
16 14 24 20
100 50 60
CASO 2 - DEMANDA > OFERTA
➢Introduzimos uma fonte de oferta fantasma que 
tenha custos de transporte unitário de todos os 
destinos iguais a zero. 
➢Capacidade da fonte = total demandado – total 
ofertado
10 15 20 100
12 25 18 80
16 14 24 20
0 0 0 10
100 50 60
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
Depois de inserida uma demanda ou uma oferta 
fantasma, garantimos que as restrições do problema 
serão de igualdade. 
➢ O total fabricado será virtualmente igual a demanda 
dos centros consumidores e vice-versa.
CONCLUSÃO
Capacidade > Demanda Demanda > Capacidade
Ação: busca de novos 
centros consumidores
Ação: criação de nova 
origem
Interpretação: capacidade 
ociosa das origens
Interpretação: demanda 
não atendida.
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
CASO 3 - OFERTA > DEMANDA
➢Nem todas as origens produzirão em plena capacidade.
Os centros consumidores irão receber as quantidades que 
desejam.
i
n
j
ij
ox 
=1
( )mi ,,1=
j
m
i
ij dx =
=1
( )nj ,,1=
11131211
oxxxx
n
++++ 


22232221
oxxxx
n
++++
mmnmmm
oxxxx ++++ 
321
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
CASO 4 - DEMANDA > OFERTA
➢Nem todos os centros consumidores receberão toda a 
quantidade que desejam.
As origens irão produzir tudo o que puderem.
i
n
j
ij
ox =
=1
( )mi ,,1=
j
m
i
ij
dx 
=1
( )nj ,,1=
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
EXEMPLO 1
Uma companhia tem três instalações industriais que 
podem produzir, cada uma delas, três diferentes 
produtos P1, P2 e P3. Os custos em cada instalação 
variam de acordo com a tabela abaixo. Determine o 
modelo ótimo de transporte.
P1 P2 P3 Capacidade
Instalação 1 8 4 10 800
Instalação 2 9 6 10 1000
Instalação 3 12 10 11 1200
Demanda 1000 900 800
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
P1 P2 P3 Capacidad
e
Instalação 1 8 4 10 800
Instalação 2 9 6 10 1000
Instalação 3 12 10 11 1200
Demanda 1000 900 800
P1 P2 P3 P4 Capacidade
Instalação 1 8 4 10 0 800
Instalação 2 9 6 10 0 1000
Instalação 3 1210 11 0 1200
Demanda 1000 900 800 300
3000
2700
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
MODELO DO TRANSPORTE
4,,13,,10
300
800
900
1000
1200
1000
800
:
11101210691048
342414
332313
322212
312111
34333231
24232221
14131211
333231232221131211
 ==
=++
=++
=++
=++
=+++
=+++
=+++
++++++++=
jeix
xxx
xxx
xxx
xxx
xxxx
xxxx
xxxx
asujeito
xxxxxxxxxzMin
ij
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
Três fábricas abastecem três pontos de venda. O 
quadro abaixo mostra os custos de distribuição, a 
capacidade dos armazéns e as necessidades nos pontos 
de venda. Determine o modelo de transporte.
EXEMPLO 2
P1 P2 P3 O
F1 10 15 20 100
F2 12 25 18 80
F3 16 14 24 20
D 100 50 60
P1 P2 P3 O
F1 10 15 20 100
F2 12 25 18 80
F3 16 14 24 20
F4 0 0 0 10
D 100 50 60
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
MODELO DO TRANSPORTE
3,,14,,10
60
50
100
10
20
80
100
:
241416182512201510
43332313
42322212
41312111
434241
333231
232221
131211
333231232221131211
 ==
=+++
=+++
=+++
=++
=++
=++
=++
++++++++=
jeix
xxxx
xxxx
xxxx
xxx
xxx
xxx
xxx
asujeito
xxxxxxxxxzMin
ij
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL
RESUMINDO
O PROBLEMA DE TRANSPORTE – AULA 9
PESQUISA OPERACIONAL