Maths › Decision Mathematics 1 › The Simplex algorithm
The Simplex algorithm
Graphs run out at two variables. Simplex walks from corner to corner algebraically instead, improving at every step, and stops when no move can improve the objective any further.
Builds on Linear programming: formulation and graphical solution and Matrix algebra and transformations.
IN THIS TOPIC
- Set up the initial tableau from a formulated problem.
- Choose the pivot column and row and carry out the row operations.
- Read the solution from a final tableau and recognise when to stop.
COMMON MISCONCEPTION
The Simplex algorithm stops when the value in the bottom right corner stops increasing.
Setting up and pivoting
Add a slack variable to each constraint and write the objective as P − 4x − 5y = 0. The tableau then has one row per constraint and one for the objective, with the slack variables forming the starting basic solution. Every real variable is zero, so you begin at the origin, a feasible corner here, because a ≤ constraint with a non-negative right-hand side is satisfied when everything is zero.
Each iteration has three steps. Choose the pivot column as the one with the most negative entry in the objective row, since increasing that variable improves P fastest. Choose the pivot row by the ratio test: divide each row's value by its entry in the pivot column and take the smallest non-negative result, skipping negative and zero entries entirely.
Then divide the pivot row by the pivot element, and add or subtract multiples of that row from the others until the pivot column has a one in the pivot row and zeros everywhere else.
WORKED EXAMPLE
The first pivot
Maximise P = 4x + 5y subject to x + y ≤ 10 and 2x + 3y ≤ 24.
The objective row is P − 4x − 5y = 0, so the most negative entry is −5 and the pivot column is y.
Ratio test: 10 ÷ 1 = 10 and 24 ÷ 3 = 8, so the pivot row is the second.
After pivoting, P = 40 with y = 8. The objective row still has a negative entry in x, so another iteration follows and finishes at P = 44 with x = 6, y = 4.
Stopping, and reading the answer
The algorithm stops when no negative entries remain in the objective row. At that point no variable can be increased without reducing P. That is a condition on the row, not on whether the corner value has changed: stopping as soon as an iteration leaves P where it was would quit too early on degenerate problems, which do just that.
Reading the answer off is mechanical. Any column that looks like a column of the identity gives a basic variable equal to its row's value, and every other variable is zero. To minimise instead of maximise, maximise the negative of the objective and change the sign back at the end.
GUIDED PRACTICE
Reading a final tableau
A final tableau has objective row P + 2s1 + s2 = 44, and rows giving x = 6 and y = 4. State the solution and explain how you know it is optimal.
Show the working
No entry in the objective row is negative, so no variable can be increased to improve P: the tableau is optimal.
x = 6, y = 4, and the slack variables are non-basic so s1 = s2 = 0.
P = 44, read from the value column of the objective row.
Both slacks being zero says both constraints are tight, which matches the graphical answer at the intersection.
Constraints that break the starting basis
Ordinary Simplex starts from the free corner the slack variables provide: with ≤ constraints and non-negative right-hand sides, the origin is feasible and the slacks are the starting basic solution. A ≥ constraint with a positive right-hand side breaks that. The origin no longer satisfies it, and subtracting a surplus variable leaves no obvious basic feasible solution to pivot from, so a starting point has to be manufactured. Both methods on the specification do that with artificial variables.
The two-stage method spends its first stage minimising the sum of the artificial variables. When that sum reaches zero the tableau sits at a genuine feasible corner, and ordinary Simplex takes over for the second stage. The big-M method instead subtracts a large multiple M of each artificial variable from the objective, which makes keeping them positive so expensive that the algorithm drives them out on its own. Either way, check at the end that every artificial variable has come back to zero.
ASSESSMENT FOCUS
- Write the objective row with the signs reversed, as P − 4x − 5y = 0.
- Show the ratio test in full, including the entries you skipped and why.
- State the row operations you performed, in the form 'row 1 minus row 2'.
- Stop only when no negative entries remain in the objective row, and say that is why you stopped.
- Give the values of the slack variables as well as x and y; they are usually worth a mark.
- After a two-stage or big-M run, confirm the artificial variables have returned to zero.
CHECK YOURSELF
In a tableau the pivot column entries are 2, −1 and 4, with values 12, 8 and 20. Which row is the pivot row?
Show a hint
Skip the negative entry.
Show the answer
Ratios are 12 ÷ 2 = 6 and 20 ÷ 4 = 5; the −1 is skipped entirely. The smallest is 5, so the third row is the pivot row.
Pivot on the most negative entry in the objective row.
Choose the row by the smallest non-negative ratio of value to pivot-column entry, skipping negative and zero entries.
Stop when no negative entries remain in the objective row; ≥ constraints need the two-stage or big-M method to get started.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
Or read them with their worked answers on the the simplex algorithm questions page.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- Set up the initial tableau from a formulated problem.
- Choose the pivot column and row and carry out the row operations.
- Read the solution from a final tableau and recognise when to stop.
Open the full revision checklist to see every objective in the course in one place.