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
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
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 Lecture Notes
Wed, Oct 25 The revised simplex method, continued Chvátal p102-105 Lecture Notes
Fri, Oct 27 Interpretation of the revised simplex method Quiz 4 Lecture Notes
Mon, Oct 30 Another example of the revised simplex method and its interpretation. Lecture Notes
Wed, Nov 1 General LPs and their duals Chvátal p118-120, 137-146 Lecture Notes
Fri, Nov 3 More on duals in general form; maybe start on the dual simplex method Chvátal p149-156 Assignment 3 due Lecture Notes
Mon, Nov 6 Finish with duals in general form; start on the dual simplex method Chvátal p149-156 Lecture Notes
Wed, Nov 8 Continue with the dual simplex method. Lecture Notes
Fri, Nov 10 Finish up on the dual simplex method. Quiz 5 Lecture Notes
Mon, Nov 13 No class (Remembrance Day weekend)
Wed, Nov 15 Sensitivity Analysis Chvátal p158-161 or Vanderbei sec 7.1 Lecture Notes
Fri, Nov 17 Sensitivity analysis continued Assignment 4 due Lecture Notes
Mon, Nov 20 More sensitivity analysis examples Lecture Notes
Wed, Nov 22 Finishing up with sensitivity analysis Handout by Richard Anstee from a previous version of this class, that the example covered this class and the one before it is from. Lecture Notes
Fri, Nov 24 The cutting-stock problem Chvátal ch. 13 (you can skim this)
Javascript applet for generating LINDO code for cutting stock problems (written by Omar Antolín Camarena, a previous instructor for this course)
Assignment 5 due Lecture Notes
Mon, Nov 27 Integer programming Vanderbei ch. 23.5 (you can skim this)
Handout by Richard Anstee with some more examples of the branch-and-bound method.
Lecture Notes
Wed, Nov 29 Matrix games Chvátal ch. 15 (you can skim this) Lecture Notes
Fri, Dec 1 More on matrix games Lecture Notes