Reading Assignment:

• Class Notes, Sections 4: Due Friday, October 30.
• Course notes: Section 5: Due Monday, November 16.

Homework Assignment:

• Modeling: Modeling problems 1-14 on the class webpage. Due Friday, November 13.
• Supplementary Exercises: Do the supplementary exercises on Complementary Slackness. Due Wednesday, November 4.
• 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 Wednesday, November 6.

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.

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

Skills to Master:

• setting up the auxiliary problem and applying the initial pivot
• applying the two phase simplex method
• applying the complementary slackness theorem to verify optimality
• computing general duals without conversion to standard form
• Apply the dual simplex algorithm
• apply the geometric duality theorem to test optimality

Midterm Exam: