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

Topic Questions

	Download	View
Medium

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.

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?

Did this page help you?

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.

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.

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?

Did this page help you?

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$
$s$	$\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?

Did this page help you?

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}$
$a_{1}$	1	$\frac{2}{3}$	0	0	$- \frac{1}{3}$	0	$\frac{1}{3}$	0	3
$a_{2}$	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