Consider the following optimisation problem: MAX: 3X15X2 Subject to: 2X1 + 4X2 25 X1 8 2X2...

Transcribed Image Text:

Consider the following optimisation problem: MAX: 3X15X2 Subject to: 2X1 + 4X2 25 X1 8 2X2 10 0 X2 0 X1, X2 must be integers (a) Solve the problem by breaking it into multiple subproblems using the Branch and Bound algorithm. Implement and solve each of the subproblems into a separate sheet under the same Excel workbook. (When solving each individual subproblem in Excel, do NOT apply the integrality condition.) Save it as a single Excel file (with multiple sheets) and upload it under the textbox provided. [3 points] (b) Create a Branch and Bound Tree diagram to show the steps you have completed. Save it as a PNG file and upload it under the textbox provided. [3 points] Hints and instructions: . You may need to apply constraints on a decision variable multiple times. (i.e. your Branch and Bound Tree diagram can have more than 4 layers). No further branching for the current sub-problem is needed if 1) all decision variables in the current sub-problem are integers, 2) the solver cannot find a feasible solution for the current sub- problem, or 3) the objective function value of the current sub-problem is not as good as that of another feasible solution that has been found so far. When any of these happens, add a horizontal bar under the circle of your sub-problem. For case 2), put the word "Infeasible" inside the circle of the sub-problem, instead of the decision variables and the objective function value. For case 3), put "Early termination" under the bar. Put "Optimal" under the bar of the sub-problem that can yield the best objective function value. The first two sub-problems have been done for you. Their corresponding Excel sheets and Branch and Bound Tree diagram (half completed) can be found below Put "Optimal" under the bar of the sub-problem that can yield the best objective function value. The first two sub-problems have been done for you. Their corresponding Excel sheets and Branch and Bound Tree diagram (half-completed) can be found below. Problem 1 X =8.0 X 2 Problem 1-1 X =2.25 OFV=32.25 X 23 X =8.0 X =2.0 OFV=34 Consider the following optimisation problem: MAX: 3X15X2 Subject to: 2X1 + 4X2 25 X1 8 2X2 10 0 X2 0 X1, X2 must be integers (a) Solve the problem by breaking it into multiple subproblems using the Branch and Bound algorithm. Implement and solve each of the subproblems into a separate sheet under the same Excel workbook. (When solving each individual subproblem in Excel, do NOT apply the integrality condition.) Save it as a single Excel file (with multiple sheets) and upload it under the textbox provided. [3 points] (b) Create a Branch and Bound Tree diagram to show the steps you have completed. Save it as a PNG file and upload it under the textbox provided. [3 points] Hints and instructions: . You may need to apply constraints on a decision variable multiple times. (i.e. your Branch and Bound Tree diagram can have more than 4 layers). No further branching for the current sub-problem is needed if 1) all decision variables in the current sub-problem are integers, 2) the solver cannot find a feasible solution for the current sub- problem, or 3) the objective function value of the current sub-problem is not as good as that of another feasible solution that has been found so far. When any of these happens, add a horizontal bar under the circle of your sub-problem. For case 2), put the word "Infeasible" inside the circle of the sub-problem, instead of the decision variables and the objective function value. For case 3), put "Early termination" under the bar. Put "Optimal" under the bar of the sub-problem that can yield the best objective function value. The first two sub-problems have been done for you. Their corresponding Excel sheets and Branch and Bound Tree diagram (half completed) can be found below Put "Optimal" under the bar of the sub-problem that can yield the best objective function value. The first two sub-problems have been done for you. Their corresponding Excel sheets and Branch and Bound Tree diagram (half-completed) can be found below. Problem 1 X =8.0 X 2 Problem 1-1 X =2.25 OFV=32.25 X 23 X =8.0 X =2.0 OFV=34