Overview of 407 Week 5

Reading Assignment:
 Course notes: Section 3:
Due Friday, October 23.
 Course notes: Section 4:
Due Friday, October 30.

Homework Assignment:

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.