The Simplex algorithm
Studying this course? Keep your progress in one place.
Key facts
- The Simplex algorithm moves from vertex to vertex without drawing, and handles up to four variables.
- Write the objective row as , with slack variables as the starting basic variables.
- Pivot column: most negative entry in the row. Pivot row: smallest non-negative ratio, ignoring zero and negative entries.
- Divide the pivot row by the pivot, then use row operations to make the rest of the column 0.
- Stop when the row has no negative entries. To minimise , maximise .
The initial tableau
Add a slack variable to each constraint, write the objective as , and list each equation as a row.
The Simplex algorithm solves a linear program by moving from vertex to vertex of the feasible region, improving the objective each time.
For a maximising problem with constraints, add a slack variable to each. The objective becomes .
The tableau comes from , and . The starting solution has , as the basic variables and , .
| Row r | Row s | Row P | |
|---|---|---|---|
| x | 1 | 1 | -2 |
| y | 1 | 2 | -3 |
| r | 1 | 0 | 0 |
| s | 0 | 1 | 0 |
| Value | 10 | 16 | 0 |
Row r
- x:
- 1
- y:
- 1
- r:
- 1
- s:
- 0
- Value:
- 10
Row s
- x:
- 1
- y:
- 2
- r:
- 0
- s:
- 1
- Value:
- 16
Row P
- x:
- -2
- y:
- -3
- r:
- 0
- s:
- 0
- Value:
- 0
How is written in the objective row?
Choosing the pivot
The pivot column has the most negative -row entry; the pivot row has the smallest positive ratio.
Each iteration chooses a pivot in steps.
Ignore zero and negative entries in the ratio test: they would give an infeasible next solution. Choosing the smallest ratio keeps every value non-negative.
In the example, the most negative entry is (column ). The ratios are and , so row is the pivot row and the pivot is the 2.
- 1
Pivot column
most negative entry in the P row; this variable enters
- 2
Ratio test
value divided by the positive entry in the pivot column
- 3
Pivot row
smallest ratio; this variable leaves
- 4
Pivot element
where they meet
Entries in a pivot column are 2, 0 and 4 with values 6, 5 and 4. Which row is the pivot row?
Row operations
Divide the pivot row by the pivot, then subtract multiples of it from every other row to make the pivot column 0.
- Divide the pivot row by the pivot element so the pivot becomes 1: row becomes (now row ).
- For every other row, including , subtract a multiple of the new pivot row so the pivot column becomes 0.
Row minus row gives . Row plus row gives .
Now , , and , better than 0.
| Row r | Row y | Row P | |
|---|---|---|---|
| x | 1/2 | 1/2 | -1/2 |
| y | 0 | 1 | 0 |
| r | 1 | 0 | 0 |
| s | -1/2 | 1/2 | 3/2 |
| Value | 2 | 8 | 24 |
Row r
- x:
- 1/2
- y:
- 0
- r:
- 1
- s:
- -1/2
- Value:
- 2
Row y
- x:
- 1/2
- y:
- 1
- r:
- 0
- s:
- 1/2
- Value:
- 8
Row P
- x:
- -1/2
- y:
- 0
- r:
- 0
- s:
- 3/2
- Value:
- 24
Which operation turns the entry in the pivot column into 0?
Optimality
Repeat until the row has no negative entries. Then read the solution from the basic variables.
Repeat iterations until the row has no negative entries. The tableau is then optimal.
Continuing the example, (with ) enters. The ratios are and , so row is the pivot row.
Basic variables take the value in their row and non-basic variables are 0. So , , and .
Check: and , both binding, and .
| Row x | Row y | Row P | |
|---|---|---|---|
| x | 1 | 0 | 0 |
| y | 0 | 1 | 0 |
| r | 2 | -1 | 1 |
| s | -1 | 1 | 1 |
| Value | 4 | 6 | 26 |
Row x
- x:
- 1
- y:
- 0
- r:
- 2
- s:
- -1
- Value:
- 4
Row y
- x:
- 0
- y:
- 1
- r:
- -1
- s:
- 1
- Value:
- 6
Row P
- x:
- 0
- y:
- 0
- r:
- 1
- s:
- 1
- Value:
- 26
A tableau has row . Is it optimal?
Minimising problems
Maximise instead, then give the minimum as .
The Simplex algorithm as set out maximises. To minimise , maximise , then state the minimum as .
With three or four variables the process is the same, with more columns. Keep fractions exact and check each row operation.
Substitute back into the original constraints to check your final answer.
- Minimise maximise
- Minimum of
Worked example
Minimise subject to and .
- 1
Maximise , so .
- 2
Add slack variables to both constraints and set up the tableau.
- 3
After two iterations the optimum is , , with .
- 4
Convert back: .
Maximising gives . What is the minimum of ?
Try an exam question
Maximise subject to and , . Use one iteration of the Simplex algorithm from the initial tableau, with slack variables and , and state the solution.
[4 marks]
- [1]Chooses the column as pivot column, the most negative entry in the row.
- [1]Ratios and , so row is the pivot row.
- [1]New row is after adding 3 times the pivot row.
- [1]No negatives in the row, so optimal: , , .
That's the notes covered.
Carry on to the next subtopic.
Try a question
Which equation is the objective row of the initial tableau?
1 mark, marked against the mark scheme
Which equation is the objective row of the initial tableau?
1 mark, marked against the mark scheme