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

Introduction to the Simplex Algorithm

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

Slack Variables

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 ≤

Initial Tableau

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

e.g.

Constructing the initial tableau for the objective function

and equations (constraints)

Simplex Algorithm

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