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

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