Math 482
Course Documents & Links
Lecture Notes
Simplex Method:
Lecture 1: Introduction to Linear Programming
Lecture 2: Convex sets, feasible regions of linear programs, standard/canonical and equational forms
Lecture 3: Basic feasible solutions, pivoting
Lecture 4: Simplex tableaux, objective functions
Lecture 5: Simplex method examples (unbounded LPs, degenerate pivoting)
Lecture 6: Two-phase simplex method
Lecture 7: Pivoting rules
Lecture 8: Lexicographic pivoting example, notation for basic and non-basic parts
Lecture 9: Equivalence of vertices, extreme points, and basic feasible solutions
Lecture 10: Formulas for simplex tableaux
Lecture 11: The revised simplex method
Lecture 12: Worst-case scenarios
Duality:
Lecture 13: Introduction to Duality
"Sensible Rules for Remembering Duals" (by Arthur Benjamin)
An applet for practicing computing the duals of linear programs (by Dominik Peters)Lecture 14: Complementary slackness
Lecture 15: Duality & simplex tableaux
Lecture 16: Dual simplex method
Lecture 17: Finding BFS & Introduction to sensitivity analysis
Lecture 18: More sensitivity analysis
Lecture 19: Introduction to zero-sum games
Lecture 20: Duality and optimality in zero-sum games
Lecture 21: Fourier-Motzkin elimination and Farkas's Lemma
Graph Theory:
Lecture 22: Bipartite graphs, maximum matching and minimum vertex cover problems
Lecture 23: Totally unimodular matrices, integrality of optimal solutions
Lecture 24: Introduction to Networks
Lecture 25: Max-flow, min-cut theorem
Lecture 26: Directed s,t-paths and augmenting paths
Lecture 27: Ford-Fulkerson Algorithm
Quanta article about a new maximum-flow algorithm (optional, for-fun reading)Lecture 28: Variants on max-flow problems
Lecture 29: Minimum-cost flow problems
Lecture 30: Two-phase simplex method for minimum-cost flow problems
Primal-Dual Algorithm:
Lecture 31: Introduction to the primal-dual algorithm
Lecture 32: Finding the direction vector from the restricted primal program
Lecture 33: Finding initial feasible points, application to Ford-Fulkerson algorithm
Integer Linear Programs:
Homework Assignments
As mentioned in the syllabus, I highly encourage typesetting assignments rather than writing by hand. You may wish to do so using Overleaf, which is free and cloud-based. In case you find it helpful, I have created a basic template for homework in this course (the TeX code is available here). You are not required to use this template or to use LaTeX.
Homework assignments will be posted here as well as on Gradescope.
Other Resources
"Guidelines for good mathematical writing," by Francis Su.
Detexify, a web app for identifying the LaTeX command(s) for various symbols.
Overleaf, a cloud-based LaTeX editor.