Skip Navigation

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. This course is offered as both MBA 540 and AMS 540. 
Prerequisite: A course in linear algebra 
3 credits, ABCF grading 

Text: Linear Programming. by Ignizio, 94, Pearson
ISBN# 9780131837577 - Recommended

Linear Programming and Network Flows. By Bazaraa, 4th Edition Wiley
ISBN#: 9780470462720 - Recommended

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.

Login to Edit