Linear Programming


Credit Hours:


Learning Objective:

As a beginning graduate course, the first goal is to teach the students the skills to formulate real-world problems as linear programs, and solve them using the available software. The second goal is to teach the students the theoretical principles of linear optimization.


Linear programming (LP) problems arise pervasively in science and engineering. The students will obtain a broad exposure to the theoretical underpinnings of linear optimization, as well as to the algorithms for solving LP problems. Prior exposure to optimization is not necessary; however, good knowledge of linear and matrix algebra is strongly desired.

Topics Covered:

Introduction; classification of optimization problems; formulation of linear optimization problems; geometry of 2-dimentional linear programs; Simplex method: basic feasible solutions, pivoting, degeneracy, cycling and anti-cycling, pivot rules, phase I and phase II algorithms; duality; sensitivity analysis.


Linear algebra

Applied / Theory:

20 / 80

Web Address:


Six to eight assignments, assigned roughly every two weeks, may be downloaded from the course web page; the assignments will count for approximately 30% of the course grade.


There will be a final project. For distance learning students, the project will involve using software packages (such as Excel, MatLab, etc) to solve LP problems. Students can also choose to do a programming project, which is to program an algorithm to solve given LP problems, using whichever programming languages students may choose.


Three take-home exams worth approximately 18% of the course grade each.


Official textbook information is now listed in the Schedule of Classes. NOTE: Textbook information is subject to be changed at any time at the discretion of the faculty member. If you have questions or concerns please contact the academic department.
Linear Programming and Network Flows by Mokhtar S. Bazaraa, John J. Jarvis and Hanif D. Sherali, 4th edition, Wiley, 2010. ISBN-13: 978-0470462720 (Freely available through Purdue???s library online) Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis, Athena Scientific, 1997. ISBN-13: 978-1886529199

Computer Requirements:

ProEd Minimum Computer Requirements

Other Requirements:

Any software packages that can solve linear programming problems, such as Excel, MATLAB, cplex, Gurobi, etc, all of which should be freely available through Purdue's academic license.

ProEd Minimum Requirements: