Consider the following linear program:
maximize x1 + 4x2 subject to x1 + x2 ≤ 3
4x1 − 2x2 ≤ 0 x1,x2 ≥0
(a) Construct the dual problem.
(b) Write the complementary slackness conditions.
(c) Suppose you are told that the solutions (x1, x2) = (0, 3) and (y1, y2) = (4, 0) are feasible solutions to the primal and dual problems, respectively. Explain two different ways of verifying whether they are also optimal solutions to the primal and dual problems.
(d) Suppose now that the right hand side of the first constraint in the primal problem is increased from 3 to 4, and that this does not change the optimal basis. Without solving the primal or the dual problem, what are the new optimal objective function values of the primal and dual problems?