1

Branch-and-Bound

Marcone Jamilson Freitas Souza

Departamento de ComputaçãoPrograma de Pós-Graduação em Ciência da Computação

Universidade Federal de Ouro Pretohttp://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:Programação inteira:Branch-and-BoundBranch-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

34

152

xou41

4

152

x

x1 =9

4x2 =

15

4Z=

1

441

Disjuntiva

Solução Contínua

Programação inteira:Programação inteira:Branch-and-BoundBranch-and-Bound

6

x2

x1O

z=5x1 +8x2

5x1 + 9x2 =45

x1 + x2 =6

Soluções Inteiras

AB

C

Programação inteira:Programação inteira:Branch-and-BoundBranch-and-Bound

7

Programação inteira:Programação inteira:Branch-and-BoundBranch-and-Bound

8

P 0 x 1 = 2 , 2 5 x 2 = 3 , 7 5 z = 4 1 , 2 5

P 2 x 1 = 1 , 8 x 2 = 4 , 0 z = 4 1

P 1 x 1 = 3 , 0 x 2 = 3 , 0 z = 3 9

P 3 I n v i á v e l P 4

x 1 = 1 , 0 x 2 = 4 , 4 4 z = 4 0 , 5 6

P 5 x 1 = 0 x 2 = 5 z = 4 0

P 6 x 1 = 1 , 0 x 2 = 4 , 0 z = 3 7

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:Programação inteira:Árvore de BranchingÁ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 xx21, xx

1 jj xx

10

Programação inteira:Programação inteira:Árvore de BranchingÁrvore de Branching

11

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