Search

AMS 540, Linear Programming
Formulation of linear programming problems and solutions by simplex method. Duality, sensitivity analysis, dual simplex algorithm, decomposition. Applications to the transportation problem, two-person games, assignment problem, and introduction to integer and nonlinear programming.
Prerequisite: A course in linear algebra

Recommended Textbooks:

"Linear Programming" by James Ignizio and Tom Cavalier, 1994, Pearson/Prentice-Hall; ISBN# 9780131837577

"Linear Programming and Network Flows" by M. Bazaraa, J. Jarvis and H. Sherali, 4th edition, 2010 Wiley Publishing; ISBN#: 9780470462720

Fall Semester

Learning Outcomes:

1) Learn to formulate optimization problems as linear progams.

2) Develop skill in using linear programming software, including Lindo/AMPL.

3) Understand theory from linear algebra and convex analysis that applies to the theory of linear programming.

4) Learn the simplex algorithm and use it to solve linear programs:
* Putting linear programs in standard form with slack and excess variables;
* Finding an initial basic feasible solution (using big M or two-phase simplex for min problems);
* Choosing which variable enters and which variable leaves the basis;
* Handling unbounded and infeasible problems;
* Analyzing convergence in nondegenerate programs;
* Analyzing convergence and methods in degenerate programs, including Bland's pivot rule, perturbation, and lexicographical methods.

5) Understand and apply principles of duality:
* Defining dual programs;
* Developing duality theorems;
* Applying the dual simplex algorithm.

6) Apply sensitivity analysis to solutions of linear programs:
* Shadow prices and reduced costs;
* Range for objective function coefficients and right-hand sides;
* Connections to the dual linear programs and complementary slackness.

7) Learn and use special forms of the simplex method:
* Transportation problems;
* Transshipment problems;
* Assignment problems;
* Network simplex method.

8) Other recent algorithms for linear programming:
* Ellipsoid algorithm;
* Karmarkar and related interior-point methods.