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
3 credits, ABCF grading
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.