A LevelFurther MathsEdexcelDecision 1Exam QuestionsLinear programmingSimplex Algorithm

Simplex Algorithm (Edexcel A Level Further Maths: Decision 1): Exam Questions

Exam code: 9FM0

3 hours12 questions

1 mark

A linear programming problem in $x, y$ and $z$ is described as follows.

Maximise $P = 2 x + 2 y - z$

subject to $3 x + y + 2 z \leq 30$

$x - y + z \geq 8$

$4 y + 2 z \geq 15$

$x, y, z \geq 0$

Explain why the Simplex algorithm cannot be used to solve this linear programming problem.

How did you do?

7 marks

Write your answer in the Answer Booklet (opens in a new tab).

Set up the initial tableau for solving this linear programming problem using the big-M method.

How did you do?

1 mark

After a first iteration of the big-M method, the tableau is

b.v.	$x$	$y$	$z$	$s_{1}$	$s_{2}$	$s_{3}$	$a_{1}$	$a_{2}$	Value
$s_{1}$	3	0	1.5	1	0	0.25	0	-0.25	26.25
$a_{1}$	1	0	1.5	0	-1	-0.25	1	0.25	11.75
$y$	0	1	0.5	0	0	-0.25	0	0.25	3.75
$P$	$- (2 + M)$	0	$2 - 1.5 M$	0	$M$	$- 0.5 + 0.25 M$	0	$0.5 + 0.75 M$	$7.5 - 11.75 M$

State the value of each variable after the first iteration.

How did you do?

1 mark

Explain why the solution given by the first iteration is not feasible.

How did you do?

2 marks

Taking the most negative entry in the profit row to indicate the pivot column,

Obtain the most efficient pivot for a second iteration. You must give reasons for your answer.

How did you do?

Was this exam question helpful?

5 marks

Susie is preparing for a triathlon event that is taking place next month. A triathlon involves three activities: swimming, cycling and running.

Susie decides that in her training next week she should

maximise the total time spent cycling and running
train for at most 39 hours
spend at least 40% of her time swimming
spend a total of at least 28 hours of her time swimming and running

Susie needs to determine how long she should spend next week training for each activity. Let

$x$ represent the number of hours swimming
$y$ represent the number of hours cycling
$z$ represent the number of hours running

Formulate the information above as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients.

How did you do?

6 marks

Write your answer in the Answer Booklet (opens in a new tab).

Susie decides to solve this linear programming problem by using the two-stage Simplex method.

Set up an initial tableau for solving this problem using the two-stage Simplex method. As part of your solution you must show how

the constraints have been made into equations using slack variables, exactly one surplus variable and exactly one artificial variable
the rows for the two objective functions are formed

How did you do?

2 marks

The following tableau $T$ is obtained after one iteration of the second stage of the two‑stage Simplex method.

b.v.	$x$	$y$	$z$	$s_{1}$	$s_{2}$	$s_{3}$	Value
$y$	0	1	0	1	0	1	11
$s_{2}$	0	0	5	–2	1	–5	62
$x$	1	0	1	0	0	–1	28
$P$	0	0	–1	1	0	1	11

Obtain a suitable pivot for a second iteration. You must give reasons for your answer.

How did you do?

5 marks

Write your answer in the Answer Booklet (opens in a new tab).

Starting from tableau $T$ , solve the linear programming problem by performing one further iteration of the second stage of the two-stage Simplex method. You should make your method clear by stating the row operations you use.

How did you do?

Was this exam question helpful?

5 marks

A garden centre makes hanging baskets to sell to its customers. Three types of hanging basket are made, $S u n s h i n e, D r a m a$ and $P e a c e f u l$ . The plants used are categorised as $I m p a c t, F l o w e r i n g$ or $T r a i l i n g$ .

Each $S u n s h i n e$ basket contains 2 $I m p a c t$ plants, 4 $F l o w e r i n g$ plants and 3 $T r a i l i n g$ plants.
Each $D r a m a$ basket contains 3 $I m p a c t$ plants, 2 $F l o w e r i n g$ plants and 4 $T r a i l i n g$ plants.
Each $P e a c e f u l$ basket contains 1 $I m p a c t$ plant, 3 $F l o w e r i n g$ plants and 2 $T r a i l i n g$ plants.

The garden centre can use at most 80 $I m p a c t$ plants, at most 140 $F l o w e r i n g$ plants and at most 96 $T r a i l i n g$ plants each day.

