Upload
adelino-ferrao-aldeia
View
217
Download
0
Embed Size (px)
Citation preview
Problema de Transporte e Alocação
Luiz Henrique de Campos Merschmann
Conteúdo da aula Problemas de transporte:
Definição. Modelagem matemática. Método de solução.
Problema de Alocação
Introdução Os problemas de transporte e de
alocação fazem parte da classe de problemas de fluxos em redes.
Os modelos de P.L. para esses problemas possuem uma estrutura especial que permite o desenvolvimento de algoritmos eficientes e especializados em suas soluções.
Problemas de Fluxos em Redes
Problemas de fluxo em redes aparecem em uma série de serviços,
como entrega postal, entrega de mercadorias, rotas de ônibus
escolar, coleta de lixo industrial, serviço de entregas noturnas, operações de frete, e outros.
Problemas de Fluxos em Redes
Problema de Transporte
Problema de Alocação
Problema de TransporteEm geral, o problema de transporte pode ser visto da seguinte forma:
Conjunto m de pontos de fornecimento. Cada fornecedor i possui uma capacidade de
fornecimento si unidades de material. Conjunto de n pontos de demanda. Cada ponto de demanda j deve receber pelo
menos dj unidades de material. O custo de transporte de cada unidade de
material do fornecedor i para o consumidor j é dado por cij.
Representação Gráfica
Fornecedor 1
Fornecedor 2
Fornecedor 3
Consumidor 1
Consumidor 2
Consumidor 3
Consumidor 4
s1
s2
s3
d1
d2
d3
d4
cij
Exemplo Uma companhia tem três fábricas que produzem
um certo produto que será remetido a quatro centros de distribuição.
As fábricas 1,2 e 3 produzem 12, 17 e 11 remessas por mês, respectivamente.
Cada centro de distribuição precisa receber 10 remessas por mês .
A distância de cada fábrica até os respectivos centros de distribuição é dada abaixo em quilômetros:Fabricas 1 2 3 4
1 800 1.300 400 7002 1.100 1.400 600 1.0003 600 1.200 800 900
Centros de Distribuição
Exemplo (cont.) Quanto deveria ser remetido de cada
fábrica para cada um dos centros de distribuição para minimizar os custos totais de transporte?
Formule este problema como um problema de transporte.
Problema de Transporte Modelo matemático:
mi
i
nj
jijij xc
1 1
min
nj
jiij isx
1
m ..., 2, ,1
n ..., 2, 1, j 1
j
mi
iij dx
j i, 0 ijx
Problema de Transporte
Problema de transporte balanceado.
Oferta = Demanda
Problema de transporte não balanceado.
Oferta ‡ Demanda
Problema de Transporte Balanceado
Método de Solução
Método de Solução Como o problema de transporte é um
problema de P.L., o Simplex pode ser utilizado.
Devido às características específicas do Problema de Transporte, uma versão modificada do Simplex, denominado “Método Simplex de Transporte”, torna a resolução desse tipo de problema muito mais eficiente, quando comparado ao Simplex tradicional.
Representação Tabular do Problema de Transporte
OfertaDestinos
Origens
1
2
3
1 2 3 4
c11
c31
c21 c22
c32
c12 c13
c23
c33 c34
c24
c14
Destinos
Origens
1
2
3
c11
c31
c21 c22
c32
c12 c13
c23
c33 c34
c24
c14
x11
x21
x31
x12
x22
x32
x13
x23
x33
x14
x24
x34
Demanda d1 d2 d3 d4
s1
s2
s3
Método Simplex de Transporte
Seja o seguinte problema de transporte:Destinos
Origens
1
2
3
1 2 3 4
c11
c31
c21 c22
c32
c12 c13
c23
c33 c34
c24
c14
Destinos
Origens
1
2
3
8
14
9 12
9
6 10
13
16 5
7
9
x11
x21
x31
x12
x22
x32
x13
x23
x33
x14
x24
x34
Demanda 45 20 30 30
40
50
35
Oferta
Algoritmo 1º Passo: Solução Inicial
Método do Canto Noroeste. Método de Aproximação de Vogel.
2º Passo: Teste de Otimalidade. 3º Passo: Atualização do Quadro.
Método do Canto NoroesteSolução Inicial
Destinos
Origens
1
2
3
1 2 3
c11
c31
c21 c22
c32
c12 c13
c23
c33 c34
c24
c14
Destinos
Origens
1
2
3
4
8
14
9 12
9
6 10
13
16 5
7
9
35
10 20 20
10 30
Demanda 45 20 30 30
40
50
35
Oferta
2º Passo: Teste de Otimalidade
A cada linha i é associada uma variável auxiliar Ui.
A cada coluna j é associada uma variável auxiliar Vj.
Para cada variável básica xij, que compõe a solução atual, deve-se ter:
Ui + Vj = Cij
2º Passo: Teste de Otimalidade
Para cada variável não básica deve-se calcular:
Pij = Cij - Ui - Vj Se todos os Pij forem não negativos a
solução é ótima, ou A avaliação mais negativa indica a
variável que deve entrar na base.
Método Simplex de Transporte
Teste de otimalidade
14 9 16 5
7
910
1312
68
9
Vj
Ui
8
9
12
0 3 4 - 7
2
- 5
- 6
- 2 8
5
3º Passo: Atualização do Quadro
A entrada de uma variável na base ocasiona uma reação em cadeia para compensar as restrições de linha (oferta) e coluna (demanda).
O valor da variável que entra na base deve ser o maior possível, sem tornar nenhuma variável básica negativa. A variável básica que tiver seu valor anulado como conseqüência da variável que entra na base será a variável que sairá da base.
Método Simplex de Transporte
Traçar caminho e atualizar tabelaDestinos
Origens
1
2
3
1 2 3 4
c11
c31
c21 c22
c32
c12 c13
c23
c33 c34
c24
c14
Destinos
Origens
1
2
3
8
14
9 12
9
6 10
13
16 5
7
9
35
10 20 20
10 30
Demanda 45 20 30 30
40
50
35
Oferta
+
+
-
-10 30
10
Método Simplex de Transporte
Teste de otimalidade
14 9 16 5
7
910
1312
68
9
Vj
Ui
8
9
6
0 3 4 - 1
8
- 5
- 2 2
- 1
6
Método Simplex de Transporte
Traçar caminho e atualizar tabelaDestinos
Origens
1
2
3
1 2 3 4
c11
c31
c21 c22
c32
c12 c13
c23
c33 c34
c24
c14
Destinos
Origens
1
2
3
8
14
9 12
9
6 10
13
16 5
7
9
35
10
10 30
Demanda 45 20 30 30
40
50
35
Oferta
+
+
-
-
10 30
10
25
20
10
Método Simplex de Transporte
Teste de otimalidade
14 9 16 5
7
910
1312
68
9
Vj
Ui
8
9
11
0 -2 4 - 6
3
5
- 2 7
4
1
Método Simplex de Transporte
Traçar caminho e atualizar tabelaDestinos
Origens
1
2
3
1 2 3 4
c11
c31
c21 c22
c32
c12 c13
c23
c33 c34
c24
c14
Destinos
Origens
1
2
3
8
14
9 12
9
6 10
13
16 5
7
9
10 30
Demanda 45 20 30 30
40
50
35
Oferta
+
+
-
-
30
10
25
20
10
45 5
25
Método Simplex de Transporte
Teste de otimalidade
14 9 16 5
7
910
1312
68
9
Vj
Ui
6
9
9
0 0 4 - 4
5
3
2 7
2
3
Método Simplex de Transporte
Solução finalDestinos
Origens
1
2
3
1 2 3 4
c11
c31
c21 c22
c32
c12 c13
c23
c33 c34
c24
c14
Destinos
Origens
1
2
3
8
14
9 12
9
6 10
13
16 5
7
9
10 30
Demanda 45 20 30 30
40
50
35
Oferta
10
10
45 5
25
Problema de Transporte Não Balanceado
Método de Solução
Problema de Transporte Não Balanceado
Se Oferta > Demanda Inserir uma coluna fictícia no quadro com custos
de transporte iguais a zero. Aplicar o Método Simplex de Transporte como visto anteriormente.
Se Demanda > Oferta Inserir uma linha fictícia no quadro com custos de
transporte iguais a zero. Aplicar o Método Simplex de Transporte como visto anteriormente.
Problema de Transporte Não Balanceado
c31 c32 c33
c13
c23c22
c12c11
c21
Destinos
Origens
1
2
3
1 2 3
c34
c24
c14
4
0
0
0
A
Quadro Inicial ( Oferta > Demanda)
ExercícioQuatro postos de gasolina A, B, C e D necessitam de 50, 40, 60 e 40 galões de gasolina, respectivamente. É possível suprir essas demandas partindo dos fornecedores 1, 2 e 3 que dispõem de 80, 100 e 50 galões, respectivamente. Os custos de envio de um galão de gasolina são mostrados no quadro abaixo. Determinar a quantidade de gasolina a ser enviada de cada fornecedor para cada posto de gasolina.A B C D
1 70 60 60 602 50 80 60 703 80 50 80 60
Problema de Transporte Não Balanceado
c31 c32 c33 c34
c24
c14c13
c23c22
c12c11
c21
Destinos
Origens
1
2
3
1 2 3 4
0 0 0 0A
Quadro Inicial ( Demanda > Oferta)
ExercícioUma firma tem fábricas nas cidades A, B, C e D, todas fabricando o mesmo tipo de painel de madeira para residências. Os produtos são atualmente distribuídos pelas fábricas para os revendedores 1, 2 e 3. As capacidades de produção das fábricas nas cidades A, B, C e D são de 5, 20, 12 e 13 caixas de painel, respectivamente. A demanda dos revendedores 1, 2 e 3 são de 8, 32 e 15 caixas, respectivamente. Os custos de transporte são mostrados na tabela abaixo. Quantas caixas devem ser transportadas de cada fábrica para cada revendedor de modo a minimizarmos o custo de transporte?
1 2 3A 6 5 8B 13 12 1C 7 9 5D 10 6 4
FIM