Lecture Summaries for COMP
566
Autumn 2006
also check:announcements
return to:course home page
Text
Linear Programming, V.
Chvatal
Sep 5 What is operations research,
mathematical programming and linear programming. The diet problem and
its solution. Criticisms
of the optimum solution, and some remedies.
Read: text Chapter 1.
Sep 7 Formulating a linear
program in standard form. Dictionaries, bases, co-bases, slack
variables and pivoting. How to solve a
small feasible LP from scratch. Read: text Chapter 2.
Sep 12 The simplex method
for LPs for which the initial dictionary is feasible. Termination at
optimality or with an unbounded solution. A proof of optimality from
the final dictionary. Cycling example. Read: Chapter 3, pp 27-34
Sep 14 Initialization. The
two phase simplex method. Fundamental theorem of linear programming.
Sign patterns for optimum and unbounded dictionaries. Why for a given
problem, dictionaries with both of these patterns
cannot exist. Read text Chapter 3, 39-42. Assignment 1 posted.
Sep 19: How fast is the simplex
method? The examples of Klee and Minty. Geometry, and geometrical
interpretation of the simplex method. Read: Ch: 4 and pp 250-257.
Sep 21: Linear programming
duality and the weak duality theorem. Read: Start reading chapter 5.
Try to write down the duals for the problems you considered in
assignment 1, and figure out what they may mean!
Sept 26: Proof of finiteness of
Bland's rule. Finding a solution to a system of inequalities the easy
way. Farkas' lemma and certificates of optimality. Read: handout (pdf) also text pp. 37-38.
Oct 19: First class test.
Nov 23: Second class test.
Nov 28,30,Dec 5 Class
presentations. Attendance
compulsory!
return
to: course home page