The profit on $S u n s h i n e$ , $D r a m a$ and $P e a c e f u l$ baskets are £12, £20 and £16 respectively.
The garden centre wishes to maximise its profit.

Let $x, y$ and $z$ be the number of $S u n s h i n e$ , $D r a m a$ and $P e a c e f u l$ baskets respectively, produced each day.

Formulate this situation as a linear programming problem, giving your constraints as inequalities.

How did you do?

1 mark

State the further restriction that applies to the values of $x, y$ and $z$ in this context.

How did you do?

2 marks

The Simplex algorithm is used to solve this problem. After one iteration, the tableau is

b.v.	$x$	$y$	$z$	$r$	$s$	$t$	Value
$r$	$- \frac{1}{4}$	$0$	$- \frac{1}{2}$	$1$	$0$	$- \frac{3}{4}$	$8$
$s$	$\frac{5}{2}$	$0$	$2$	$0$	$1$	$- \frac{1}{2}$	$92$
$y$	$\frac{3}{4}$	$1$	$\frac{1}{2}$	$0$	$0$	$\frac{1}{4}$	$24$
$P$	$3$	$0$	$- 6$	$0$	$0$	$5$	$480$

State the variable that was increased in the first iteration. Justify your answer.

How did you do?

1 mark

Determine how many plants in total are being used after only one iteration of the Simplex algorithm.

How did you do?

2 marks

Explain why for a second iteration of the Simplex algorithm the 2 in the $z$ column is the pivot value.

How did you do?

1 mark

After a second iteration, the tableau is

b.v.	$x$	$y$	$z$	$r$	$s$	$t$	Value
$r$	$\frac{3}{8}$	$0$	$0$	$1$	$\frac{1}{4}$	$- \frac{7}{8}$	$31$
$z$	$\frac{5}{4}$	$0$	$1$	$0$	$\frac{1}{2}$	$- \frac{1}{4}$	$46$
$y$	$\frac{1}{8}$	$1$	$0$	$0$	$- \frac{1}{4}$	$\frac{3}{8}$	$1$
$P$	$\frac{21}{2}$	$0$	$0$	$0$	$3$	$\frac{7}{2}$	$756$

Use algebra to explain why this tableau is optimal.

How did you do?

1 mark

State the optimal number of each type of basket that should be made.

How did you do?

2 marks

The manager of the garden centre is able to increase the number of $I m p a c t$ plants available each day from 80 to 100. She wants to know if this would increase her profit.

Use your final tableau to determine the effect of this increase. (You should not carry out any further calculations.)

How did you do?

Was this exam question helpful?

4 marks

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$	$s_{1}$	$s_{2}$	$s_{3}$	$a_{1}$	$a_{2}$	Value
$s_{1}$	2	3	4	1	0	0	0	0	13
$a_{1}$	1	−2	2	0	−1	0	1	0	8
$a_{2}$	3	0	−4	0	0	−1	0	1	12
$P$	$2 - 4 M$	$- 3 + 2 M$	$- 1 + 2 M$	0	$M$	$M$	0	0	$- 20 M$

Using the information in the above tableau, formulate the linear programming problem. You should

list each of the constraints as an inequality
state the two possible objectives

How did you do?

2 marks

Obtain the most efficient pivot for a first iteration of the big‑M method. You must give reasons for your answer.

How did you do?

Was this exam question helpful?

5 marks

Graph with lines forming a triangular region R, labelled x and y axes. Equations: y=2x+1, x+y=8, 7x+2y=46, x+2y=12. Shaded area surrounds R.

Figure 5 shows the constraints of a linear programming problem in $x$ and $y$ where $R$ is the feasible region.

The objective is to maximise $P = x + k y$ , where $k$ is a positive constant.

The optimal vertex of $R$ is to be found using the Simplex algorithm.

Set up an initial tableau for solving this linear programming problem using the Simplex algorithm.

A blank table with six rows and five columns. Headers read: b.v., x, y, and Value; the first column under b.v. lists P.

How did you do?

1 mark

After two iterations of the Simplex algorithm a possible tableau $T$ is

