TEORIA TRANSPORTE 20 DE MAIO TURMA 3004

Prévia do material em texto

Problema de Transporte
Vamos considerar a seguinte situação:
· Transportar produtos das várias origens onde estão estocados para vários destinos onde são necessários.
 ROTA DE TRASNPORTE
origem -------------> destino fluxo direto
oferta ou disponibilidade demanda ou necessidade
i ou m (linha) j ou n (coluna)
· custo unitário de transporte: Cij onde i = origem e j = destino
por exemplo: C12 = 10 reais
a mercadoria sai da origem 1 para o destino 2, custo unitário da rota é 10 reais
· Quantidade transportada: xij variável que vamos determinar através do algoritmo de transporte.
· Despesa do transporte numa determinada rota: Cij.xij
despesa na rota = custo unitário x quantidade transportada
Exemplo: custo unitário
origens (oferta)					destinos (demandas)
 c11 = 10 e X11
fábrica 1	40					destino 1 50
 c12 = 15 e X12
fábrica 2	100					destino 2 40
 c13 = 20 e X13
fábrica 3	10					destino 3 60
soma da oferta: 150
soma da demanda: 150
Devemos ter sempre oferta = demanda
MODELOS DE TRANSPORTE 
Três fábricas e 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 custo mínimo de transporte. 
 cada número dentro do quadro representa um custo unitário
			 
	
	D1 
j = 1
	D2 
j = 2
	D3 
j = 3
	OFERTA
	F1 i=1
	c11
10
	c12
15
	c13
20
	
40
	F2 i = 2
	
12
	
25
	
18
	
100
	 F3 i = 3
	
16
	
14
	
24
	
10
	DEMANDA
	
50
	
40
	
 (
150
)60
	150
	
	D1
	D2
	D3
	OFERTA
	F1
	
X11
	
X12
	
X13
	
40
	F2
	
X21
	
X22
	
X23
	
100
	F3
	
X31
	
X32
	
X33
	
10
	DEMANDA
	
50
	
40
	
 (
150
)60
	150
CUSTO UNITÁRIO DE TRANSPORTE: 
F1D1 => C11 = 10
F1D2 => C12 = 15
F1D3 => C13 = 20
CUSTO DA ROTA: C11.X11 => 10.X11
CUSTO DA ROTA: C12.X12 => 15.X12
CUSTO DA ROTA: C13.X13 => 20.X13
Objetivo do algoritmo de transporte: 
Determinar a quantidade transportada xij e o custo mínimo de transporte.
Modelo:
Min Z = 10x11 +15x12 + 20x13 +12x21 +25x22 +18x23 +16x31 +14x32 +24x33
Sujeito a:	x11 + x12 + x13 = 40 restrição de oferta
		x21 + x22 + x23 = 100 restrição de oferta
		x31 + x32 + x33 = 10 restrição de oferta
		x11 + x21 + x31 = 50 restrição de demanda
		x12 + x22 + x32 = 40 restrição de demanda
		x13 + x23 + x33 = 60 restrição de demanda
		xij ≥ 0 para i = 1, 2, 3 e j = 1, 2, 3 condição de não negatividade
x11≥ 0;x12≥ 0; ....
Sistemas de transportes equilibrados => oferta = demanda
Exemplo:
	
	D1
	D2
	D3
	OFERTA
	F1
	
10
	
15
	
20
	
40
	F2
	
12
	
25
	
18
	
100
	F3
	
16
	
14
	
24
	
10
	DEMANDA
	
50
	
40
	
 (
150
)60
	150
Sistemas de transportes não equilibrados => oferta ≠ demanda
 oferta ou disponibilidade
	
10 
	
 15
	
20
	
100
	
12
	
25
	
18
	
80
	
16
	
14
	
24
	
20
	
100
	
50
	
60
	
 
 demanda ou necessidade
oferta: 100 + 80 + 20 = 200
demanda: 100 + 50 + 60 = 210
oferta < demanda
Como a oferta é diferente da demanda será necessário equilibrar o sistema.
Criar uma linha artificial com custo unitário zero
	
10 
	
 15
	
20
	
100
	
12
	
25
	
18
	
80
	
16
	
14
	
24
	
20
	0
	0
	0
	 (
linha artificial
)10
	 
100
	
50
	
60
	
Outro exemplo:
	
	1
	2
	3
	4
	Ofer.
	1
	2,1
	1,8
	1,8
	1,8
	
160
	2
	1,5
	2,4
	1,8
	2,1
	
200
	3
	2,4
	1,5
	2,4
	1,8
	
100
	Dem.
	
100
	
80
	
120
	
80
	
oferta: 160 + 200 + 100 = 460
demanda: 100 + 80 + 120 + 80 = 380
oferta > demanda
Criar uma coluna artificial com custo unitário zero
	
	1
	2
	3
	4
	5
	Ofer.
	1
	2,1
	1,8
	1,8
	1,8
	0
	
160
	2
	1,5
	2,4
	1,8
	2,1
	0
	
200
	3
	2,4
	1,5
	2,4
	1,8
	0
	
100
	Dem.
	
100
	
80
	
120
	
80
	 (
460
)80
	 460
 
MODELAGEM - EXERCÍCIO
1.(ENADE) Uma empresa fabricante de lubrificantes especiais para o mercado industrial tem duas refinarias, uma em Duque de Caxias (RJ) e outra em Paulínia (SP), e três centros de distribuição nas cidades de São Paulo (SP), Belo Horizonte (MG) e Brasília (DF).
Com base nos dados apresentados nas tabelas 1 e 2 e considerando xmn a quantidade transportada da cidade produtora m para a cidade consumidora n, qual função tem o objetivo de otimizar os custos de transporte para distribuição dos lubrificantes?
(A) Maximizar f(x11 .... xmn) = 5x11+7x12+10x13+1x21+6x22+11x23
(B) Maximizar f(x11 .... xmn) = - 500x11- 400x12- 800x23+1.000x24+800x15
(C) Minimizar f(x11 .... xmn) = 5x11+1x21+7x12+6x22- 10x13- 11x23
(D) Minimizar f(x11 .... xmn) = 5x11+1x21+7x12+6x22+10x13+11x23 correta
(E) Minimizar f(x11 .... xmn) = 1.000x24+800x15- 500x11- 400x12- 800x23
2. Com base nos dados apresentados nas tabelas 1 e 2 e considerando xmn a quantidade transportada da cidade produtora m para a cidade consumidora n, qual das equações a seguir NÃO é uma restrição deste problema de transporte?
(A) x11+x12+ x13 ≤ 800 
(B) x21+x22+ x23 ≤ 1.000
(C) x11+ x21 = 800 
(D) x12+ x22 = 500
(E) x11 ≤ 0 correta a variável de decisão não pode ser negativa
3. Uma empresa de transportes coletivo tem um problema para ser resolvido. São necessários(demanda) na próxima semana 6 carros no Rio de Janeiro, 4 carros em São Paulo e 14 carros em Curitiba. No entanto, os carros disponíveis (oferta)nesta época estão nas garagens de Belo Horizonte e Porto Alegre, nas quantidades 13 e 11, respectivamente. Determine o modelo de transporte desses carros até as cidades onde são necessários. 
A função objetivo é formada pelos custos unitários multiplicados pelas variáveis de decisão.
Min Z = 1200x11 + 800x12 + 600x13 + 400x21 + 600x22 + 1000x23
sujeito a: 
x11 + x12 + x13 =11 restrição de oferta
x21 + x22 + x23 = 13 restrição de oferta
x11 + x21 = 6 restrição de demanda
x12 + x22 = 4 restrição de demanda
x13 + x23 = 14 restrição de demanda
xij ≥ 0, onde i = 1,2 e j =1, 2, 3
4. A Miss Daisy Ltda. é um laboratório de manipulação que presta serviços de entrega para idosos. A empresa possui duas filiais e fornece o serviço a seis bairros diferentes. Tendo em vista que atualmente a demanda é superior à oferta de entrega da companhia, a mesma gostaria de saber a quais clientes atender e o custo total do transporte, partir das filiais. As demandas dos bairros e os custos unitários de entrega estão evidenciados na tabela a seguir:
	
	Ipanema
	Copacabana
	Centro
	Barra
	Leblon
	Tijuca
	Oferta
	Filial Centro
	7,00
	9,00
	1,00
	12,00
	7,00
	4,00
	2500
	Filial Barra
	4,00
	5,00
	12,00
	1,00
	3,00
	8,00
	2000
	Filial artificial
	0
	0
	0
	0
	0
	0
	500
	Demanda
	1400
	1560
	400
	150
	870
	620
	
