Linear Programming: Mathematics, Theory and Algorithms

by M.J. Panik

Overview

Linear Programming provides an in-depth look at simplex based as well as the more recent interior point techniques for solving linear programming problems. Starting with a review of the mathematical underpinnings of these approaches, the text provides details of the primal and dual simplex methods with the primal-dual, composite, and steepest edge simplex algorithms. This then is followed by a discussion of interior point techniques, including projective and affine potential reduction, primal and dual affine scaling, and path following algorithms. Also covered is the theory and solution of the linear complementarity problem using both the complementary pivot algorithm and interior point routines. A feature of the book is its early and extensive development and use of duality theory.
Audience: The book is written for students in the areas of mathematics, economics, engineering and management science, and professionals who need a sound foundation in the important and dynamic discipline of linear programming.

Product Details

ISBN-13:	9781461334361
Publisher:	Springer US
Publication date:	01/26/2012
Series:	Applied Optimization , #2
Edition description:	1996
Pages:	498
Product dimensions:	6.30(w) x 9.45(h) x 0.04(d)

Table of Contents

1. Introduction and Overview.- 2. Preliminary Mathematics.- 2.1 Vectors in Rn.- 2.2 Rank and Linear Transformations.- 2.3 The Solution Set of a System of Simultaneous Linear Equations.- 2.4 Orthogonal Projections and Least Squares Solutions.- 2.5 Point-Set Theory: Topological Properties of Rn.- 2.6 Hyperplanes and Half-Planes (-Spaces).- 2.7 Convex Sets.- 2.8 Existence of Separating and Supporting Hyperplanes.- 2.9 Convex Cones.- 2.10 Basic Solutions to Linear Equalities.- 2.11 Faces of Polyhedral Convex Sets: Extreme Points, Facets, and Edges.- 2.12 Extreme Point Representation for Polyhedral Convex Sets.- 2.13 Directions for Polyhedral Convex Sets.- 2.14 Combined Extreme Point and Extreme Direction Representation for Polyhedral Convex Sets.- 2.15 Resolution of Convex Polyhedra..- 2.16 Simplexes.- 2.18 Linear Functionals.- 3. Introduction to Linear Programming.- 3.1 The Canonical Form of a Linear Programming Problem.- 3.2 A Graphical Solution to the Linear Programming Problem.- 3.3 The Standard Form of a Linear Programming Problem.- 3.4 Properties of the Feasible Region.- 3.5 Existence and Location of Finite Optimal Solutions.- 3.6 Basic Feasible and Extreme Point Solutions to the Linear Programming Problem.- 3.7 Solutions and Requirements Spaces.- 4. Duality Theory.- 4.1 The Symmetric Dual.- 4.2 Unsymmetric Duals.- 4.3 Duality Theorems.- 5. The Theory of Linear Programming.- 5.1 Finding Primal Basic Feasible Solutions.- 5.2 The Reduced Primal Problem.- 5.3 The Primal Optimality Criterion.- 5.4 Constructing the Dual Solution.- 5.5 The Primal Simplex Method.- 5.6 Degenerate Basic Feasible Solutions.- 5.7 Unbounded Solutions Reexamined.- 5.8 Multiple Optimal Solutions.- 6. Duality Theory Revisited.- 6.1 The Geometry of Duality and Optimality.- 6.2 Lagrangian Saddle Points and Primal Optimality.- 7. Computational Aspects of Linear Programming.- 7.1 The Primal Simplex Method Reexamined.- 7.2 Improving a Basic Feasible Solution.- 7.3 The Cases of Multiple Optimal, Unbounded, and Degenerate Solutions.- 7.4 Summary of the Primal Simplex Method.- 7.5 Obtaining the Optimal Dual Solution From the Optimal Primal Matrix.- 8. One-Phase, Two-Phase, and Composite Methods of Linear Programming.- 8.1 Artificial Variables.- 8.2 The One-Phase Method.- 8.3 Inconsistency and Redundancy.- 8.4 Unbounded Solutions to the Artificial Problem.- 8.5 The Two-Phase Method.- 8.6 Obtaining the Optimal Primal Solution from the Optimal Dual Matrix.- 8.7 The Composite Simplex Method.- 9. Computational Aspects of Linear Programming: Selected Transformations.- 9.1 Minimizing the Objective Function.- 9.2 Unrestricted Variables.- 9.3 Bounded Variables.- 9.4 Interval Linear Programming.- 9.5 Absolute Value Functionals.- 10. The Dual Simplex, Primal-Dual, and Complementary Pivot Methods.- 10.1 Dual Simplex Method.- 10.2 Computational Aspects of the Dual Simplex Method.- 10.3 Dual Degeneracy.- 10.4 Summary of the Dual Simplex Method.- 10.5 Generating an Initial Primal-Optimal Basic Solution: The Artificial Constraint Method.- 10.6 Primal-Dual Method.- 10.7 Summary of the Primal-Dual Method.- 10.8 A Robust Primal-Dual Algorithm.- 10.9 The Complementary Pivot Method.- 11. Postoptimality Analysis I.- 11.1 Sensitivity Analysis.- 11.2 Structural Changes.- 12. Postoptimality Analysis II.- 12.1 Parametric Analysis.- 12.2 The Primal-Dual Method Revisited.- 13. Interior Point Methods.- 13.1 Optimization Over a Sphere.- 13.2 An Overview of Karmarkar’s Algorithm.- 13.3 The Projective Transformation T(X).- 13.4 The Transformed Problem.- 13.5 Potential Function Improvement andComputational Complexity.- 13.6 A Summary of Karmarkar’s Algorithm.- 13.7 Transforming a General Linear Program to Karmarkar Standard Form.- 13.8 Extensions and Modifications of Karmarkar’s Algorithm.- 13.9 Methods Related to Karmarkar’s Routine: Affine Scaling Scaling Algorithms.- 13.10 Methods Related to Karmarkar’s Routine: A Path-Following Following Algorithm.- 13.11 Methods Related to Karmarkar’s Routine: Potential Reduction Algorithms.- 13.12 Methods Related to Karmarkar’s Routine: A Homogeneous and Self-Dual Interior-Point, Method.- 14. Interior Point Algorithms for Solving Linear Complementarity Problems.- 14.1 Introduction.- 14.2 An Interior-Point, Path-Following Algorithm for LCP(q,M).- 14.3 An Interior-Point, Potential-Reduction Algorithm for LCP(q,M).- 14.4 A Predictor-Corrector Algorithm for Solving LCP(q,M).- 14.5 Large-Step Interior-Point Algorithms for Solving LCP(q,M).- 14.6 Related Methods for Solving LCP(q, M).- Appendix A: Updating the Basis Inverse.- Appendix B: Steepest Edge Simplex Methods.- Appendix C: Derivation of the Projection Matrix.- References.- Notation Index.

Editorial Reviews

‘ ... a carefully written textbook in a clear style. It is a very informative introduction to this field and may be recommended to students as well as to everybody interested in this special field of applied mathematics.'
Optimization, 43 (1998)

From the Publisher

Presents to students of management science, mathematics, engineering, and economics the salient features of the theory and the computational aspects of linear programming. Assumes basic calculus and some exposure to linear algebra and matrix theory. Provides the mathematical tools to study the theory and implement a set of algorithms. Introduces duality theory early and fully integrates both the primal and dual programs throughout. Includes both simplex routines and the newer interior-point methods. Double spaced. Annotation c. Book News, Inc., Portland, OR (booknews.com)

Booknews