• Simplex Algorithm for LPs with Feasible Origin: Due Friday, October 11.
• Two Phase Simplex Algorithm. Due Wednesday, Oct 23.
• Complementary Slackness: Due Friday, Oct. 25.
• Computing Duals: Due Monday, Oct 28.
• Modeling: Modeling problems 1-17 on the class webpage. Due Friday, November 1.

Vocabulary List:

• Section 3:
  • LP with feasible origin
  • the basic rule for choosing the entering variable
  • the basic rule for choosing the leaving variable
  • degeneracy
  • a degenerate basic solution
  • a degenerate simplex iteration
  • cycling
  • smallest subscript rule
  • auxiliary problem
  • two phase simplex method
  • the fundamental theorem of linear programming
  • What is the block structure of both the initial and the optimal tableaus, and why does the optimal tableau have this structure?
  • How do you read off the optimal solutions for both the primal and dual problems from the block structured optimal tableau?
• 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, not as stated in the book)
  • What is the structure of both the initial and the optimal dictionaries, and why does the optimal dictionary have this structure?
  • What is the block structure of both the initial and the optimal tableaus, and why does the optimal tableau have this structure?
  • 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 general 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
• 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 2:
  • Dictionaries
  • LP tableau
  • Basic feasible solutions
  • The basis associated with a dictionary
  • A simplex pivot and the simplex algorithm
• Section 3:
  • simplex iteration
  • degeneracy
  • cycling
  • the auxiliary problem and the two phase simplex algorithm
  • the fundamental theorem of linear programming
• 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 BFSs
  • geometry of duality
  • geometry of degeneracy
  • degeneracy and multiple optimal solutions

Skills to Master:

• Setting up a dictionary
• Setting up a tableau
• Pivoting and the simplex algorithm
• 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