Determine o modelo de transporte.
Min Z = 7x11 + 9x12 + 1.x13 + 12x14 + 7x15 + 4x16 + 4x21 + 5x22 + 12x23 + 1.x24 + 3x25 + 8x26 + 0.x31 + 0.x32 + 0x33 + 0x34 + 0x35 + 0x36
sujeito a: 
x11+x12+x13+x14+x15+x16 = 2500
x21+x22+x23+x24+x25+x26 = 2000
x31+x32+x33+x34+x35+x36 = 500
x11+x21+x31 = 1400
x12+x22+x32 = 1560
x13+x23+x33 = 400
x14+x24+x34 = 150
x15+x25+x35 = 870
x16+x26+x36 = 620
xij≥0, onde i = 1, 2, 3 e j = 1,2,3,4,5,6
O algoritmo de transporte 
A solução do problema do transporte é representado por um modelo de programação linear. Podemos dizer que usaremos um Simplex modificado.
O algoritmo é dividido em duas partes:
Parte 1: Determinar a solução básica inicial
Um solução básica para o problema é um conjunto de valores a transportar que obedecem a duas condições:
a) satisfazem as restrições de origem e destino;
b) não apresentam circuitos entre as variáveis básicas.
Temos dois métodos para a construção da solução inicial:
1) Método de Vogel ou método das penalidades;
2) Método do canto noroeste.
Métodode Vogel ou método das penalidades
A ideia desse método é fazer o transporte com prioridade na linha ou coluna que apresenta a maior penalidade. Como o transporte é feito na célula de menor custo, tenta-se evitar com isso o transporte na célula de maior custo, evitando assim incorrer num aumento de custo igual à penalidade calculada. 
Descrição do método:
a) Calcular a penalidade para cada linha e coluna. Em cada linha e coluna selecionar os dois menores custos e subtraí-los. O resultado encontrado chamaremos de penalidade.
b) Escolher a linha ou coluna para transporte, que apresente a maior penalidade. Em caso de empate, escolha arbitrariamente uma delas.
c) Na linha ou coluna com a maior penalidade selecionar o menor custo unitário de transporte. Esse processo zera a oferta ou a demanda da célula correspondente. A linha ou coluna que tenha sua disponibilidade zerada deve ser eliminada.
d) Retornar ao item a, até que todos os transportes tenham sido realizados.
Exemplo 1:
Uma empresa de transportes coletivo tem um problema para ser resolvido. São necessários (demanda) na próxima semana 6 carros no Rio de Janeiro, 4 carros em São Paulo e 14 carros em Curitiba. No entanto, os carros disponíveis (oferta) nesta época estão nas garagens de Belo Horizonte e Porto Alegre, nas quantidades 13 e 11 respectivamente. Determine o custo mínimo de transporte desses carros até as cidades onde são necessários. 
	
	
RJ
	
SP
	
CURITIBA
	oferta
	penalidades
	
P.Alegre
	
1200
	
800
	
600
	11
	800 – 600 = 200
	
BH Horizonte
	
400
	
600
	
1000
	13
	600 – 400 = 200
	demanda
	6
	4
	14
	
	
	penalidades
	1200 – 400 = 800
Maior penalidade
	800 – 600 = 200
	1000 – 600 = 400
	
	
Na coluna com a maior penalidade (800) selecionar o menor custo unitário de transporte. Em outras palavras, selecione o quadrado com menor valor. No exemplo acima o menor valor é 400.
No quadrado com o menor custo unitário (400), observe que o valor da demanda é 6 e o valor da oferta é 13.
Escolha entre 6 e 13 o menor valor para transportar. Isso significa que a oferta é de 13, mas a demanda é apenas de 6. Logo envio apenas 6. O quadro ficará da seguinte forma:
	
	
RJ
	
