Lecture Summaries for COMP
566
Autumn 2008
also check:announcements
return to:course home page
Text
Linear Programming, V.
Chvatal
Sep
2: What is operations research,
mathematical programming and linear programming. Read:
Review analysis of algorithms extracted from Nielsen & Chuang (you
may skip the proof of Thm 3.2): pdf
Sep 4: How to solve a linear
program. Read: Text, Ch. 2
Sep 9: Another example and a
general description of dictionaries and the simplex method. Redundancy.
Some geometry. Read pp. 250-55
Sep 11: Pivot
selection and cycling. Read pp. 27-33.
(Extra material for those interested: For more about cycling take a
look here.
For more about Zadeh's rule see here
and here.)
Sep 16: Initialization.
Klee-Minty examples. Read
39-42 and Chapter 4.
Sep 18: Proof of the finiteness
of Bland's rule. The Fundamental theorem of linear programming. Read:
pp. 37-38,42-43.
Sep 23: Duality. Interpretations
of duality. The weak duality theorem. Relationships between outcomes
for primal and dual problems. Read: pp. 54-62 (except proof of duality
theorem.)
Sep 25,30: Proof of the strong
duality theorem and complementary slackness. Economic interpretations.
Read: 57-59, 62-68.
Oct 2: Revised simplex method.
Read: 97-105
Oct 7: Review of assignments, old
exam problems, etc.
Oct 9: First class test.
Oct 14: Review of test. General
linear programming (bounds on variables). Read: 118-124
Oct 16,21: Network simplex
method. Read ; 291-305
Oct 23: Network
applications: Scheduling production and inventory, napkins
and the transportation problem. Read 320-327, 345
Oct 28: Dual simplex method.
Sensitivity analysis. Read class handout Ch 10 and text 148-153.
Oct 30: Integer programming. Read
class handout Ch. 11. pdf
ppt
Nov 4: Review of assignments,
old exams etc.
Nov 6: Second class test.
Material up to and including Oct. 30.
Nov11: Interior point
methods (Attendance compulsory). Read class handout, up to the
top of page 9.
Nov 13: Interior point methods.
Read: rest of class handout.
Nov 18, 20, 25, 27: Class
presentations. (Attendance compulsory)
return
to: course home page