An Introduction to Linear Programming and the Simplex Algorithm

by Spyros Reveliotis

Acknowledgements

There are a number of people who have contributed during the inceptional and implementational phases of this project through constructive comments and discussions, provision of information and technical assistance. At this point, I would like to acknowledge their valuable aid. Hence, I would like to say a "big" THANKS to: Evangelia Dimaraki, Amy Pritchett, Bhaskar Manda, Darren Hunt, Victoria Burse, Randy Riegsecker, Balu Vandor, Javier Ruiz and Fangjun Zhou . Many thanks go also to my students of the past IE3231 classes , since it was my interaction with them that motivated and inspired this whole effort. I would also like to acknowledge the financial (and not only) support of the School of Industrial and Systems Engineering and the CETL group at the Georgia Institute of Technology .

The integrated software supporting the execution of interactive examples "re-uses" the very nice software modules developed by (i) Drs Ken Goldberg and Ilan Adler at the Dept. of Industrial Engineering and Operations Research, University of California at Berkeley, and (ii) Dr. Timothy Wisniewski, of Northwestern University. The remaining JAVA applets were developed "in house", by Panagiotis Reveliotis. In fact, this software is still under testing, so, please, report any problems with it, to spyros@isye.gatech.edu.

This text is intended to function as an introduction to Linear Programming (LP) and the Simplex algorithm. The specific topics covered and the structure of the material is as follows:

• The LP formulation and the underlying assumptions
• Graphical solution of 2-var LP's
• Generalization to the n-var case: the ``geometry'' of the LP feasible region and the Fundamental Theorem of Linear Programming.
• An algebraic characterization of the solution search space: Basic Feasible Solutions
• The Simplex Algorithm

Most of the text material is presented inductively, by generalizing some introductory highlighting examples. In fact, the basic structure of the material and many of the examples used in the text have been inspired by W. L. Winston's ``Introduction to Mathematical Programming'', ed. Duxbury, which has been used as the class text in an introductory LP course at the School of Industrial & Systems Engineering, at Georgia Tech.

An additional and innovative feature of this text is the integration of some software modules which allow the reader to run her own examples interactively. Specifically, this software is distributed at the end of key sections, and it is intended to demonstrate/visualize basic concepts and the functionality of the algorithms discussed in the text.

• The LP formulation and the underlying assumptions
  • A prototype LP problem:
  • The general LP formulation
• Graphical solution of 2-var LP's
  • Feasible Regions of Two-Var LP's
  • The solution space of a single equality constraint
  • The solution space of a single inequality constraint
  • Representing the Objective Function in the LP solution space
  • Graphical solution of the prototype example: a 2-var LP with a unique optimal solution
  • 2-var LP's with many optimal solutions
  • Infeasible 2-var LP's
  • Unbounded 2-var LP's
• Generalization to the n-var case: the ``geometry'' of the LP feasible region and the Fundamental Theorem of Linear Programming
  • The geometry of n-var LP's
  • Polytope Convexity and Extreme Points
  • The Fundamental Theorem of Linear Programming
• An algebraic characterization of the solution search space: Basic Feasible Solutions
  • Example:
  • LP's in ``standard form''
  • Basic Feasible Solutions: An algebraic characterization of extreme points for LP's in ``standard form''
  • Example:
• The Simplex Algorithm
  • The basic Simplex iteration through an example:
• About this document ...