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: [email protected]
1
Resolução de PPL’s Inteiros
Seja resolver:
max
x1

19 x 2
x1

20 x 2

50
x1

x2

20
x1
,
x2

Z

cuja solução ótima (contínua) é:
x1 = 18,89
x2 = 1,58 z = 48,42
2
Resolução de PPL’s Inteiros
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
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
Melhor
valor
3
Programação inteira:
Branch-and-Bound
Maximizar
sujeito
z  5 x1  8 x 2
a:
x1  x 2  6
5 x1  9 x 2  45
Exemplo extraído de:
GOLDBARG & LUNA (2005), Otimização
Combinatória, Editora Campus.
x1 , x 2  Z

4
Programação inteira:
Branch-and-Bound
Solução Contínua
9
x1 =
4
x2 =
15
4
Z= 41
1
4
Disjuntiva
15 
15 
x     1  4 ou x    3
2
2
4
4
5
Programação inteira:
Branch-and-Bound
x2
S olu ções In teiras
z= 5x 1 + 8x 2
A
B
5x 1 + 9x 2 = 45
x1 + x2 =6
O
C
x1
6
Programação inteira:
Branch-and-Bound
7
Programação inteira:
Árvore de Branching
P0
x 1 = 2 ,2 5
x
2
= 3 ,7 5
z= 4 1 ,2 5
x 2 
 4 ,0
x 2  3 ,0
P1
P2
x 1 = 1 ,8 x 2 = 4 ,0
z= 4 1
x 1 
 2 ,0
x 1 = 3 ,0
x
2
= 3 ,0
z= 3 9
x 1  1 ,0
P3
In v iáv e l
P4
x 1 = 1 ,0 x 2 = 4 ,4 4
z= 4 0 ,5 6
x 2  5 ,0
P5
x 1 =0
x 2 =5
z= 4 0
x 1  4 ,0
P6
x 1 = 1 ,0 x 2 = 4 ,0
z= 3 7
8
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 x j  x j   1
min z  4 x 1  3 x 2
8 x 1  3 x 2  24
5 x 1  6 x 2  30
x1  2 x 2  9
x1 , x 2  

9
Programação inteira:
Árvore de Branching
10
Programação inteira:
Árvore de Branch-and-Bound
11