Description
Problem 1. Prove the dual of the dual of a linear programming (standard form) is itself.[25pts]
Problem 2. Prove the dual objective increases after a pivot of the dual simplex method.[25pts]
Problem 3. Let L(x,λ) be the Lagrangian of a linear programming problem, and (x
∗
,λ
∗
) be the optimal primaldual solution. Prove that
L(x,λ
∗
) ≥ L(x
∗
,λ
∗
) ≥ L(x
∗
,λ),
for any primal feasible x and dual feasible λ.[25pts]
Problem 4. Construct a linear programming problem for which both the primal and the dual problem has no feasible
solution.[25pts]