Overview of Week 7
Math 407 Section A, November 5, 2012
-
Reading Assignment:
- Course notes:Section 4: pages 1-8:
Due Friday, Oct 26.
- Course notes:Section 4: pages 8-11:
Due Monday, Oct 29.
- Course notes:Section 5: pages 1-9:
Due Wednesday, Nov 7.
- Course notes:Section 5: pages 9-17:
Due Friday, Nov 9.
-
Homework Assignment:
-
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, not as stated in the book)
- What is the structure of both the initial and
the optimal dictionaries, and why does the optimal dictionary
have this structure?
- What is the block structure of both the initial and
the optimal tableaus, and why does the optimal tableau
have this structure?
- 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 general 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
- 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 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:
- 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
-
Quiz:
Friday, November 9
- The first question quiz is based on the vocabulary words for
Section 4 of the notes or models 1-18. The second question
will ask you to apply
the dual simplex algorithm to solve an LP.