## Overview of 407 Week 4

• Course notes: Section 2: Due Friday, October 16.
• Course notes: Section 3: Pages 32 - 37, Due Monday, October 19.
• Course notes: Section 3: Due Friday, October 23.

• #### Vocabulary List:

• Section 2:
• slack variables
• dictionary (for an LP)
• feasible solution
• feasible dictionary
• basic feasible solution
• basic variables in a dictionary
• nonbasic variables in a dictionary
• a basis for a dictionary
• pivot row
• pivot column
• pivoting
• LP simplex tableau
• What is the requirement for choosing the entering variable?
• What is the requirement for choosing the leaving variable?
• Section 3:
• LP with feasible origin
• the basic requirement for choosing the entering variable
• the basic requirement 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
• 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 dictionary or 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?
• #### Key Concepts:

• Section 2:
• Dictionaries
• LP simplex tableau
• Basic feasible solutions and how to read them off of a simplex tableau
• 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
• #### Skills to Master:

• Transforming an arbitrary LP to one in standard form.
• Setting up a dictionary
• Setting up a tableau
• Pivoting and the simplex algorithm for problems with feasible origin.
• setting up the auxiliary problem and applying the initial pivot
• applying the two phase simplex algorithm
• #### Quiz:

Friday, October 23.
• The first quiz questions are either based on the theory and vocabulary words for Section 2 and Section 3 through "smallest subscript rule", or one of the models 1-9.
The last question will ask you to solve an LP with feasible origin providing the solution to both the primal and dual problems.