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)
- 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 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)
- 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
-
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.