Overview of 407 Week 3
-
Reading Assignment:
- Course notes: Section 1:
Due Friday, Oct 9
- 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 1:
- linear function
- linear inequality
- the solution set of a system of linear inequalities
- linear programming
- objective function
- explicit and implicit linear constraints
- standard form
- optimal value
- optimal solution
- feasible solution
- infeasible LP
- unbounded LP
- decision variables
- sensitivity analysis
- optimal value function
- the marginal value of a resource (shadow prices)
- the dual of an LP in standard form
- the statement of the Weak Duality Theorem (from online class notes)
- the proof of the Weak Duality Theorem (from online class notes)
- Section 2:
- slack variables
- dictionary (for an LP)
- simplex tableau
- feasible solution
- feasible dictionary / feasible tableau
- basic feasible solution
- basic variables in a dictionary or simplex tableau
- nonbasic variables in a dictionary or simplex tableau
- a basis for a dictionary or simplex tableau
- 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 or 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
- 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?
-
Key Concepts:
- Section 1:
- What is an LP?
- graphical solutions of two dimensional LPs
- sensitivity analysis
- duality
- standard form
- Section 2:
- Dictionaries
- LP 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 product 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 simplex 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, Oct. 16.
- This quiz is based on the theory, vocabulary words and homework
associated with
Section 1 and Section 2 (sections 2.1 and 2.2) of the Course Notes.
The first problems on the quiz
concern the theory and vocabulary in
Section 1 and Section 2 (sections 2.1 and 2.2) of the Course Notes,
or you will be asked to model one of the LP models 1-4
on the class webpage.
The last problem on the quiz, will ask you to
transform an arbitrary LP into standard form.