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

Two-stage simplex and big-M

Surplus and artificial variables, the two-stage method and the big-M method for ≥ constraints.

12 original questions, 98 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 = 3x + 4y

subject to

x + 2y ≤ 20
x + y ≥ 6
x, y ≥ 0

  1. Explain why the Simplex algorithm cannot be used directly to solve this problem.
  2. Write each constraint as an equation, using exactly one slack variable, one surplus variable and one artificial variable. State which of your variables is which.
  3. Explain why the artificial variable is needed.
4 marks
Show answer
a) The ≥ constraint x + y ≥ 6 means the origin is not in the feasible region, so the algorithm has no basic feasible solution to start from b) x + 2y + s1 = 20, x + y - s2 + a1 = 6; s1 slack, s2 surplus, a1 artificial c) With x = y = 0 the second equation would need s2 = -6, which is not allowed; a1 = 6 gives a starting basic feasible solution
2

A linear programming problem is given as

Maximise P = 2x + 3y + z

subject to

x + y + z ≤ 30
2x + y ≥ 8
x, y, z ≥ 0

The problem is to be solved using the big-M method, with slack variable s1, surplus variable s2 and artificial variable a1.

  1. Define, in this context, what M represents.
  2. Show that the objective row of the initial tableau represents the equation

P − (2 + 2M)x − (3 + M)y − z + Ms2 = −8M

4 marks
Show answer
M is an arbitrarily large positive real number; P = 2x + 3y + z - Ma1 with a1 = 8 - 2x - y + s2 gives the result
3

A linear programming problem is given as

Maximise P = 5x + 3y + 2z

subject to

3x + y + 2z ≤ 40
x + y + z ≥ 10
y − z ≥ 2
x, y, z ≥ 0

The problem is to be solved using the big-M method.

  1. Using slack variable s1, surplus variables s2 and s3, and artificial variables a1 and a2, set up the initial tableau. You must show how you obtain the objective row. Use the template below.
  2. Identify the pivot for the first iteration of the big-M method, giving reasons for your choice.
Initial tableaub.v.xyzs₁s₂s₃a₁a₂Value
7 marks
Show answer
a) s1: 3, 1, 2, 1, 0, 0, 0, 0 | 40; a1: 1, 1, 1, 0, -1, 0, 1, 0 | 10; a2: 0, 1, -1, 0, 0, -1, 0, 1 | 2; P: -5 - M, -3 - 2M, -2, 0, M, M, 0, 0 | -12M b) y column (-3 - 2M is most negative); θ = 40, 10, 2 so the pivot is the 1 in the a2 row
4

A linear programming problem is given as

Maximise P = 4x + y + 3z

subject to

x + 2y + z ≤ 30
2x + y ≥ 10
x + y + z = 15
x, y, z ≥ 0

The problem is to be solved using the two-stage Simplex method.

  1. Write the three constraints as equations, using slack variable s1, surplus variable s2 and artificial variables a1 and a2.
  2. Set up the initial tableau for the first stage, including the objective row for P and the row for the new objective A. You should make your method for the A row clear. Use the template below.
Initial tableaub.v.xyzs₁s₂a₁a₂Value
7 marks
Show answer
a) x + 2y + z + s1 = 30, 2x + y - s2 + a1 = 10, x + y + z + a2 = 15 b) s1: 1, 2, 1, 1, 0, 0, 0 | 30; a1: 2, 1, 0, 0, -1, 1, 0 | 10; a2: 1, 1, 1, 0, 0, 0, 1 | 15; P: -4, -1, -3, 0, 0, 0, 0 | 0; A: -3, -2, -1, 0, 1, 0, 0 | -25
5

A linear programming problem in x, y and z is to be solved using the big-M method. The initial tableau is shown below.

b.v.xyzs1s2s3a1a2Value
s11211000024
a11−120−10106
a231000−1019
P−2 − 4M1−3 − 2M0MM00−15M
  1. Using the information in the tableau, formulate the linear programming problem. You should list each constraint as an inequality and state two possible ways of writing the objective.
  2. Obtain the pivot for the first iteration of the big-M method. You must give reasons for your answer.
7 marks
Show answer
a) x + 2y + z ≤ 24, x - y + 2z ≥ 6, 3x + y ≥ 9, x, y, z ≥ 0; maximise P = 2x - y + 3z (or minimise -P = -2x + y - 3z) b) x column: -2 - 4M is the most negative (largest multiple of M); θ = 24, 6, 3, so the pivot is the 3 in the a2 row
6

