P Answer the following questions. Consider the following L.P. problems: min { { s.t. Ax=b...

 

Transcribed Image Text:

P₁ Answer the following questions. Consider the following L.P. problems: min сх { { s.t. Ax=b Dx=p X≥0 P2 min CX s.t. Ax=b x > 0 Suppose x¹, x² are optimal solutions and x³ is a non-optimal solution of P₁. Say True, False or Maybe to the following. Give a brief explanation; treat each case independently. i) The point x0 = (0.25) x¹ + (0.75) x² is another optimal solution for P₁. ii) The point x0 = (0.25) x¹ + (0.25) x² + (0.50) x3 is another feasible solution for P₁. iii) The optimal value of problem P2 is unbounded. iv) Problem P2 is inconsistent. v) U = c x¹ is a Upper Bound for the optimal value of problem P2. b) (12 pts) Consider the application of Branch & Bound (B-B) procedure to the integer programming problem, P3: {min e x; subject to A x=b, x≥ 0, x integer} Suppose a last subset, say S₁, is being investigated (with all other subsets of solutions having been eliminated at earlier iterations) and the optimal solution, x*, of the Relaxed Problem on this subset turns out to be an integer solution. Say True, False or Maybe to the following statements. Support your answer with a brief explanation. Treat each case independently. i) U = cx*, is the optimal value of P3; ii) Subset, S, is also eliminated from further consideration and B-B procedure terminates; iii) The B-B procedure continues by dividing the subset, S, into further subsets. iv) There are no "integrality constraints" in the "Relaxed Problem". P₁ Answer the following questions. Consider the following L.P. problems: min сх { { s.t. Ax=b Dx=p X≥0 P2 min CX s.t. Ax=b x > 0 Suppose x¹, x² are optimal solutions and x³ is a non-optimal solution of P₁. Say True, False or Maybe to the following. Give a brief explanation; treat each case independently. i) The point x0 = (0.25) x¹ + (0.75) x² is another optimal solution for P₁. ii) The point x0 = (0.25) x¹ + (0.25) x² + (0.50) x3 is another feasible solution for P₁. iii) The optimal value of problem P2 is unbounded. iv) Problem P2 is inconsistent. v) U = c x¹ is a Upper Bound for the optimal value of problem P2. b) (12 pts) Consider the application of Branch & Bound (B-B) procedure to the integer programming problem, P3: {min e x; subject to A x=b, x≥ 0, x integer} Suppose a last subset, say S₁, is being investigated (with all other subsets of solutions having been eliminated at earlier iterations) and the optimal solution, x*, of the Relaxed Problem on this subset turns out to be an integer solution. Say True, False or Maybe to the following statements. Support your answer with a brief explanation. Treat each case independently. i) U = cx*, is the optimal value of P3; ii) Subset, S, is also eliminated from further consideration and B-B procedure terminates; iii) The B-B procedure continues by dividing the subset, S, into further subsets. iv) There are no "integrality constraints" in the "Relaxed Problem".

Answer rating: 100% (QA)

The image displays a set of questions regarding linear programming problems LPP I will address each statement one by one a Part 1 i True If x1 and x2 are optimal solutions to a linear programming prob... View the full answer