Buscar

Capítulo_2_-_Problema_do_Trans

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 5 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Capítulo 2 Problema do Transporte 
Pesquisa Operacional II Jhoab Negreiros 
1
 
 
 
 
 
 
 
 
 
 
 
 
 
 
CAPÍTULO 2 
Problema do Transporte 
 
 
 
 
 
 
 
1 Problema do Transporte 
 
Um problema bastante comum que muitas vezes pode ser modelado como um problema de 
programação linear é o problema de transporte. Este problema envolve o transporte de alguma 
carga de diversas fontes a diversos pontos de destino. Dados o custo da distribuição entre cada 
fonte e destino, as produções das fontes e as capacidades dos destinos pretendem-se minimizar o 
custo total do transporte. 
 
2 O Problema do Transporte como um PPL 
 
Nos dois exemplos a seguir é mostrado como modelar um problema do transporte utilizando a 
mesma estrutura que é aplicada nos problemas clássicos de programação linear. 
 
Exemplo 1. Uma firma comercial tem 40 unidades de mercadoria no depósito D1 e 50 unidades no 
depósito D2. Deve enviar 30 unidades ao cliente A e 40 ao cliente B. Os gastos de transporte por 
unidade de mercadoria estão indicados no esquema abaixo. De que maneira deve enviar essas 
mercadorias para que o gasto com transporte seja mínimo? 
Capítulo 2 Problema do Transporte 
Pesquisa Operacional II Jhoab Negreiros 
2
 
 
Exemplo 2. Uma empresa produz televisão em 3 fábricas: São Paulo, João Pessoa e Manaus. Os 
pontos principais de revenda, com as respectivas encomendas mensais são: 
 
Rio de Janeiro 6.000 unidades 
Salvador 5.000 unidades 
Aracajú 2.000 unidades 
Maceió 1.000 unidades 
Recife 3.000 unidades 
 
A produção máxima mensal em cada fábrica é: 
 
São Paulo 10.000 unidades 
João Pessoa 5.000 unidades 
Manaus 6.000 unidades 
 
O custo de transportes das fábricas até as revendas é dado pelo quadro abaixo: 
R$ por 1.000 unidades de TV. 
 
Para 
De 
Rio de Janeiro 
(1) 
Salvador 
(2) 
Aracaju 
(3) 
Maceió 
(4) 
Recife 
(5) 
(1) São Paulo 1.000 2.000 3.000 3.500 4.000 
(2) João Pessoa 4.000 2.000 1.500 1.200 1.000 
(3) Manaus 6.000 4.000 3.500 3.000 2.000 
 
Determinar o número de unidades produzidas em cada fábrica e entregues a cada revenda, a fim de 
minimizar o custo de transporte. 
 
 
Capítulo 2 Problema do Transporte 
Pesquisa Operacional II Jhoab Negreiros 
3
3 Modelos de Transporte 
 
O modelo de transporte pode ser representado por uma matriz em que as linhas representam 
os centros produtores e as colunas, os centros distribuidores, ou seja, 
 
 Centro 
consumidor 1 
Centro 
consumidor 2 
⋯ 
 
Centro 
consumidor n 
Centro produtor 1 ��� ��� ⋯ ��� 
Centro produtor 2 ��� ��� ⋯ ��� 
⋮ ⋮ ⋮ ⋱ ⋮ 
Centro produtor m ��� ��� ⋯ ��� 
 
em que �	
 define a quantidade produzida na origem � e é consumida no destino �. 
 A definição do modelo de transporte é: 
 
��	� =���	
�	
�
��
�
	��
 
Sujeita as restrições: 
 
• Restrições de origens; 
 
��	
 = �	; 		� = 1,2, … ,�
�
��
 
 
• Restrições de destinos; 
 
��	
 = �
; 		� = 1,2, … , �
�
	��
 
 
 
• Restrições de não negatividade. 
 
�	
 ≥ 0; � = 1,2, … ,�; � = 1,2, … , � 
 
em que: 
�	 = destinos 
�	 =	origens 
�	 = produção da origem � 
�
 = demanda do destino � 
�	
 = quantidade enviadas de � para � 
�	
 = custo de transporte de � para � 
Capítulo 2 Problema do Transporte 
Pesquisa Operacional II Jhoab Negreiros 
4
 Para que o modelo do transporte tenha solução viável, é necessário que o total de oferta 
seja igual ao total da demanda, ou seja, 
 
��	 =��
�
	��
�
��
 
 
 No caso de oferta maior que demanda, introduz-se uma variável representando uma 
demanda fictícia, indicando a necessidade de um novo centro consumidor e o custo de transporte 
de todas as origens para esse destino fictício é nulo. A demanda desse destino é dada pela 
diferença entre o total ofertado e total demandado. 
 No caso de demanda maior que oferta, introduz-se uma oferta fictícia, indicando a 
necessidade de uma nova fábrica e o custo de transporte de todos os destinos para essa origem 
fictícia é nulo. A oferta dessa origem é dada pela diferença entre o total ofertado e o total 
demandado. 
 Agora os dois exemplos iniciais será resolvidos novamente via Solver, mas dessa vez 
utilizando a estrutura de matrizes. 
 
Exemplo 3. Resolva o Exemplo 1 utilizando a estrutura matricial. 
 
Exemplo 4. Resolva o Exemplo 2 utilizando a estrutura matricial. 
 
 
4 Atividades 
 
Exercício 1. No quadro de transporte a seguir, a terceira linha mostra às necessidades nos destinos 
e a quarta coluna as disponibilidades nas origens. Os outros dados representam custos unitários de 
transporte das origens para os respectivos destinos. 
 
15 20 15 150 
12 20 15 300 
100 150 200 
 
Determinar o plano de transporte que minimiza o custo total das transferências. 
 
Exercício 2. Resolva o exercício 1 novamente considerando o quadro abaixo. 
 
15 20 15 150 
12 20 15 250 
170 150 230 
 
 
 
 
Capítulo 2 Problema do Transporte 
Pesquisa Operacional II Jhoab Negreiros 
5
Exercício 3. Uma Companhia despacha caminhões de grãos provenientes de três silos para quatro 
moinhos. As quantidades fornecidas e as demandas aliadas aos custos unitários de transporte por 
caminhões nas diferentes rotas estão resumidas na tabela a seguir. 
 
 Moinho 
 
 
1 2 3 4 Fornecimento 
 1 10 8 20 11 15 
Silo 2 12 7 9 20 25 
 3 13 14 16 18 10 
 Demanda 5 15 15 15 
 
Exercício 4. Resolva novamente o exercício 3 supondo que as seguintes situações: 
 
(a) Não é possível enviar caminhões do Silo 2 para o Moinho 2 
(b) É possível enviar no máximo 5 caminhões do Silo 2 para o Moinho 2

Outros materiais