A maximisation linear programming problem in x, y and z is to be solved using the two-stage Simplex method. The partially completed initial tableau is shown in the template below; the objective for the first stage is to minimise A = a1 + a2.

  1. Complete the bottom row of the initial tableau. You should make your method clear.
  2. Carry out the first stage of the two-stage Simplex method, taking the most negative number in the A row to indicate the pivot column each time. State the row operations you use.
  3. State the basic feasible solution found at the end of the first stage.
Initial tableaub.v.xyzs₁s₂s₃a₁a₂ValueRow opss₁2121000023a₁2010−101012a₂32100−10116P−1−4−1000000Tableau after 1st iterationb.v.xyzs₁s₂s₃a₁a₂ValueRow opsTableau after 2nd iterationb.v.xyzs₁s₂s₃a₁a₂ValueRow ops
9 marks
Show answer
a) A: -5, -2, -2, 0, 1, 1, 0, 0 | -28 b) Two iterations: x enters (pivot 3 in the a2 row), then s3 enters (pivot 2/3 in the a1 row); A = 0 c) x = 6, y = 0, z = 0, s1 = 11, s2 = 0, s3 = 2
7

A linear programming problem is given as

Maximise P = 6x + 4y

subject to

x + y ≤ 12
x + 2y ≤ 14
y ≥ 4
x, y ≥ 0

  1. Using slack variables s1 and s2, surplus variable s3 and artificial variable a1, set up the initial tableau for solving this problem using the big-M method.
  2. Solve the problem using the big-M method, 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 and P.

Use the templates below.

Initial tableaub.v.xys₁s₂s₃a₁ValueRow opsTableau after 1st iterationb.v.xys₁s₂s₃a₁ValueRow opsTableau after 2nd iterationb.v.xys₁s₂s₃a₁ValueRow ops
10 marks
Show answer
a) s1: 1, 1, 1, 0, 0, 0 | 12; s2: 1, 2, 0, 1, 0, 0 | 14; a1: 0, 1, 0, 0, -1, 1 | 4; P: -6, -4 - M, 0, 0, M, 0 | -4M b) y enters first (pivot 1 in the a1 row), then x (pivot 1 in the s2 row); x = 6, y = 4, P = 52
8

A linear programming problem in x and y is being solved using the big-M method. The constraints are 3x + y ≤ 35, x + y ≥ 7 and x ≥ 4, and the objective is to maximise P = 3x + 4y. After the first iteration the tableau is

b.v.xys1s2s3a1a2Value
s1011030−323
a1010−111−13
x1000−1014
P0−4 − M0M−3 − M03 + 2M12 − 3M
  1. Explain why the solution given by this tableau is not feasible.
  2. State the values of x and y given by this tableau.
  3. Identify the pivot for the second iteration. You must give reasons for your answer.
  4. Perform the second iteration, stating the row operations you use. Use the template below.
  5. Explain whether the tableau you obtained in part (d) gives a feasible solution.
Tableau after 2nd iterationb.v.xys₁s₂s₃a₁a₂ValueRow ops
9 marks
Show answer
a) The artificial variable a1 is basic and equal to 3, but must be 0 in a feasible solution b) x = 4, y = 0 c) y column (most negative entry); smallest θ is in the a1 row, so the pivot is 1 d) x = 4, y = 3, P = 24 e) Feasible: no artificial variable is basic, so both are zero
9

A linear programming problem is given as

Maximise P = 6x + y + 5z

subject to

2x + 4y ≤ 38
x + 4y + z ≤ 38
y ≥ 5
x, y, z ≥ 0

It is being solved using the two-stage Simplex method, with slack variables s1 and s2, surplus variable s3 and artificial variable a1. The tableau at the end of the first stage is

b.v.xyzs1s2s3a1Value
s1200104−418
s2101014−418
y01000−115
P−60−500−115
A00000010
  1. Explain how the tableau shows that a basic feasible solution has been found.
  2. Write down the initial tableau for the second stage and complete the second stage, 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. State the optimal values of x, y, z and P.
Second stage 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) The value of A is 0, so the artificial variable is zero b) Remove the A row and a1 column; x enters (pivot 2 in R1), then z enters (pivot 1 in R2) c) x = 9, y = 5, z = 9, P = 104
10

A park manager mixes two fertilisers, Growfast and Bloomwell, for the flower beds. Each bag of Growfast contains 2 units of nitrogen and 1 unit of potash and costs £4. Each bag of Bloomwell contains 1 unit of nitrogen and 2 units of potash and costs £3. The mixture must contain at least 10 units of nitrogen and at least 11 units of potash, and there is room to store at most 12 bags.

