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

Instructor's 540 Webpage

 

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.