IOE 510: Linear Programming

Winter 2002

Additional Information
Lecture Notes



Instructor: Prof. Katta G. Murty

Office: 2773 IOE Bldg.

Prerequisites: A course in linear or matrix algebra.

Background Required: Elementary matrix algebra(concept of linear independence, bases, matrix inversion, pivotal methods for solving linear equations), geometry of Rn including convex sets and affine spaces.

Reference Books:

  1. K. G. Murty, Operations Research: Deterministic Optimization Models, Prentice Hall, 1995.
  2. K. G. Murty, Linear Programming, Wiley, 1983.
  3. M.S. Bazaraa, J. J. Jarvis, and H. D. Shirali, Linear Programming and Network Flows, Wiley, 1990.
  4. R. Saigal, Linear Programming: A Modern Integrated Analysis, Kluwer, 1995.
  5. D. Bertsimas and J. N. Tsitsiklis,Introduction to Linear Optimization, Athena, 1997.
  6. R. Fourer, D. M. Gay, and B. W. Kernighan, AMPL: A Modeling Language for Mathematical Programming, Scientific Press, 1993.

Course Content:

  1. Linear Programming models and their various applications. Separable piece-wise linear convex function minimization problems, uses in curve fitting and linear parameter estimation. Approaches for solving multi-objective linear programming models, the Goal programming technique.
  2. What useful planning information can be derived from an LP model (marginal values and their planning uses).
  3. Pivot operations on systems of linear equations, basic vectors, basic solutions, and bases. Brief review of the geometry of convex polyhedra.
  4. Duality and optimality conditions for LP.
  5. Revised primal and dual simplex methods for LP.
  6. Infeasibility analysis, marginal analysis, cost coefficient and right hand side constant ranging, and other sensitivity analyses.
  7. Algorithm for transportation models.
  8. Bounded variable primal simplex method.
  9. Brief review of Interior point methods for LP.


Appoximateweights for determining final grade are: Homeworks(15%), Midterm(20%), Final Exam(50%), Computer Projects(15%).

Additional Information

Lecture Notes


Last Update on 04/18/02
By Junghoon Hyun