The simplex algorithm
Studying this course? Keep your progress in one place.
Key facts
- Add a slack variable to each constraint to make an equation, and write the objective as .
- Pivot column: the most negative entry in the objective row.
- Pivot row: the smallest ratio of right-hand side to a positive pivot-column entry.
- A solution is optimal when no objective-row coefficient is negative.
- To minimise , maximise and change the sign of the result.
Slack variables and the first tableau
Add a slack variable to each constraint to make it an equation, and write the objective with every variable on the left.
The simplex algorithm solves LPs algebraically, so it works when there are too many variables to draw.
A slack variable is the unused part of the resource: becomes with .
The initial tableau has one row per constraint plus the objective row. The variables that are non-zero (here and ) are the basic variables; the others are non-basic and equal 0. At the start, , the slacks take the right-hand sides and .
- Objective
How is written with a slack variable ?
One iteration of simplex
Pick the pivot column, pick the pivot row by the smallest positive ratio, then row-reduce so the pivot column is a unit column.
Choose the pivot column: the most negative entry in the objective row. If there is none, stop.
For the pivot row, find the ratio (right-hand side divided by entry) for each row where the pivot-column entry is positive, and take the smallest.
Divide the pivot row by the pivot entry, then add or subtract multiples of it to make every other entry in the pivot column 0, including the objective row. The new tableau gives a better value of .
- 1
Pivot column
most negative objective entry
- 2
Pivot row
smallest ratio, positive entries only
- 3
Pivot
divide the pivot row by the pivot entry
- 4
Clear the column
make every other entry 0
Worked example
Do one iteration for , , .
- 1
Pivot column: is the most negative, so the column is .
- 2
Ratios: and . The smallest is 5, so the pivot is the 2 in the row.
- 3
Divide the pivot row by 2: .
- 4
Subtract it from the row: .
- 5
Add 4 times it to the objective row: .
For , , , which entry is the pivot?
A two-iteration example
Repeat iterations until the objective row has no negative entries, then read off the solution.
Maximise subject to and .
The initial equations are , and . Two iterations are needed.
The result agrees with the graphical method, where the optimum is the vertex . Simplex first moves along to , then along the line to .
Worked example
Solve with the simplex algorithm.
- 1
Initial: , , .
- 2
Pivot column ; ratios and , so pivot on the 2.
- 3
After iteration 1: , , .
- 4
The objective row still has . Pivot column ; ratios and , so pivot on the .
- 5
After iteration 2: , , .
- 6
No negative coefficients remain, so the solution is optimal.
An objective row reads . Is the solution optimal?
Interpreting a tableau
Basic variables equal their right-hand sides, non-basic variables are 0, and a zero slack means the resource is fully used.
Read the current solution from the tableau. Basic variables take the right-hand side of their row, non-basic variables are 0, and is the right-hand side of the objective row.
A solution is optimal when every coefficient in the objective row is non-negative.
A slack of 0 means the constraint is a binding constraint: that resource is fully used. A positive slack is the amount unused. If the final tableau has , and , the first two resources are fully used and 8 units of the third are spare.
Slack is 0
- Binding constraint
- Resource fully used
Slack is positive
- Not binding
- The slack is the amount unused
In the final tableau, the slack variable for a constraint is 0. What does this mean?
Minimising an objective function
Maximise the negative of the objective, then change the sign of the result.
The simplex algorithm as set out maximises. To minimise , maximise instead. Then the minimum of is .
- Minimise maximise
- Minimum of
Worked example
Minimise subject to and .
- 1
Maximise , with objective row .
- 2
The pivot column is and the ratios are and , so the pivot is the 1 in the second row.
- 3
After one iteration the objective row is , with no negative entries.
- 4
So , and .
To minimise , which objective do you maximise?
Try an exam question
Perform one iteration of the simplex algorithm on the tableau given by , , . State the new objective row.
[4 marks]
- [1]The pivot column is (most negative entry, ).
- [1]The ratios are and , so the pivot is the 2 in the row.
- [1] row divided by 2: ; row becomes .
- [1]New objective row: .
That's the notes covered.
Carry on to the next subtopic.
Try a question
Which equation results from adding the slack variable to the constraint ?
1 mark, marked against the mark scheme
Which equation results from adding the slack variable to the constraint ?
1 mark, marked against the mark scheme