Answer Happy

I. A student solved the following integer programming (IP) problem using the branch and bound method. Max z=5x1+4x2 x1+x2 < 5 10x1 + 6x2 s 45 x1, x2, non-negative and integer The order he/she used to solve the 7 subproblems is indicated by the numbers inside each circle at the top of each box (i.e. subproblem). Original Oder: X1=3.75 X2=1.25 Z=23.75 X1<=3 (7) X1=3 X2=2 Z=23 (2 X1=4 X2=0.83 Z=23.33 (3 (4 X1=4.5 X2=0 Z=22.5 Non feasible (6) x1=4 X2=0 Z=20 Non feasible 1. (5%) In the diagram above, complete the mation that goes over each branch of the tree (i.e. above the lines) and identify the subproblem that represents an upper bound for this IP problem Box number: upper bound:
2. (5%) Write what was the first lower bound he/she found when solving this IP problem? (Specify box number (i.e. subproblem), x's values, and the value for z) Box number: x's values: z: 3. (5%) What is the optimal solution to this problem? (Specify the box number (i.e. subproblem), the values for the x's, and the value for z) Box number: x's values: Z: 4. (5%) If he/she uses the branch and bound method but a different order to solve the subproblems, as shown in the figure on the next page, which subproblems(use the node numbers inside the circle) need to be cross out or deleted because they are not necessary to solve.