questão branch-and-bound

Prévia do material em texto

Z= 4x1 + 2x2 
X2 = x2 
5- x1 = 21/2 – 6x1/2 x1 = 2,75 
Logo: x2= 5 – x1 = 5 – 2,75 x2 = 2,25 
x1 x2 
2,75 2,25 
Z= 4(2,75) + 2(2,25) 
Z = 15,5 
 
 
 
 
Max Z = 4x1 + 2x2 
S.a 
x1 + x2 <= 5 
-x1+ x2 <= 0 
6x1 + 2x2 <= 21 
x1,x2>=0 e inteiros 
 
 
 
 
 
 
 
Método Gráfico 
 
Pontos: 
B: (0;0)  Z= 4(0)+2(0)= 0 
D: (2,5;2,5)  Z= 4(2,5)+2(2,5)= 15 
E: (2,75;2,25)  Z= 4(2,75)+2(2,25)= 15,5 
G: (3,5;0)  Z= 4(3,5)+2(0)= 14 
O Valor máximo da função objetivo ocorre no ponto E, sendo x1 = 2,75 e x2=2,25. Logo a 
solução ótima é x1=2,75 , x2= 2,25 e Z= 15,5. 
 
 
Restrição 1 
x1 + x2 ≤ 5 
x2 = 5 – x1 
x1 x2 
0 5 
5 0 
 
 
 
 
Restrição 2 
-x1 + x2 ≤ 0 
x2 = 0 – x1 
x1 x2 
0 0 
0 0 
 
 
 
 
Restrição 3 
6x1 + 2x2 ≤ 21 
x2 = 5 – x1 
x1 x2 
0 10,5 
3,5 0 
 
 
 
 
Método Branch-and-Bound 
 
Solução: Z=14 e x1= 3 x2= 1 
Ramificação B: Z= 4x1 + 2x2 Z = 4 (2) + 2 (2) = Z=12 
Ramificação C: Z= 4x1 + 2x2 Z = 4 (3) + 2 (1,5) = Z=15 
Ramificação D: Z= 4x1 + 2x2 Z = 4 (3,17) + 2 (1) = Z= 14,7 
Ramificação E: Inviável 
Ramificação F: Z= 4x1 + 2x2 Z = 4 (3) +2 (1) = Z=14 
Ramificação G: Inviável