3. The following model is being solved using the branch and bound technique with LP relaxations for bounding. Current solution tree is given in the following figure. The values in parenthesis are the optimal solution vectors of LP relaxations; for example, the solution to the first LP relaxation is (X1, X2, X3, X4) = (5/6,0, 1, 1). max 2 = 9x1 +4x2 +5x3 +6x4 s.t. 6x1 Subproblem 1 (5/6, 0, 1, 1) z = 18.5 1 x1, +4x2+2x3 +2x4 9 0

3. The following model is being solved using the branch and bound technique with L.P relaxations for bounding. Current solution tree is given in the following figure. The values in parenthesis are the optimal solution vectors 1 of L.P relaxations; for example, the solution to the first L.P relaxation is (x1,x2,x1,x4)=(5/6,0,1,1) maxz=9x1+4x2+5x3+6x4s.t.6x1+4x2+2x3+2x4x2x2x1,x3901{0,1}{0,1}{0,1} (a) (8 pts) What are the largest and the least values the optimal objective function value can take according to the current tree? (b) (16 pts) Complete the solution procedure and find the optimal solution of the problen. Show explicitly each fathoming or branching operation