** Date** | ** What we covered **
| ** Material** |

Aug 5
| Introduction to the course. History and applications of linear programming. Basic definitions. Two exercises in modelling problems as linear programs.
| Slides. BT-Ch-1.1 - 1.3 MG-Ch-1, MG-Ch-2 |

Aug 8
| Word Problem to LP formulation | BT-Ch-1.2, MG-Ch-2 |

Aug 12 | Linear Equations, Gaussian elimination, Solution space. | Slides BT-Ch-1.5, MG-Ch-1.3, MG-Ch-4.1 Related Gilbert Strang's video lectures Geometry of linear equations Elimination with Matrices Solving Ax=b Independence, Basis and dimension The four fundamental subspaces |

Aug 19 | Continued from last class Geometry of linear equations and linear inequalities | |

Aug 26 | Geometry of Linear Programs Solving LPs graphically Fourier-Motzkin Elimination
| BT-Ch-2, MG-Ch-4 |

Aug 29
| Simplex Algorithm: Definition of the tableau and examples.
| |

Sep 2
| Simplex algorithm - dealing with unboundedness, infeasibility
| |

Sep 5
| Simplex algorithm: Cycling
| |

Sep 9
| Two-phase Simplex: examples.
| |

Sep 12
| Linear Programming Duality
| |

Sep 16
| LP Duality cond... Weak duality, strong duality, complementary slackness.
| |

Sep 19
| Application of LP Duality: Equilibrium in Zero-sum games.
| |

Sep 30
| Polyhedra, Polytopes, Extreme points, basic solutions, basic feasible solutions. Proof of equivalence of definitions of extreme point, vertex and basic feasible solution.
| |

Oct 7
| Continued proof of equivalence of extreme points, vertex and basic feasible solution. Dependence of basic solutions on the form of the LP.
| |

Oct 8
| Proof that an LP has an extreme point if and only if it does not contain a line, Optimality of extreme points.
| |

Oct 10
| Development of simplex algorithm: Feasible directions,reduced cost.
| |

Oct 14
| Problems with degeneracy, simplex algorithm.
| |

Oct 17
| Revised simplex algorithm and simplex tableau implementation.
| |

Oct 28
| Simplex Tableau implementation.
| |

Oct 31
| Proof of convergence of simplex with lexicographic pivoting rule.
| |

Nov 4
| Proof of convergence of Simplex. Example where simplex takes exponential time: Klee-Minty cubes.
| |

Nov 7
| Proof of strong duality via Simplex. Proof of Farkas Lemma via Simplex. Application of Farkas Lemma: Markov Chains
| |

Nov 11
| Separating hyperplanes and proof of strong duality via separating hyperplane.
| |

Nov 14
| The Khachiyan-Grigoriadis algorithm for solving zero-sum games.
| |

Nov 18
| Network flows and matchings
| |

Nov 21
| Applications | |