Branch and Bound

IFES

Parte 01

Programação Linear Inteira
O método de resolução do modelo de programação inteira, em geral, é pior e mais complexo que o método Simplex. n Max Z =

c

j

. xj

ij

. x j  bi

j 1 n s.a.

a j 1

x  0 (contínuo)

x  Inteiro +

Aplicação: Problema uma restrição ou a outra (  do problema e). x2 E

F.O.

D

max Z = 3 x1 + 2 x2
s.t.

F

2 x1  x 2  4
 x1  2 x 2  4

ou 

x1; x2  0
A

B

C x1

Região Viável do problema "e": ABDF
Ponto Ótimo do problema "e": F
Ponto Ótimo do problema "ou": C
Modelagem do problema:
Max Z = 3 x1 + 2 x2
s.t.
(a) 2 x1  x 2  4  yM
(b) x1  2 x 2  4  (1  y ) M

OU 

x1; x2  0 y = {0; 1}
Logo:
se y = 0 se y = 1




(a) = ativa (desativo b)
(b) = ativa (desativo a)

IFES

Parte 01

Resolução do PPI:
Arredondamento não funciona!!!
1. Primeiro problema do arredondamento: perde-se a viabilidade do problema
Ex.1: Max Z = x1 + 2 x2
s.t.

x1 + x2  16,5
-x1 + x2  3,5 x1; x2  Z (inteiro)

x2

10

A
F.O.

x1
6,5
Ponto A = (6,5; 10) Ponto ótimo solução contínua
Arredondando:

 B  (6;10)

C  (7;10)



não faz parte da região convexa

IFES

Parte 01

2. Segundo problema do arredondamento: perde-se a otimalidade do problema
Ex.2: Max Z = x1 + 5 x2 x1 + 10 x2  20 x1  2 x1; x2  Z (inteiro)

s.t.

x2

D

B
A
C

1

F.O.

x1
1

2

Ponto A = (2; 1,8) Ponto ótimo solução contínua 
Arredondando:

B  (2; 2) inviável

C  (2;1) não ótimo

Ponto D = (0; 2) Ponto ótimo solução inteira

O que funciona???

Branch and Bound

F.O. (A) = 11



F.O. (C) = 7



F.O. (D) = 10

IFES

Parte 01

BRANCH AND BOUND
Max Z = 2x1 + x2
s.t.
2x1 + 2x2  9
-2x1 - 2x2  5
2x1 - 2x2  3 x1; x2  Z (inteiro)
BRANCH
PPL 0
X1=3
X2=1,5
Z=7,5

x2  1

1ª Iteração:
Os dois ramos com soluções não inteiras

x2  2

PPL 1a
X1= 2,5
X2=1
Z=6