Overview of Week 3
Math 407 Section A, October 8, 2012
-
Reading Assignment:
- Course notes: Section 1:
Introduction Due Wednesday, Oct 3.
- Course notes: Section 2: pages 1-6:
Due Monday, Oct 8.
- Course notes: Section 2: pages 6-12:
Due Friday, Oct 12.
- Course notes:Section 2: pages 12-16:
Due Monday, Oct 15.
- Course notes:Section 3: pages 31-37:
Due Wednesday, Oct 17.
- Course notes:Section 3: pages 37-39:
Due Friday, Oct 19.
- Course notes:Section 3: pages 39-42:
Due Monday, Oct 22.
-
Homework Assignment:
-
Vocabulary List:
- Section 1:
- decision variable
- linear function
- linear inequality
- the solution set of a system of linear inequalities
- objective function
- linear programming
- explicit and implicit linear constraints
- the 4 steps in LP modeling
- standard form
- optimal value
- optimal solution
- feasible solution
- infeasible LP
- unbounded LP
- optimal value function
- sensitivity analysis
- the marginal value of a resource (shadow prices)
- the dual of an LP in standard form
- the Weak Duality Theorem
- Section 2:
- slack variables
- objective variable
- the initial dictionary (standard form)
- the initial tableau (standard form)
- dictionary (for an LP in standard form)
- simplex tableau (for an LP in standard form)
- feasible solution
- feasible dictionary
- basic solution
- basic feasible solution
- basic variables in a dictionary
- nonbasic variables in a dictionary
- a basis for a dictionary
- pivot row
- pivot column
- pivoting
- What is the rule for choosing the entering variable?
- What is the rule for choosing the leaving variable?
- optimal dictionary
- optimal tableau
- 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 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?
-
Key Concepts:
- Section 1:
- What is an LP?
- the 4 steps of LP modeling
- graphical solutions of two dimensional LPs
- sensitivity analysis
- standard form
- the Weak Duality Theorem
- Section 2:
- Dictionaries
- simplex tableau
- Basic feasible solutions
- The basis associated with a dictionary
- A simplex pivot and the simplex algorithm
- Section 3:
- simplex iteration
- degeneracy
- cycling
- the auxiliary problem and the two phase simplex algorithm
- the fundamental theorem of linear programming
-
Skills to Master:
- solving a 2 dimensional LP graphically
- 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 12.
- This quiz is based on the vocabulary words and homework
associated with
Sections 1 and 2 of the Course Notes. The first problem on the quiz
will either ask that you define, describe, or give an example of
one or more of the
vocabulary words from Section 1 of the notes (as given above),
or you will be asked to model one of the LP models 1-6
on the class webpage.
For the second problem, you will be asked to
transform an arbitrary LP into standard form
or to solve an LP that is
given in standard form and has feasible origin using the simplex
algorithm with simplex tableaus.