IOE 510: Linear Programming Winter 2002 Syllabus Additional Information Lecture Notes Homework

Syllabus

Instructor: Prof. Katta G. Murty

Office: 2773 IOE Bldg.
E-mail: katta_murty@umich.edu
Phone:763-3513 

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 Rⁿ 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.

Work: 

• Weekly Homework Assignments.
• Midterm
• Final Exam
• Two Computational Projects to be solved using AMPL.

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

Additional Information

• AMPL Information(.pdf file, 431K)
• AMPL model for the diet problem
• AMPL model for problem 7.7 in the first reference book(.pdf file, 47K)
• Using AMPL at CAEN
• AMPL: specifying data
• AMPL: commands
• AMPL Homepage
• AMPL FAQ
• Linear Programming FAQ
• Some small AMPL models

Lecture Notes

• Notes 0- Introduction (.pdf file) (.ps file)
• Notes 1- Formulation Techniques (.pdf file) (.ps file)
• Notes 2- Geometric Method, Planning Uses (.pdf file) (.ps file)
• Notes 3- Polyhedral Geometry(.pdf file) (.ps file)
• Notes 4- Simplex Method Using Canonical Tableaus (.pdf file) (.ps file)
• Notes 5- Duality, Optimality Conds. (.pdf file) (.ps file)
• Notes 6- Revised Primal Simplex Method (.pdf file) (.ps file)
• Notes 7- Dual Simplex Algorithm (.pdf file)(.ps file)
• Notes 8- Marginal and Sensitivity Analyses (.pdf file) (.ps file)
• Notes 9- Transportation Problem (.pdf file) (.ps file)
• Notes 10- Bounded Variable Primal Simplex (.pdf file) (.ps file)
• Notes 11- Interior Point Methods (.pdf file) (.ps file)
• Notes 12- AMPL Examples Solved (.pdf file) (.ps file)

Homework

• Homework 2  due 23 January 2002                                                   
• Homework 3  due 30 January 2002  
• Homework 4  due 6 Feb. 2002  
• Homework 5  due 13 Feb. 2002  
• Homework 6  due18 Feb. 2002   Simplex Method for LP
• Homework 7  due13 Mar. 2002
• Homework 8  due20 Mar. 2002  
• Homework 9  due27 Mar. 2002  
• Homework 10  due 3 Apr. 2002  
• AMPL project due 8 Apr. 2002
• Homework 11 (last homework) due 15 Apr. 2002 

Last Update on 04/18/02
By Junghoon Hyun
Email: hyunjh@umich.edu