Overview of Week 7

Reading Assignment:
 Course notes: Section 5:
Due Monday, November 16
 Course notes: Section 6:
Due Friday, November 20

Homework Assignment:
 Modeling: Modeling problems 114 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)
 breakeven 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 breakeven prices
 computing ranges (cost coefficients and righthand 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.