Linear Optimization
Revised: October 2021
Course Description
Formulation and solution of linear programming models; development of simplex method;
duality theory; sensitivity analysis; software; and applications.
Prerequisites: MATH 255 and MATH 362 or permission of instructor.
Three semester hours.
Student Learning Objectives
By the end of the course students will be able to
- Formulate a linear optimization problem for a given application;
- Solve the optimization problem using the simplex method (both by hand and through
the use of mathematical software);
- Provide geometric interpretation of linear programming;
- Explain the significance of sensitivity analysis and its role in linear programming;
and
- Apply their understanding of theory to real life applications that warrant linear
programming techniques.
Text
M.S. Bazaraa, J.J. Jarvis, and H.D. Sherali, Linear Programming and Network Flows (4th Edition), 2010, John Wiley & Sons.
Grading Procedure
Grading procedures and factors influencing course grade are left to the discretion
of individual instructors, subject to general university policy.
Attendance Policy
Attendance policy is left to the discretion of individual instructors, subject to
general university policy.
Course Outline
- Chapter 1: Introduction. (6 class days) The Linear Programming Problem, Linear Programming Modeling and Examples, Geometric
Solutions, Requirement Space.
- Chapter 2: Linear Algebra, Convex Analysis, and Polyhedral Sets. (6 class days) Properties of Vectors and Matrices, Simultaneous Linear Equations, Convex Sets and
Convex Functions, Polyhedral Sets and Polyhedral Cones, Geometric Insights.
- Chapter 3: The Simplex Method. (10 class days) Extreme Points and Optimality, Basic Feasible Solutions, Simplex Method, Geometric
Motivation of Simplex Method, Algebra of Simplex Method, Optimality and Unboundedness,
Tableau Form of Simplex Method.
- Chapter 5: Special Simplex Implementations and Optimality Conditions. (6 class days) Revised Simplex Method, Farkas' Lemma, Karush-Kuhn-Tucker Optimality Conditions
- Chapter 6: Duality and Sensitivity Analysis. (14 class days) Formulation of the Dual Problem, Primal-Dual Relationships, Economic Interpretation
of the Dual, Dual Simplex Method, Primal-Dual Method, Artificial Constraint Technique,
Sensitivity Analysis, Parametric Analysis
Additional Topics (dependent upon time) Recommended additional topics include Chapter 9: Minimal-Cost Network Flows.