Overview of Week 4
Math 407, January 28, 2019
-
Reading Assignment:
- Course notes: Section 2:
Due Friday, Jan. 25.
- Course notes: Section 3: Pages 32 - 37,
Due Wednesday, January 30.
- Course notes: Section 3:
Due Monday, Feb. 4.
- Course notes: Section 4:
Due Friday, Feb. 8.
-
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, Feb. 1.
-
The first question on the quiz is either
based on the vocabulary words for Section 2,
or one of the models 1-7.
In the second question you will be asked to solve an LP with
feasible origin.