Lecture schedule:

Date |
Topic |
Reading to prepare for class, and other resources |
Assignment/Quiz? |
Lecture Notes |

Wed, Sep 6 | Course overview; introduction to linear programming | Lecture Notes | ||

Fri, Sep 8 | Standard form for linear programming problems | Chvátal Ch. 1 | Lecture Notes | |

Mon, Sep 11 | Matrix formalism for linear programs, and geometric interpretation in 2 dimensions. | Lecture Notes | ||

Wed, Sep 13 | Slack variables, and first examples of the simplex method. | Chvátal Ch. 2 (The "first example" section and possibly the "dictionaries" one) | Lecture Notes | |

Fri, Sep 15 | The standard rule for choosing how to pivot. | Chvátal Ch. 2 (the rest of the chapter) | Quiz 1 |
Lecture Notes |

Mon, Sep 18 | Examples of the simplex method for unbounded and initially-infeasible LPs. | Chvátal Ch. 3 p.27-29 (through the end of "finding the leaving variable") and p.39-42 ("Initialization"). Alternatively Vanderbei sections 2.3 and 2.4. | Lecture Notes | |

Wed, Sep 20 | The two-phase simplex method, and degeneracy. | Chvátal Ch. 3 p.29-33 (or Vanderbei sections 3.1 and 3.2) | Lecture Notes | |

Fri, Sep 22 | Degeneracy and Chvátal's example of cycling | Quiz 2 |
Lecture Notes | |

Mon, Sep 25 | The simplex method in terms of matrix formalism. | The "matrix description of dictionaries" section of Chvátal Ch. 7, p98-100. (Or Vanderbei section 6.1 + the beginning of section 6.2, up to where it talks about duals) | Lecture Notes | |

Wed, Sep 27 | Anti-cycling methods: Bland's rule, and maybe a bit about the perturbation method. | Chvátal p.34-38 or Vanderbei Sections 3.3 and 3.4. (I'll only talk about the perturbation method briefly, so it's fine to just skim the explanation of that one). | Lecture Notes | |

Fri, Sep 29 | Finishing up with the simplex method (for now): The fundamental theorem of linear programming, and a bit about efficiency of the simplex method. | Fundamental theorem: Chvátal p42-43 or Vanderbei sec 3.5. Efficiency of the simplex method (you can skim this): Chvátal ch. 4 or Vanderbei ch. 4. | Assignment 1 Due |
Lecture Notes |

Mon, Oct 2 | Introduction to Duality | Chvátal p54-57 or Vanderbei sec. 5.1 and 5.2 | Lecture Notes | |

Wed, Oct 4 | The weak duality theorem and some consequences | Chvátal p60-62 or Vanderbei sec. 5.3 | Lecture Notes | |

Fri, Oct 6 | The strong duality theorem | Chvátal p58-59 or Vanderbei sec. 5.4 | Quiz 3 |
Lecture Notes (updated) |

Mon, Oct 9 | Thanksgiving - No Class |
|||

Wed, Oct 11 | More on Strong Duality, and Complementary Slackness | Chvátal p62-65 or Vanderbei sec 5.5 | Lecture Notes (updated) | |

Fri, Oct 13 | Complementary Slackness | Assignment 2 Due |
Lecture Notes | |

Mon, Oct 16 | Economic significance of dual variables | Chvátal p65-68 | Lecture Notes | |

Wed, Oct 18 | Uniqueness or non-uniqueness of optimal solutions. | Lecture Notes | ||

Fri, Oct 20 | Midterm |
|||

Mon, Oct 23 | The revised simplex method | Chvátal p100-102 or Vanderbei section 6.2 | ||

Wed, Oct 25 | ||||

Fri, Oct 27 | Quiz 4 |