Consider the following linear program: min s.t.: (1) : (2): (3): (4): -x+y x-y 3 2x...

Transcribed Image Text:

Consider the following linear program: min s.t.: (1) : (2): (3): (4): -x+y x-y≤ 3 2x - 3y ≤ 4 x < 5 x, y ≥ 0. a) (5 points) Graph the feasible region of the LP. Is the feasible region unbounded? Does the feasible region have any basic feasible solutions? If so, what are they? b) (4 points) Using the graphical method (Lectures 4-5, Slide 6), determine the optimal solution for the LP. c) (3 points) Is there more than one optimal solution? d) (8 points) For this question, we will demonstrate (without using the graphical method, nor the simplex algorithm) that the solution found in part b) is indeed an optimal solution for the LP. i. (3 points) To this end, first show that the solution found in part b) is indeed a feasible solution for the LP. What is its objective value? ii. (5 points) Then, by looking at the constraints of the LP, argue that no feasible solution can have an objective value strictly better than that of the solution found in part b). e) (5 points) If the objective were changed from minimization to maximization, what would the new optimal solution be? f) (5 points) Are any of the above constraints redundant? If so, indicate which one(s). (Redun- dancy will play an important role in the formulation of integer programs.) As a reminder, a constraint is redundant if removing it does not change the feasible region. Consider the following linear program: min s.t.: (1) : (2): (3): (4): -x+y x-y≤ 3 2x - 3y ≤ 4 x < 5 x, y ≥ 0. a) (5 points) Graph the feasible region of the LP. Is the feasible region unbounded? Does the feasible region have any basic feasible solutions? If so, what are they? b) (4 points) Using the graphical method (Lectures 4-5, Slide 6), determine the optimal solution for the LP. c) (3 points) Is there more than one optimal solution? d) (8 points) For this question, we will demonstrate (without using the graphical method, nor the simplex algorithm) that the solution found in part b) is indeed an optimal solution for the LP. i. (3 points) To this end, first show that the solution found in part b) is indeed a feasible solution for the LP. What is its objective value? ii. (5 points) Then, by looking at the constraints of the LP, argue that no feasible solution can have an objective value strictly better than that of the solution found in part b). e) (5 points) If the objective were changed from minimization to maximization, what would the new optimal solution be? f) (5 points) Are any of the above constraints redundant? If so, indicate which one(s). (Redun- dancy will play an important role in the formulation of integer programs.) As a reminder, a constraint is redundant if removing it does not change the feasible region.

Answer rating: 100% (QA)

Here are the stepbystep workings a i Plot the constraints on a graph with x and y axes Constraint 1 ... View the full answer