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