Linear Programming: Lecture Notes

Two graphs, one illustrating KKT conditions and one outlining a multi-stage inventory control and manufacturing problem

Credit: Image adapted from figures by Christopher Griffin and is licensed under CC BY-NC-SA 3.0 US

Resource Description

This is a set of lecture notes for Penn State’s undergraduate Linear Programming course.

The lecture notes are (roughly) based on the first 6 chapters of Bazaraa et al.’s Linear Programming and Network Flows book. This is a reasonably good book, written primarily by and for Industrial Engineers. However, it does not present major results in the standard theorem-proof style common to mathematical discourse. This set of notes corrects this situation by presenting the material in a format for presentation to a mathematics class.

Many of the proofs in this set of notes are adapted from the textbook with some minor additions. Additionally, I prefer to present maximization problems, while Linear Programming and Network Flows prefers the minimization format. I’ve modified all the proofs to operate on maximization problems. When used with the book, the student can obtain a complete set of proofs for elementary Linear Programming.

Course Number

MATH 484

License

CC BY-NC-SA 3.0 US

Resource
Author(s)
Table of Contents

View E-Book

View the e-book in a new tab: .pdf

Download Source Files

Download the resource's source files here: .zip (9.61 MB)

Christopher Griffin

I am a Research Professor at the Applied Research Laboratory (ARL) at Penn State. In the broadest possible sense, my work is in applied math. Some of my work is on applied statistics on (real-world) dynamical systems.

Learn more

Chapter 1. Introduction to Optimization
- A General Maximization Formulation
- Some Geometry for Optimization
- Gradients, Constraints and Optimization
Chapter 2. Simple Linear Programming Problems
- Modeling Assumptions in Linear Programming
- Graphically Solving Linear Programs Problems with Two Variables (Bounded Case)
- Formalizing The Graphical Method
- Problems with Alternative Optimal Solutions
- Problems with No Solution
- Problems with Unbounded Feasible Regions
Chapter 3. Matrices, Linear Algebra and Linear Programming
- Matrices
- Special Matrices and Vectors
- Matrices and Linear Programming Expression
- Gauss-Jordan Elimination and Solution to Linear Equations
- Matrix Inverse
- Solution of Linear Equations
- Linear Combinations, Span, Linear Independence
- Basis
- Rank
- Solving Systems with More Variables than Equations
- Solving Linear Programs with Matlab
Chapter 4. Convex Sets, Functions and Cones and Polyhedral Theory
- Convex Sets
- Convex and Concave Functions
- Polyhedral Sets
- Rays and Directions
- Directions of Polyhedral Sets
- Extreme Points
- Extreme Directions
- Caratheodory Characterization Theorem
Chapter 5. The Simplex Method
- Linear Programming and Extreme Points
- Algorithmic Characterization of Extreme Points
- The Simplex Algorithm–Algebraic Form
- Simplex Method–Tableau Form
- Identifying Unboundedness
- Identifying Alternative Optimal Solutions
- Degeneracy and Convergence
Chapter 6. Simplex Initialization
- Artificial Variables
- The Two-Phase Simplex Algorithm
- The Big-M Method
- The Single Artificial Variable Technique
- Problems that Can’t be Initialized by Hand
Chapter 7. Degeneracy and Convergence
- Degeneracy Revisited
- The Lexicographic Minimum Ratio Leaving Variable Rule
- Bland’s Rule, Entering Variable Rules and Other Considerations
Chapter 8. The Revised Simplex Method and Optimality Conditions
- The Revised Simplex Method
- Farkas’ Lemma and Theorems of the Alternative
- The Karush-Kuhn-Tucker Conditions
- Relating the KKT Conditions to the Tableau
Chapter 9. Duality
- The Dual Problem
- Weak Duality
- Strong Duality
- Geometry of the Dual Problem
- Economic Interpretation of the Dual Problem
- The Dual Simplex Method