Problemas de Transporte

Prévia do material em texto

Pesquisa Operacional I 
(CEP/CT025) – Aula 06
UNIVERSIDADE FEDERAL DO PIAUÍ
CAMPUS MINISTRO PETRÔNIO PORTELLA – CT
CURSO DE ENGENHARIA DE PRODUÇÃO
PROF. ÁLVARO LÉDO FERREIRA
CONTATO: a lvaro.ferre i ra@ufpi .edu.br 
7. Problemas de transportes e designação
7.1. Problemas de transportes;
7.2. Sistemas não-equilibrados;
7.3. Designação.
7.1. Problemas de transportes
• Visa minimizar o custo total do transporte necessário para 
abastecer n centros consumidores (destinos) a partir de m centros 
fornecedores (origens);
• As quantidades disponíveis, ou oferta, em cada origem são: 
𝑎!, 𝑎", … , 𝑎#;
• As quantidades requeridas, ou demanda, em cada destino são: 
𝑏!, 𝑏", … , 𝑏$; 
• O custo unitário de transporte entre a origem 𝑖 e o destino 𝑗 é 𝑐%&
7.1. Problemas de transportes
• Considerando 𝑥%& a quantidade que deve ser transportada de 
origem 𝑖 ao destino 𝑗, o modelo assume a seguinte forma:
𝑀𝑖𝑛	𝑍 ='
!"#
$
'
%"#
&
𝑐!%𝑥!% 	
𝑠. 𝑎.
	'
%"#
&
𝑥!% = 𝑎! 	 𝑖 = 1, 2, … ,𝑚
	
