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.