You are here

Linear Optimization: The Simplex Workbook

Glenn H. Hurlbert
Publisher: 
Springer
Publication Date: 
2009
Number of Pages: 
272
Format: 
Hardcover
Series: 
Undergraduate Texts in Mathematics
Price: 
59.95
ISBN: 
9780387791470
Category: 
Textbook
[Reviewed by
Brian Borchers
, on
02/27/2010
]

Linear programming is a well established subject, with numerous textbooks available at both the advanced undergraduate and graduate levels. Most introductory textbooks in linear programming begin with the simplex algorithm for linear programming in the tableau notation. Students typically spend a lot of time learning how to solve small linear programming problems by hand. This is typically followed by coverage of the revised simplex method, the dual simplex method, and specialized versions of the simplex method for network flow problems. Unfortunately, the emphasis on algorithms often comes at the expense of important mathematical issues in the theory of linear programming. Furthermore, this approach tends to leave out many important issues in the computer implementation of the simplex method and it entirely ignores recent work on interior point methods for linear programming.

An alternative approach is to shift the focus towards the mathematics of linear programming, with the simplex method taking a less central role. Hurlbert’s textbook focuses on the mathematics of linear programming and important connections to linear algebra, graph theory, convexity, and game theory. The author has adopted the Moore method in which students are given some basic terminology and definitions and are then asked to develop the subject by proving a series of theorems. The author has broken the proofs down into a series of “workouts” that are reasonably sized exercises for students to complete. In addition to these workouts, there are also “problems”, “challenges”, and “projects” for students to work on. The problems are relatively straight forward homework exercises, the challenges are more difficult exercises, and the projects ask the students to research topics that go beyond the material presented in the book. Clearly, students taking a course out of this textbook will spend most of their time writing proofs and not solving linear programming problems by hand.

The most common criticism of the Moore method is that it is impossible to cover as much material in a Moore method course as in a conventional course. Instructors who adopt this textbook will find that it leaves out some topics that commonly appear in introductory textbooks on linear programming. For example, the author states Bland’s theorem that the simplex method with the least subscript rule does not cycle, but the author does not offer a proof of this fact and does not challenge the reader to prove this theorem. No mention is made of the lexicographic rule for pivot selection which is more often used in practice.

This textbook would be very suitable for an undergraduate course in linear programming that uses the Moore method. Instructors looking for a textbook with a similar focus on the mathematics of linear programming and the simplex method that uses a more conventional pedagogical approach will probably find Chvátal’s Linear Programming to be a better choice. A somewhat more advanced textbook that also includes coverage of interior point methods is Vanderbei’s Linear Programming: Foundations and Extensions.

References:

Chvátal, Vasek. Linear Programming. W. H. Freeman, 1983.

Vanderbei, Robert. Linear Programming: Foundations and Extensions, 3rd ed. Springer, 2008.


Brian Borchers is a professor of Mathematics at the New Mexico Institute of Mining and Technology. His interests are in optimization and applications of optimization in parameter estimation and inverse problems.

Introduction.- The Simplex Algorithm.- Geometry.- The Duality Theorem.- Matrix Implementation.- General Form.- Unsolvable Systems.- Geometry Revisited.- Game Theory.- Network Implementation.- Combinatorics.- Economics.- Integer Optimization.- Appendix A: Linear Algebra Overview.- Appendix B: The Equivalence of the Auxiliary and Shortcut Methods.- Appendix C: Complexity.- Appendix D: LOP Catalog.