Simplex Algorithm - Slack Variables & Initial Tableau (Edexcel A Level Further Maths: Decision Maths 1)

What is the simplex algorithm?

• The simplex algorithm is an alternative to the graphical method for solving linear programming problems
  • It is particularly useful when there are more than 2 decision variables as these cannot be drawn graphically (Not very easily at least!)
  • Essentially the simplex algorithm works by considering each vertex of the basic feasible region in turn until an optimal solution is found
• Initially the simplex algorithm can only be applied to an LP problem that has a basic feasible solution
  • For problems where the basic feasible region contains the origin, the basic feasible solution is the origin
    • In practical situations though, this is often not realistic
      • For example, the number of chairs and tables made by a furniture manufacturer trying to maximise their profit
      • if they make no chairs and no tables, they won't make any profit!
      • but the origin would satisfy all constraints if it is in the feasible region 
  • For problems where the basic feasible region does not contain the origin the algorithm is adapted such that a basic feasible solution is found first
    • then the simplex algorithm can be applied as usual

What are slack variables?

• In the first instance, the simplex algorithm deals with constraints (inequalities) involving ≤ (excluding the non-negativity constraints)
  • Slack variables are used to turn inequalities involving ≤ into equations
• A slack variable, as the name implies, takes up the spare (slack) that a function falls short on in "less than or equal to" constraints
  • A slack variable will be added to (the left hand side of) each constraint so will be non-negative
• The number of slack variables required in a problem will be the same as the number of (non-negativity) constraints involving ≤

What is the initial tableau?

• The simplex algorithm is performed by creating a series of matrices, or tables, showing the values of each decision variable, each slack variable and the objective function until an optimal solution is found
• The first of these tables is called the initial tableau
• To set up the initial tableau, the equations derived from the inequalities (constraints) are needed along with a rearrangement of the objective function such that zero is on one side
  • e.g.  becomes 
• The initial tableau is created by
  • columns represent the basic variable (b.v.), the decision variables (), the slack variables  and the value (the RHS of each equation)
  • rows are completed with the coefficients of each equation/constraint
    • the last row is the (rearranged) objective function
  • the basic variable column is completed last
    • the basic variable for each row is the variable that has a 1 in that row but 0's in all other rows of that column
    • the last row is always the objective row

How do I apply the simplex algorithm?

• Once the initial tableau is set up the first iteration can begin

• STEP 1
  For each row (except the objective row), find the -value by dividing the 'Value' by the entry in the pivot column
  • Deduce the pivot column by looking for the most negative entry in the objective row (excluding 'Value')

• STEP 2
  Find the pivot element (often just called the pivot) by finding where the pivot column and pivot row meet
  • Deduce the pivot row by selecting the row with the least positive -value

• STEP 3
  Use a series of row operations to update the tableau
  • manipulate the pivot row so that the pivot element is 1
  • for each 'old row' (i.e. each row from the previous tableau) use a multiple of the 'new pivot row' to make each entry in the pivot column zero, including the objective row

• STEP 4
  Complete the updated tableau by completing the header column of basic variables (b.v.)
  • to do this look for the column with one 1 and all other entries 0

How do I know when the simplex algorithm is complete?

• The simplex algorithm is compete when there are no negative entries in the objective row (excluding 'Value')
  • This tableau is called the final tableau
  • The optimal solution can be found from the final tableau

How do I find the optimal solution from the final tableau?

• The basic variable (b.v.) and value column indicate the optimal solution
  • The variables in the basic value column take the value in their value column
  • The objective function will then have a maximum value of the entry in its value column
  • All other variables are non-basic and take the value of 0, regardless of values in the table