SP
	
CURITIBA
	oferta
	
Porto Alegre
	
	
800
	
600
	11
	
BH Horizonte
	
6
	
600
	
1000
	13
	demanda
	6
	4
	14
	
O processo começa novamente.
	
	
RJ
	
SP
	
CURITIBA
	oferta
	penalidades
	
P.Alegre
	
	
800
	
600
	11
	800-600 = 200
	
BH Horizonte
	
6 qtde
	
600
	
1000
	13
	1000 – 600 = 400
	demanda
	6
	4
	14
	
	
	penalidades
	
	800 – 600 = 200
	1000 – 600 = 400
	
	
Na coluna com a maior penalidade (400) selecionar o menor custo unitário de transporte. No exemplo acima o menor valor é 600.
No quadrado com o menor custo unitário (600), observe que o valor da demanda é 14 e o valor da oferta é 11.
Escolha entre 11 e 14 o menor valor para transportar. Isso significa que a oferta é de 11, mas a demanda é apenas de 14. Logo envio apenas 11. O quadro ficará da seguinte forma:
	
	
RJ
	
SP
	
CURITIBA
	oferta
	
P.Alegre
	
	
	
11
	11
	
BH Horizonte
	
6
	
600
	
1000
	13
	demanda
	6
	4
	14
	
Começa o processo novamente.
	
	
RJ
	
SP
	
CURITIBA
	oferta
	penalidades
	
P.Alegre
	
	
	
11
	11
	
	
BH Horizonte
	
6
	
600
	
1000
	13
	1000 – 600 = 400
	demanda
	6
	4
	14
	
	
	penalidades
	
	600
	1000
	
	
Na coluna com a maior penalidade (1000) selecionar o menor custo unitário de transporte. No exemplo acima o menor valor é 1000.
No quadrado com o menor custo unitário (1000), observe que o valor da demanda é 14 e o valor da oferta é 13.
Escolha entre 13 e 14 o menor valor para transportar. O menor valor é 13, mas de 13 já foram enviados 6 carros p/RJ. Na coluna já tem 11. Logo, só podemos enviar 3 carros.
O quadro ficará da seguinte forma:
	
	
RJ
	
SP
	
CURITIBA
	oferta
	
P.Alegre
	
	
	
11
	11
	
BH Horizonte
	
6
	
600
	
3
	13
	demanda
	6
	4
	14
	
Começa o processo novamente.
	
	
RJ
	
SP
	
CURITIBA
	oferta
	penalidades
	
P.Alegre
	
	
	
11
	11
	
	
BH Horizonte
	
6
	
600
	
3
	13
	600
	demanda
	6
	4
	14
	
	
	penalidades
	
	600
	
	
	
Na coluna com a maior penalidade (600) selecionar o menor custo unitário de transporte. No exemplo acima o menor custo é 600.
No quadrado com o menor custo unitário (600), observe que o valor da demanda é 4 e o valor da oferta é 13.
Escolha entre 13 e 4 o menor valor para transportar. O menor valor é 4.
Solução básica inicial determinada através do método de Vogel:
	
	
RJ
	
SP
	
CURITIBA
	oferta
	
P.Alegre
	
	
	
11
	11
	
BH Horizonte
	
6
	
4
	
3
	13
	demanda
	6
	4
	14
	
Exercício.
Três fábricas abastecem 4 pontos de venda. O quadro abaixo mostra os custos de distribuição, a capacidade dos armazéns e as necessidades nos pontos de venda. 
a) Determine o modelo de transporte
b) Determine a solução básica inicial através do método de Vogel.
	
	D1
	D2
	D3
	D4
	 oferta 
	Fábrica 1
	10
	5
	6
	7
	25
	Fábrica 2
	8
	2 
	7
	6
	25
	Fábrica 3
	9
	3
	4 
	8
	50
	demanda
	15
	20
	30
	35