• 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

• 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

• 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 block 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 block structured optimal tableau?

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
  • 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:

• 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
• applyig the two phase simplex algorithm

Quiz:

• 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 Sections 1 and 2 of the notes (as given above), or you will be asked to model one of the LP models 1-10 on the class webpage. For the second problem, you will be asked to solve an LP that is given in standard form and has feasible origin using the simplex algorithm with simplex tableaus (not with dictionaries).