3 The Simplex Method
By the fundamental theorem, an optimal solution of an LP can be found among its basic feasible solutions. Dantzig’s simplex method (1947) moves from one BFS to an adjacent one with a better objective value, until no neighbour is better. Each move is a pivot: one variable enters the basis and one leaves. This section derives the method from the algebra of bases, proves that it stops at an optimum, shows how to start it, and explains the two things that can go wrong, degeneracy and exponential running time.
3.1 Reduced costs and the optimality test
3.2 The tableau
3.3 Starting the method: artificial variables
3.4 Degeneracy, cycling and Bland’s rule
3.5 How fast is the simplex method?
3.6 The simplex method in software
3.7 Practice Problems
3.2 The tableau
3.3 Starting the method: artificial variables
3.4 Degeneracy, cycling and Bland’s rule
3.5 How fast is the simplex method?
3.6 The simplex method in software
3.7 Practice Problems
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.