## Overview of 407 Week 5

• #### 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 dictionary
• a degenerate simplex tableau
• a degenerate basic solution
• a degenerate simplex iteration
• cycling
• smallest subscript rule
• auxiliary problem
• two phase simplex method
• state and prove the fundamental theorem of linear programming
• 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?
• How do you read off the optimal solutions for both the primal and dual problems from the optimal tableau?
• 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?
• 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.
• #### 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
• the fundamental block matrix equation that shows how every simplex tableau can be obtained by multiplying the initial tableau on the left by a nonsingular matrix
• degeneracy
• cycling
• the auxiliary problem and the two phase simplex algorithm
• the fundamental theorem of linear programming
• Section 4:
• the fundamental block matrix equation that shows how every simplex tableau can be obtained by multiplying the initial tableau on the left by a nonsingular matrix
• 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 30.
• The first questions on this weeks quiz will focus on the theory and vocabulary words from Sections 2, 3 and 4 (not including the dual simplex algorithm) 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 - 11. In the final question you will need to be able to solve LPs using the two phase simplex algorithm. For the two phase simplex algorithm, 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 the original problem.
See the supplementary exercises on the two phase simplex algorithm.