b.v.	$x$	$y$	$s_{1}$	$s_{2}$	$s_{3}$	$s_{4}$	Value
$s_{1}$	$0$	$0$	$1$	$- \frac{3}{5}$	$0$	$\frac{1}{5}$	$1$
$x$	$1$	$0$	$0$	$\frac{1}{5}$	$0$	$- \frac{2}{5}$	$2$
$s_{3}$	$0$	$0$	$0$	$- \frac{11}{5}$	$1$	$\frac{12}{5}$	$22$
$y$	$0$	$1$	$0$	$\frac{2}{5}$	$0$	$\frac{1}{5}$	$5$
$P$	$0$	$0$	$0$	$\frac{1}{5} + \frac{2}{5} k$	$0$	$- \frac{2}{5} + \frac{1}{5} k$	$5 k + 2$

State the value of each variable after the second iteration.

How did you do?

9 marks

It is given that $T$ does not give an optimal solution to the linear programming problem.

After a third iteration of the Simplex algorithm the resulting tableau does give an optimal solution to the problem.

Perform the third iteration of the Simplex algorithm and hence determine the range of possible values for $P$ . You should state the row operations you use and make your method and working clear.

A table with headers: b.v., x, y, s1, s2, s3, s4, Value, Row Ops. Row P is visible with empty cells below each header.

How did you do?

Was this exam question helpful?

5 marks

A publisher plans to produce three versions of the same book: a paperback, a hardcover, and a deluxe edition.

Each paperback takes 4 minutes to print and 1 minute to bind
Each hardcover takes 8 minutes to print and 5 minutes to bind
Each deluxe edition takes 15 minutes to print and 12 minutes to bind

The printing machine is available for at most 150 hours and the binding machine must be used for at least 60 hours.

The publisher decides to produce

at least 1600 books in total
at least three times as many paperbacks as hardcovers

The profit on each paperback sold is £8, the profit on each hardcover sold is £20 and the profit on each deluxe edition sold is £40

Let $x, y$ and $z$ represent the number of paperbacks, hardcovers and deluxe editions produced.

Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients.

How did you do?

6 marks

The publisher decides to solve this linear programming problem by using the two-stage simplex method.

Set up an initial tableau for solving this problem using the two-stage simplex method.

As part of your solution, you must show how

the constraints have been made into equations by using slack variables, exactly two surplus variables and exactly two artificial variables
the rows for the two objective functions are formed

Empty table with six columns labeled b.v., x, y, z, and Value. Rows include variables P and I, with spaces for additional data entries.

How did you do?

5 marks

The following tableau is obtained after two iterations of the first stage of the two-stage simplex method.

b.v.	$x$	$y$	$z$	$s_{1}$	$s_{2}$	$s_{3}$	$s_{4}$	$a_{1}$	$a_{2}$	Value
$s_{1}$	$0$	$0$	$0$	$1$	$1$	3	$0$	$- 1$	$- 3$	$600$
$z$	$0$	$\frac{4}{11}$	$1$	$0$	$- \frac{1}{11}$	$\frac{1}{11}$	$0$	$\frac{1}{11}$	$- \frac{1}{11}$	$\frac{2000}{11}$
$x$	$1$	$\frac{7}{11}$	$0$	$0$	$\frac{1}{11}$	$- \frac{12}{11}$	$0$	$- \frac{1}{11}$	$\frac{12}{11}$	$\frac{15600}{11}$
$s_{4}$	$0$	$\frac{40}{11}$	$0$	$0$	$\frac{1}{11}$	$- \frac{12}{11}$	$1$	$- \frac{1}{11}$	$\frac{12}{11}$	$\frac{15600}{11}$
$P$	$0$	$- \frac{4}{11}$	$0$	$0$	$- \frac{32}{11}$	$- \frac{56}{11}$	$0$	$\frac{32}{11}$	$\frac{56}{11}$	$\frac{204800}{11}$
$I$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$1$	$1$	$0$

Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the second stage of the two-stage simplex method to obtain a new tableau. Make your method clear by stating the row operations you use.

Table for a linear programming tableau with columns for variables, slack variables, value, and row operations. Six rows, starting with b.v. and P.

How did you do?

2 marks

After three iterations of the second stage of the two-stage simplex method, the following tableau is obtained.

