TEORIA TRANSPORTE 20 DE MAIO

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
origem -------------> destino
oferta demanda
i j
· 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:
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
	D2
	D3
	OFERTA
	F1
	
10
	
15
	
20
	
40
	F2
	
12
	
25
	
18
	
100
	 F3
	
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 => 10X11
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
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 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 
(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 
3. Uma empresa de transportes coletivo tem um problema para ser resolvido. São necessários 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 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. 
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étodo de 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 ou 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 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 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
	
Porto Alegre
	
1200
	
800
	
600
	11
	
Belo Horizonte
	
400
	
600
	
1000
	13
	demanda
	6
	4
	14
	
	
	
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. No exemplo acima O MENO 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
	
Belo Horizonte
	
6
	
600
	
1000
	13
	demanda
	6
	4
	14
	
O processo começa novamente até chegar no quadro abaixo:
	
	
RJ
	
SP
	
CURITIBA
	oferta
	penalidades
	
P.Alegre
	
	
800
	
600
	11
	800-600 = 200
	
BH Horizonte
	
6
	
600
	
1000
	13
	600 – 400 = 200
	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 MENO 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
	600 – 400 = 200
	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 MENO 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 MENO VALOR é 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. 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