Aula 6 - Transporte

Prévia do material em texto

Pesquisa 
Operacional
Rafael Pinheiro Amantéa, D.Sc.
rafael.amantea@prof.una.br
Aula – O problema de Transporte
Breve introdução
• O problema de transporte é um tipo de problema 
particular e importante ainda relacionado com a 
programação linear.
• Recebeu esta denominação em virtude de várias de 
suas aplicações envolverem como transportar 
mercadorias de maneira otimizada.
Exemplo - protótipo
• Um dos principais produtos da P & T Company são
ervilhas enlatadas. As ervilhas preparadas em três
fábricas de enlatados ( próximas a Bellingham,
Washington; Eugene e Oregon; e Albert Lea, Minessota)
e depois transportadas por caminhão para quatro
depósitos de distribuição no oeste dos estados unidos (
Sacramento, Califórnia; Salt Lake City, Utah; Rapid City,
Dakota do Sul; e Albuquerque, Novo México), conforme
mostrado na figura a seguir.
• Pelo fato de os custos de transporte serem uma despesa
importante, a gerência da empresa inicia um estudo para
reduzi-los tanto quanto possível. Para a próxima temporada
fez-se uma estimativa do volume proveniente de cada fábrica
de enlatados e destinou-se a cada depósito certa quantidade
do suprimento total de ervilhas. Essas informações (em
unidades de carretas ) , junto ao custo de transporte por
carreta para cada combinação fábrica depósito são fornecidas
na tabela a seguir. Portanto há uma carga total a ser
arremetida de 300 carretas. O problema agora é determinar
qual o plano de destinação dessas remessas às diversas
combinações fábrica – depósito, minimizaria o custo total de
remessa desta mercadoria.
Fábrica
Depósito
Número de carretas despachadas 
para este depósito
Saída de carretas
Formulação do modelo
• Para formular o modelo, façamos que Z represente o
custo total de transporte e que xij (i = 1, 2, 3; j = 1, 2, 3,
4) seja o número de carretas a ser despachado da
fábrica i para o depósito j. Portanto, o objetivo é escolher
os valores dessas 12 variáveis de decisão (os xij ) de
modo a
���������		
= 464
�� + 513
�� + 654
�� + 867
��
+ 352
�� + 416
�� + 690
�� + 791
��
+ 995
�� + 682
�� + 388
�� + 685
��
• Sujeito às restrições:
�� + 
�� + 
�� + 
�� = 75
�� + 
�� + 
�� + 
�� = 125
�� + 
�� + 
�� + 
�� = 100
�� + 
�� + 
�� = 80
�� + 
�� + 
�� = 65
�� + 
�� + 
�� = 70
�� + 
�� + 
�� = 85 
�� � 0 � = 1,2,3; = 1,2,3,4
Procure identificar a função 
objetivo e suas restrições na 
tabela abaixo !!!
O modelo do problema de 
transporte (geral)
• Para descrever o modelo genérico para o problema de
transporte, precisamos usar termos que são
consideravelmente menos específicos que aqueles para os
componentes do exemplo protótipo.
• Em particular o modelo genérico se refere a distribuir
qualquer comodity de qualquer grupo de centros de
fornecimento, chamado de origens, a qualquer grupos de
centros de recepção chamados destinos, de modo a minimizar
o custo total de distribuição.
• Cada origem possui determinada oferta de unidades a serem
distribuídas aos destinos, e cada destino tem certa demanda
pelas unidades a serem recebidas das origens.
Suposições sobre ofertas e 
demandas
• Hipótese das exigências: cada origem tem uma oferta 
fixa de unidades em que toda essa oferta tem que ser 
distribuída aos destinos. (Façamos que si represente o 
número de unidades sendo distribuídos pela origem i, 
para i = 1, 2, ..., m). De forma similar cada destino tem 
uma demanda fixa por unidades, nas quais toda essa 
demanda deve ser recebida das origens. (Façamos que 
dj represente o número de unidades recebidas pelo 
destino j, para j = 1, 2, ..., n). 
• Propriedade das soluções viáveis: um problema de 
transporte terá solução viável se e somente se:
!"� =!#�
$
�%�
&
�%�
• Hipótese do custo: o custo de distribuição de unidades 
de qualquer origem em particular para qualquer destino 
em particular é diretamente proporcional ao número de 
unidades distribuídas. Portanto, esse custo é 
simplesmente o custo unitário de distribuição vezes o 
número de unidades distribuídas.
• Modelo: qualquer problema (envolva ele transporte ou 
não) se ajusta a um problema de transporte caso possa 
ser descrito completamente em termos de uma tabela de 
parâmetros e satisfaça tanto a hipótese das exigências 
quanto a hipótese de custo. O Objetivo é minimizar o 
custo total de distribuição.
O modelo matemático genérico
���������							 =!!'��
��
$
�%�
&
�%�
Sujeito a
!
�� = "� 																															(���	� = 1,2,… ,�
$
�%�
!
�� = #� 																															(���	 = 1,2,… , �
&
�%�
�� � 0, 																															(���	*+#+	�	,