The manager buys x bags of Growfast and y bags of Bloomwell and wants to minimise the cost, £C.

  1. Formulate this as a linear programming problem in which the objective is to maximise P.
  2. Set up the initial tableau for solving the problem using the big-M method, using surplus variables s1 and s2, slack variable s3 and artificial variables a1 and a2. You must show how you obtain the objective row.
  3. Solve the problem using the big-M method, stating the row operations you use. State how many bags of each fertiliser should be bought and the minimum cost.

Use the templates below.

Initial tableaub.v.xys₁s₂s₃a₁a₂ValueRow opsTableau after 1st iterationb.v.xys₁s₂s₃a₁a₂ValueRow opsTableau after 2nd iterationb.v.xys₁s₂s₃a₁a₂ValueRow ops
12 marks
Show answer
a) Maximise P = -4x - 3y subject to 2x + y ≥ 10, x + 2y ≥ 11, x + y ≤ 12, x, y ≥ 0 b) a1: 2, 1, -1, 0, 0, 1, 0 | 10; a2: 1, 2, 0, -1, 0, 0, 1 | 11; s3: 1, 1, 0, 0, 1, 0, 0 | 12; P: 4 - 3M, 3 - 3M, M, M, 0, 0, 0 | -21M c) x = 3, y = 4; minimum cost £24
11

A linear programming problem is given as

Maximise P = 2x + 3y

subject to

x + y ≤ 6
x + 2y ≥ 16
x, y ≥ 0

  1. Using slack variable s1, surplus variable s2 and artificial variable a1, set up the initial tableau for the first stage of the two-stage Simplex method, including the A row.
  2. Carry out the first stage, stating the row operations you use, and explain what your final tableau shows about the problem.
  3. Explain, by considering the constraints, why this result is correct.

Use the templates below.

Initial tableaub.v.xys₁s₂a₁ValueRow opsTableau after 1st iterationb.v.xys₁s₂a₁ValueRow ops
8 marks
Show answer
a) s1: 1, 1, 1, 0, 0 | 6; a1: 1, 2, 0, -1, 1 | 16; P: -2, -3, 0, 0, 0 | 0; A: -1, -2, 0, 1, 0 | -16 b) y enters, pivot 1 in the s1 row; the A row is then 1, 0, 2, 1, 0 | -4: optimal for stage 1 with A = 4 ≠ 0, so the problem is infeasible c) If x + y ≤ 6 and x, y ≥ 0 then x + 2y ≤ 12 < 16, so no point satisfies both constraints
12

An animal sanctuary mixes three dry feeds, Alfa, Bran and Corn. Each kilogram of Alfa contains 2 units of protein and costs £4, each kilogram of Bran contains 4 units of protein and costs £5, and each kilogram of Corn contains 3 units of protein and costs £4. Each day the sanctuary needs at least 40 kg of feed containing at least 130 units of protein in total. It can store at most 25 kg of Alfa.

The sanctuary uses x kg of Alfa, y kg of Bran and z kg of Corn each day, and wants to minimise the daily cost, £C.

  1. Formulate this as a linear programming problem.
  2. The problem is to be solved by maximising P = −C using the big-M method, with surplus variables s1 and s2, slack variable s3 and artificial variables a1 and a2. Set up the initial tableau, showing how you obtain the objective row. Use the template below.

After three iterations of the big-M method the tableau is

b.v.xyzs1s2s3a1a2Value
z201−4104−130
y−1103−10−3110
s31000010025
P100110−1 + M−1 + M−170
  1. Explain how you know this tableau is optimal.
  2. State how much of each feed the sanctuary should use each day and the minimum daily cost.
  3. Interpret the values of the slack and surplus variables in context.
Initial tableaub.v.xyzs₁s₂s₃a₁a₂Value
12 marks
Show answer
a) Minimise C = 4x + 5y + 4z subject to x + y + z ≥ 40, 2x + 4y + 3z ≥ 130, x ≤ 25, x, y, z ≥ 0 b) a1: 1, 1, 1, -1, 0, 0, 1, 0 | 40; a2: 2, 4, 3, 0, -1, 0, 0, 1 | 130; s3: 1, 0, 0, 0, 0, 1, 0, 0 | 25; P: 4 - 3M, 5 - 5M, 4 - 4M, M, M, 0, 0, 0 | -170M c) There are no negative values in the objective row d) x = 0, y = 10, z = 30; minimum cost £170 e) s1 = s2 = 0: exactly 40 kg of feed and exactly 130 units of protein; s3 = 25: no Alfa is stored

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