Consider the following final tableau obtained after simplex iteration for a maximization problem. Assume the problem satisfies the conditions needed to develop Gomorys fractional cut. Assume that the objective function coefficients in the original problem were integer. x1 x2 x3 x4 x5 x6 x7 x8 x9 rhs 5 0 1.2 0 4 0 2 0 1.5 7.8 2 1 1.4 0 -1.6 0 0 0 4.9 0.3 5 0 -0.8 1 -0.3 0 1 0 2.1 2.7 1 0 -3.7 0 3.9 1 0 0 1.7 0.6 -9.3 0 0.3 0 -5.2 0 0 1 -3.6 4.5 (a) Identify all the basic and non-basic variables. Identify the current solution. (b) Generate as many Gomorys cuts as possible. (c) Pick any of the above Gomorys cut, and show it is valid. Consider the following BnB enumeration tree: P1 z (1) = 950 P3 z (3) = A P9 z (9) = 920 x2 3 P4 z (4) = B P6 z (6) = D P8 z (8) = 910 x3 F P7 z (7) = 915 x3 E x1 63 P5 z (5) = C IFS x1 64 x2 4 x3 7 P2 z (2) = 935 IFS x3 8 Answer the following based on the above tree, using the strategies discussed in the class. Note: IFS stands for Integer Feasible Solution. (d) Is it a maximization or a minimization problem? Explain. (e) Write all the possible pairwise relations among A, B, C, D. Also suggest a possible upper or lower value for A, B, C, D. (f) What could be the node selection strategy in the above tree? Explain your answer using: best bound, depth first best back, breadth first best next, most recent. (g) What could be the branching direction selection strategy in the above tree? Explain your answer using: branch-up, branch-down, mixed. (h) At (P3), the LP solution is x (3) 1 = 5, x (3) 2 = 3.1, x (3) 3 = 7, x (3) 4 = 5.9. What could be the variable selection strategy? Explain your answer using: highest fraction, lowest fraction, or nearest to integer. (i) Write the relationship between E & F. Also suggest a possible upper or lower value for E & F. (j) Explain a possible sequence of events that occurred from node (P7) to node (P9). Based on the explanation, what should be the next node to process? (k) What is the incumbent solution in the above tree? How far is it from the global optimal solution?

Show transcribed image textISE-321 HW-2 Problem #2 0 4 0 1 0 0 Consider the following final tableau obtained after simplex iteration for a maximization problem. Assume the problem satisfies the conditions needed to develop Gomory's fractional cut. Assume that the objective function coefficients in the original problem were integer. 14 IS 17 18 Ths 5 1.2 2 1.5 7.8 2 1.4 0 -1.6 4.9 0.3 -0.8 -0.3 2.1 2.7 1 -3.7 3.9 0 1.7 0.6 -9.3 0 03 0 -5.2 0 0 1 -3.6 4.5 (a) Identify all the basic and non-basie variables. Identify the current solution. (b) Generate as many Gomory's cuts as possible. (c) Pick any of the above Gomory's cut, and show it is valid. 0 0 0 1 0 1 0 0 0 0 5 1 0 Consider the following BnB enumeration tree: P. 60 8 . P). -95 IPS P. 120 P.-B PT. PS). IPS Answer the following based on the above tree, using the strategies discussed in the class. Note: IFS stands for Integer Feasible Solution. (d) Is it a maximization or a minimization problem? Explain. (e) Write all the possible pairwise relations among A, B, C, D. Also suggest a posible upper or lower value for A, B, C, D. (1) What could be the node selection strategy in the above tree? Explain your answer using: best bound, depth first best back, breadth first best next, most recent. (8) What could be the branching direction selection strategy in the above tree? Explain your answer using: branch-up, branch-down, mixed. (h) At (P), the LP solution is :(") = 5,25") = 3.1,25") = 7,1% = 5.9. What could be the variable selection strategy? Explain your answer using: highest fraction, lowest fraction, or nearest to integer (1) Write the relationship between E & F. Also suggest a possible upper or lower value for E& F. () Explain a possible sequence of events that occurred from node (Py) to node (P). Based on the explanation, what should be the next node to process? (k) What is the incumbent solution in the above tree? How far is it from the global optimal solution?

ISE-321 HW-2 Problem #2 0 4 0 1 0 0 Consider the following final tableau obtained after simplex iteration for a maximization problem. Assume the problem satisfies the conditions needed to develop Gomory's fractional cut. Assume that the objective function coefficients in the original problem were integer. 14 IS 17 18 Ths 5 1.2 2 1.5 7.8 2 1.4 0 -1.6 4.9 0.3 -0.8 -0.3 2.1 2.7 1 -3.7 3.9 0 1.7 0.6 -9.3 0 03 0 -5.2 0 0 1 -3.6 4.5 (a) Identify all the basic and non-basie variables. Identify the current solution. (b) Generate as many Gomory's cuts as possible. (c) Pick any of the above Gomory's cut, and show it is valid. 0 0 0 1 0 1 0 0 0 0 5 1 0 Consider the following BnB enumeration tree: P. 60 8 . P). -95 IPS P. 120 P.-B PT. PS). IPS Answer the following based on the above tree, using the strategies discussed in the class. Note: IFS stands for Integer Feasible Solution. (d) Is it a maximization or a minimization problem? Explain. (e) Write all the possible pairwise relations among A, B, C, D. Also suggest a posible upper or lower value for A, B, C, D. (1) What could be the node selection strategy in the above tree? Explain your answer using: best bound, depth first best back, breadth first best next, most recent. (8) What could be the branching direction selection strategy in the above tree? Explain your answer using: branch-up, branch-down, mixed. (h) At (P), the LP solution is :(") = 5,25") = 3.1,25") = 7,1% = 5.9. What could be the variable selection strategy? Explain your answer using: highest fraction, lowest fraction, or nearest to integer (1) Write the relationship between E & F. Also suggest a possible upper or lower value for E& F. () Explain a possible sequence of events that occurred from node (Py) to node (P). Based on the explanation, what should be the next node to process? (k) What is the incumbent solution in the above tree? How far is it from the global optimal solution