## Overview of Week 6

• #### Homework Assignment:

• Modeling: Modeling problems 1-14 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.