Método de otimização discreta - unicamp

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 s.a.

20 x1 + 30 x2 − 550 y1 − 720 y 2 1.5 x1 + 4 x2 ≤ 300 x1 ≤ 200 y1 x2 ≤ 75 y 2 x1 , x2 ≥ 0 y1 , y 2 ∈ {0,1}
5

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

v∗ = 3450

ProfFernandoGomide

©DCA-FEEC-Unicamp

Restrições Revisadas
1.5 x1 + 4 x 2 ≤ 600 x1 ≤ 400 y1 x 2 ≤ 150 y 2 x1 , x 2 ≥ 0 y1 , y 2 ∈ {0,1}

Discussão

• dobra capacidades ótimo: x1 = 400, x2 = 0, y1 = 1, y2 = 0 v = 7450 • não é significativamente mais tratável

x1 ≤ 200 y1 x2 ≤ 75 y2 x1 , x2 ≥ 0 y1 , y2