Linear programming. 1: Introduction. Incl. 1 CD-ROM

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01) Linear programming (90C05)

Review text

This book is the first volume of a projected three-volume work on linear programming. As its title indicates, the book provides an introduction to the subject. Most of the topics covered are the standard ones: motivation for and formulation of linear programs, solving simple linear programs with graphical methods and techniques like the Fourier-Motzkin Elimination Technique, the Simplex Method including the Phase I/Phase II approach and the Revised Simplex Method, duality, the price mechanism and sensitivity analysis, specialized problems such as the transportation and assignment problems, and network flows. Those familiar with traditional linear programming textbooks will recognize all of these. This volume also provides a brief excursion into an interior point method and some linear programming formulations of diverse problems. The book has two appendices: one on linear algebra (mostly elementary matrix theory), the other an elementary discourse on solving systems of linear equations by pivoting methods. Another significant feature is the inclusion of a CD rom containing some Windows-based software for solving small linear programs. The Preface of this volume provides an important -- but incomplete -- clue to its nature. After identifying ``models,\dots algorithms,\dots and software based on the mathematical theory as the appropriate tools for stating general goals and ``laying out a path of detailed decisions to be taken in order to `best' achieve these goals when faced with practical situations of great complexity, the authors announce that ``our goal\dots is to provide a simple introduction to these various tools in the context of linear programming. To accomplish this goal, the authors ``state the key ideas as theorems and lemmas. Because the book is intended as ``an introduction to the field at the undergraduate level, they say, ``no proofs of key ideas are provided except for a few that are easy to follow. In fact, there are eighteen such proofs in this volume. They go on to say that ``proofs of all the theorems and lemmas can be found in Linear Programming 2 (i.e., the second, so far unpublished, volume of this three-volume set). This is not to say that Linear Programming 1 is devoid of mathematical reasoning. Demonstrations abound in this work, but they are not labeled as proofs of lemmas, theorems or corollaries. Moreover, the text is sprinkled with exercises many of which call upon the reader to prove an assertion or supply the justification for something just considered. With the exception of the statement of Bland's Least-Index Pivoting Rule, this volume lacks a systematic treatment of degeneracy resolution in the Simplex Method for linear programming. It also contains no treatment of parametric linear programming, a topic that is intimately related to sensitivity analysis and the economic interpretation of dual variables. Nevertheless, the book does contain many illustrative numerical examples, exercises and problems of various kinds. The latter represent modeling, algorithms, theory and computation. They range from truly introductory to decidedly challenging. In fact, many of them are taken from past Ph.D. Comprehensive Examinations in Operations Research at Stanford University. The book closes with a useful index and an extensive -- indeed, fifty-nine-page -- list of references. The software on the CD rom packed inside the book allows the user to create new problems for solution or to run existing problems corresponding to examples or exercises in the text. Among the features of this software are options regarding solution method (Primal Simplex Method, Fourier-Motzkin Elimination, or the Primal Affine (Dikin) Method). Within the Primal Simplex Method option, one can choose between the Phase I Method or the Big M Method for finding an initial basic feasible solution. One can also obtain sensitivity analysis relative to the objective function, the right-hand side and the coefficient matrix. It is possible to modify problems by inserting or deleting rows or columns, to redimension the problem, and to print the input and output. Although the intermediate data are not accessible, one can at least obtain a record of the basis exchanges and the corresponding objective function values at each iteration.

Recommendations

Cited in

(61)

This page was built for publication: Linear programming. 1: Introduction. Incl. 1 CD-ROM

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4344060)