PO 2020 - Unidade 4 - Slide 3 Problema de Transporte - Método de Voguel

Prévia do material em texto

1 / 31
PESQUISA OPERACIONAL
UNIDADE 4 - Método VAM ou MAV
Problema de Transporte
Prof. Carlos Guimarães
2 / 31
Objetivo
Introduzir o problema do transporte por meio da
apresentação:
• Da Método de Aproximação de Vogel (MAV ou VAM);
• Da detalhamento das etapas do método; e
• Do cálculo do custo total.
3 / 31
Método de Aproximação de Vogel
(VAM - Vogel Approximation Method, em inglês)
É uma rotina de cálculos que permite obter uma
solução aproximada ao Problema de Transporte.
A grande vantagem desse método é a de fornecer
uma solução bem próxima à solução ótima ou, às
vezes, a própria solução ótima.
Vamos ver um fluxo de como trabalhar
4 / 31
Fluxo do VAM
1. Determinar as penalidades;
2. Identificar a maior penalidade;
3. Identificar o menor custo;
4. Alocar a maior carga;
5. Calcular a carga não alocada;
6. Eliminar a coluna/linha alocada;
7. Recalcular as penalidades;
8. Verificar se existem penalidades;
9. Se sim, voltar para 2;
10. Se não, finalizar as alocações; e
11. Calcular o custo total.
5 / 31
Método de Aproximação de Vogel
O Método de Vogel faz as alocações de forma
indireta, por meio dos custos.
CALCULO DAS PENALIDADES
Considerando cada linha e cada coluna,
separadamente, são inspecionados os custos de
transporte, para se verificar qual o menor de todos
e aquele que imediatamente se segue, ou seja, o
primeiro e o segundo menor custo. Identificando o
menor e o segundo menor custo, para cada linha e
cada coluna, calcula-se a diferença entre os dois.
6 / 31
Método de Aproximação de Vogel
Essa diferença representa um custo de
arrependimento, caso se escolha o segundo menor
custo em detrimento do primeiro, ou seja, é uma
penalidade fictícia, na qual se incorreria caso se
escolhesse alocar carga na célula em que está o
segundo menor custo, em vez de no primeiro.
Vamos trabalhar COM A TABELA
7 / 31
Exemplo
D1 D2 D3 D4 Suprimento
F1 3 2 2 3 4.000
F2 4 4 5 5 8.000
F3 7 7 6 4 13.000
Demanda 9.000 8.000 3.000 5.000 25.000
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2 2 3 4.000
F2 4 4 5 5 8.000
F3 7 7 6 4 13.000
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade
Não Alocada
• Acrescentar as colunas e linhas de
✓ Penalidade e
✓ Não alocado
8 / 31
Exemplo
• Determinar as penalidades
✓ Calcular a diferença entre o primeiro e o segundo menor custo
para cada linha e cada coluna.
✓ Essa diferença representa um custo de arrependimento, caso se
escolha o segundo menor custo em detrimento do primeiro, ou
seja, é uma penalidade fictícia.
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2 2 3 4.000 0
F2 4 4 5 5 8.000 0
F3 7 7 6 4 13.000 2
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 1 2 3 1
Não Alocada
9 / 31
Exemplo
• Identificar a maior penalidade
✓ No caso de serem obtidas penalidades idênticas, a alocação
poderá ser feita na linha ou coluna que apresentar o menor custo.
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2 2 3 4.000 0
F2 4 4 5 5 8.000 0
F3 7 7 6 4 13.000 2
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 1 2 3 1
Não Alocada
10 / 31
Exemplo
• Identificar o menor custo
✓ Se os custos também forem iguais, realizar aleatoriamente a
alocação, escolhendo uma das células possíveis (de menor
suprimento ou demanda).
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2 2 3 4.000 0
F2 4 4 5 5 8.000 0
F3 7 7 6 4 13.000 2
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 1 2 3 1
Não Alocada
11 / 31
Exemplo
• Alocar a maior carga possível
✓ Alocar tanta carga quanto possível à célula identificada.
✓ A quantidade a ser alocada será ou o total da demanda do destino
ou o total do suprimento da fonte correspondentes à célula, o
que for menor.
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2 2
3.000
3
4.000 0
F2 4 4 5 5 8.000 0
F3 7 7 6 4 13.000 2
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 1 2 3 1
Não Alocada
12 / 31
Exemplo
• Calcular a carga não alocada
✓ Calcular a diferença na demanda e no suprimento correspondente
para que seja posteriormente alocada.
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2 2
3.000
3
4.000 0 1.000
F2 4 4 5 5 8.000 0
F3 7 7 6 4 13.000 2
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 1 2 3 1
Não Alocada 0
13 / 31
Exemplo
• Eliminar a coluna/linha alocada
✓ Calcular a diferença na demanda e no suprimento correspondente
para que seja posteriormente alocada.
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2 2
3.000
3
4.000 0 1.000
F2 4 4 5 5 8.000 0
F3 7 7 6 4 13.000 2
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 1 2 3 1
Não Alocada 0
14 / 31
Exemplo
• Recalcular as penalidades
✓ Calcular a diferença entre o primeiro e o segundo menor custo
para cada linha e cada coluna restante.
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2 2
3.000
3
4.000 1 1.000
F2 4 4 5 5 8.000 0
F3 7 7 6 4 13.000 3
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 1 2 – 1
Não Alocada 0
15 / 31
Exemplo
• Identificar a maior penalidade
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2 2
3.000
3
4.000 1 1.000
F2 4 4 5 5 8.000 0
F3 7 7 6 4 13.000 3
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 1 2 – 1
Não Alocada 0
16 / 31
Exemplo
• Identificar o menor custo
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2 2
3.000
3
4.000 1 1.000
F2 4 4 5 5 8.000 0
F3 7 7 6 4 13.000 3
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 1 2 – 1
Não Alocada 0
17 / 31
Exemplo
• Alocar a maior carga possível
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2 2
3.000
3
4.000 1 1.000
F2 4 4 5 5 8.000 0
F3 7 7 6 4
5.000 13.000 3
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 1 2 – 1
Não Alocada 0
18 / 31
Exemplo
• Calcular a carga não alocada
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2 2
3.000
3
4.000 1 1.000
F2 4 4 5 5 8.000 0
F3 7 7 6 4
5.000 13.000 3 8.000
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 1 2 – 1
Não Alocada 0 0
19 / 31
Exemplo
• Eliminar a coluna/linha alocada
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2 2
3.000
3
4.000 1 1.000
F2 4 4 5 5 8.000 0
F3 7 7 6 4
5.000 13.000 3 8.000
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 1 2 – 1
Não Alocada 0 0
20 / 31
Exemplo
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2 2
3.000
3
4.000 1 1.000
F2 4 4 5 5 8.000 0
F3 7 7 6 4
5.000 13.000 0 8.000
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 1 2 – –
Não Alocada 0 0
• Recalcular as penalidades
✓ Calcular a diferença entre o primeiro e o segundo menor custo
para cada linha e cada coluna restante.
21 / 31
Exemplo
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2 2
3.000
3
4.000 1 1.000
F2 4 4 5 5 8.000 0
F3 7 7 6 4
5.000 13.000 0 8.000
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 1 2 – –
Não Alocada 0 0
• Identificar a maior penalidade
22 / 31
Exemplo
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2 2
3.000
3
4.000 1 1.000
F2 4 4 5 5 8.000 0
F3 7 7 6 4
5.000 13.000 0 8.000
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 1 2 – –
Não Alocada 0 0
• Identificar o menor custo
23 / 31
Exemplo
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2
1.000
2
3.000
3
4.000 1 1.000
F2 4 4 5 5 8.000 0
F3 7 7 6 4
5.000 13.000 0 8.000
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 1 2 – –
Não Alocada 0 0
• Alocar a maior carga possível
24 / 31
Exemplo
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2
1.000
2
3.000
3
4.000 1 0
F2 4 4 5 5 8.000 0
F3 7 7 6 4
5.000 13.000 0 8.000
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 1 2 – –
Não Alocada 7.000 0 0
• Calcular a carga não alocada
25 / 31
Exemplo
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2
1.000
2
3.000
3
4.000 1 0
F2 4 4 5 5 8.000 0
F3 7 7 6 4
5.000 13.000 0 8.000
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 1 2 – –
Não Alocada 7.000 0 0
• Eliminar a coluna/linha alocada
26 / 31
Exemplo
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2
1.000
2
3.000
3
4.000 – 0
F2 4 4 5 5 8.000 0
F3 7 7 6 4
5.00013.000 0 8.000
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 3 3 – –
Não Alocada 7.000 0 0
• Recalcular as penalidades
✓ Calcular a diferença entre o primeiro e o segundo menor custo
para cada linha e cada coluna restante.
27 / 31
Exemplo
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2
1.000
2
3.000
3
4.000 – 0
F2 4 4 5 5 8.000 0
F3 7 7 6 4
5.000 13.000 0 8.000
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 3 3 – –
Não Alocada 7.000 0 0
• Identificar a maior penalidade
✓ No caso de serem obtidas penalidades idênticas, a alocação
poderá ser feita na linha ou coluna que apresentar o menor custo.
28 / 31
Exemplo
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2
1.000
2
3.000
3
4.000 – 0
F2 4 4 5 5 8.000 0
F3 7 7 6 4
5.000 13.000 0 8.000
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 3 3 – –
Não Alocada 7.000 0 0
• Identificar o menor custo
✓ Se os custos também forem iguais, realizar aleatoriamente a
alocação, escolhendo uma das células possíveis (de menor
suprimento ou demanda).
29 / 31
Exemplo
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2
1.000
2
3.000
3
4.000 – 0
F2 4
8.000
4 5 5
8.000 0
F3 7 7 6 4
5.000 13.000 0 8.000
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 3 3 – –
Não Alocada 7.000 0 0
• Alocar a maior carga possível
30 / 31
Exemplo
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2
1.000
2
3.000
3
4.000 – 0
F2 4
8.000
4 5 5
8.000 0 0
F3 7 7 6 4
5.000 13.000 0 8.000
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 3 3 – –
Não Alocada 1.000 7.000 0 0
• Calcular a carga não alocada
31 / 31
Exemplo
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2
1.000
2
3.000
3
4.000 – 0
F2 4
8.000
4 5 5
8.000 0 0
F3 7 7 6 4
5.000 13.000 0 8.000
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 3 3 – –
Não Alocada 1.000 7.000 0 0
• Eliminar a coluna/linha alocada
32 / 31
Exemplo
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2
1.000
2
3.000
3
4.000 – 0
F2 4
8.000
4 5 5
8.000 0 0
F3 7
1.000
7
7.000
6 4
5.000 13.000 0 8.000
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 3 3 – –
Não Alocada 1.000 7.000 0 0
• Fim das penalidades
• Finalizar as alocações
33 / 31
Exemplo
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2
1.000
2
3.000
3
4.000 – 0
F2 4
8.000
4 5 5
8.000 0 0
F3 7
1.000
7
7.000
6 4
5.000 13.000 0 0
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade – – – –
Não Alocada 0 0 0 0
• Calcular a carga não alocada
34 / 31
Exemplo
D1 D2 D3 D4 Suprimento Penalidade Não Alocada
F1 3 2
1.000
2
3.000
3
4.000 – 0
F2 4
8.000
4 5 5
8.000 0 0
F3 7
1.000
7
7.000
6 4
5.000 13.000 0 0
Demanda 9.000 8.000 3.000 5.000 25.000
Penalidade 3 3 – –
Não Alocada 0 0 0 0
• Calcular o custo total usandp apenas as rotas
com menor custo apuradas pelo método:
2 x 1.000 + 2 x 3.000 + 4 x 8.000 + 7 x 1.000 + 7 x 7.000 + 4 x 5.000 = 116.000