**Text**

Linear Programming, V. Chvatal

Sept 2: Introduction to Mathematical programming, Operations research and course goals. Formulations of "the tragedy of the commons"

Sept 7: How to solve LPs in standard form. Read ch 2 of the text. Make up and solve one complete example by hand !

Sept 9: The simplex method in terms of dictionaries. Dantzig and Bland's pivot selection rule. Examples of cycling. Read Ch. 3 up to p.38.

(A nice treatment of the lexicographic ratio test is contained in Ignizio & Cavalier, Linear Programming, pp118-122, on reserve in Schulich library.)

Sept 14: Geometry of the simplex method. Degeneracy in polyhedra. Klee -Minty examples of worst case behaviour for Dantzig's rule.

Read text: Ch. 4 and pp. 250-260.

Sept 16: Initialization of the simplex method. Introduction to duality. Read Remainder of Ch. 3 and pp 54-57.

Optional: Another way of getting a feasible solution to a system of inequalities is described here.

Sept 21: Duality theory. Proofs of the weak and strong duality theorems. Read: Ch 5 up to p. 62.

Sept 23: Complementary slackness. Economic interpretations of duality. Proof of the finiteness of Bland's rule. Read: Rest of Ch 5. Also pp. 37-8 Thm 3.3

Sept 28: Introduction to Revised Simplex method. How to avoid taking the inverse of the basis matrix.

Sept 30: An example of Revised Simplex. Eta factorization of the basis matrix. Deriving Farkas lemma from phase 1 of the Simplex Method. Read: Ch. 7 and pp143-5.

Oct 5: General LP problems: how to handle bounded variables. Duality for LPs not in standard form. Read: Ch 8, pp118-124 and C h. 9 (except proof of duality theorem).

Oct 7: Review. Test will cover all of the above material.

Oct 12: First class test.

Oct 14: Review of test. The dual simplex method. Introduction to integer programming. Read: Text, Ch 10 up to p.153.

Oct 19: Gomory's cutting plane algorithm for integer programming. Read: class handout.

Oct 21: Zero sum games. LP formulation and minmax theorem. Read: Text, Chapter 15

Oct 26: Non-zero sum games and Nash equilibria. Read: First 10 pages of von Stengel's survey here. Supplemental notes here.

Oct 28: Basic information on vertex enumeration can be found in text pp. 271-275. The approach given in class is based on my paper (Read up to the end of Prop. 3.1.).

A tutorial on reverse search is contained in the paper. (will not be covered in test.)

Nov 2,4: Introduction to primal dual interior point methods. Read: Class handout. Second class test on Nov 11 covers all material up to Nov 4 lecture.

Nov 9: Review, Nash games again.

Nov 11: Second Class test.

Nov 16, 18: More on interior point methods: convergence, feasibility regions, barrier methods.

Nov 23, 25, 30: Class presentations. Attendance compulsory!

* return
to*: course home page