b.v.	$x$	$y$	$z$	$s_{1}$	$s_{2}$	$s_{3}$	$s_{4}$	Value
$s_{2}$	$0$	$0$	$0$	$1$	$1$	$3$	$0$	$600$
$z$	$0$	$0$	$1$	$\frac{1}{10}$	$0$	$\frac{1}{2}$	$- \frac{1}{10}$	$100$
$x$	$1$	$0$	$0$	$- \frac{3}{40}$	$0$	$- \frac{9}{8}$	$- \frac{7}{40}$	$1125$
$y$	$0$	$1$	$0$	$- \frac{1}{40}$	$0$	$- \frac{3}{8}$	$\frac{11}{40}$	$375$
$P$	$0$	$0$	$0$	$\frac{29}{10}$	$0$	$\frac{7}{2}$	$\frac{1}{10}$	$20500$

Given that the publisher produces the optimal number of each version of the book,

(i) state the maximum profit the publisher can earn,

(ii) find the number of hours the binding machine will be used.

How did you do?

1 mark

Give a reason why the publisher may not earn the profit stated in (d)(i).

How did you do?

Was this exam question helpful?

11a

6 marks

A game uses two positive numbers $x$ and $y$ . A valid pair of numbers must satisfy all of these conditions:

twice $x$ is at least 100 more than $y$
$x$ is at most four times as large as $y$
$x$ together with twice $y$ is at least 100

The score of a valid pair is $3 x + 4 y$ , and a player wants to make the score as small as possible. The player decides to solve this problem using the big-M method.

Set up an initial tableau for solving this problem using the big-M method. As part of your solution, you must show

how the constraints were made into equations using one slack variable, exactly two surplus variables and exactly two artificial variables
how the objective function was formed

How did you do?

11b

3 marks

The big-M method is applied until the tableau containing the optimal solution to the problem is found. One row of this final tableau is as follows.

b.v.	x	y	s₁	s₂	s₃	a₁	a₂	Value
x	1	0	-2/5	0	-1/5	2/5	1/5	60

(i) State the value of $x$ .

(ii) Hence deduce the value of $y$ , making your reasoning clear.

How did you do?

Was this exam question helpful?

12a

2 marks

A maximisation linear programming problem in $x$ , $y$ and $z$ is to be solved using the Simplex method. The tableau after the 1st iteration is shown below.

b.v.	x	y	z	s₁	s₂	s₃	Value
x	1	1/2	0	1/2	0	0	10
s₂	0	-1/2	1	-1/2	1	0	26
s₃	0	-1/2	-1	-1/2	0	1	10
P	0	-3/2	-4	5/2	0	0	50

State the column that contains the pivot value for the 1st iteration. You must give a reason for your answer.

How did you do?

12b

5 marks

By considering the equations represented in the above tableau, formulate the linear programming problem in $x$ , $y$ and $z$ only. State the objective and list the constraints as inequalities with integer coefficients.

How did you do?

12c

4 marks

Taking the most negative number in the profit row to indicate the pivot column, perform the 2nd iteration of the Simplex algorithm, to obtain a new tableau, T. Make your method clear by stating the row operations you use.

How did you do?

12d

2 marks

(i) Explain, using T, how you know that an optimal solution to the original linear programming problem has not been found after the 2nd iteration.

(ii) State the values of the basic variables after the 2nd iteration.

How did you do?

12e

1 mark

A student attempts the 3rd iteration of the Simplex algorithm and obtains the tableau below.

b.v.	x	y	z	s₁	s₂	s₃	Value
y	2	1	0	1	0	0	20
z	1	0	1	0	1	0	36
s₃	2	0	0	0	1	1	56
P	7	1	0	4	4	0	224

Explain how you know that the student's attempt at the 3rd iteration is not correct.

How did you do?

Was this exam question helpful?

More Revision Notes you might like

Basic variable	$x$	$y$	$z$	$S_{1}$	$S_{2}$	$S_{3}$	$a_{1}$	$a_{2}$	Value
$S_{1}$	0	$\frac{5}{6}$	0	1	$\frac{7}{12}$	$\frac{3}{4}$	$- \frac{7}{12}$	$- \frac{3}{4}$	$\frac{147}{4}$
$x$	1	$\frac{2}{3}$	0	0	$- \frac{1}{3}$	0	$\frac{1}{3}$	0	3
$z$	0	$\frac{1}{6}$	1	0	$- \frac{1}{12}$	$- \frac{1}{4}$	$\frac{1}{12}$	$\frac{1}{4}$	$\frac{7}{4}$
$P$	0	$\frac{5}{6}$	0	0	$- \frac{11}{12}$	$- \frac{3}{4}$	$\frac{11}{12}$	$\frac{3}{4}$	$\frac{45}{4}$
$A$	0	0	0	0	0	0	1	1	0