Lecture Summaries  for COMP 566A                     Autumn 2003

      also check:announcements                        return to:course home page

Text
        Linear Programming, V. Chvatal


Nov 4: More on zero sum games.  Bimatrix games. Nash equilibria and "generalized" complementary slackness
Oct 30: Matrix games.  Read:  Ch 15. Second test will  cover all material up to this point.
Oct 28: More on network simplex method. Initialization. Integrality of LP solution. Finish Ch 19.
October 23:  Network Simplex method. Start reading Ch 19.
October 21: Dual simplex method and sensitivity analysis. How to change c and b vectors, and add new variables and constraints. Read: Ch 10 up to p.162 - you can skip revised dual simplex method.
October 16: Linear programming with bounds on the variables. We used dictionaries, the book uses revised simplex method.                             Read: Ch 8 up to p. 124
October 14: Class Test.
October 9: Efficient implementation of Revised Simplex using Eta matrices. Economic interpretation of Revised Simplex.                                Read: rest of Ch 7.
 October 7: Revised Simplex Method. Read: Chapter 7 up to p. 105.

October 2: Infeasible problems. Certificate of infeasibility, and how to compute it via Phase 1 of the simplex method.
       We proved that Ax <= b, x>= 0 is infeasible if and only if there is a dual vector y >= 0  s.t   yA>=0 and yb < 0.
       The proof is similar to the more general theorem on pp 143-145.

Sept 30: Complementary Slackness Theorem and proof using Duality Theorem . Economic interpretation.
                 Unbounded solutions and their certificates.
Sept 25: Proof of Duality Theorem. Use as a certificate of optimality. Complementary slackness. Read: rest of Chapter 5.
Sept 23: Dual linear program. Weak duality theorem and proof. Statement of strong duality theorem. Read: pp. 54-62
Sept 18: Initialization and the two phase simplex method. Read: Chapter 3
Sept 16: How good is the simplex method. Klee-Minty examples. Read: Chapter 4

Sept. 11: General form of dictionaries. Pivot selection rules. Cycling in the simplex method.  Read: Text Chapter 2 and pp. 31-32

Sept. 9: Saxby foods formulation. How to solve an LP from scratch.            Read: Text Chapter 1 

Sept 4: Introduction to Operations Research, Mathmetical Programming, Linear Programming and
          Integer Programming. Course outline and requirements. Buy text!