In this introductory text on linear programming, a thorough, up-to-date, and
comprehensive summary of the philosophies and procedures used in the modeling,
solution, and analysis of so-called linear programming problems is provided.
The text is for the senior-level college student or for the first-year graduate
student having some previous exposure to linear algebra -- and earlier versions
(or selected portions) have been used in such courses over the past decade. An
associated solutions manual is provided for all exercises and is available to
those adopting the text for classroom use.
The text is divided into three parts. Part 1, consisting of Chapters 2 through
8, addresses linear programming in general -- emphasizing the development,
presentation, and illustration (via numerous examples) of the fundamentals necessary
to model, solve, and analyze linear programs. Although the coverage is relatively
traditional, some very unique aspects should be noted. First, coverage is provided
in Chapter 7 of recent results with regard to alternative methods to the simplex
algorithm, in particular the affine scaling variants of the Karmarkar algorithm.
Second, Chapters 8 deals with the use of linear programming in information
technology -- particularly as a means to analyze large amounts of data. Topics
covered include prediction/forecasting, pattern classification/pattern recognition,
clustering analysis, input-output analysis, and even the design and training of
neural networks -- all achieved by means of linear programming.
Part 2 addresses integer linear programming, including the network simplex
method (Chapter 9), transportation and assignment problems (Chapter 10), and
general integer programming methods (Chapter 11). In addition, the very
important and all too often neglected area of heuristic programming is addressed
in Chapter 12. Further, the coverage of heuristics in that chapter is extended
to such currently popular heuristic methods as genetic algorithms, simulated
annealing, and various related techniques that are -- as of late -- often
associated with the field of artificial intelligence.
Finally, in Part 3, the topic of multiple objective optimization is addressed.
This is accomplished by an original, unified approach to both modeling and
solution -- the multiplex concept. Topics covered include various multiobjective
philosophies, their models, and their solution and analysis via a single
algorithm. Discussions and demonstrations are given to how such problems may
be solved via conventional linear programming algorithms and software.
The text may be employed in a variety of ways, depending upon the needs/interests
of the reader or the purpose of the associated course. For example, a one-term
introductory course in linear programming might cover Chapters 1, 2, 3, 4, and 6
(omitting the starred sections) followed by Chapter 10 and selected topics from
Chapters 8, 11, and 13. A more advanced course in linear programming might cover
Chapter 1 and all of Part 1 (that is, Chapters 2 to 8) with additional topics
selected from Chapters 11 and 12. A course emphasizing network and integer
models might cover Chapters 1, 3, 4, and 6 (omitting the starred sections)
followed by Part 2 (that is, Chapters 9 to 12). A course devoted solely to
multiobjective models and methods might cover Chapter 1 and Part 3 (that is,
Chapters 13 to 17). Finally, we advocate the use of group projects as a part
of any course, and the use of various existing softwares for the solution of a
variety of LP models (and the choice of software is left to the reader or course
instructor). From experience, a combination of lectures, examples/exercises,
projects, and computer implementation has -- we believe -- best served to
reinforce the understanding and appreciation of both the power and limitations
of the linear programming method.
In this text, the emphasis is to provide a basis for the understanding and
appreciation of the truly remarkable power of the linear programming method.
As such, emphasis is not placed on the computer implementation of the tools
associated with the overall methodology. However, there now exist numerous,
inexpensive, commercial linear programming packages that the instructor and/or
student may wish to use to accompany the text. Although we certainly advocate
such computational support, we would hope that the main emphasis is, and will
be, that of the understanding of the fundamental concepts, theory, and solution
methods that serve to comprise the linear programming method.
We would like to acknowledge the reviewers selected by Prentice Hall, Professors
Wonjang Baek of Mississippi State University and Romesh Saigal of the University
of Michigan for taking the time to evaluate the manuscript.