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.
Explain why the Simplex algorithm cannot be used directly to solve this problem.
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.
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 fromb) x + 2y + s1 = 20, x + y - s2 + a1 = 6; s1 slack, s2 surplus, a1 artificialc) 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.
Define, in this context, what M represents.
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.
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.
Identify the pivot for the first iteration of the big-M method, giving reasons for your choice.
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 | -12Mb) 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.
Write the three constraints as equations, using slack variable s1, surplus variable s2 and artificial variables a1 and a2.
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.
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.
x
y
z
s1
s2
s3
a1
a2
Value
s1
1
2
1
1
0
0
0
0
24
a1
1
−1
2
0
−1
0
1
0
6
a2
3
1
0
0
0
−1
0
1
9
P
−2 − 4M
1
−3 − 2M
0
M
M
0
0
−15M
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.
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.
Complete the bottom row of the initial tableau. You should make your method clear.
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.
State the basic feasible solution found at the end of the first stage.
9 marks
Show answer
a) A: -5, -2, -2, 0, 1, 1, 0, 0 | -28b) Two iterations: x enters (pivot 3 in the a2 row), then s3 enters (pivot 2/3 in the a1 row); A = 0c) 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
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.
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.
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 | -4Mb) 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.
x
y
s1
s2
s3
a1
a2
Value
s1
0
1
1
0
3
0
−3
23
a1
0
1
0
−1
1
1
−1
3
x
1
0
0
0
−1
0
1
4
P
0
−4 − M
0
M
−3 − M
0
3 + 2M
12 − 3M
Explain why the solution given by this tableau is not feasible.
State the values of x and y given by this tableau.
Identify the pivot for the second iteration. You must give reasons for your answer.
Perform the second iteration, stating the row operations you use. Use the template below.
Explain whether the tableau you obtained in part (d) gives a feasible solution.
9 marks
Show answer
a) The artificial variable a1 is basic and equal to 3, but must be 0 in a feasible solutionb) x = 4, y = 0c) y column (most negative entry); smallest θ is in the a1 row, so the pivot is 1d) x = 4, y = 3, P = 24e) 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.
x
y
z
s1
s2
s3
a1
Value
s1
2
0
0
1
0
4
−4
18
s2
1
0
1
0
1
4
−4
18
y
0
1
0
0
0
−1
1
5
P
−6
0
−5
0
0
−1
1
5
A
0
0
0
0
0
0
1
0
Explain how the tableau shows that a basic feasible solution has been found.
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.
State the optimal values of x, y, z and P.
9 marks
Show answer
a) The value of A is 0, so the artificial variable is zerob) 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.
Formulate this as a linear programming problem in which the objective is to maximise P.
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.
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.
12 marks
Show answer
a) Maximise P = -4x - 3y subject to 2x + y ≥ 10, x + 2y ≥ 11, x + y ≤ 12, x, y ≥ 0b) 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 | -21Mc) 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
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.
Carry out the first stage, stating the row operations you use, and explain what your final tableau shows about the problem.
Explain, by considering the constraints, why this result is correct.
Use the templates below.
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 | -16b) 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 infeasiblec) 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.
Formulate this as a linear programming problem.
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.
x
y
z
s1
s2
s3
a1
a2
Value
z
2
0
1
−4
1
0
4
−1
30
y
−1
1
0
3
−1
0
−3
1
10
s3
1
0
0
0
0
1
0
0
25
P
1
0
0
1
1
0
−1 + M
−1 + M
−170
Explain how you know this tableau is optimal.
State how much of each feed the sanctuary should use each day and the minimum daily cost.
Interpret the values of the slack and surplus variables in context.
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 ≥ 0b) 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 | -170Mc) There are no negative values in the objective rowd) x = 0, y = 10, z = 30; minimum cost £170e) 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.