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.

Required Textbooks:

1. Linear Programming by James P. Ignizio and Tom M. Cavalier, 1994, Prentice Hall
2. Linear Programming and Network Flows by Mokhtar S. Bazaraa, John J. Jarvis and Hanif D. Sherali, 4th edition, 2009, Wiley

Supplementary Textbooks:

1. Optimization in Operations Research by Ronald L. Rardin, 2nd edition, 2016, Pearson
2. Operations Research: An Introduction by Hamdy A. Taha, 10th edition, 2016, Pearson
3. Introduction to Mathematical Programming: Operations Research, Volume One by Wayne L. Winston, and Munirpallam Venkataramanan, 4th edition, 2002, Thomson
4. Operations Research: Applications and Algorithms by Wayne L. Winston, 4th edition, 2003, Cengage
5. Applied Mathematical Programming by Stephen P. Bradley, Arnoldo C. Hax and Thomas L. Magnanti, 1997, Addison-Wesley
6. Introduction To Operations Research by Hillier Lieberman, 1995, McGraw-Hill
7. Linear Programming by Vasek Chvatal, 1983, W. H. Freeman
8. Linear Programs and Related Problems by Evar D. Nering and Albert W. Tucker, 1992, Academic Press
9. Linear Programming by Katta G. Murty, 1991, Wiley
10. Linear Programming and Extensions by George B. Dantzig, 1998, Princeton University Press
11. Linear Programming by Howard Karloff, 1991, Birkhäuser
12. Methods of Mathematical Economics: Linear and Multilinear programming by Joel N. Franklin, 1987, Society for Industrial and Applied Mathematics

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.