Question

Question 3 : Branch and Bound max 36a1282+8as s.t. 21i + 20r2 6xs 23 a e 10, 1]3 Write the LP Relaxation of this problem. 1. 2. What type of problem is this? (this type of problem has a particular name) Solve this problem by branch-and-bound, using the branching rule for binary variables of branching o 3. the most fractional variable. On the next page, write down the branch-and-bound tree you obtained. a. Each node should include the solution letter, objective function value, and variable values. b. Write the branching decision used on each branch of the tree clearly along the branch. c. Indicate clearly on your tree which nodes are leaf nodes (the end of the tree) d. Indicate clearly on your tree where pruning has occurred and why e. Identify the optimal integer solution. nay use the information that x-(1,0,0) is feasible for the Integer Program, with objective value 36. the solution to the LP relaxation at a node of the branch-and-bound tree, you may find the t termine helpful. In the table are listed solutions for the LP relaxations at the nodes of the branch-and-bound tree, together with other points that are feasible for the LP relaxation of the problem. The points are listed in decreasing order of their LP objective value.

Answer 1

Answer: - 1).

Solution Find solution using Branch and Bound method MAX Z-36x1 + 28x2 + 8x3 subject to 21x1 + 20x2 6x3 23 and x1,x2,x3 >= 0 Solution Solution stpes by BigM method Max Z 36x 28x8x3 subject to 2131-20x-6x s 23 and x1,x2, x3 2 0; Solution is Max Z4-39 4286 (x1 = 1.0952, x,-0, x,-0) and Z1 -36 (x-1,x20,x30) obtainted by the rounded off solution values.

The branch and bound diagram 1 = 1.0952, x2 0, x3 = 4 39.4286 Z1-36 Solution stpes by BigM method In Sub-problem A, x1( 1.0952) must be an integer value, so two new constraints are created, x 1 and x1 2 2 Sub-problem B:Solution is found by adding x 1 Solution stpes by BigM method Max z 36xi 28x 8x subject to 21x 20x26x3 s 23 Sub-problem C: Solution is found by adding x 2 Solution stpes by BigM method Max Z-36x1 +28x2 + 8xj subject to 21 x20x2 +6X3 s 23 2 and x1, x2,x3 2 0; and x,x3 20 Solution is Max ZB 38.8 (x,-1, x,-0.1, x3-0 and Z - 36 (x1 -1,x2-0,x3-0 obtainted by the rounded off solution values Solution is This Problem has an infeasible solution, so this branch is terminated.

The branch and bound diagram x1 = 1.0952, x2-0, x3-o Z4 39.4286 Zz -36 Solution stpes by BigM method -1,x-0.1,x3-0 -38.8 Z1-36 Infeasible Solution Solution stpes by Solution stpes by BigM method pon

Sub-problem D:Solution is found by adding2S0 Solution stpes by BigM method Max Z -36x1 + 28x2 + 8x3 subject to 21 x 20x2 6x3 s 23 Sub-problem E Solution is found by adding x2 2 1 Solution stpes by BigM method Max Z -36x1 + 28x2 8x subject to 21x 20x2 6x3 s 23 and x x2,x32 0; Solution is Max ZD 38.6667 (x,1,x20,x3 0.3333 and Z 36(x1-1,x2-0,x3-0) obtainted by the rounded off solution values and xxx3 2 0; Solution is Max ZE-33. 1429 (x,-0.1429, x2-1, x,-0 and Z-28 x10,x2-1, x3-obtainted by the rounded off solution values

The branch and bound diagram x1-10952, x2 0, x3-o Z4 394286 Z36 Solution stpes by BigM method x1-1,x2-0.1,x3 Z3-38.8 Z1-36 Solution stpes by BigM method Infeasible Solution Solution stpes by BigM method 1-1,x2-0,x3 - 0.3333x1-0.1429, x2 - 1,x3-0 Zp - 38.6667 Z 36 Solution stpes by BigM method E 33.1429 1-28 Solution stpes by BigM method

In Sub-problem D, x3(-0.3333) must be an integer value, so two new constraints are created, x3 S0 and x3 21 Sub-problem F: Solution is found by adding x s0 Solution stpes by BigM method Max Z 36x28x2 8x3 subject to 21x20x26x3 s23 Sub-problem G: Solution is found by adding x3 2 1 Solution stpes by BigM method Max Z 36x28x2 8x3 subject to 21x20x26x3 s23 *3 2 1 and x,x2,Xj 2 Solution is Max ZF 36 (x11,x0,x3 and ZL-36 (x,-1, x2-0, x,-0 ) obtainted by the rounded off solution values and x,x2,Xj 2 Solution is Max ZG-37. 1429 (x,-0.8095, x2-0, x,-1 and ZL = 8 (x1 = 0, x2-0, x,-1) obtainted by the rounded off solution values This Problem has integer solution, so no further branching is required.

This Problem has integer solution, so no further branching is required The branch and bound diagram 1.0952, x2 0, x3 0 #1 Z4 394286 21-36 Solution stpes by BigM method Z3-38.S Zi-36 Solution stpes by BigM method Infeasible So Solution stpes by BigM method 1 #0 1429, x2 1, x3- Zz 33.1429 x1-1,x2-0,x3-0.3333 ZD-3.6667 Z 36 Solution stpes by Solution stpes by BigM method 2F-36 Z1-36 Solution stpes by BinM method G 37.1429 Solution stpes by BigM method

In Sub-problem G, x-0.8095) must be an integer value, so two new constraints are created, x1 0 and x 2 1 Sub-problem H: Solution is found by addingx1 S0 Solution stpes by BigM method Max Z36x1 + 28x2 8x3 subject to 21x 20x26x3 s23 Sub-problem I: Solution is found by adding x12 1 Solution stpes by BigM method Max Z- 36x1 + 28x2 + 8x3 subject to 21x 20x2 6x3 s23 *3 è 1 2 *3 è 1 and x1,x2, X3 2 0; Solution is Max ZH = 30.6667 (x,-0, x2 = 0, x,-3.8333 and ZL-24 (x1-0, x2-0, x,-3 ) obtainted by the rounded off solution values. ZH 30.6667 ZF 36, so no further branching is required and x,x2,X3 20; Solution is This Problem has an infeasible solution, so this branch is terminated.

The branch and bound diagram x1 1.0952,x20,x30 Z4 394286 Z 36 Solution stpes by BigM method ZB- 38.8 ZL -36 Solution stpes by BigM method Infeasible Solution Solution stpes by BigM method ,x-0,x3-0.3333 ZD- 38.6667 Z 36 Solution stpes by BigM method 0.1429,x2-1,x3-0 z-33.1429 1 28 Solution stpes by BigM method

-0.8095, x2-0x-1 ZG 37.1429 ZF 36 Z1-36 Solution stpes by BigM method Solution stpes by BigM method 10,x2 0,x3-3.8333 Z 30.6667 Zz 24 Solution stpes by BigM method Infeasible Solu Solution stpes by BigM method The branch and bound algorithm thus terminated and the optimal integer solution is ZF- 36 and x1-1,x2 -0,x3-0

as per HomeworkLib policy, i have done only one question send separate........................