## Math 340 Lecture Schedule

### Main Page — Quiz/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