Slide - Exemplo Resolvido Branch-and-bound - 2023-2

Branch-and-Bound Exemplo 2 (extraído de ...) Objetivo: entender as técnicas de resolução de problemas de PIM implementadas em computador. Pode ser útil para definir como será a busca (largura ou profundidade) de acordo com o hardware disponível. 𝑀𝑖𝑛 𝑧 = −𝑥1 − 2𝑥2 s.a. −𝑥1 + 𝑥2 ≤ 2,2 4𝑥1 + 5𝑥2 ≤ 26 7𝑥1 + 3𝑥2 ≤ 32 𝑥1, 𝑥2 inteiros Resolver o Problema abaixo usando Branch-and- Bound (por quadros). 𝑀𝑖𝑛 𝑧 = −𝑥1 − 2𝑥2 s.a. −𝑥1 + 𝑥2 ≤ 2,2 4𝑥1 + 5𝑥2 ≤ 26 7𝑥1 + 3𝑥2 ≤ 32 𝑥1, 𝑥2 inteiros Problema a ser resolvido 𝑀𝑖𝑛 𝑧 = −𝑥1 − 2𝑥2 s.a. −𝑥1 + 𝑥2 ≤ 2,2 4𝑥1 + 5𝑥2 ≤ 26 7𝑥1 + 3𝑥2 ≤ 32 Problema relaxado 𝑀𝑎𝑥 𝑧 = +𝑥1 + 2𝑥2 s.a. −𝑥1 + 𝑥2 ≤ 2,2 4𝑥1 + 5𝑥2 ≤ 26 7𝑥1 + 3𝑥2 ≤ 32 Como maximização 𝑀𝑎𝑥 𝑧 − 𝑥1 − 2𝑥2 = 0 s.a. −𝑥1 + 𝑥2 + 𝑥3 = 2,2 4𝑥1 + 5𝑥2 + 𝑥4 = 26 7𝑥1 + 3𝑥2 + 𝑥5 = 32 Forma Padrão Preparação 𝑀𝑎𝑥 𝑧 − 𝑥1 − 2𝑥2 = 0 s.a. −𝑥1 + 𝑥2 + 𝑥3 = 2,2 4𝑥1 + 5𝑥2 + 𝑥4 = 26 7𝑥1 + 3𝑥2 + 𝑥5 = 32 Forma Padrão z x1 x2 x3 x4 x5 b 1 -1 -2 0 0 0 0 X3 0 -1 1 1 0 0 2,2 X4 0 4 5 0 1 0 26 X5 0 7 3 0 0 1 32 Quadro z x1 x2 x3 x4 x5 b 1 -1 -2 0 0 0 0 X3 0 -1 1 1 0 0 2,2 X4 0 4 5 0 1 0 26 X5 0 7 3 0 0 1 32 O ATIVO Nós ativos precisam ser resolvidos ou podados. Ocupam espaço na memória até uma das duas coisas acontecer. Z=9 X1=2,3 X2=3,4 O A B X2<=3 ATIVO ATIVO z x1 x2 x3 x4 x5 b 1 -1 -2 0 0 0 0 X3 0 -1 1 1 0 0 2,2 2,2 X4 0 4 5 0 1 0 26 5,2 X5 0 7 3 0 0 1 32 11 O z x1 x2 x3 x4 x5 b 1 -2 0 2 0 0 4,4 X2 0 -1 1 1 0 0 2,2 X4 0 6,5 0 -5 1 0 15 2,3 X5 0 8,5 0 -3 0 1 25 3 z x1 x2 x3 x4 x5 b 1 0 0 0,5 0,3 0 9 X2 0 0 1 0,6 0,1 0 3,4 X1 0 1 0 -1 0,2 0 2,3 X5 0 0 0 3,5 -1 1 5,8 O SIMPLEX parte de uma solução viável e tenta deixa-la melhor aumentando o valor da FO (para o casos de maximização). Valores negativos na linha da FO indicam possibilidade de melhorar a solução. X2>=4 Como a solução não deu resultados inteiros (apenas para as variáveis de decisão, a FO não tem essa restrição), escolhemos a que tiver parte fracionária mais próxima de 0,5 para gerar os filhos. Z=9 X1=2,3 X2=3,4 O A B X1<=2 ATIVO ATIVO O X2>=4 x2<=3 x2+x6=3 Z x1 x2 x3 x4 x5 x6 b 1 0 0 0,5 0,3 0 0 9 ? 0 0 1 0,6 0,1 0 0 3,4 ? 0 1 0 -1 0,2 0 0 2,3 ? 0 0 0 3,5 -1 1 0 5,8 ? 0 0 1 0 0 0 1 3 z x1 x2 x3 x4 x5 x6 b 1 0 0 0,5 0,3 0 0 9 X2 0 0 1 0,6 0,1 0 0 3,4 X1 0 1 0 -1 0,2 0 0 2,3 X5 0 0 0 3,5 -1 1 0 5,8 X6 0 0 0 -1 -0 0 1 -0 -1 -4 Z x1 x2 x3 x4 x5 x6 b 1 0 0 0 0,3 0 0,8 8,8 X2 0 0 1 0 0 0 1 3 X1 0 1 0 0 0,3 0 -1 2,8 X5 0 0 0 0 -2 1 5,8 3,8 X3 0 0 0 1 0,1 0 -2 0,6 A A ATIVO X1>=3 Z=8,8 X1=2,8 X2=3 O DUAL SIMPLEX parte de uma solução inviável e tenta deixa-la melhor diminuindo o valor da FO (para o casos de maximização). Valores negativos na coluna de b indicam possibilidade de melhorar a solução. Caso não haja valores negativos na linha para o valor negativo de b, não se pode usar o DUAL SIMPLEX. Z=9 X1=2,3 X2=3,4 O A B X1<=2 ATIVO PODA POR INFACTIBILIDADE O X2>=4 A A ATIVO X1>=3 Z=8,8 X1=2,8 X2=3 x2>=4 x2 - x6 = 4 z x1 x2 x3 x4 x5 x6 b 1 0 0 0,5 0,3 0 0 9 ? 0 0 1 0,6 0,1 0 0 3,4 ? 0 1 0 -1 0,2 0 0 2,3 ? 0 0 0 3,5 -1 1 0 5,8 ? 0 0 1 0 0 0 -1 4 z x1 x2 x3 x4 x5 x6 b 1 0 0 0,5 0,3 0 0 9 ? 0 0 1 0,6 0,1 0 0 3,4 ? 0 1 0 -1 0,2 0 0 2,3 ? 0 0 0 3,5 -1 1 0 5,8 ? 0 0 0 -1 -0 0 -1 0,6 z x1 x2 x3 x4 x5 x6 b 1 0 0 0,5 0,3 0 0 9 X2 0 0 1 0,6 0,1 0 0 3,4 X1 0 1 0 -1 0,2 0 0 2,3 X5 0 0 0 3,5 -1 1 0 5,8 X6 0 0 0 0,6 0,1 0 1 -1 Todos os valores da linha do b negativo são positivos. Não é possível usar DUAL SIMPLEX. Z=9 X1=2,3 X2=3,4 O A B PODA POR OTIMALIDADE (INTEGRALIDADE) PODA POR INFACTIBILIDADE O X2>=4 A A ATIVO X1>=3 Z=8,8 X1=2,8 X2=3 x1<=2 x1+x7=2 z x1 x2 x3 x4 x5 x6 x7 b 1 0 0 0 0,3 0 0,8 0 8,8 ? 0 0 1 0 0 0 1 0 3 ? 0 1 0 0 0,3 0 -1 0 2,8 ? 0 0 0 0 -2 1 5,8 0 3,8 ? 0 0 0 1 0,1 0 -2 0 0,6 ? 0 1 0 0 0 0 0 1 2 z x1 x2 x3 x4 x5 x6 x7 b 1 0 0 0 0,3 0 0,8 0 8,8 X2 0 0 1 0 0 0 1 0 3 X1 0 1 0 0 0,3 0 -1 0 2,8 X5 0 0 0 0 -2 1 5,8 0 3,8 X3 0 0 0 1 0,1 0 -2 0 0,6 X7 0 0 0 0 -0 0 1,3 1 -1 -1 z x1 x2 x3 x4 x5 x6 x7 b 1 0 0 0 0 0 2 1 8 X2 0 0 1 0 0 0 1 0 3 X1 0 1 0 0 0 0 0 1 2 X5 0 0 0 0 0 1 -3 -7 9 X3 0 0 0 1 0 0 -1 0,5 0,2 X4 0 0 0 0 1 0 -5 -4 3 Z=8 X1=2 X2=3 Z=9 (2,3 ; 3,4) O A B PODA POR OTIMALIDADE (INTEGRALIDADE) PODA POR NFACTIBILIDADE O X2>=4 A A X1>=3 Z=8,8 (2,8 ; 3) Z=8,6 (3 ; 2,8) x1>=3 x1-x7=3 z x1 x2 x3 x4 x5 x6 x7 b 1 0 0 0 0,3 0 0,8 0 8,8 0 0 1 0 0 0 1 0 3 0 1 0 0 0,3 0 -1 0 2,8 0 0 0 0 -2 1 5,8 0 3,8 0 0 0 1 0,1 0 -2 0 0,6 0 1 0 0 0 0 0 -1 3 z x1 x2 x3 x4 x5 x6 x7 b 1 0 0 0 0,3 0 0,8 0 8,8 0 0 1 0 0 0 1 0 3 0 1 0 0 0,3 0 -1 0 2,8 0 0 0 0 -2 1 5,8 0 3,8 0 0 0 1 0,1 0 -2 0 0,6 0 0 0 0 -0 0 1,3 -1 0,3 z x1 x2 x3 x4 x5 x6 x7 b 1 0 0 0 0,3 0 0,8 0 8,8 0 0 1 0 0 0 1 0 3 0 1 0 0 0,3 0 -1 0 2,8 0 0 0 0 -2 1 5,8 0 3,8 0 0 0 1 0,1 0 -2 0 0,6 0 0 0 0 0,3 0 -1 1 -0 -1 z x1 x2 x3 x4 x5 x6 x7 b 1 0 0 0 0,4 0 0 0,6 8,6 0 0 1 0 0,2 0 0 0,8 2,8 0 1 0 0 0 0 0 -1 3 0 0 0 0 -1 1 0 4,6 2,6 0 0 0 1 -0 0 0 -1 0,9 0 0 0 0 -0 0 1 -1 0,2 A A X2>=3 X2<=2 ATIVO ATIVO Z=8 (2 ; 3) X2<=3 X1<=2 Se z fosse menor que 8,0 (valor da melhor poda por otimalidade), haveria poda por qualidade. Como não aconteceu, geram-se os dois filhos, pois existe possibilidade de valor melhor que 8,0 enquanto z for maior que 8,0. Z=9 (2,3 ; 3,4) O A B PODA POR OTIMALIDADE (INTEGRALIDADE) PODA POR INFACTIBILIDADE O X2>=4 A A X1>=3 Z=8,8 (2,8 ; 3) Z=8,6 (3 ; 2,8) A A X2>=3 X2<=2 PODA POR QUALIDADE ATIVO Z=8 (2 ; 3) X2<=3 X1<=2 x2<=2 x2+x8=2 z x1 x2 x3 x4 x5 x6 x7 x8 b 1 0 0 0 0,4 0 0 0,6 0 8,6 0 0 1 0 0,2 0 0 0,8 0 2,8 0 1 0 0 0 0 0 -1 0 3 0 0 0 0 -1 1 0 4,6 0 2,6 0 0 0 1 -0 0 0 -1 0 0,9 0 0 0 0 -0 0 1 -1 0 0,2 0 0 1 0 0 0 0 0 1 2 z x1 x2 x3 x4 x5 x6 x7 x8 b 1 0 0 0 0,4 0 0 0,6 0 8,6 0 0 1 0 0,2 0 0 0,8 0 2,8 0 1 0 0 0 0 0 -1 0 3 0 0 0 0 -1 1 0 4,6 0 2,6 0 0 0 1 -0 0 0 -1 0 0,9 0 0 0 0 -0 0 1 -1 0 0,2 0 0 0 0 -0 0 0 -1 1 -1 -2 -1 z x1 x2 x3 x4 x5 x6 x7 x8 b 1 0 0 0 0,3 0 0 0 0,8 8 0 0 1 0 0 0 0 0 1 2 0 1 0 0 0,3 0 0 0 -1 4 0 0 0 0 -2 1 0 0 5,8 -2 0 0 0 1 0,1 0 0 0 -2 2,2 0 0 0 0 0 0 1 0 -1 1 0 0 0 0 0,3 0 0 1 -1 1 -0,1 z x1 x2 x3 x4 x5 x6 x7 x8 b 1 0 0 0 0 0,1 0 0 1,6 7,7 0 0 1 0 0 0 0 0 1 2 0 1 0 0 0 0,1 0 0 -0 3,7 0 0 0 0 1 -1 0 0 -3 1,1 0 0 0 1 0 0,1 0 0 -1 2,1 0 0 0 0 0 0 1 0 -1 1 0 0 0 0 0 0,1 0 1 -0 0,7 Z=7,7 (3,7 ; 2) Z=9 (2,3 ; 3,4) O A B PODA POR OTIMALIDADE (INTEGRALIDADE) PODA POR INFACTIBILIDADE O X2>=4 A A X1>=3 Z=8,8 (2,8 ; 3) Z=8,6 (3 ; 2,8) A A X2>=3 X2<=2 PODA POR QUALIDADE Z=8 (2 ; 3) X2<=3 X1<=2 Z=7,7 (3,7 ; 2) x2>=3 x2-x8=3 z x1 x2 x3 x4 x5 x6 x7 x8 b 1 0 0 0 0,4 0 0 0,6 0 8,6 0 0 1 0 0,2 0 0 0,8 0 2,8 0 1 0 0 0 0 0 -1 0 3 0 0 0 0 -1 1 0 4,6 0 2,6 0 0 0 1 -0 0 0 -1 0 0,9 0 0 0 0 -0 0 1 -1 0 0,2 0 0 1 0 0 0 0 0 -1 3 z x1 x2 x3 x4 x5 x6 x7 x8 b 1 0 0 0 0,4 0 0 0,6 0 8,6 0 0 1 0 0,2 0 0 0,8 0 2,8 0 1 0 0 0 0 0 -1 0 3 0 0 0 0 -1 1 0 4,6 0 2,6 0 0 0 1 -0 0 0 -1 0 0,9 0 0 0 0 -0 0 1 -1 0 0,2 0 0 0 0 -0 0 0 -1 -1 0,2 z x1 x2 x3 x4 x5 x6 x7 x8 b 1 0 0 0 0,4 0 0 0,6 0 8,6 0 0 1 0 0,2 0 0 0,8 0 2,8 0 1 0 0 0 0 0 -1 0 3 0 0 0 0 -1 1 0 4,6 0 2,6 0 0 0 1 -0 0 0 -1 0 0,9 0 0 0 0 -0 0 1 -1 0 0,2 0 0 0 0 0,2 0 0 0,8 1 -0,1 PODA POR INFACTIBILIDADE Resposta ótima do problema de PI (a melhor resposta de todas as podas por otimalidade, no caso de haver mais de uma): X1=2 e X2=3 Busca em Profundidade • Usa menos memória e mais processamento (ou seja, é mais lento mas usa menos memória). Em caso de haver mais de uma opção de caminho na árvore de solução, escolhe-se o nó mais profundo dentre os ativos. Busca em Largura • Usa mais memória e menos processamento (ou seja, é mais rápido mas precisa de mais memória física). Escolhe-se o nó ativo com maior valor da FO. Como você escolheria entre as Buscas?