Overview of Week 8

Reading Assignment:

Homework Assignment:

Vocabulary List:
 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 Strong Duality Theorem
 Complementary slackness
 general duality correspondences
 primal and dual feasibility for tableaus and dictionaries
 the dual simplex algorithm
 Section 5:
 vertices and basic feasible solutions
 geometry of duality
 geometry of degeneracy
 Section 6:
 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

Skills to Master:
 setting up the auxiliary problem and applying the initial pivot
 applying the two phase simplex algorithm
 computing general duals without conversion to standard form
 Apply the dual simplex algorithm
 apply the Geometric Duality Theorem to assess optimality

Quiz:
Friday, November 15.

The first question on the quiz will concern the
theory and vocabulary words from Sections 5 and 6.
In the second question you will be asked to apply
the Geometric Duality Theorem to assess optimality.