## Overview of Week 7

• #### Homework Assignment:

• Modeling: Modeling problems 1-14 on the class webpage. Due Friday, November 13.
• 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 Friday, November 6.
• Supplementary Exercises: Do the supplementary exercises on the Geometric duality. Due Friday, November 20.
• Sensitivity Analysis: The Silicon Chip Corp problems due Monday, Nov 23.
• Sensitivity Analysis: The Concrete Products Corp problems, due Monday, Nov. 30.
• #### 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.
• Section 6: Sensitivity Analysis
• 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?
• tableau approach to sensitivity analysis (block matrix structure)
• break-even price
• reduced cost
• marginal values
• shadow prices
• objective coefficient range
• right hand side (or resource) range
• pricing out
• the fundamental theorem on sensitivity analysis
• #### 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
• Section 6:
• tableau approach to sensitivity analysis
• Range analysis (cost coefficients and right hand sides)
• Pricing out
• #### Skills to Master:

• Compute duals to LPs in generalized standard form.
• Apply the dual simplex algorithm
• apply the geometric duality theorem to test optimality
• computing break-even prices
• computing ranges (cost coefficients and right-hand sides)
• pricing out a new activity
• #### Quiz:

Friday, November 13.
• The first questions on this quiz will focus on the vocabulary and theory in Section 4 of the notes and and the last question will focus on the dual simplex algorith. solve an LP in standard form by the dual simplex algorithm.