Branch And Bound 1n1b2s

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 x2

x1 x1

 20 x2  x2

 

x1

,

 Z

x2

50 20

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

Melhor valor

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

3

Programação inteira: Branch-and-Bound Maximizar z  5 x1  8 x2 sujeito a : x1  x2  6 5 x1  9 x2  45 Exemplo extraído de: GOLDBARG & LUNA (2005), Otimização Combinatória, Editora Campus.

x1 , x2  Z

 4

Programação inteira: Branch-and-Bound

Solução Contínua 9 x1 = 4

15 x2 = 4

1 Z= 41 4

Disjuntiva

15  15  x2     1  4 ou x2    3 4 4 5

Programação inteira: Branch-and-Bound x2 Soluções Inteiras

A

z=5x1 +8x2

B 5x1 + 9x2 =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 x 1 = 3 ,0 x 2 = 3 ,0 z= 3 9

P2 x 1 = 1 , 8 x 2 = 4 ,0 z= 4 1 x 1  2 , 0

x 1  1 ,0

P3 I n 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 x1  3 x2 8 x1  3x2  24 5 x1  6 x2  30

x1  2 x2  9 x1 , x2   

9

Programação inteira: Árvore de Branching

10

Programação inteira: Árvore de Branch-and-Bound

11