The simplex algorithm

The simplex algorithm

Spec DD3–DD4 · AQA A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • Add a slack variable to each ≤\le constraint to make an equation, and write the objective as P−4x−3y=0P-4x-3y=0.
  • 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 QQ, maximise P=−QP=-Q 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: 2x+y≤102x+y\le10 becomes 2x+y+r=102x+y+r=10 with r≥0r\ge0.

The initial tableau has one row per constraint plus the objective row. The variables that are non-zero (here rr and ss) are the basic variables; the others are non-basic and equal 0. At the start, x=y=0x=y=0, the slacks take the right-hand sides and P=0P=0.

12345624681012xy(0, 10)(5, 0)2x + y = 10 (r = 0)
The constraint 2x + y ≤ 10: the slack r = 10 − 2x − y is the distance below the line, and r = 0 on the line.
  • 2x+y≤102x+y\le102x+y+r=102x+y+r=10
  • Objective P=4x+3yP=4x+3yP−4x−3y=0P-4x-3y=0

How is 2x+3y≤182x+3y\le18 written with a slack variable rr?

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 PP.

  1. 1

    Pivot column

    most negative objective entry

  2. 2

    Pivot row

    smallest ratio, positive entries only

  3. 3

    Pivot

    divide the pivot row by the pivot entry

  4. 4

    Clear the column

    make every other entry 0

One iteration

Worked example

Do one iteration for P−4x−3y=0P-4x-3y=0, 2x+y+r=102x+y+r=10, x+y+s=8x+y+s=8.

For P−2x−5y=0P-2x-5y=0, x+y+r=6x+y+r=6, 2x+5y+s=202x+5y+s=20, 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 P=3x+2yP=3x+2y subject to 2x+y≤142x+y\le14 and x+2y≤10x+2y\le10.

The initial equations are 2x+y+r=142x+y+r=14, x+2y+s=10x+2y+s=10 and P−3x−2y=0P-3x-2y=0. Two iterations are needed.

The result agrees with the graphical method, where the optimum is the vertex (6,2)(6,2). Simplex first moves along xx to (7,0)(7,0), then along the line 2x+y=142x+y=14 to (6,2)(6,2).

12345678910112468101214xy(7, 0)(6, 2)2x + y = 14x + 2y = 10
Simplex moves from (0, 0) to (7, 0) to the optimum (6, 2).

Worked example

Solve with the simplex algorithm.

An objective row reads P−2y+3r+s=12P-2y+3r+s=12. 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 PP 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 r=0r=0, s=0s=0 and t=8t=8, the first two resources are fully used and 8 units of the third are spare.

02468rstSlack variableValue
Slack values in the example's final tableau: r and s are 0 (binding), t = 8 units unused.

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 QQ, maximise P=−QP=-Q instead. Then the minimum of QQ is −P-P.

−112345−10−8−6−4−2246810xymin Q = 1max P = −1Q (minimise)P = −Q (maximise)
Illustrative values: Q = (x − 2)² + 1 has minimum 1; P = −Q has maximum −1, so min Q = −max P.
  • Minimise QQmaximise P=−QP=-Q
  • Minimum of QQ−P-P

Worked example

Minimise Q=x−2yQ=x-2y subject to 2x+y≤122x+y\le12 and x+y≤7x+y\le7.

To minimise Q=2x−yQ=2x-y, which objective do you maximise?

Try an exam question

Perform one iteration of the simplex algorithm on the tableau given by P−2x−3y=0P-2x-3y=0, x+y+r=8x+y+r=8, x+2y+s=10x+2y+s=10. State the new objective row.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Which equation results from adding the slack variable rr to the constraint x+y≤8x+y\leq8?

1 mark, marked against the mark scheme

Revision notes