Robinson Tuition
A-level Decision Mathematics 1 · Edexcel 9FM0 · free Further Maths worksheet

The simplex algorithm

Slack variables, initial tableau, pivoting, reading and interpreting a tableau, optimality.

12 original questions, 102 marks. Type your answers below for an instant mark and a score (algebra in any equivalent form, e.g. 2sqrt(3) or 2√3), or print the worksheet, mark it with the answers sheet, and use the solutions to see every step written out by hand.

Worksheet PDFWorked solutions PDFAnswers PDF

The questions

1

A linear programming problem is given as

Maximise P = 4x + 5y + 3z

subject to

3x + 2y + z ≤ 60
x + 4y + 2z ≤ 48
2x + y + 3z ≤ 45
x, y, z ≥ 0

The problem is to be solved using the Simplex algorithm.

  1. Using slack variables s1, s2 and s3, write the three constraints as equations.
  2. Write the objective function in the form used for the objective row of a Simplex tableau.
  3. State the values of x, y, z, s1, s2, s3 and P at the start of the algorithm, and the vertex of the feasible region this represents.
4 marks
Show answer
a) 3x + 2y + z + s1 = 60, x + 4y + 2z + s2 = 48, 2x + y + 3z + s3 = 45 (s1, s2, s3 ≥ 0) b) P - 4x - 5y - 3z = 0 c) x = y = z = 0, s1 = 60, s2 = 48, s3 = 45, P = 0: the origin
2

A linear programming problem is given as

Maximise P = 6x + 5y

subject to

x + y ≤ 12
3x + 2y ≤ 30
x + 3y ≤ 27
x, y ≥ 0

  1. Using slack variables s1, s2 and s3, set up the initial tableau for solving this problem using the Simplex algorithm. Use the template below.
  2. Identify the pivot for the first iteration. You must give reasons for your choice of column and row, showing your θ values.
Initial tableaub.v.xys₁s₂s₃Value
5 marks
Show answer
a) s1: 1, 1, 1, 0, 0 | 12; s2: 3, 2, 0, 1, 0 | 30; s3: 1, 3, 0, 0, 1 | 27; P: -6, -5, 0, 0, 0 | 0 b) x column (most negative, -6); θ values 12, 10, 27, so the pivot is the 3 in the s2 row
3

The initial tableau for a linear programming problem in x, y and z is shown below. The objective is to maximise P.

b.v.xyzs1s2s3Value
s112210040
s231201045
s322100150
P−4−3−50000
  1. Explain why the z column is chosen as the pivot column for the first iteration.
  2. Perform one iteration of the Simplex algorithm. You should show your θ values and state the row operations you use.
  3. Explain whether the tableau you obtained in part (b) is optimal.
Tableau after 1st iterationb.v.xyzs₁s₂s₃ValueRow ops
6 marks
Show answer
a) z has the most negative entry (-5) in the objective row b) z: 1/2, 1, 1, 1/2, 0, 0 | 20 (R1 ÷ 2); s2: 2, -1, 0, -1, 1, 0 | 5 (R2 - 2R1); s3: 3/2, 1, 0, -1/2, 0, 1 | 30 (R3 - R1); P: -3/2, 2, 0, 5/2, 0, 0 | 100 (R4 + 5R1) c) Not optimal: -3/2 in the x column of the objective row
4

A linear programming problem is given as

Maximise P = 5x + 4y

subject to

x + y ≤ 10
3x + y ≤ 24
x + 2y ≤ 16
x, y ≥ 0

  1. Using slack variables, set up the initial tableau for solving this problem with the Simplex algorithm.
  2. Solve the problem using the Simplex algorithm. Take the most negative number in the profit row to indicate the pivot column each time, and state the row operations you use.
  3. Explain how you know your final tableau is optimal, and state the optimal values of x, y, P and the slack variables.

Use the templates below.

Initial tableaub.v.xys₁s₂s₃ValueRow opsTableau after 1st iterationb.v.xys₁s₂s₃ValueRow opsTableau after 2nd iterationb.v.xys₁s₂s₃ValueRow ops
10 marks
Show answer
a) s1: 1, 1, 1, 0, 0 | 10; s2: 3, 1, 0, 1, 0 | 24; s3: 1, 2, 0, 0, 1 | 16; P: -5, -4, 0, 0, 0 | 0 b) Two iterations: x enters (pivot 3 in R2), then y enters (pivot 2/3 in R1) c) No negative values in the objective row; x = 7, y = 3, P = 47, s1 = 0, s2 = 0, s3 = 3
5

A bakery makes loaves of three types: wholemeal, rye and spelt, in batches. It makes x batches of wholemeal, y batches of rye and z batches of spelt each day. The profit, P, in pounds, is to be maximised, where P = 5x + 4y + 3z.

The constraints are

