Sample Syllabus for a Semester Course on
Linear Programming

using Optimization in Operations Research
by Ronald L. Rardin, Prentice Hall, 1998

Audience

This course is intended as an advanced undergraduate or beginning graduate course in linear programming for students in engineering, management and mathematics.

Background

This course assumes elementary background in multivariate differential calculus and in linear algebra, plus familiarity with vector/matrix notation and arithmetic. Most students will also have had an introductory course in deterministic operations research that includes at least formulation of mathematical programs, but self study of Chapter 2 can serve as an adequate substitute.

Topics

Schedule (less one week of examinations)

Week Topics Reading
1 Class Organization
Nature of Linear Programs
Allocation and Blending LPs
Section 2.4
Sections 4.1-4.2
2 Operations Planning LPs
Shift Scheduling LPs		 Section 4.3
Section 4.4
3 Time-Phased LPs
Linearized Nonlinear Models
Improving Search Paradigm		 Section 4.5
Section 4.6
Section 3.1
4 Improving and Feasible Directions
Global Optima for LP		 Sections 3.2-3.3
Section 3.4
5 LP Standard Form
Extreme Points and Basic Solutions
Rudimentary Simplex Algorithm		 Section 5.1
Section 5.2
Section 5.3
6 Two Phase Simplex
Degeneracy, Cycling and Finiteness of Simplex		 Section 5.5
Sections 5.6-5.7
7 Revised Simplex
Lower- and Upper-Bounded Simplex		 Section 5.8
Section 5.9
8 Activities vs. Resources, Qualititative Sensitivity
Quantitative Sensitivity and Duality
Formulating Duals		 Sections 7.1-7.2
Section 7.3
Section 7.4
9 Primal-to-Dual Relationships
Output Analysis and Parametric Programming		 Section 7.5
Sections 7.6-7.7
10 Interior Point Strategies for LP
Affine Scaling of Solutions
Affine Scaling Search		 Section 6.1
Section 6.2
Section 6.3
11 Log Barrier Methods for LP
Primal-Dual Search		 Section 6.4
Section 6.5, Supplement 1
12 Polynomial-Time Solution of LPs
Formulation of Multiobjective Optimization Models		 Supplement 2
Section 8.1
13 Efficient Points and the Efficient Frontier
Preemptive Optimization and Weighted Sums
Goal Programming		 Section 8.2
Section 8.3
Section 8.4
14 Column Generation Supplement 3

Supplements

Although the text provides foundations and intuitions for nearly all topics of this course, instructors will need to add rigor where the level of the course requires formal proofs. Also, the following supplemental notes are suggested:
  1. Primal-Dual Algorithms: Extensions of the book's treatment of primal-dual search to more fully explain and develop that strategy for solving LPs.
  2. Polynomiality in LP: Notes on the issue of polynomial-time solution of LPs including the polynomial order criterion for efficient solution, the failure of the simplex to meet it on Klee-Minty examples, and a sketch of polynomiality proofs for barrier methods.
  3. Column Generation: An overview of the column generation extension of Revised Simplex including its use in important applications.

Computer Support

The course should be conducted in part using standard class optimization software such as GAMS, AMPL, or LINGO. It is strongly recommended that students use such software to solve all assigned formulations that have numbers.

Still, the combination of simple hand exercises and full "black box" optimization is often not sufficient for students to master LP algorithm strategies. Better learning can result from assigning students to program and run their own crude versions of revised simplex, barrier search and/or column generation.

Back to Optimization in Operations Research mainpage