Questão branch-and-bound e metodo grafico

Prévia do material em texto

2 - Resolva o problema de programação Inteira abaixo através do método gráfico e do 
algoritmo branch-and-bound. Registre os valores de x1, x2 e Z na árvore de soluções. 
Selecione x2 como a variável de ramificação no nó 0 da árvore. 
Min Z = 4x1 + 5x2 
S.a 
x1 + 4x2 >= 5 
3x1+ 2x2 >= 7 
x1,x2>=0 e inteiros 
 
 
 
 
 
 
 
 
Árvore 
 
 
 
 
 
 
 
 
 
 
 
 
 
Solução: Z=13 e x1= 2 x2= 1 
Restrição 1 
x1 + 4x2 ≥ 5 
x2 = 1,25 – 0,25x1 
x1 x2 
0 1,25 
5 0 
 
 
 
 
Restrição 2 
3x1 + 2x2 ≥ 7 
x2 = 3,5 – 1,5x1 
x1 x2 
0 3,5 
2,333 0 
 
 
 
 
Z= 11,2 
X1= 1,8 
X2= 0,8 
Z= 20 
X1= 0 
X2= 5 
Z= 11,66 
X1= 1,666 
X2= 1 
Z= 14 
X1= 1 
X2= 2 
Z= 13 
X1= 2 
X2= 1 
X1≤0 
X1≥2 X1≤1 
X1≥1 
2 3 
4 5 
Z= 4x1 + 2x2 
X2 = x2 
1,25- 0,25x1 = 3,5 – 1,5x1 x1 = 1,8 
 
Logo: x2= 1,25 -0,25(1,8) x2= 1,25-0,45 x2 = 0,8 
 
x1 x2 
1,8 0,8 
Z= 4(1,8) + 5(0,8) 
Z = 11,2