Math 340 Lecture Schedule

Main PageQuiz/Exam info

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