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 14
on the class webpage.
The last problem on the quiz, will ask you to
transform an arbitrary LP into standard form.