**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!

*return to*: course home page