Exercícios propostos transporte - gabarito

Prévia do material em texto

Universidade Presbiteriana Mackenzie
Pesquisa Operacional Aplicada -
Problemas de Transporte
Exercícios Propostos - Solução
Faculdade de Computação e Informática
Exercício 1: Dada solução inicial já obtida para o problema de 
transporte abaixo, verifique se ela é ótima. Se não for obtenha a 
solução ótima.
Solução:
Variáveis de decisão: xij quantidade de produto enviado de i para j
Função objetivo:
min 𝑐 = 6𝑥11 + 5𝑥12 + 6𝑥13 + 7𝑥14 +
8𝑥21 + 2𝑥22 + 7𝑥23 + 6𝑥24 +
9𝑥31 + 3𝑥32 + 4𝑥33 + 8𝑥34
restrições: 
𝑥11 + 𝑥12 + 𝑥13 + 𝑥14 = 250
𝑥21 + 𝑥22 + 𝑥23 + 𝑥24 = 500
𝑥31 + 𝑥32 + 𝑥33 + 𝑥34 = 250
𝑥11 + 𝑥21 + 𝑥31 = 150
𝑥12 + 𝑥22 + 𝑥32 = 200
𝑥13 + 𝑥23 + 𝑥33 = 300
𝑥14 + 𝑥24 + 𝑥34 = 350
xij ≥ 0
Solução Inicial:
Custo inicial: c = 150*6 +50*6 + 50*7 + 200*2 + 300*6 + 250*4 = 4750
Rota inicial:
F1
F2
F3
D1
D2
D3
D4
150
50
50
200
300
250
250
500
250
150
200
300
350
Verificação: Multiplicadores de Lagrange
1) variáveis auxiliares para linha: 𝑢1, 𝑢2 e 𝑢3
2) variáveis auxiliares para coluna: 𝑣1, 𝑣2, 𝑣3 𝑒 𝑣4
3) Obter 𝑐𝑖𝑗 − 𝑢𝑖 − 𝑣𝑗 = 0 para cada variável básica:
para 𝑥11: 𝑐11 − 𝑢1 − 𝑣1 = 0 → 6 − 𝑢1 − 𝑣1 = 0 → 𝑢1 = 0 𝑣1 = 6
para 𝑥13: 𝑐13 − 𝑢1 − 𝑣3 = 0 → 6 − 𝑢1 − 𝑣3 = 0 → 𝑣3 = 6
para 𝑥14: 𝑐14 − 𝑢1 − 𝑣4 = 0 → 7 − 𝑢1 − 𝑣4 = 0 → 𝑣4 = 7
para 𝑥22: 𝑐22 − 𝑢2 − 𝑣2 = 0 → 2 − 𝑢2 − 𝑣2 = 0 → 𝑣2= 3
para 𝑥24: 𝑐24 − 𝑢2 − 𝑣4 = 0 → 6 − 𝑢2 − 𝑣4 = 0 → 𝑢2 = −1
para 𝑥33: 𝑐33 − 𝑢3 − 𝑣3 = 0 → 4 − 𝑢3 − 𝑣3 = 0 → 𝑢3 = −2
4) Para as variáveis não básicas calcular: 𝑃𝑖𝑗 = 𝑐𝑖𝑗 − 𝑢𝑖 − 𝑣𝑗
para 𝑥12: 𝑃12 = 𝑐12 − 𝑢1 − 𝑣2 → 𝑃12 = 5 − 0 − 3 = 2
para 𝑥21: 𝑃21 = 𝑐21 − 𝑢2 − 𝑣1 → 𝑃21 = 8 − (−1) − 6 = 3
para 𝑥23: 𝑃23 = 𝑐23 − 𝑢2 − 𝑣3 → 𝑃23 = 7 − (−1) − 6 = 2
para 𝑥31: 𝑃31 = 𝑐31 − 𝑢3 − 𝑣1 → 𝑃31 = 9 − (−2) − 6 = 5
para 𝑥32: 𝑃32 = 𝑐32 − 𝑢3 − 𝑣2 → 𝑃32 = 3 − (−2) − 3 = 2
para 𝑥34: 𝑃31 = 𝑐34 − 𝑢3 − 𝑣4 → 𝑃34 = 8 − (−2) − 7 = 3
Logo, a solução é ótima, pois todos os 𝑃𝑖𝑗 são maiores ou iguais a zero.
Exercício 2: calcular o plano de transporte de menor custo para o 
problema. Monte o modelo, obtenha a solução inicial, verifique se a 
solução obtida é ótima. Se não for, obtenha a solução ótima.
6
D1 D2 D3 Disponibilidade
O1 10
O2 20
O3 12
O4 13
Necessidades 8 32 15
57
113
86 5
12
9
10 46
Modelo:
Variáveis de decisão: xij quantidade de produto enviado de i para j
Função objetivo:
min 𝑐 = 6𝑥11 + 5𝑥12 + 8𝑥13 +
13𝑥21 + 12𝑥22 + 1𝑥23 +
7𝑥31 + 9𝑥32 + 5𝑥33 +
10𝑥41 + 6𝑥42 + 4𝑥43
restrições: 
𝑥11 + 𝑥12 + 𝑥13 = 10
𝑥21 + 𝑥22 + 𝑥23 = 20
𝑥31 + 𝑥32 + 𝑥33 = 12
𝑥41 + 𝑥42 + 𝑥43 = 13
𝑥11 + 𝑥21 + 𝑥31 + 𝑥41 = 8
𝑥12 + 𝑥22 + 𝑥32 + 𝑥42 = 32
𝑥13 + 𝑥23 + 𝑥33 + 𝑥43 = 15
𝑥𝑖𝑗 ≥ 0
Solução inicial:
Custo inicial: c = 10*5 + 5*12 + 15*1 + 8*7 + 4*9 + 13*6 = 295
F1
F2
F3
F4
D1
D2
D3
10
5
15
8
10
4
13
10
20
12
13
8
32
15
Rota inicial:
Verificação de otimalidade: Multiplicadores de Lagrange
1) variáveis auxiliares para linha: 𝑢1, 𝑢2, 𝑢3 𝑒 𝑢4
2) variáveis auxiliares para coluna: 𝑣1, 𝑣2 𝑒 𝑣3
3) Obter 𝑐𝑖𝑗 − 𝑢𝑖 − 𝑣𝑗 = 0 para cada variável básica:
para 𝑥12: 𝑐12 − 𝑢1 − 𝑣2 = 0 → 5 − 𝑢1 − 𝑣2 = 0 → 𝑢1 = 0 𝑣2 = 5
para 𝑥22: 𝑐22 − 𝑢2 − 𝑣2 = 0 → 12 − 𝑢2 − 𝑣2 = 0 → 𝑢2 = 7
para 𝑥23: 𝑐23 − 𝑢2 − 𝑣3 = 0 → 1 − 𝑢2 − 𝑣3 = 0 → 𝑣3 = −6
para 𝑥31: 𝑐31 − 𝑢3 − 𝑣1 = 0 → 7 − 𝑢3 − 𝑣1 = 0 → 𝑣1= 3
para 𝑥32: 𝑐32 − 𝑢3 − 𝑣2 = 0 → 9 − 𝑢3 − 𝑣2 = 0 → 𝑢3 = 4
para 𝑥42: 𝑐42 − 𝑢4 − 𝑣2 = 0 → 6 − 𝑢4 − 𝑣2 = 0 → 𝑢4 = −1
4) Para as variáveis não básicas calcular: 𝑃𝑖𝑗 = 𝑐𝑖𝑗 − 𝑢𝑖 − 𝑣𝑗
para 𝑥11: 𝑃11 = 𝑐11 − 𝑢1 − 𝑣1 → 𝑃12 = 6 − 0 − 3 = 3
para 𝑥13: 𝑃13 = 𝑐13 − 𝑢1 − 𝑣3 → 𝑃13 = 8 − 0 − (−6) =14
para 𝑥21: 𝑃21 = 𝑐21 − 𝑢2 − 𝑣1 → 𝑃21 = 13 − 7 − 3 = 3
para 𝑥33: 𝑃33 = 𝑐33 − 𝑢3 − 𝑣3 → 𝑃33 = 5 − 4 − (−6) = 7
para 𝑥41: 𝑃41 = 𝑐41 − 𝑢4 − 𝑣1 → 𝑃41 = 10 − (−1) − 3 =8
para 𝑥43: 𝑃43 = 𝑐43 − 𝑢4 − 𝑣3 → 𝑃43 = 4 − −1 − (−6) = 11
Logo, a solução é ótima, pois todos os 𝑃𝑖𝑗 são maiores ou iguais a zero.