mixing time (minutes): 2x + y + 2z ≤ 95
oven time (minutes): 2x + 2y + z ≤ 110
shaping time (minutes): x + 3y + 3z ≤ 115

where s1, s2 and s3 are the slack variables for these constraints. After applying the Simplex algorithm the tableau below is obtained.

b.v.xyzs1s2s3Value
x10321−12040
y01−1−11015
s300922−52130
P00121320260
  1. Explain how you know that this tableau is optimal.
  2. State the number of batches of each type the bakery should make and the maximum daily profit.
  3. State the values of the slack variables and explain what they mean in context.
  4. Write down the equation represented by the profit row and use it to explain why making any batches of spelt would reduce the profit.
7 marks
Show answer
a) There are no negative values in the profit (objective) row b) x = 40, y = 15, z = 0; profit £260 c) s1 = 0 and s2 = 0: all mixing and oven time used; s3 = 30: 30 minutes of shaping time unused d) P = 260 - 1/2 z - s1 - 3/2 s2: every batch of spelt would reduce P by £0.50
6

The initial tableau for a linear programming problem in x, y and z is shown below. The objective is to maximise P.

b.v.xyzs1s2s3Value
s123110036
s211201020
s332400148
P−3−5−40000
  1. Solve the problem using the Simplex algorithm, taking the most negative number in the profit row to indicate the pivot column at each stage. You must show your θ values and state the row operations you use. Use the templates below.
  2. Explain how you know your final tableau is optimal and state the optimal values of x, y, z and P.
Tableau after 1st iterationb.v.xyzs₁s₂s₃ValueRow opsTableau after 2nd iterationb.v.xyzs₁s₂s₃ValueRow ops
8 marks
Show answer
a) First iteration: y enters, pivot 3 in R1; second iteration: z enters, pivot 5/3 in R2 b) No negative values in the profit row; x = 0, y = 52/5, z = 24/5, P = 356/5
7

A maximisation linear programming problem in x, y and z is being solved using the Simplex algorithm. The slack variables are s1, s2 and s3. The tableau after the first iteration is shown below.

b.v.xyzs1s2s3Value
s11031−1020
y14114014020
s3340340−14175
P−400020160
  1. State the column that contained the pivot for the first iteration. You must give a reason.
  2. By considering the row operations that were used, formulate the original linear programming problem. State the objective and list the constraints as inequalities with integer coefficients.
  3. Perform the second iteration, showing your θ values and the row operations you use.
  4. State whether the tableau you obtained in part (c) is optimal, giving a reason.
Tableau after 2nd iterationb.v.xyzs₁s₂s₃ValueRow ops
10 marks
Show answer
a) The y column, as y is now a basic variable b) Maximise P = 6x + 8y + 2z subject to 2x + 4y + 4z ≤ 100, x + 4y + z ≤ 80, x + y + z ≤ 95, x, y, z ≥ 0 c) x = 20, y = 15, s3 = 60, P = 240 d) Not optimal: -2 in the s2 column in the objective row
8

A linear programming problem is given as

Maximise P = x + ky

subject to

x + 2y ≤ 16
3x + y ≤ 18
x − y ≤ 4
x, y ≥ 0

where k is a positive constant. After two iterations of the Simplex algorithm a possible tableau is

b.v.xys1s2s3Value
y0135−1506
x10−152504
s30045−3516
P00−1 + 3k52 − k504 + 6k
  1. State the values of x, y and P given by this tableau, in terms of k where necessary.
  2. Find the range of values of k for which this tableau is optimal.
  3. Given that k = 3, identify the pivot for the next iteration. You must give reasons for your answer.
8 marks
Show answer
a) x = 4, y = 6, P = 4 + 6k b) 1/3 ≤ k ≤ 2 c) s2 column, since (2 - k)/5 = -1/5 is the only negative entry; only the x row has a positive entry (θ = 4 ÷ 2/5 = 10), so the pivot is the 2/5 in the x row
9

A linear programming problem is given as

Minimise C = 2x − 3y − 4z

subject to

2x + y + z ≤ 30
3x + y + 2z ≤ 75
2x + 2y + 3z ≤ 80
x, y, z ≥ 0

  1. Explain how this problem can be rewritten as a maximisation problem, stating the new objective.
  2. Set up the initial tableau for solving the problem with the Simplex algorithm, using slack variables s1, s2 and s3.
  3. Solve the problem, taking the most negative number in the objective row to indicate the pivot column each time. State the row operations you use and the optimal values of x, y, z and C.

Use the templates below.

Initial tableaub.v.xyzs₁s₂s₃ValueRow opsTableau after 1st iterationb.v.xyzs₁s₂s₃ValueRow opsTableau after 2nd iterationb.v.xyzs₁s₂s₃ValueRow ops
9 marks
Show answer
a) Maximise P = -C = -2x + 3y + 4z b) s1: 2, 1, 1, 1, 0, 0 | 30; s2: 3, 1, 2, 0, 1, 0 | 75; s3: 2, 2, 3, 0, 0, 1 | 80; P: 2, -3, -4, 0, 0, 0 | 0 c) x = 0, y = 10, z = 20, C = -110
10

