Consider the following optimisation problem: MAX: 3X + 5X Subject to: 2X + 4X < 25...

Transcribed Image Text:

Consider the following optimisation problem: MAX: 3X₁ + 5X₂ Subject to: 2X₁ + 4X₂ < 25 X₁ < 8 2X₂ 10 X₁ 0 X₂20 X₁, 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 hav 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 tha 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 no 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 an 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. Decision Variable X1 Values Coefficients Constraints Coefficients Coefficients Coefficients 00 m 8 3 210 X2 2.25 Obj Val 5 402 35.25 25 00 in 8 4.5 25 8 10 Decision Variable Values Coefficients Constraints Coefficients Coefficients Coefficients Coefficients X1 8 003 210 0 X2 2 Obj Val 5 4 JONA 0 2 1 34 24 8 00N 4 2 25 8 10 2 Problem 1-1 X.=8.0 X₁-2.0 OFV-34 X₂2 Proziem X, -8.0 X, 2.25 OFV=32.25 X₂23 Consider the following optimisation problem: MAX: 3X₁ + 5X₂ Subject to: 2X₁ + 4X₂ < 25 X₁ < 8 2X₂ 10 X₁ 0 X₂20 X₁, 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 hav 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 tha 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 no 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 an 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. Decision Variable X1 Values Coefficients Constraints Coefficients Coefficients Coefficients 00 m 8 3 210 X2 2.25 Obj Val 5 402 35.25 25 00 in 8 4.5 25 8 10 Decision Variable Values Coefficients Constraints Coefficients Coefficients Coefficients Coefficients X1 8 003 210 0 X2 2 Obj Val 5 4 JONA 0 2 1 34 24 8 00N 4 2 25 8 10 2 Problem 1-1 X.=8.0 X₁-2.0 OFV-34 X₂2 Proziem X, -8.0 X, 2.25 OFV=32.25 X₂23

Answer rating: 100% (QA)

a I have solved the subproblems using Branch and Bound algorithm by breaking it into multiple sheets ... View the full answer