Overview of Week 6

Reading Assignment:

Homework Assignment:
 Modeling: Modeling problems 114 on the class webpage.
Due Friday, November 13.
 Supplementary Exercises: Do the supplementary exercises on
Complementary Slackness.
Due Wednesday, November 4.
 Supplementary Exercises: Do the supplementary exercises
on computing dual LPs.
Due Friday, November 6.
 Supplementary Exercises: Do the supplementary exercises
on the dual simplex algorithm.
Due Wednesday, November 6.

Vocabulary List:
 Section 4:
 the dual LP to an LP in standard form
 Statement and proof of the Weak Duality Theorem for LP
(as stated in the notes)
 primal feasible dictionary or tableau
 dual feasible dictionary or tableau
 optimal dictionary or tableau
 What is the structure of both the initial and
the optimal dictionaries, and why does the optimal dictionary
have this structure?
 What is the structure of both the initial and
the optimal tableaus, and why does the optimal tableau
have this structure?
 What is the fundamental block matrix product that shows how
every simplex tableau can be obtained by multiplying the initial tableau
on the left by a nonsingular matrix?
 How do you read off the optimal solutions for both the
primal and dual problems from the optimal tableau or dictionary?
 Statement and proof of the Strong Duality Theorem
 all relationships between primal and dual problems
 The Complementary Slackness Theorem
 State the primal and dual problems for the more general
standard form.
 What are the primal and dual correspondences between the
primal and dual in the more genral standard form?
 State and prove the weak Duality theorem for the more general
standard form.
 primal and dual feasible tableaus and dictionaries
 primal simplex pivot
 dual simplex pivot
 dual simplex algorithm
 primal degeneracy and dual degeneracy and the relationship to multiple
optimal solutions to the dual and promal problems, respectively.
 Section 5:
 hyperplane
 halfspace
 convex set
 polyhedral convex set
 vertex of a polyhedral convex set
 geometric interpretation of Basic Feasible Solutions
 geometric interpretation of Degeneracy
 geometric interpretation of Duality
 Fundamental representation theorem for vertices.
 The geometry of degeneracy.
 the relationship between primal (dual) degeneracy and
multiple optimal solutions to the (dual) primal problem.
 The Geometric Duality Theorem.

Key Concepts:
 Section 4:
 The fundamental Theorem of Linear Programming
 The Strong Duality Theorem
 Complementary slackness
 general duality correspondences
 primal and dual feasibility for tableaus and dictionaries
 the dual simplex algorithm
 Section 5:
 vertices and BFSs
 geometry of duality
 geometry of degeneracy
 degeneracy and multiple optimal solutions

Skills to Master:
 setting up the auxiliary problem and applying the initial pivot
 applying the two phase simplex method
 applying the complementary slackness theorem to verify optimality
 computing general duals without conversion to standard form
 Apply the dual simplex algorithm
 apply the geometric duality theorem to test optimality

Midterm Exam:
Friday November 6 and Monday November 9.