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 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.