Consider the following primal LP problem: Maximize X1 + 2X2 – 9X3 + 8X4 – 36X5 Subject to 2X2 – X3 + X4 – 3X5 ≤ 40 X1 – X2 + 2X4 – 2X5 ≤ 10 X1 ≥ 0, X2 ≤ 0, X3 ≥ 0, X4 ≥ 0, X5 ≥ 0 (a) Write the dual of the LP above, using variables Y1, Y2, etc. (b) Sketch the feasible region of the dual LP in 2 dimensions, and use the graphical method to find the dual optimal solution (Plot an isovalue line corresponding to the feasible solution, move the line in improving direction, find the last one touching the feasible region, and any point(s) on the intersection of the last isovalue line and feasible region are optimal solutions) (c) Using complementary slackness conditions, - write equations which must be satisfied by the optimal primal solution X* - which primal variables must be zero? (d) Using the information in (c), determine the optimal primal solution X* (e) Compare the optimal objective values of the primal and dual solutions
Consider the following primal LP problem:
Maximize X1 + 2X2 – 9X3 + 8X4 – 36X5
Subject to 2X2 – X3 + X4 – 3X5 ≤ 40
X1 – X2 + 2X4 – 2X5 ≤ 10
X1 ≥ 0, X2 ≤ 0, X3 ≥ 0, X4 ≥ 0, X5 ≥ 0
(a) Write the dual of the LP above, using variables Y1, Y2, etc.
(b) Sketch the feasible region of the dual LP in 2 dimensions, and use the graphical method to find the dual optimal
solution (Plot an isovalue line corresponding to the feasible solution, move the line in improving direction, find
the last one touching the feasible region, and any point(s) on the intersection of the last isovalue line and
feasible region are optimal solutions)
(c) Using complementary slackness conditions,
- write equations which must be satisfied by the optimal primal solution X*
- which primal variables must be zero?
(d) Using the information in (c), determine the optimal primal solution X*
(e) Compare the optimal objective values of the primal and dual solutions
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 6 images
