Homework Assignment:

• Supplemantary Exercises:
  • Simplex Algorithm for LPs with Feasible Origin: Due Friday, October 12.
  • Two Phase Simplex Algorithm. Due Friday, Oct 26.
  • Complementary Slackness
  • Modeling: Modeling problems 1-14 on the class webpage. Due Friday, Oct 26.

• 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

• 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

• 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

• Quiz:

  Friday, Oct 26.
  • This weeks quiz will focus on the vocabulary words from Sections 2 and 3 of the class notes. It is important that you learn the terminology (vocabulary) for both the dictionary and the tableau presentations of this material. You will also be responsible for the LP models 1--14. Finally, you will need to be able to apply the two phase simplex algorithm to solve LPs that do not have feasible origin. That is, you need to
    • (a) set up the auxiliary problem for an LP in standard form that does not have feasible origin,
    • (b) write the initial tableau for the auxiliary problem,
    • (c) know how to perform the first pivot on the auxiliary problem so as to obtain an initial feasible tableau for the auxiliary problem,
    • (d) solve the auxiary problem,
    • (e) extract the initial feasible tableau for the original problem, and
    • (f) solve for the solution.
    See the supplementary exercises on the two phase simplex algorithm.