Linear programming. (English) Zbl 0537.90067

Chvátal, Vašek

A series of books in the mathematical sciences. New York - San Francisco: W. H. Freeman and Company. XIII, 478 p. (1983).

The book is divided in four parts and one appendix. In Part I, Basic Theory, the foundations of linear programming are established using the Simplex Method as the cornerstone of the whole treatment both computationally and theoretically. The Duality Theorem is obtained as a consequence of the simplex algorithm which is shown to be cycling free if any of the usual techniques is applied (perturbation, lexicographic or combinatorial methods). The exposition is selfcontained in the sense that the necessary results on systems of linear equations, Gaussian elimination, matrix theory, etc. are proved directly without any appeal to previous knowledge of linear algebra. The Revised Simplex Method, parametric linear programming, sensitivity analysis and a number of remarks and comments on speeds of convergence and computational work involved in different algorithms are also included in this Part I.
Part II, Selected Applications, begins by describing a number of linear programs derived from real life situations: scheduling, inventory, cutting stock and others. Also linear programming techniques to obtain the ”best approximate solution” of (possibly inconsistent) systems of linear equations are presented. One brief chapter in this part gives the fundamental result on matrix games (i.e.: Minimax Theorem, essentially equivalent to the duality theorem) and another, also brief, deals with solving systems of linear equations as a problem equivalent to a linear program. The last two chapter in this part (nos. 17 and 18) are of a geometric-combinatorial character. Geometric interpretations of the simplex method, the duality theorem and the perturbation techniques are explained. Also the notion of convexity appears here, for the first time in the book, since up to this point the exposition has been purely algorithm-algebraic, and in Chapter 18 the connection between basic solutions and the vertices of the convex polyhedral set of feasible points is established. Some geometric and combinatorial results which do not appear often in this type of text-book close this Part II.
Part III is titled in the index network flow problems (amusingly the heading of the opening page 289 reads ”Narrow Flow Problems”) and covers transshipment problems which are treated, as the author says in the preface, ”from scratch” to obtain the solving algorithm, that is the Network Simplex Method whose connection with the Revised Simplex Method is left to the reader to elaborate as an exercise. Techniques to avoid cycling are described together with comments on number of iterations and computer implementation of the algorithm. Then, applications to a variety of topics are presented. They range from the caterer problem to proofs of the Birkhoff-Von Neumann theorem on doubly stochastic matrices and the Hall theorem on systems of representatives. Again reversing the usual order, the assignment and transportation problems appear as particular cases of the transshipment problem. No reference is made to the standard ”transportation tableau”. Upper bound problems, maximum flow programs and primal-dual method are the subjects of the last three chapters (nos. 21,22,23) of Part III.
Part IV, Advanced Techniques, goes back to the original linear programming problem and contains three chapters titled ”Updating a triangular factorization of the basis”, ”Generalized upper bounding” and ”The Dantzig-Wolfe decomposition principle”.
Finally the Appendix describes the ”ellipsoid algorithm” of Khachiyan in a reasonably detailed form with numerous bibliographic references and remarks on the historical background. There is also mention of some recent related results.
At the end of each chapter there is a set of exercises, some of them supplementing the material in the main text with solutions of selected ones appearing at the end of the book which closes with ten pages of references.
The whole work is carefully writen in clear style. If duality is considered as the core of mathematical programming, then it is possible to object to the relegation of the duality theorem (at least in the first part of the book) to the role of a corollary of the simplex method. Apart from this relatively minor criticism this is a very informative and up to date book which should be most suitable for the teaching of linear programming at the senior-graduate level from different standpoints: purely mathematical, managerial, operation research oriented and others.

Reviewer: A.G.Azpeitia

MSC:

90C05	Linear programming
90-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
49-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to calculus of variations and optimal control
90C90	Applications of mathematical programming
65K05	Numerical mathematical programming methods
65F10	Iterative numerical methods for linear systems
91A05	2-person games
90B10	Deterministic network models in operations research
90C08	Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90B35	Deterministic scheduling theory in operations research
90B05	Inventory, storage, reservoirs
90C35	Programming involving graphs or networks
15B51	Stochastic matrices

Keywords:

cycling avoidance; Khachiyan algorithm; ellipsoidal method; Simplex Method; parametric linear programming; sensitivity analysis; speeds of convergence; inventory; cutting stock; best approximate solution; systems of linear equations; duality; perturbation techniques; convex polyhedral set of feasible points; transshipment problems; theorem on doubly stochastic matrices; Upper bound problems; maximum flow programs; primal- dual method; triangular factorization; Generalized upper bounding; Dantzig-Wolfe decomposition