The simplex algorithm¶
Part 2 of the course, volume 2 of the lecture notes. The simplex algorithm on dictionaries, optimality conditions, pivot rules and cycling, Phase 0 with the auxiliary problem. Examples worked out step by step and exercises with complete solutions at the end of each chapter.
-
6. Simplex algorithm
The standard form of an LP problem in canonical max form · Basis of the LP problem in standard form and dictionaries · Pivoting operations · High-level pseudo-code of the simplex algorithm
-
7. Optimality conditions and pivot rules
Sufficient conditions for optimality · Necessary conditions for optimality · Pivot rules
-
8. Phase 0 of the simplex algorithm
The simplex auxiliary problem · Solving the simplex auxiliary problem · From the Phase \(0\) to the simplex algorithm · Detecting infeasible LP problems · …