A workshop makes garden chairs, stools and benches. Each item passes through three processes. The time, in hours, each item needs for each process and the time available each week are shown in the table.

ChairStoolBenchHours available
Cutting21165
Sanding23180
Finishing322110

The profit is £9 on each chair, £5 on each stool and £6 on each bench. The workshop wants to maximise its weekly profit, £P, by making x chairs, y stools and z benches.

  1. Formulate this as a linear programming problem.
  2. Using slack variables s1, s2 and s3, set up the initial tableau and solve the problem using the Simplex algorithm, taking the most negative number in the profit row to indicate the pivot column each time. State the row operations you use. Use the templates below.
  3. Interpret your final tableau in context, including the value of any slack variable that is not zero.
Initial tableaub.v.xyzs₁s₂s₃ValueRow opsTableau after 1st iterationb.v.xyzs₁s₂s₃ValueRow opsTableau after 2nd iterationb.v.xyzs₁s₂s₃ValueRow ops
12 marks
Show answer
a) Maximise P = 9x + 5y + 6z subject to 2x + y + z ≤ 65, 2x + 3y + z ≤ 80, 3x + 2y + 2z ≤ 110, x, y, z ≥ 0 b) Two iterations: x enters (pivot 2 in R1), then z enters (pivot 1/2 in R3); x = 20, z = 25, s2 = 15, P = 330 c) Make 20 chairs, no stools and 25 benches for a profit of £330; cutting and finishing time are used up, 15 hours of sanding time are spare
11

Consider the linear programming problem

Maximise P = 3x + 2y + 4z

subject to

2x + y + z ≤ 53
x + 3y + z ≤ 37
x + 2y + 2z ≤ 50
x ≥ 2, y ≥ 3, z ≥ 1

  1. Explain why the Simplex algorithm cannot be used to solve this problem in its current form.
  2. Use the substitutions x = X + 2, y = Y + 3, z = Z + 1 and P = Q + 16 to reformulate the problem in X, Y and Z so that the Simplex algorithm can be used. Write the constraints as simplified inequalities with integer coefficients.
  3. Using slack variables s1, s2 and s3, solve the reformulated problem with the Simplex algorithm, taking the most negative number in the objective row each time. State the row operations you use. Use the templates below.
  4. Hence state the optimal values of x, y, z and P.
Initial tableaub.v.XYZs₁s₂s₃ValueRow opsTableau after 1st iterationb.v.XYZs₁s₂s₃ValueRow opsTableau after 2nd iterationb.v.XYZs₁s₂s₃ValueRow ops
12 marks
Show answer
a) The lower bounds x ≥ 2, y ≥ 3, z ≥ 1 mean the origin is not feasible, so there is no starting basic feasible solution b) Maximise Q = 3X + 2Y + 4Z subject to 2X + Y + Z ≤ 45, X + 3Y + Z ≤ 25, X + 2Y + 2Z ≤ 40, X, Y, Z ≥ 0 c) X = 10, Y = 0, Z = 15, Q = 90 d) x = 12, y = 3, z = 16, P = 106
12

A linear programming problem is given as

Maximise P = 4x + 6y

subject to

2x + 3y ≤ 30
x + y ≤ 12
x ≤ 8
x, y ≥ 0

  1. Using slack variables s1, s2 and s3, set up the initial tableau and perform one iteration of the Simplex algorithm, taking the most negative number in the objective row to indicate the pivot column. State the row operations you use.
  2. Explain why the tableau you obtained in part (a) is optimal.
  3. Explain how the tableau shows that the optimal solution is not unique.
  4. Perform a further iteration, with x entering the basis, to find a second optimal vertex.
  5. Describe the complete set of optimal solutions.

Use the templates below for parts (a) and (d).

Initial tableaub.v.xys₁s₂s₃ValueRow opsTableau after 1st iterationb.v.xys₁s₂s₃ValueRow opsTableau after 2nd iterationb.v.xys₁s₂s₃ValueRow ops
11 marks
Show answer
a) y enters, pivot 3 in R1: y = 10, s2 = 2, s3 = 8, P = 60 b) No negative values in the objective row c) The non-basic variable x has a zero in the objective row, so it can enter without changing P d) Pivot 1/3 in R2 (θ = 15, 6, 8): x = 6, y = 6, s3 = 2, P = 60 e) All points on 2x + 3y = 30 between (0, 10) and (6, 6), with P = 60

Your score

Answer the questions above and your score appears here.

Every question here is original and written by Robinson Tuition. It follows the Edexcel A-level Further Mathematics specification and suits AQA and OCR Further Maths too; this is not an exam-board paper.

All A-level Decision Mathematics 1 topics