The Simplex Method of Linear Programming

This is a mathematical treatment of the simplex method in linear programming that does not use linear algebra, and so has probably outlived its usefulness. It is a Dover 2015 unaltered reprint of a 1961 Holt Rinehart & Winston edition.

This is a brief book that covers the mathematical theory of the simplex algorithm, rather than the practice. The body of the book is 36 pages, with an additional 22 pages of background material and further treatment of duality. It’s not really a how-to book, although it has a few examples. There’s no discussion of numerical issues; for example, pivoting is not covered. There’s also no discussion of run-time performance. The worst-case run-time in the simplex method is very bad, although the method works well in practice, and there has been a lot of interest in alternative methods as a backup.

One peculiarity of the book is that it makes no mention, even in the bibliography, of George Dantzig, the inventor of the simplex method.

A good modern treatment of the same material at the same level (but using linear algebra) is in Chapter 2 of Guenin & Könemann & Tunçel’s A Gentle Introduction to Optimization. Most books on algorithms have a discussion of the practice of the simplex method, for example, Chapter 29 of Cormen et al.’s Introduction to Algorithms.

Allen Stenger is a math hobbyist and retired software developer. He is an editor of the Missouri Journal of Mathematical Sciences. His mathematical interests are number theory and classical analysis.