Overview of 407 Week 4

Reading Assignment:
 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.

Homework Assignment:

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 19.
The last question will ask you to solve an LP with
feasible origin providing the solution
to both the primal and dual problems.