Lecture Summaries for 308-566A
Linear Programming, V. Chvatal
November 6: Second class test, covers
all material below except October 18 and 30.
November 1: Cutting planes for integer
programming. Read: handout, section 14.1
October 30: Guest lecture by Bohdan Kaluzny:
case study and cplex.
October 25: Inventory control problem
via networks. Unimodular matrices. Read: pp.
October 23: Network Simplex method, duality
and complementary slackness. Read: 291-307
October 18: Integer programming, relationship
to P/NP question.
October 16: Dual simplex method and sensitivity
analysis. Read pp 148-162.
October 11: General LP problems: how to
handle bounded variables. Read: pp118-129.
October 9: Revised simplex method. Eta
matrices and fast update of basis matrix. Read:
October 4: First class test. Closed book
- calculators allowed. Covers all material below.
October 2: Finiteness of Bland's rule.
Classification of dictionaries. Generalized duality. Read:
September 27: Strong duality and proof
of duality theorem. Complementary slackness. Read:
Sept. 25: Getting upper bounds. Duality
and weak duality theorem. Read: pp 54-57.
Sept. 20: Complexity of the simplex method.
Sept. 18: More on solving Simplex method.
Pivot selection rules. Unbounded and infeasible problems.Cycling in the
simplex method. Initialization. Bland's least subscript rule to avoid cycling.
Read Chapter 3 except pp 34-8. Assignment
Sept. 13: Saxby foods example of production
scheduling. How to solve an LP from scratch. Read:
Text Chapter 2
Sept. 11: Polly's
diet problem. Formulation, solution
by Maple and discussion of solution. All solutions costing at most a dollar
Text Chapter 1
Sept 6: Introduction to Operations Research,
Mathmetical Programming, Linear Programming and Integer Programming. Course
outline and requirements. Buy text!