'
!"#
$
𝑥!% = 𝑏% 	 𝑗 = 1, 2, … , 𝑛
𝑥!% ≥ 0	 𝑖 = 1, 2, … ,𝑚 (𝑗 = 1, 2, … , 𝑛)
7.1. Problemas de transportes
• É importante ressaltar que nas restrições do modelo todos os 
coeficientes das variáveis são iguais a 1;
• Ao se somar as 𝑚 restrições de oferta obtém-se:
'
!"#
$
'
%"#
&
𝑥!% ='
!"#
$
𝑎!
• Ao se somar as 𝑛 restrições de demanda obtém-se:
!
!"#
$
!
%"#
&
𝑥%! =!
!"#
$
𝑏!
7.1. Problemas de transportes
• Igualando:
!
%"#
&
𝑎% =!
!"#
$
𝑏!
• Indicando que o modelo de transporte exige uma igualdade entre 
oferta e demanda;
• O modelo de transporte pode ser resolvido pelo método Simplex já 
que este método resolve qualquer problema de programação linear;
• Entretanto, devido as peculiaridades do modelo, torna-se preferível 
utilizar o algoritmo do transporte;
7.1. Problemas de transportes
• Para aplicação do algoritmo de transporte é necessário representar 
o problema através de um quadro resumindo as ofertas 𝑎% , 
demandas 𝑏& e os custos unitários de transporte 𝑐%& :
Destinos /
Origens 1 2 ... n Oferta
1 𝑐!! 𝑐!" ... 𝑐!# 𝑎!
2 𝑐"! 𝑐"" ... 𝑐"# 𝑎"
... ... ... ... ... ...
m 𝑐$! 𝑐$" ... 𝑐$# 𝑎$
Demanda 𝑏! 𝑏" ... 𝑏#
7.1. Problemas de transportes
• A resolução do modelo de transporte envolve três etapas:
1) Obtenção da solução inicial;
2) Regra de melhoria da solução;
3) Regra de parada.
• Existem diversas técnicas que podem ser utilizadas em cada uma 
das etapas do algoritmo;
• De modo a facilitar o entendimento, considere o exemplo 
apresentado a seguir que será utilizado;
7.1. Problemas de transportes
• Seja um produto que possua três fornecedores (F), com capacidades 
conhecidas e quatro centros de distribuição (CD). Suponha que os 
três fornecedores ofereçam 𝐹! = 300, 𝐹" = 700 e 𝐹' = 500 
unidades de um certo produto e os quatro centros de distribuição 
demandem 𝐷! = 400, 𝐷" = 300, 𝐷' = 400 e 𝐷( = 400 unidades 
do referido produto.
7.1. Problemas de transportes
1
2
3
1
2
3
4
Oferta
F! = 300
F" = 700
F# = 500
Demanda
D! = 400
D" = 300
D# = 400
D$ = 400
Fornecedores CD
7.1. Problemas de transportes
• Quais devem ser as quanXdades despachadas de cada fornecedor 
para cada centro de distribuição com base nos custos unitários de 
transporte apresentados no quadro a seguir:
D! D" D% D& Oferta
F! 6 6 12 1 300
F" 11 8 5 4 700
F% 12 6 6 8 500
Demanda 400 300 400 400 1500
7.2. Sistemas não-equilibrados
• Para aplicação do algoritmo, é necessário que a oferta seja igual a 
demanda, o que nem sempre é verificado;
• Assim, caso a oferta seja maior que a demanda, deve ser criado um 
centro consumidor fictício cuja demanda seja exatamente a 
diferença entre o total da oferta e o total da demanda e com custos 
de transporte de cada origem até esse centro fictício iguais a zero, de 
tal modo que a quantidade transportada até o consumidor fictício 
represente o excesso de oferta;
7.2. Sistemas não-equilibrados
• De modo análogo, caso a oferta seja menor que a demanda, deve 
ser criado uma origem fictícia cuja demanda seja exatamente a 
diferença entre o total da demanda e o total da oferta e com custos 
de transporte dessa origem fictícia até os centros consumidores 
iguais a zero, de tal modo que a quantidade transportada a partir da 
origem fictícia represente o excesso de demanda;
7.3. Designação
• Considere que no problema original de transportes apresentado 
anteriormente, sejam introduzidas as seguintes restrições:
a) Número de origens = número de destinos (i.e. 𝑛 = 𝑚);
b) Capacidade de cada origem = 1 (i.e. 𝐹! = 1 para todo 𝑖);
c) Demanda de cada destino = 1 (i.e. 𝐷" = 1 para todo j).
7.3. Designação
• Dessa forma, se obtém o modelo de alocação ou atribuição:
𝑀𝑖𝑛	𝑍 ='
!"#
&
'
%"#
&
𝑐!%𝑥!% 	
𝑠. 𝑎.
	'
%"#
&
𝑥!% = 1	 𝑖 = 1, 2, … , 𝑛
	
'
!"#
&
𝑥!% = 1	 𝑗 = 1, 2, … , 𝑛
𝑥!% ≥ 0	 𝑖 = 1, 2, … , 𝑛 (𝑗 = 1, 2, … , 𝑛)
7.3. Designação
• Assim, cada origem 𝑖 abastecerá somente um único destino 𝑗, de 
modo que as últimas restrições do modelo de designação sejam 
equivalentes a:
𝑥%& = 31	se	origem	i	for	designada	para	abastecer	o	destino	j;
0	caso	contrário.
7.3. Designação
• O problema consiste em determinar como as designações devem 
ser feitas de modo a minimizar o custo total;
• Por ser um caso especial do problema de transporte, esse modelo 
possui um algoritmo próprio para sua otimização;
• Como as capacidades de cada origem e as demandas de cada 
destino são unitárias, o algoritmo de designação é baseado somente 
na seguinte matriz:
7.3. Designação
Des;nos
1 2 ... N
Origens
1 𝑐!! 𝑐!" ... 𝑐!#
2 𝑐"! 𝑐"" ... 𝑐"#
⋮ ... ... ... ...
n 𝑐#! 𝑐#" ... 𝑐##
7.3. Designação
• Suponha, por exemplo, que 𝑐%& seja o salário do operário 𝑖 para 
executar a tarefa 𝑗;
• Deseja-se então contratar 𝑛 operários para executar 𝑛 tarefas a um 
custo mínimo;
• Deve-se determinar então um elemento de cada linha e cada coluna 
da matriz de custos de modo que a soma dos custos seja o menor 
possível;
7.3. Designação
• O processo iterativo que conduz à solução ótima para o problema 
de designação é baseado na propriedade:
Ø Ao se adicionar (subtrair) uma constante a cada elemento de uma 
linha (coluna) qualquer da matriz de custo de um problema de 
designação, a solução ótima da matriz alterada será também a 
solução ótima da matriz inicial.
7.3. Designação
• Exemplo: Um gerente deve alocar 4 funcionários para 4 tarefas 
diferentes. Cada funcionário recebe um valor que depende da tarefa 
atribuída, conforme indica a seguinte matriz. Deseja-se atribuir os 
operários às tarefas de maneira que o gasto total com salários seja o 
mínimo possível.
7.3. Designação
• Exemplo:
Destinos
I II III IV
Tarefas
A 34 4 21 12
B 17 9 5 12
C 11 25 7 4
D 14 9 12 2
7.3. Designação
• Exemplo: Deve-se determinar o menor valor de cada linha e subtraí-
lo de todos os elementos da linha correspondentes;
Destinos
I II III IV
Tarefas
A 34 4 21 12 (4)
B 17 9 5 12 (5)
C 11 25 7 4 (4)
D 14 9 12 2 (2)
7.3. Designação
• Exemplo: Deve-se determinar o menor valor de cada linha e subtraí-
lo de todos os elementos da linha correspondentes;
Destinos
I II III IV
Tarefas
A 30 0 17 8
B 12 4 0 7
C 7 21 3 0
D 12 7 10 0
7.3. Designação
• Exemplo: Em seguida deve-se determinar o menor valor de cada 
coluna e subtrair de todos os elementos da coluna correspondente;
Destinos
I II III IV
Tarefas
A 30 0 17 8
B 12 4 0 7
C 7 21 3 0
D 12 7 10 0
(7) (0) (0) (0)
7.3. Designação
• Exemplo: O critério de parada do algoritmo é quando houver pelo 
menos um elemento igual a 0 em cada linha e em cada coluna;
Destinos
I II III IV
Tarefas
A 23 0 17 8
B 5 4 0 7
C 0 21 3 0
D 5 7 10 0
7.3. Designação
• Os valores iguais a 0 indicam a solução ótima para o problema de 
designação;
• Assim, a solução ótima para o exemplo é:
Tarefa → Homem
A → II
B → III
C → I
D → IV
7.3. Designação
• Para essa solução, o valor total a ser gasto é determinado pela 
matriz de eficiênciainicial, ao somar os valores que cada homem 
gasta em sua tarefa:
𝑍∗ = 𝐶2;44 + 𝐶5;444 + 𝐶6;4 + 𝐶7;48
	
𝑍∗ = 4 + 5 + 11 + 2 = 22	𝑢.𝑚.
Pesquisa Operacional I 
(CEP/CT025) – Aula 06
UNIVERSIDADE FEDERAL DO PIAUÍ
CAMPUS MINISTRO PETRÔNIO PORTELLA – CT
CURSO DE ENGENHARIA DE PRODUÇÃO
PROF. ÁLVARO LÉDO FERREIRA
CONTATO: a lvaro.ferre i ra@ufpi .edu.br