Duality and the dual simplex¶
Part 3 of the course, volume 3 of the lecture notes. The dual problem, weak and strong duality, the possible outcomes of a primal-dual pair, complementary slackness; the dual simplex algorithm, infeasibility certificates and re-optimization. Examples worked out step by step and exercises with complete solutions at the end of each chapter.
-
9. Duality theory
Dual problem of an LP problem in canonical max form · Primal and dual problems: possible outcomes · Complementary Slackness · Dual problem of a generic LP problem
-
10. Dual Simplex algorithm
Pair of primal and dual problems · Primal and dual feasible bases · Finding an initial dual basic feasible solution · Dual pivoting operations · …