MATH 450 Syllabus

Linear Optimization

Revised: September 2014

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. 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 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, Simplex Method of Bounded Variables, 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 Minimal-Cost Network Flows.