simplex-algorithm-slack-variables-and-initial-tableau

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

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 ≤