Branch and Bound

Prévia do material em texto

1 
Branch-and-Bound 
Marcone Jamilson Freitas Souza 
 
 
Departamento de Computação 
Programa de Pós-Graduação em Ciência da Computação 
Universidade Federal de Ouro Preto 
http://www.decom.ufop.br/marcone 
E-mail: marcone.freitas@yahoo.com.br 
2 
Resolução de PPL’s Inteiros 
Seja resolver: 




Zxx
xx
xx
xx
21
21
21
21
,
20
5020
19max
cuja solução ótima (contínua) é: 
x1 = 18,89 x2 = 1,58 z = 48,42 
3 
Resolução de PPL’s Inteiros 
No entanto, a solução ótima inteira é: 
x1 = 10 x2 = 2 z = 48 
isto é, o erro é de 21% no arredondamento. 
Conclusão: Não é uma boa estratégia resolver o PPL (contínuo) e 
arredondar a solução resultante 
Aplicando a estratégia de arredondamento, uma vez que os valores 
ótimos são fracionários, e providenciando uma busca racional no 
entorno do ponto ótimo, teríamos: 
x1 x2 Z=x1+19*x2 
19 2 Inviável 
19 1 38 
18 2 Inviável 
18 1 37 
Melhor 
valor 
4 
Programação inteira: 
Branch-and-Bound 




Zxx
xx
xx
xxz
21
21
21
21
,
4595
6
:asujeito
85Maximizar
Exemplo extraído de: 
GOLDBARG & LUNA (2005), Otimização 
Combinatória, Editora Campus. 
5 
3 
4 
15 
2 
  
 
 
 
 
 
 x ou 4 1 
4 
15 
2 
   
 
 
 
 
 
 x 
x1 = 
9 
4 
x2 = 
15 
4 
Z= 
1 
4 
41 
Disjuntiva 
Solução Contínua 
Programação inteira: 
Branch-and-Bound 
6 
x2
x1O
z=5x1 +8x2 
5x1 + 9x2 =45
x1 + x2 =6
Soluções Inteiras
A
B
C
Programação inteira: 
Branch-and-Bound 
7 
Programação inteira: 
Branch-and-Bound 
8 
 
 P 0 
x 1 =2,25 x 2 =3,75 
 z=41,25 
 P 2 
x 1 =1,8 x 2 =4,0 
 z=41 
 P 1 
x 1 =3,0 x 2 =3,0 
 z=39 
 P 3 
 Inviável 
 P 4 
x 1 =1,0 x 2 =4,44 
 z=40,56 
 P 5 
 x 1 =0 x 2 =5 
 z=40 
 P 6 
 x 1 =1,0 x 2 =4,0 
 z=37 
x 2  4,0  x 2  3,0 
x 1  2,0  x 1  1,0 
x 2  5,0 x 1  4,0 
 
Programação inteira: 
Árvore de Branching 
9 
Programação inteira: 
Branch-and-Bound 
 Resolva pelo método Branch-and-Bound o PLI abaixo 
 Use a variante de Dank para decidir a variável a ramificar 
(Nessa variante, a variável a ramificar é aquela cujo valor está 
mais próximo de um valor inteiro) 
 Em caso de empate, escolha a de menor índice 
 Use busca em profundidade e analise primeiro o valor maior 
da variável ramificada, isto é, o valor 
21 34min xxz 
2438 21  xx
3065 21  xx
92 21  xx
21, xx
  1 jj xx
10 
Programação inteira: 
Árvore de Branching 
11 
Programação inteira: 
Árvore de Branch-and-Bound