Metodos de otmização

EA 044 Planejamento e Análise de Sistemas de Produção

Métodos de Otimização
Discreta

ProfFernandoGomide

©DCA-FEEC-Unicamp

Introdução e Motivação
• Métodos de otimização discreta
– enumeração
– relaxação
– busca
• Maioria dos problemas práticos requer uso de heurísticas

• Busca: determinística e estocástica

2
ProfFernandoGomide

©DCA-FEEC-Unicamp

Enumeração
Enumeração total: resolve problemas de otimização discreta comparando e verificando a factibilidade de todos os valores possíveis das variáveis de decisão (combinações dos valores discretos das variáveis de decisão).

max 7 x1 + 4 x 2 + 19 x3
s.a.
x1 + x3 ≤ 1 x 2 + x3 ≤ 1 x1 , x2 , x3 = 0 ou 1

solução
(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(0, 1, 1)
(1, 0, 0)
(1, 0, 1)
(1, 1, 0)
(1, 1, 1)

objetivo
0
19
4
infactível
7
infactível
11
infactível

solução ótima 3
ProfFernandoGomide

©DCA-FEEC-Unicamp

• Problema com a enumeração total:
– explosão combinatorial
– k variáveis de decisão (binárias) → 2k soluções !

• k = 100 → 2100 ≈ 1030
• computador que verifique 1 trilhão de soluções/segundo = 1012
– 1030 / 1012 = 1018 segundos
– 1018 segundos ≈ 400 milhões de séculos !!

4
ProfFernandoGomide

©DCA-FEEC-Unicamp

Relaxação de Modelos Discretos
• Modelo P é uma relaxação (de restrições) do modelo P se toda solução factível de P também é uma solução factível de P e ambos modelos possuem a mesma função objetivo
• Relaxações devem ser significativamente mais tratáveis que modelos originais. max

20 x1 + 30 x2 − 550 y1 − 720 y 2

s.a.

1.5 x1 + 4 x2 ≤ 300 x1 ≤ 200 y1 x2 ≤ 75 y 2 x1 , x2 ≥ 0

∗
∗
x1 = 200, x2 = 0
∗
y1 = 1,

∗ y2 = 0

v∗ = 3450

y1 , y 2 ∈ {0,1}
5
ProfFernandoGomide

©DCA-FEEC-Unicamp

Restrições Revisadas
1.5 x1 + 4 x 2 ≤ 600

Discussão

x 2 ≤ 150 y 2

• dobra capacidades ótimo: x1 = 400, x2 = 0, y1 = 1, y2 = 0 v = 7450

x1 , x 2 ≥ 0

• não é significativamente mais tratável