Linear Programming

From an AS paper

Edexcel

Edexcel · Old spec

A2 June 2025 Q7

EdexcelCurrent spec12 marksLinear Programming

7.

Figure 5: the lines x = 1, 3x + 4y = 20, 3x + y = 8 and 2x + 3y = 6 with the feasible region R unshaded, to the right of x = 1, above 2x + 3y = 6 and below 3x + 4y = 20 and 3x + y = 8
Figure 5

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 = 11x + ky\), where \(k\) is a positive constant.

The optimal value of \(P\) is to be found using the big-M method.

(a) Set up an initial tableau for solving this linear programming problem using the big-M method.
You should use exactly 2 slack variables, 2 surplus variables and 2 artificial variables. (7)

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

b.v.\(x\)\(y\)\(s_1\)\(s_2\)\(s_3\)\(s_4\)\(a_1\)\(a_2\)Value
\(s_1\)0010\(\dfrac{9}{7}\)\(-\dfrac{1}{7}\)0\(-\dfrac{9}{7}\)\(\dfrac{78}{7}\)
\(x\)1000\(\dfrac{1}{7}\)\(\dfrac{3}{7}\)0\(-\dfrac{1}{7}\)\(\dfrac{18}{7}\)
\(y\)0100\(-\dfrac{3}{7}\)\(-\dfrac{2}{7}\)0\(\dfrac{3}{7}\)\(\dfrac{2}{7}\)
\(s_2\)0001\(\dfrac{1}{7}\)\(\dfrac{3}{7}\)−1\(-\dfrac{1}{7}\)\(\dfrac{11}{7}\)
\(P\)0000\(\frac{11}{7} - \frac{3}{7}k\)\(\frac{33}{7} - \frac{2}{7}k\)\(M\)\(M - \frac{11}{7} + \frac{3}{7}k\)\(\frac{198}{7} + \frac{2}{7}k\)
(b) Given that the third iteration gives the optimal value for \(P\), determine this value. (5)

A2 June 2025 Q5

EdexcelCurrent spec12 marksLinear Programming

5. Consider the following linear programming problem in \(x\), \(y\) and \(z\).

Maximise \(P = 3x + 4y + 2z\)

subject to \[\begin{aligned} 2x + 2y + 2z &\leqslant 21 \\ 2x - y - z &\leqslant 18 \\ -3x + y - 2z &\leqslant 1 \end{aligned}\] \[x \geqslant 4 \qquad y \geqslant 1 \qquad z \leqslant -3\]

(a) Explain why the Simplex algorithm cannot be used to solve this linear programming problem in its current form. (1)
(b) Use the substitutions \(x = X + 4,\ y = Y + 1,\ z = -Z - 3\) and \(P = Q + 10\) to reformulate the linear programming problem into a form in which the Simplex algorithm can be used to solve the problem. You should write the constraints as simplified inequalities with integer coefficients. (3)

After a second iteration of the Simplex algorithm, a possible tableau \(T\) is

b.v.\(X\)\(Y\)\(Z\)\(s_1\)\(s_2\)\(s_3\)Value
\(X\)10\(-\dfrac{3}{4}\)\(\dfrac{1}{8}\)0\(-\dfrac{1}{4}\)\(\dfrac{5}{8}\)
\(s_2\)00\(\dfrac{9}{4}\)\(\dfrac{1}{8}\)1\(\dfrac{3}{4}\)\(\dfrac{117}{8}\)
\(Y\)01\(-\dfrac{1}{4}\)\(\dfrac{3}{8}\)0\(\dfrac{1}{4}\)\(\dfrac{63}{8}\)
\(Q\)00\(-\dfrac{5}{4}\)\(\dfrac{15}{8}\)0\(\dfrac{1}{4}\)\(\dfrac{267}{8}\)
(c) Write down the profit equation given by \(T\). (1)
(d) Using your answer to (c), explain why \(T\) is not optimal. (1)
(e)
(i) Perform the third iteration of the Simplex algorithm. You should state the row operations you use.
(ii) Hence determine the maximum value of \(P\), and the corresponding values of \(x\), \(y\) and \(z\). (6)

AS June 2025 Q4

EdexcelAS paperCurrent spec11 marksLinear Programming

4.

Figure 3: graph with x from 0 to 16 and y from 0 to 32; the line from (0, 20) to (16, 0) is drawn and the region above it is shaded
Figure 3

George is a baker who bakes \(x\) sponge cakes and \(y\) fruit cakes every day.

One of George’s constraints is shown on Figure 3.

(a) Write down this constraint as a simplified inequality with integer coefficients. (1)

Three further constraints are

  • George must bake at least four fruit cakes every day
  • for every two sponge cakes George bakes, he must bake at most three fruit cakes
  • George needs 200 g of butter for each sponge cake and 100 g for each fruit cake and has 2.8 kg of butter available each day
(b)
(i) Write down the three inequalities which model these constraints. Give your answers in simplified form with integer coefficients.
(ii) Add lines and shading to Diagram 1 in the answer book to represent these three constraints. Hence determine the feasible region and label it \(R\). (5)

[Diagram 1 in the answer book is a copy of Figure 3.]

George makes £8 profit from each sponge cake he sells and £5 profit from each fruit cake he sells. Given that he wishes to maximise his profit,

(c) use the vertex method to determine the number of sponge cakes and the number of fruit cakes George should bake each day. You must make your method and working clear. (5)

A2 June 2024 Q7

EdexcelCurrent spec14 marksLinear Programming

7. 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_1\)\(s_2\)\(s_3\)Value
\(s_1\)0\(-\dfrac{1}{2}\)\(\dfrac{3}{2}\)1\(-\dfrac{1}{2}\)030
\(x\)1\(\dfrac{1}{4}\)\(-\dfrac{1}{4}\)0\(\dfrac{1}{4}\)010
\(s_3\)01100126
\(P\)0\(-\dfrac{1}{4}\)\(-\dfrac{11}{4}\)0\(\dfrac{3}{4}\)030
(a) State the column that contains the pivot value for the 1st iteration. You must give a reason for your answer. (2)
(b) 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. (5)
(c) 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. (4)
(d)
(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. (2)

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

b.v.\(x\)\(y\)\(z\)\(s_1\)\(s_2\)\(s_3\)Value
\(z\)001\(\dfrac{1}{2}\)\(-\dfrac{1}{4}\)\(\dfrac{1}{4}\)\(\dfrac{43}{2}\)
\(x\)100\(\dfrac{1}{4}\)\(\dfrac{1}{8}\)\(-\dfrac{1}{8}\)\(\dfrac{57}{4}\)
\(y\)010\(-\dfrac{1}{2}\)\(\dfrac{1}{4}\)\(\dfrac{3}{4}\)\(\dfrac{9}{2}\)
\(P\)010\(\dfrac{5}{4}\)\(\dfrac{1}{8}\)\(\dfrac{7}{8}\)\(\dfrac{361}{4}\)
(e) Explain how you know that the student’s attempt at the 3rd iteration is not correct. (1)

A2 June 2024 Q5

EdexcelCurrent spec9 marksLinear Programming

5. Two friends, Anaira and Tommi, play a game involving two positive numbers \(x\) and \(y\)

Anaira gives Tommi the following clues to see if he can correctly determine the value of \(x\) and the value of \(y\)

  • \(x\) is greater than \(y\) and the difference between the two is at least 100
  • \(x\) is at most 5 times as large as \(y\)
  • the sum of \(2x\) and \(3y\) is at least 350
  • the sum of \(x\) and \(y\) is as small as possible

Tommi decides to solve this problem by using the big-M method.

(a) 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
(6)

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_1\)\(s_2\)\(s_3\)\(a_1\)\(a_2\)Value
\(x\)10\(-\dfrac{3}{5}\)0\(-\dfrac{1}{5}\)\(\dfrac{3}{5}\)\(\dfrac{1}{5}\)130
(b)
(i) State the value of \(x\)
(ii) Hence deduce the value of \(y\), making your reasoning clear. (3)

AS June 2024 Q4

EdexcelAS paperCurrent spec12 marksLinear Programming

4.

Figure 4: graph for x from -5 to 30 showing the lines x + y = 30, y = 2x + 10 and 5y = 2x - 10, with the region satisfying all three left unshaded
Figure 4

Figure 4 shows three of the six constraints for a linear programming problem in \(x\) and \(y\)

The unshaded region and its boundaries satisfy these three constraints.

(a) State these three constraints as simplified inequalities with integer coefficients. (3)

The variables \(x\) and \(y\) represent the number of orange fish and the number of blue fish, respectively, that are to be kept in an aquarium.

The number of fish in the aquarium is subject to these three further constraints

  • there must be at least one blue fish
  • the orange fish must not outnumber the blue fish by more than ten
  • there must be no more than five blue fish for every orange fish
(b) Write each of these three constraints as a simplified inequality with integer coefficients. (2)
(c) Represent these three constraints by adding lines and shading to Diagram 1 in the answer book, labelling the feasible region, \(R\) (3)

[Diagram 1 in the answer book is a copy of Figure 4.]

The total value (in pounds) of the fish in the aquarium is given by the objective function

\[\text{Maximise } P = 3x + 5y\]
(d)
(i) Use the objective line method to determine the optimal point of the feasible region, giving its coordinates as exact fractions.
(ii) Hence find the maximum total value of the fish in the aquarium, stating the optimal number of orange fish and the optimal number of blue fish. (4)

A2 June 2023 Q7

EdexcelCurrent spec19 marksLinear Programming

7. 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.

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

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

(b) 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
(6)

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\)0001130\(-1\)\(-3\)600
\(z\)0\(\dfrac{4}{11}\)10\(-\dfrac{1}{11}\)\(\dfrac{1}{11}\)0\(\dfrac{1}{11}\)\(-\dfrac{1}{11}\)\(\dfrac{2000}{11}\)
\(x\)1\(\dfrac{7}{11}\)00\(\dfrac{1}{11}\)\(-\dfrac{12}{11}\)0\(-\dfrac{1}{11}\)\(\dfrac{12}{11}\)\(\dfrac{15600}{11}\)
\(s_4\)0\(\dfrac{40}{11}\)00\(\dfrac{1}{11}\)\(-\dfrac{12}{11}\)1\(-\dfrac{1}{11}\)\(\dfrac{12}{11}\)\(\dfrac{15600}{11}\)
\(P\)0\(-\dfrac{4}{11}\)00\(-\dfrac{32}{11}\)\(-\dfrac{56}{11}\)0\(\dfrac{32}{11}\)\(\dfrac{56}{11}\)\(\dfrac{204800}{11}\)
\(I\)0000000110
(c) 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. (5)

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\)0001130600
\(z\)001\(\dfrac{1}{10}\)0\(\dfrac{1}{2}\)\(-\dfrac{1}{10}\)100
\(x\)100\(-\dfrac{3}{40}\)0\(-\dfrac{9}{8}\)\(-\dfrac{7}{40}\)1125
\(y\)010\(-\dfrac{1}{40}\)0\(-\dfrac{3}{8}\)\(\dfrac{11}{40}\)375
\(P\)000\(\dfrac{29}{10}\)0\(\dfrac{7}{2}\)\(\dfrac{1}{10}\)20500

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

(d)
(i) state the maximum profit the publisher can earn,
(ii) find the number of hours the binding machine will be used. (2)
(e) Give a reason why the publisher may not earn the profit stated in (d)(i). (1)

AS June 2023 Q4

EdexcelAS paperCurrent spec7 marksLinear Programming

4.

Figure 3: graph showing the lines x = 8, 3y = 4x + 5, 4x + 15y = 120 and 3x + 8y = 32, an objective line, and the unshaded feasible region R
Figure 3

Figure 3 shows the constraints of a linear programming problem in \(x\) and \(y\).
The unshaded area, including its boundaries, forms the feasible region, \(R\).
An objective line has been drawn and labelled on the graph.

(a) State the inequalities that define the feasible region. (2)

The maximum value of the objective function is \(\dfrac{160}{3}\)

The minimum value of the objective function is \(\dfrac{883}{41}\)

(b) Determine the objective function, showing your working clearly. (5)

A2 June 2022 Q7

EdexcelCurrent spec15 marksLinear Programming

7.

Figure 5: the lines y = 2x + 1, 7x + 2y = 46, x + y = 8 and x + 2y = 12 with the feasible region R left unshaded: R lies above the x-axis, to the right of the y-axis, below y = 2x + 1, below x + 2y = 12, below x + y = 8 and to the left of 7x + 2y = 46
Figure 5

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 + ky\), where \(k\) is a positive constant.

The optimal vertex of \(R\) is to be found using the Simplex algorithm.

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

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\)001\(-\frac{3}{5}\)0\(\frac{1}{5}\)1
\(x\)100\(\frac{1}{5}\)0\(-\frac{2}{5}\)2
\(s_3\)000\(-\frac{11}{5}\)1\(\frac{12}{5}\)22
\(y\)010\(\frac{2}{5}\)0\(\frac{1}{5}\)5
\(P\)000\(\frac{1}{5} + \frac{2}{5}k\)0\(-\frac{2}{5} + \frac{1}{5}k\)\(5k + 2\)
(b) State the value of each variable after the second iteration. (1)

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.

(c) 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. (9)

A2 June 2022 Q4

EdexcelCurrent spec6 marksLinear Programming

4. 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\)2341000013
\(a_1\)1\(-2\)20\(-1\)0108
\(a_2\)30\(-4\)00\(-1\)0112
\(P\)\(2 - 4M\)\(-3 + 2M\)\(-1 + 2M\)0\(M\)\(M\)00\(-20M\)
(a) 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
(4)
(b) Obtain the most efficient pivot for a first iteration of the big-M method. You must give reasons for your answer. (2)

AS June 2022 Q4

EdexcelAS paperCurrent spec9 marksLinear Programming

4.

Figure 3: graph for x from 0 to 16 and y from 0 to 14 showing three constraint lines through (0, 14) and (14, 0), through (0, 6) and (16, 14), and through (5, 0); the unshaded feasible region R is next to the origin, and an objective line runs from (0, 4) to (10, 0)
Figure 3

Figure 3 shows the constraints of a maximisation linear programming problem in \(x\) and \(y\), where \(x \geqslant 0\) and \(y \geqslant 0\). The unshaded area, including its boundaries, forms the feasible region, \(R\). An objective line has been drawn and labelled on the graph.

(a) List the constraints as simplified inequalities with integer coefficients. (3)

The optimal value of the objective function is 216

(b)
(i) Calculate the exact coordinates of the optimal vertex.
(ii) Hence derive the objective function. (5)

Given that \(x\) represents the number of small flower pots and \(y\) represents the number of large flower pots supplied to a customer,

(c) deduce the optimal solution to the problem. (1)

A2 October 2021 Q8

EdexcelCurrent spec18 marksLinear Programming

8. 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
(a) Formulate the information above as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients. (5)

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

(b) 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
(6)

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\)01010111
\(s_2\)005\(-2\)1\(-5\)62
\(x\)10100\(-1\)28
\(P\)00\(-1\)10111
(c) Obtain a suitable pivot for a second iteration. You must give reasons for your answer. (2)
(d) 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. (5)

A2 October 2020 Q7

EdexcelCurrent spec17 marksLinear Programming

7. 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 below.

Basic variable\(x\)\(y\)\(z\)\(s_1\)\(s_2\)\(s_3\)\(a_1\)\(a_2\)Value
\(s_1\)1231000045
\(a_1\)3200\(-1\)0109
\(a_2\)\(-1\)0400\(-1\)014
\(P\)\(-2\)\(-1\)\(-3\)000000
\(A\)         
(a) Using the information in the above tableau, formulate the linear programming problem. State the objective and list the constraints as inequalities. (4)
(b) Complete the bottom row of Table 1 in the answer book. You should make your method and working clear. (2)

[Table 1 in the answer book is a copy of the partially completed initial tableau above.]

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

Basic variable\(x\)\(y\)\(z\)\(s_1\)\(s_2\)\(s_3\)\(a_1\)\(a_2\)Value
\(s_1\)0\(\frac{5}{6}\)01\(\frac{7}{12}\)\(\frac{3}{4}\)\(-\frac{7}{12}\)\(-\frac{3}{4}\)\(\frac{147}{4}\)
\(x\)1\(\frac{2}{3}\)00\(-\frac{1}{3}\)0\(\frac{1}{3}\)03
\(z\)0\(\frac{1}{6}\)10\(-\frac{1}{12}\)\(-\frac{1}{4}\)\(\frac{1}{12}\)\(\frac{1}{4}\)\(\frac{7}{4}\)
\(P\)0\(\frac{5}{6}\)00\(-\frac{11}{12}\)\(-\frac{3}{4}\)\(\frac{11}{12}\)\(\frac{3}{4}\)\(\frac{45}{4}\)
\(A\)000000110
(c)
(i) Explain how the above tableau shows that a basic feasible solution has been found for the original linear programming problem.
(ii) Write down the basic feasible solution for the second stage. (3)
(d) 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, \(T\). Make your method clear by stating the row operations you use. (5)
(e)
(i) Explain, using \(T\), whether or not an optimal solution to the original linear programming problem has been found.
(ii) Write down the value of the objective function.
(iii) State the values of the basic variables. (3)

A2 October 2020 Q4

EdexcelCurrent spec10 marksLinear Programming

4.

Figure 3: graph for 0 ≤ x ≤ 5.5 and 0 ≤ y ≤ 7 showing the lines 2y = 5x, y = x + 1 and 6x + 5y = 30, with the feasible region R the triangle between them
Figure 3

Figure 3 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region.

(a) Write down the inequalities that define \(R\). (2)

The objective is to maximise \(P\), where \(P = 3x + y\)

(b) Obtain the exact value of \(P\) at each of the three vertices of \(R\) and hence find the optimal vertex, \(V\). (4)

The objective is changed to maximise \(Q\), where \(Q = 3x + ay\). Given that \(a\) is a constant and the optimal vertex is still \(V\),

(c) find the range of possible values of \(a\). (4)

AS October 2020 Q4

EdexcelAS paperCurrent spec9 marksLinear Programming

4.

Figure 3: graph for x from 0 to 12 and y from -2 to 12 showing three constraint lines, through (0, 12) and (6, 0), through (0, 12) and (10, 0), and a steep line through about (6.3, 0); the unshaded feasible region R with optimal vertex V, and an objective line from (0, 5) to (3, 0)
Figure 3

Figure 3 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region. Figure 3 also shows an objective line for the problem and the optimal vertex, which is labelled as \(V\).

The value of the objective at \(V\) is 556

Express the linear programming problem in algebraic form. List the constraints as simplified inequalities with integer coefficients and determine the objective. (9)

A2 June 2019 Q7

EdexcelCurrent spec12 marksLinear Programming

7. A shop sells two types of watch, analogue watches and digital watches.

The shop manager knows that, each month, she should order at least 60 watches in total. In addition, at most 80% of the watches she orders must be digital.

Let \(x\) be the number of analogue watches ordered and let \(y\) be the number of digital watches ordered.

(a) Write down inequalities, in terms of \(x\) and \(y\), to model these constraints. (2)

Two further constraints are

\[\begin{gathered} y + 3x \geqslant 140 \\ 4y + x \geqslant 80 \end{gathered}\]
(b) Represent all these constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region, \(R\). (4)
Diagram 1: blank grid with x from 0 to 100 and y from 0 to 160
Diagram 1

The cost to the shop of ordering an analogue watch is five times the cost of ordering a digital watch. The shop manager wishes to minimise the total cost.

(c) Determine the number of each type of watch the shop manager should order. You must make your method clear. (3)

Given that the minimum total cost of ordering the watches is £4455

(d) determine the cost of ordering one analogue watch and the cost of ordering one digital watch. You must make your method clear. (3)

A2 June 2019 Q6

EdexcelCurrent spec12 marksLinear Programming

6. A linear programming problem in \(x\), \(y\) and \(z\) is described as follows.

Maximise\(P = 2x + 2y - z\)
subject to\(\begin{aligned} 3x + y + 2z &\leqslant 30 \\ x - y + z &\geqslant 8 \\ 4y + 2z &\geqslant 15 \\ x, y, z &\geqslant 0 \end{aligned}\)
(a) Explain why the Simplex algorithm cannot be used to solve this linear programming problem. (1)
(b) Set up the initial tableau for solving this linear programming problem using the big-M method. (7)

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\)301.5100.250\(-0.25\)26.25
\(a_1\)101.50\(-1\)\(-0.25\)10.2511.75
\(y\)010.500\(-0.25\)00.253.75
\(P\)\(-(2 + M)\)0\(2 - 1.5M\)0\(M\)\(-0.5 + 0.25M\)0\(0.5 + 0.75M\)\(7.5 - 11.75M\)
(c) State the value of each variable after the first iteration. (1)
(d) Explain why the solution given by the first iteration is not feasible. (1)

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

(e) obtain the most efficient pivot for a second iteration. You must give reasons for your answer. (2)

AS June 2019 Q5

EdexcelAS paperCurrent spec10 marksLinear Programming

5. Ben is a wedding planner. He needs to order flowers for the weddings that are taking place next month. The three types of flower he needs to order are roses, hydrangeas and peonies.

Based on his experience, Ben forms the following constraints on the number of each type of flower he will need to order.

  • At least three-fifths of all the flowers must be roses.
  • For every 2 hydrangeas there must be at most 3 peonies.
  • The total number of flowers must be exactly 1000

The cost of each rose is £1, the cost of each hydrangea is £5 and the cost of each peony is £4

Ben wants to minimise the cost of the flowers.

Let \(x\) represent the number of roses, let \(y\) represent the number of hydrangeas and let \(z\) represent the number of peonies that he will order.

(a) Formulate this as a linear programming problem in \(x\) and \(y\) only, stating the objective function and listing the constraints as simplified inequalities with integer coefficients. (7)

Ben decides to order the minimum number of roses that satisfy his constraints.

(b)
(i) Calculate the number of each type of flower that he will order to minimise the cost of the flowers.
(ii) Calculate the corresponding total cost of this order. (3)

AS June 2018 Q4

EdexcelAS paperCurrent spec11 marksLinear Programming

4. The manager of a factory is planning the production schedule for the next three weeks for a range of cabinets. The following constraints apply to the production schedule.

  • The total number of cabinets produced in week 3 cannot be fewer than the total number produced in weeks 1 and 2
  • At most twice as many cabinets must be produced in week 3 as in week 2
  • The number of cabinets produced in weeks 2 and 3 must, in total, be at most 125

The production cost for each cabinet produced in weeks 1, 2 and 3 is £250, £275 and £200 respectively.

The factory manager decides to formulate a linear programming problem to find a production schedule that minimises the total cost of production.

The objective is to minimise \(250x + 275y + 200z\)

(a) Explain what the variables \(x\), \(y\) and \(z\) represent. (1)
(b) Write down the constraints of the linear programming problem in terms of \(x\), \(y\) and \(z\). (2)

Due to demand, exactly 150 cabinets must be produced during these three weeks. This reduces the constraints to

\[\begin{gathered} x + y \leqslant 75 \\ x + 3y \geqslant 150 \\ x \geqslant 25 \\ y \geqslant 0 \end{gathered}\]

which are shown in Diagram 1 in the answer book.

Diagram 1: graph for x from 0 to 175 and y from 0 to 150 showing the lines x + y = 75, x + 3y = 150 and x = 25, with only the small triangle where the three lines meet left unshaded
Diagram 1

Given that the manager does not want any cabinets left unfinished at the end of a week,

(c)
(i) use a graphical approach to solve the linear programming problem and hence determine the production schedule which minimises the cost of production. You should make your method and working clear.
(ii) Find the minimum total cost of the production schedule. (8)

D1 June 2019 Q6

EdexcelOld spec10 marksLinear Programming

6.

Figure 4: feasible region R, a quadrilateral with vertices A, B, C and D, on axes x from -3 to 6 and y from 0 to 8
Figure 4

Figure 4 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region.

The vertices of the feasible region are \(A(4, 7)\), \(B(5, 3)\), \(C(-1, 5)\) and \(D(-2, 1)\).

(a) Determine the inequality that defines the boundary of \(R\) that passes through vertices \(A\) and \(C\), leaving your answer with integer coefficients only. (3)

The objective is to maximise \(P = 5x + y\)

(b) Find the coordinates of the optimal vertex and the corresponding value of \(P\). (3)

The objective is changed to maximise \(Q = kx + y\)

(c) If \(k\) can take any value, find the range of values of \(k\) for which \(A\) is the only optimal vertex. (4)

D2 June 2019 Q5

EdexcelOld spec11 marksLinear Programming

5. A linear programming problem in \(x\), \(y\) and \(z\) is described as follows.

Maximise \(P = 2x + 3y + z\)

subject to \[\begin{aligned} 2y - 3z &\leqslant 30 \\ -3x + y + z &\leqslant 60 \\ x + 4y - z &\leqslant 80 \end{aligned}\]

(a) Complete the initial tableau in the answer book for this linear programming problem. (3)
(b) Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the simplex algorithm to obtain a new tableau, T. Make your method clear by stating the row operations you use. (5)
(c) Write down the profit equation given by T and state the values of the slack variables given by T. (2)

The following tableau is obtained after further iterations.

Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)02–310030
\(s\)013–2013300
\(x\)14–100180
\(P\)05–3002160
(d) Explain why no optimal solution can be found by applying the simplex algorithm to the above tableau. (1)

D1 June 2018 Q7

EdexcelOld spec17 marksLinear Programming

7. A café sells two types of scone, plain and fruit.

The café manager knows that each week she should order

  • at least 400 scones in total
  • at most 350 fruit scones

In addition, for every 3 fruit scones ordered, at most 5 plain scones should be ordered.

Each plain scone costs £0.11 and is sold at a profit of £0.75

Each fruit scone costs £0.14 and is sold at a profit of £1

The manager has £77 to spend each week on scones. The manager wants to maximise her profit and it can be assumed that all scones ordered will be sold.

Let \(x\) represent the number of plain scones and let \(y\) represent the number of fruit scones that are sold.

(a) Formulate this information as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients. (6)
(b) Represent these constraints on Diagram 1 in the answer book.
Hence determine the feasible region and label it R. (4)
(c) Use the objective line method to find the optimal vertex, V, of the feasible region. You must make your objective line clear and label the optimal vertex V. (3)
(d) Calculate the exact coordinates of V. (2)
(e) State the number of each type of scone that the manager should order and calculate the maximum profit. (2)

D2 June 2018 Q5

EdexcelOld spec17 marksLinear Programming

5. The initial tableau for a linear programming problem in \(x\), \(y\) and \(z\) is shown below. The objective function to be maximised is \(P = 4x + 2y + kz\), where \(k\) is a positive constant.

Basic Variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)−2−6110040
\(s\)23201080
\(t\)12200150
\(P\)−4−2\(-k\)0000
(a) Using the information in the tableau, write down the three constraints as inequalities. (2)
(b) By increasing \(x\), perform one complete iteration of the simplex algorithm to obtain tableau T1 and state the row operations you use. (4)
(c) Given that T1 is not optimal, find an inequality for the value of \(k\). (1)
(d) Perform a second complete iteration of the simplex algorithm to obtain tableau T2 and state the row operations you use. (4)
(e) Given that T2 is optimal, find a second inequality for the value of \(k\). (2)
(f) State the final value of each variable and give an expression for the final value of \(P\) in terms of \(k\). (2)
(g) Hence find the range of possible values of \(P\). (2)

D1 June 2017 Q7

EdexcelOld spec8 marksLinear Programming

7. A caterer can make three different sizes of salad; small, medium and large.

The caterer will make a total of at least 280 salads.

The caterer wants at least 35% of the salads to be small and no more than 20% of the salads to be large.

The caterer has enough ingredients to make 400 small salads or 300 medium salads or 200 large salads.

The profit on each small, medium and large salad is 40p, 60p and 85p respectively. The caterer wants to maximise his total profit.

Let \(x\) represent the number of small salads, \(y\) represent the number of medium salads and \(z\) represent the number of large salads.

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

You should not attempt to solve the problem. (8)

D2 June 2017 Q5

EdexcelOld spec13 marksLinear Programming

5. The tableau below is the initial tableau for a three-variable linear programming problem in \(x\), \(y\) and \(z\). The objective is to maximise the profit, \(P\).

Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)15–23100180
\(s\)101101080
\(t\)16–2001100
\(P\)–1–2–50000
(a) Using the information in the tableau, write down
(i) the objective function,
(ii) the three constraints as inequalities.
(3)
(b) Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. Make your method clear by stating the row operations you use. (8)
(c) State the final values of the objective function and each variable. (2)

D1 June 2017 Q5

EdexcelOld spec11 marksLinear Programming

5.

Figure 5: graph of 2y = x, 5y + 2x = 50 and 2x + y = 10 with feasible region R
Figure 5

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

(a) Write down the inequalities that form region \(R\). (2)
(b) Find the exact coordinates of the vertices of the feasible region. (3)

The objective is to maximise \(P\), where \(P = 2x + 3y\)

(c) Use point testing to find the optimal vertex, V, of the feasible region. (2)

The objective is changed to maximise \(Q\), where \(Q = 2x + \lambda y\)

Given that \(\lambda\) is a constant and V is still the only optimal vertex of the feasible region,

(d) find the range of possible values of \(\lambda\). (4)

D1 June 2016 Q8

EdexcelOld spec14 marksLinear Programming

8. Charlie needs to buy storage containers.

There are two different types of storage container available, standard and deluxe.

Standard containers cost £20 and deluxe containers cost £65. Let \(x\) be the number of standard containers and \(y\) be the number of deluxe containers.

The maximum budget available is £520

(a) Write down an inequality, in terms of \(x\) and \(y\), to model this constraint. (1)

Three further constraints are:

\[\begin{aligned} x &\geqslant 2\\ -x + 24y &\geqslant 24\\ 7x + 8y &\leqslant 112 \end{aligned}\]
(b) Add lines and shading to Diagram 1 in the answer book to represent all four constraints. Hence determine the feasible region and label it R. (4)

The capacity of a deluxe container is 50% greater than the capacity of a standard container. Charlie wishes to maximise the total capacity.

(c) State an objective function, in terms of \(x\) and \(y\). (1)
(d) Use the objective line method to find the optimal vertex, V, of the feasible region. You must make your objective line clear and label the optimal vertex V. (3)
(e) Calculate the exact coordinates of vertex V. (2)
(f) Determine the number of each type of container that Charlie should buy. You must make your method clear and calculate the cost of purchasing the storage containers. (3)

D2 June 2016 Q4

EdexcelOld spec9 marksLinear Programming

4. A three-variable linear programming problem in \(x\), \(y\) and \(z\) is to be solved. The objective is to maximise the profit, \(P\). The following tableau is obtained after the first iteration.

Basic Variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)0521–3010
\(x\)12301018
\(t\)01–10413
\(P\)03–40107
(a) State which variable was increased first, giving a reason for your answer. (1)
(b) Perform one complete iteration of the simplex algorithm, to obtain a new tableau, T. Make your method clear by stating the row operations you use. (5)
(c) Write down the profit equation given by T. (1)
(d) State whether T is optimal. You must use your answer to (c) to justify your answer. (2)

D1 June 2015 Q6

EdexcelOld spec13 marksLinear Programming

6. A linear programming problem in \(x\) and \(y\) is described as follows.

Minimise \(C = 2x + 3y\)

subject to

\[\begin{aligned} x + y &\geqslant 8\\ x &\lt 8\\ 4y &\geqslant x\\ 3y &\leqslant 9 + 2x \end{aligned}\]
(a) Add lines and shading to Diagram 1 in the answer book to represent these constraints. (4)
(b) Hence determine the feasible region and label it R. (1)
(c) Use the objective line (ruler) method to find the exact coordinates of the optimal vertex, V, of the feasible region. You must draw and label your objective line clearly. (3)
(d) Calculate the corresponding value of \(C\) at V. (1)

The objective is now to maximise \(2x + 3y\), where \(x\) and \(y\) are integers.

(e) Write down the optimal values of \(x\) and \(y\) and the corresponding maximum value of \(2x + 3y\). (2)

A further constraint, \(y \leqslant kx\), where \(k\) is a positive constant, is added to the linear programming problem.

(f) Determine the least value of \(k\) for which this additional constraint does not affect the feasible region. (2)

D2 June 2015 Q1

EdexcelOld spec7 marksLinear Programming

1. The tableau below is the initial tableau for a linear programming problem in \(x\), \(y\) and \(z\). The objective is to maximise the profit, \(P\).

Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)2–4110015
\(s\)42–801020
\(t\)1–140018
\(P\)–3270000
(a) Perform one iteration of the Simplex algorithm to obtain a new tableau, T. State the row operations you use. (5)
(b) Write down the profit equation given by T and state the current values of the slack variables. (2)

D1 June 2014 (R) Q8

EdexcelOld spec6 marksLinear Programming

8. A manufacturer of frozen yoghurt is going to exhibit at a trade fair. He will take two types of frozen yoghurt, Banana Blast and Strawberry Scream.

He will take a total of at least 1000 litres of yoghurt.

He wants at least 25% of the yoghurt to be Banana Blast. He also wants there to be at most half as much Banana Blast as Strawberry Scream.

Each litre of Banana Blast costs £3 to produce and each litre of Strawberry Scream costs £2 to produce. The manufacturer wants to minimise his costs.

Let \(x\) represent the number of litres of Banana Blast and \(y\) represent the number of litres of Strawberry Scream.

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

You should not attempt to solve the problem. (6)

D1 June 2014 (R) Q5

EdexcelOld spec11 marksLinear Programming

5. A linear programming problem in \(x\) and \(y\) is described as follows.

Maximise     \(P = 2x + 3y\)

subject to

\[\begin{aligned} x &\geqslant 25\\ y &\geqslant 25\\ 7x + 8y &\leqslant 840\\ 4y &\leqslant 5x\\ 5y &\geqslant 3x\\ x,\ y &\geqslant 0 \end{aligned}\]
(a) Add lines and shading to Diagram 1 in the answer book to represent these constraints. Hence determine the feasible region and label it R. (4)
(b) Use the objective line method to find the optimal vertex, V, of the feasible region. You must clearly draw and label your objective line and the vertex V. (3)
(c) Calculate the exact coordinates of vertex V. (2)

Given that an integer solution is required,

(d) determine the optimal solution with integer coordinates. You must make your method clear. (2)

D2 June 2014 (R) Q4

EdexcelOld spec12 marksLinear Programming

4. The tableau below is the initial tableau for a three-variable linear programming problem in \(x\), \(y\) and \(z\). The objective is to maximise the profit, \(P\).

Basic Variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)43\(\frac{5}{2}\)10050
\(s\)12101030
\(t\)05100180
\(P\)–25–40–350000
(a) Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the simplex algorithm to obtain tableau T. Make your method clear by stating the row operations you use. (9)
(b) Write down the profit equation given by T. (1)
(c) Use your answer to (b) to determine whether T is optimal, justifying your answer. (2)

D1 June 2014 Q8

EdexcelOld spec8 marksLinear Programming

8.

Figure 4: graph showing the lines 4x + y = 36, 2x + y = 36, 5y = 2x and y = 2x, with the feasible region R and its vertices A, B, C and D
Figure 4

The graph in Figure 4 is being used to solve a linear programming problem. The four constraints have been drawn on the graph and the rejected regions have been shaded out. The four vertices of the feasible region \(R\) are labelled A, B, C and D.

(a) Write down the constraints represented on the graph. (2)

The objective function, P, is given by

\[P = x + ky\]

where \(k\) is a positive constant.

The minimum value of the function P is given by the coordinates of vertex A and the maximum value of the function P is given by the coordinates of vertex D.

(b) Find the range of possible values for \(k\). You must make your method clear. (6)

D2 June 2014 Q3

EdexcelOld spec12 marksLinear Programming

3. The tableau below is the initial tableau for a three-variable linear programming problem in \(x\), \(y\) and \(z\). The objective is to maximise the profit, \(P\).

Basic Variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)53\(-\frac{1}{2}\)1002500
\(s\)3210101650
\(t\)\(\frac{1}{2}\)–12001800
\(P\)–40–50–350000
(a) Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. Make your method clear by stating the row operations you use. (10)
(b) State the final values of the objective function and each variable. (2)

D1 June 2013 (R) Q8

EdexcelOld spec16 marksLinear Programming

8.

Figure 6: graph with the lines y = 16 and a line through the origin, rejected regions shaded
Figure 6

A company makes two types of garden bench, the ‘Rustic’ and the ‘Contemporary’. The company wishes to maximise its profit and decides to use linear programming.

Let \(x\) be the number of ‘Rustic’ benches made each week and \(y\) be the number of ‘Contemporary’ benches made each week.

The graph in Figure 6 is being used to solve this linear programming problem.

Two of the constraints have been drawn on the graph and the rejected region shaded out.

(a) Write down the constraints shown on the graph giving your answers as inequalities in terms of \(x\) and \(y\). (3)

It takes 4 working hours to make one ‘Rustic’ bench and 3 working hours to make one ‘Contemporary’ bench. There are 120 working hours available in each week.

(b) Write down an inequality to represent this information. (2)

Market research shows that ‘Rustic’ benches should be at most \(\dfrac{3}{4}\) of the total benches made each week.

(c) Write down, and simplify, an inequality to represent this information. Your inequality must have integer coefficients. (2)
(d) Add two lines and shading to Diagram 1 in your answer book to represent the inequalities of (b) and (c). Hence determine and label the feasible region, R. (3)

The profit on each ‘Rustic’ bench and each ‘Contemporary’ bench is £45 and £30 respectively.

(e) Write down the objective function, P, in terms of \(x\) and \(y\). (1)
(f) Determine the coordinates of each of the vertices of the feasible region and hence use the vertex method to determine the optimal point. (4)
(g) State the maximum weekly profit the company could make. (1)

D2 June 2013 (R) Q5

EdexcelOld spec8 marksLinear Programming

5. A three-variable linear programming problem in \(x\), \(y\) and \(z\) is to be solved. The objective is to maximise the profit, \(P\).

The following tableau is obtained.

Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)\(\frac{1}{2}\)\(-\frac{1}{2}\)010\(-\frac{1}{2}\)10
\(s\)\(1\frac{1}{2}\)\(2\frac{1}{2}\)001\(-\frac{1}{2}\)5
\(z\)\(\frac{1}{2}\)\(\frac{1}{2}\)100\(\frac{1}{2}\)5
\(P\)–5–1000020220
(a) Starting by increasing \(y\), perform one complete iteration of the Simplex algorithm, to obtain a new tableau, T. State the row operations you use. (5)
(b) Write down the profit equation given by T. (1)
(c) Use the profit equation from part (b) to explain why T is optimal. (2)

D1 June 2013 Q6

EdexcelOld spec12 marksLinear Programming

6. Harry wants to rent out boats at his local park. He can use linear programming to determine the number of each type of boat he should buy.

Let \(x\) be the number of 2-seater boats and \(y\) be the number of 4-seater boats.

One of the constraints is

\[x + y \geqslant 90\]
(a) Explain what this constraint means in the context of the question. (1)

Another constraint is

\[2x \leqslant 3y\]
(b) Explain what this constraint means in the context of the question. (2)

A third constraint is

\[y \leqslant x + 30\]
(c) Represent these three constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region R. (4)

Each 2-seater boat costs £100 and each 4-seater boat costs £300 to buy. Harry wishes to minimise the total cost of buying the boats.

(d) Write down the objective function, C, in terms of \(x\) and \(y\). (1)
(e) Determine the number of each type of boat that Harry should buy. You must make your method clear and state the minimum cost. (4)

D2 June 2013 Q5

EdexcelOld spec11 marksLinear Programming

5. In solving a three-variable maximising linear programming problem, the following tableau was obtained after the first iteration.

Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)−1201018
\(s\)−13001122
\(z\)−21100111
\(P\)2−5000\(\tfrac{1}{2}\)15
(a) State which variable was increased first, giving a reason for your answer. (1)
(b) Solve this linear programming problem. Make your method clear by stating the row operations you use. (8)
(c) State the final value of the objective function and the final values of each variable. (2)

D1 January 2013 Q6

EdexcelOld spec13 marksLinear Programming

6.

Figure 6: graph with the lines x = 60, y = 30 and a line labelled (a) through the origin, rejected regions shaded
Figure 6

Lethna is producing floral arrangements for an awards ceremony.
She will produce two types of arrangement, Celebration and Party.
Let \(x\) be the number of Celebration arrangements made.
Let \(y\) be the number of Party arrangements made.

Figure 6 shows three constraints, other than \(x, y \geqslant 0\)

The rejected region has been shaded.

Given that two of the three constraints are \(y \leqslant 30\) and \(x \leqslant 60\),

(a) write down, as an inequality, the third constraint shown in Figure 6. (2)

Each Celebration arrangement includes 2 white roses and 4 red roses.

Each Party arrangement includes 1 white rose and 5 red roses.

Lethna wishes to use at least 70 white roses and at least 200 red roses.

(b) Write down two further inequalities to represent this information. (3)
(c) Add two lines and shading to Diagram 1 in the answer book to represent these two inequalities. (2)
(d) Hence determine the feasible region and label it \(R\). (1)

The times taken to produce each Celebration arrangement and each Party arrangement are 10 minutes and 4 minutes respectively. Lethna wishes to minimise the total time taken to produce the arrangements.

(e) Write down the objective function, \(T\), in terms of \(x\) and \(y\). (1)
(f) Use point testing to find the optimal number of each type of arrangement Lethna should produce, and find the total time she will take. (4)

D1 June 2012 Q7

EdexcelOld spec13 marksLinear Programming

7.

Figure 6: graph showing the lines x = 20, y = 8 and a line labelled (a) through the origin, with shading
Figure 6

A company is going to hire out two types of car, standard and luxury.

Let \(x\) be the number of standard cars it should buy.
Let \(y\) be the number of luxury cars it should buy.

Figure 6 shows three constraints, other than \(x,\ y \geqslant 0\)
Two of these are \(x \geqslant 20\) and \(y \geqslant 8\)

(a) Write, as an inequality, the third constraint shown in Figure 6. (1)

The company decides that at least \(\dfrac{1}{6}\) of the cars must be luxury cars.

(b) Express this information as an inequality and show that it simplifies to\[5y \geqslant x\]You must make the steps in your working clear. (2)

Each time the cars are hired they need to be prepared. It takes 5 hours to prepare a standard car and it takes 6 hours to prepare a luxury car. There are 300 hours available each week to prepare the cars.

(c) Express this information as an inequality. (1)
(d) Add two lines and shading to Diagram 1 in the answer book to illustrate the constraints found in parts (b) and (c). (2)
(e) Hence determine the feasible region and label it \(R\). (1)

The company expects to make £80 profit per week on each car.

It therefore wishes to maximise \(P = 80x + 80y\), where \(P\) is the profit per week.

(f) Use the objective line (ruler) method to find the optimal vertex, \(V\), of the feasible region.
You must clearly draw and label your objective line and the vertex \(V\). (3)
(g) Given that \(P\) is the expected profit, in pounds, per week, find the number of each type of car that the company should buy and the maximum expected profit. (3)

D2 June 2012 Q4

EdexcelOld spec8 marksLinear Programming

4. The tableau below is the initial tableau for a maximising linear programming problem in \(x\), \(y\) and \(z\) which is to be solved.

Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)5\(\tfrac{1}{2}\)01005
\(s\)1−240103
\(t\)8460016
\(P\)−5−7−40000
(a) Starting by increasing \(y\), perform one complete iteration of the simplex algorithm, to obtain tableau T. State the row operations you use. (5)
(b) Write down the profit equation given by tableau T. (2)
(c) Use the profit equation from part (b) to explain why tableau T is optimal. (1)

D1 January 2012 Q6

EdexcelOld spec11 marksLinear Programming

6.

Figure 6: axes x from 0 to 130 and y from 0 to 100; lines x = 40 and y = 50; regions x < 40 and y > 50 shaded
Figure 6

Edgar has recently bought a field in which he intends to plant apple trees and plum trees.

He can use linear programming to determine the number of each type of tree he should plant.

Let \(x\) be the number of apple trees he plants and \(y\) be the number of plum trees he plants.

Two of the constraints are

\[\begin{aligned}x &\geqslant 40\\ y &\leqslant 50\end{aligned}\]

These are shown on the graph in Figure 6, where the rejected region is shaded out.

(a) Use these two constraints to write down two statements that describe the number of apple trees and plum trees Edgar can plant. (1)

Two further constraints are

\[\begin{aligned}3x + 4y &\leqslant 360\\ x &\leqslant 2y\end{aligned}\]
(b) Add two lines and shading to Diagram 1 in your answer book to represent these inequalities. Hence determine the feasible region and label it R. (4)

Edgar will make a profit of £60 from each apple tree and £20 from each plum tree. He wishes to maximise his profit, P.

(c) Write down the objective function. (1)
(d) Use an objective line to determine the optimal point of the feasible region, R. You must make your method clear. (4)
(e) Find Edgar’s maximum profit. (1)

D1 June 2011 Q8

EdexcelOld spec7 marksLinear Programming

8. A firm is planning to produce two types of radio, type A and type B.

Market research suggests that, each week:

  • At least 50 type A radios should be produced.
  • The number of type A radios should be between 20% and 40% of the total number of radios produced.

Each type A radio requires 3 switches and each type B radio requires 2 switches. The firm can only buy 200 switches each week.

The profit on each type A radio is £15.

The profit on each type B radio is £12.

The firm wishes to maximise its weekly profit.

Formulate this situation as a linear programming problem, defining your variables.

D2 June 2011 Q3

EdexcelOld spec10 marksLinear Programming

3. A three-variable linear programming problem in \(x\), \(y\) and \(z\) is to be solved. The objective is to maximise the profit, \(P\).

The following tableau is obtained.

Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)\(-\tfrac{1}{2}\)021\(-\tfrac{1}{2}\)010
\(y\)\(\tfrac{1}{2}\)1\(\tfrac{3}{4}\)0\(\tfrac{1}{4}\)05
\(t\)\(\tfrac{1}{2}\)010\(-\tfrac{1}{4}\)14
\(P\)−701040320
(a) Write down the profit equation represented in the tableau. (2)
(b) Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. Make your method clear by stating the row operations you use. (5)
(c) State the value of the objective function and of each variable. (3)

D1 June 2011 Q3

EdexcelOld spec8 marksLinear Programming

3.

Figure 2: graph with lines 6x + 5y = 60, 2x + 3y = 12, 3x = 2y and x = 2y, rejected sides hatched, feasible region R between them
Figure 2

Figure 2 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region.

(a) Write down the inequalities that form region \(R\). (2)

The objective is to maximise \(3x + y\).

(b) Find the optimal values of \(x\) and \(y\). You must make your method clear. (4)
(c) Obtain the optimal value of the objective function. (1)

Given that integer values of \(x\) and \(y\) are now required,

(d) write down the optimal values of \(x\) and \(y\). (1)

D1 January 2011 Q6

EdexcelOld spec11 marksLinear Programming

6.

Figure 6: axes x from 0 to 80 and y from 0 to 60; line from (0, 15) to (80, 55) with region above shaded; line from (0, 0) to (80, 20) with region below shaded
Figure 6

The graph in Figure 6 is being used to solve a linear programming problem.
Two of the constraints have been drawn on the graph and the rejected regions shaded out.

(a) Write down the constraints shown on the graph. (4)

Two further constraints are

\[\begin{aligned}x + y &\geqslant 30\\ \text{and}\quad 5x + 8y &\leqslant 400\end{aligned}\]
(b) Add two lines and shading to Graph 1 in your answer book to represent these constraints. Hence determine the feasible region and label it R. (4)

The objective is to

\[\text{minimise }\ 15x + 10y\]
(c) Draw a profit line on Graph 1 and use it to find the optimal solution. You must label your profit line clearly. (3)

D1 June 2010 Q7

EdexcelOld spec11 marksLinear Programming

7.

Figure 6: axes x from 0 to 16 and y from 0 to 24; solid line x = 15 with x > 15 shaded; dotted line y = 6 with y < 6 shaded
Figure 6

Keith organises two types of children’s activity, ‘Sports Mad’ and ‘Circus Fun’.
He needs to determine the number of times each type of activity is to be offered.

Let \(x\) be the number of times he offers the ‘Sports Mad’ activity. Let \(y\) be the number of times he offers the ‘Circus Fun’ activity.

Two constraints are

\[\begin{aligned}x &\leqslant 15\\ \text{and}\quad y &\gt 6\end{aligned}\]

These constraints are shown on the graph in Figure 6, where the rejected regions are shaded out.

(a) Explain why \(y = 6\) is shown as a dotted line. (1)

Two further constraints are

\[\begin{aligned}3x &\geqslant 2y\\ \text{and}\quad 5x + 4y &\geqslant 80\end{aligned}\]
(b) Add two lines and shading to Diagram 1 in the answer book to represent these inequalities. Hence determine the feasible region and label it R. (3)

Each ‘Sports Mad’ activity costs £500.

Each ‘Circus Fun’ activity costs £800.

Keith wishes to minimise the total cost.

(c) Write down the objective function, C, in terms of \(x\) and \(y\). (2)
(d) Use your graph to determine the number of times each type of activity should be offered and the total cost. You must show sufficient working to make your method clear. (5)

D2 June 2010 Q6

EdexcelOld spec13 marksLinear Programming

6. The tableau below is the initial tableau for a linear programming problem in \(x\), \(y\) and \(z\). The objective is to maximise the profit, \(P\).

Basic Variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)01210024
\(s\)21401028
\(t\)−1\(\tfrac{1}{2}\)300122
\(P\)−1−2−60000
(a) Write down the profit equation represented in the initial tableau. (1)
(b) Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. Make your method clear by stating the row operations you use. (9)
(c) State the final value of the objective function and of each variable. (3)

D1 January 2010 Q7

EdexcelOld spec17 marksLinear Programming

7. You are in charge of buying new cupboards for a school laboratory.
The cupboards are available in two different sizes, standard and large.
The maximum budget available is £1800.  Standard cupboards cost £150 and large cupboards cost £300.
Let \(x\) be the number of standard cupboards and \(y\) be the number of large cupboards.

(a) Write down an inequality, in terms of \(x\) and \(y\), to model this constraint. (2)

The cupboards will be fitted along a wall 9 m long.  Standard cupboards are 90 cm long and large cupboards are 120 cm long.

(b) Show that this constraint can be modelled by \[3x + 4y \leqslant 30.\] You must make your reasoning clear. (2)

Given also that \(y \geqslant 2\),

(c) explain what this constraint means in the context of the question. (1)

The capacity of a large cupboard is 40% greater than the capacity of a standard cupboard.  You wish to maximise the total capacity.

(d) Show that your objective can be expressed as \[\text{maximise } 5x + 7y\] (2)
(e) Represent your inequalities graphically, on the axes in your answer booklet, indicating clearly the feasible region, R. (6)
(f) Find the number of standard cupboards and large cupboards that need to be purchased.  Make your method clear. (4)

D1 June 2009 Q7

EdexcelOld spec14 marksLinear Programming

7. Rose makes hanging baskets which she sells at her local market. She makes two types, large and small.

Rose makes \(x\) large baskets and \(y\) small baskets.

Each large basket costs £7 to make and each small basket costs £5 to make. Rose has £350 she can spend on making the baskets.

(a) Write down an inequality, in terms of \(x\) and \(y\), to model this constraint. (2)

Two further constraints are

\[\begin{aligned} &y \leqslant 20 \text{ and}\\ &y \leqslant 4x.\end{aligned}\]
(b) Use these two constraints to write down statements that describe the numbers of large and small baskets that Rose can make. (2)
(c) On the grid provided, show these three constraints and \(x \geqslant 0\), \(y \geqslant 0\). Hence label the feasible region, R. (4)

Rose makes a profit of £2 on each large basket and £3 on each small basket. Rose wishes to maximise her profit, £\(P\).

(d) Write down the objective function. (1)
(e) Use your graph to determine the optimal numbers of large and small baskets Rose should make, and state the optimal profit. (5)

D2 June 2009 Q5

EdexcelOld spec4 marksLinear Programming

5. While solving a maximising linear programming problem, the following tableau was obtained.

Basic Variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)value
\(z\)\(\tfrac{1}{4}\)\(-\tfrac{1}{4}\)1\(\tfrac{1}{4}\)002
\(s\)\(\tfrac{5}{4}\)\(\tfrac{7}{4}\)0\(-\tfrac{3}{4}\)104
\(t\)3\(\tfrac{5}{2}\)0\(-\tfrac{1}{2}\)012
\(P\)−2−40\(\tfrac{5}{4}\)0010
(a) Write down the values of \(x\), \(y\) and \(z\) as indicated by this tableau. (2)
(b) Write down the profit equation from the tableau. (2)

D1 January 2009 Q7

EdexcelOld spec12 marksLinear Programming

7. A linear programming problem is modelled by the following constraints

\[\begin{aligned} 8x + 3y &\leqslant 480\\ 8x + 7y &\geqslant 560\\ y &\geqslant 4x\\ x, y &\geqslant 0\end{aligned}\]
(a) Use the grid provided in your answer book to represent these inequalities graphically. Hence determine the feasible region and label it R. (6)

The objective function, \(F\), is given by

\[F = 3x + y\]
(b) Making your method clear, determine
(i) the minimum value of the function \(F\) and the coordinates of the optimal point,
(ii) the maximum value of the function \(F\) and the coordinates of the optimal point. (6)

D2 June 2008 Q8

EdexcelOld spec10 marksLinear Programming

8. The tableau below is the initial tableau for a maximising linear programming problem in \(x\), \(y\) and \(z\).

Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)4\(\dfrac{7}{3}\)\(\dfrac{5}{2}\)10064
\(s\)13001016
\(t\)42200160
\(P\)−5\(-\dfrac{7}{2}\)−40000
(a) Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the simplex algorithm. State the row operations you use. (9)
(b) Explain how you know that your solution is not optimal. (1)

D1 June 2008 Q8

EdexcelOld spec7 marksLinear Programming

8. Class 8B has decided to sell apples and bananas at morning break this week to raise money for charity. The profit on each apple is 20p, the profit on each banana is 15p. They have done some market research and formed the following constraints.

  • They will sell at most 800 items of fruit during the week.
  • They will sell at least twice as many apples as bananas.
  • They will sell between 50 and 100 bananas.

Assuming they will sell all their fruit, formulate the above information as a linear programming problem, letting \(a\) represent the number of apples they sell and \(b\) represent the number of bananas they sell.

Write your constraints as inequalities. (7)

D1 June 2008 Q6

EdexcelOld spec10 marksLinear Programming

6. The tableau below is the initial tableau for a maximising linear programming problem in \(x\), \(y\) and \(z\).

Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)4\(\dfrac{7}{3}\)\(\dfrac{5}{2}\)10064
\(s\)13001016
\(t\)42200160
\(P\)−5\(-\dfrac{7}{2}\)−40000
(a) Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the simplex algorithm. State the row operations you use. (9)
(b) Explain how you know that your solution is not optimal. (1)

D1 January 2008 Q7

EdexcelOld spec16 marksLinear Programming

7.

Figure 7: graph with x from 0 to 160 and y from 0 to 100 showing the line x + y = 70 and a fourth line through the origin, rejected region shaded
Figure 7

Phil sells boxed lunches to travellers at railway stations. Customers can select either the vegetarian box or the non-vegetarian box.

Phil decides to use graphical linear programming to help him optimise the numbers of each type of box he should produce each day.

Each day Phil produces \(x\) vegetarian boxes and \(y\) non-vegetarian boxes.

One of the constraints limiting the number of boxes is

\[x + y \geqslant 70.\]

This, together with \(x \geqslant 0\), \(y \geqslant 0\) and a fourth constraint, has been represented in Figure 7. The rejected region has been shaded.

(a) Write down the inequality represented by the fourth constraint. (2)

Two further constraints are:

\[x + 2y \leqslant 160\]\[\text{and} \quad y \gt 60.\]
(b) Add two lines and shading to Diagram 4 in your answer book to represent these inequalities. (4)
(c) Hence determine and label the feasible region, R. (1)
(d) Use your graph to determine the minimum total number of boxes he needs to prepare each day. Make your method clear. (3)

Phil makes a profit of £1.20 on each vegetarian box and £1.40 on each non-vegetarian box. He wishes to maximise his profit.

(e) Write down the objective function. (1)
(f) Use your graph to obtain the optimal number of vegetarian and non-vegetarian boxes he should produce each day. You must make your method clear. (4)
(g) Find Phil’s maximum daily profit. (1)

D2 June 2007 Q8

EdexcelOld spec18 marksLinear Programming

8. The tableau below is the initial tableau for a linear programming problem in \(x\), \(y\) and \(z\). The objective is to maximise the profit, \(P\).

basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)1245100246
\(s\)963010153
\(t\)52−2001171
\(P\)−2−4−30000

Using the information in the tableau, write down

(a) the objective function, (2)
(b) the three constraints as inequalities with integer coefficients. (3)

Taking the most negative number in the profit row to indicate the pivot column at each stage,

(c) solve this linear programming problem. Make your method clear by stating the row operations you use. (9)
(d) State the final values of the objective function and each variable. (3)
(e) One of the constraints is not at capacity. Explain how it can be identified. (1)

D1 June 2007 Q7

EdexcelOld spec18 marksLinear Programming

7. The tableau below is the initial tableau for a linear programming problem in \(x\), \(y\) and \(z\). The objective is to maximise the profit, \(P\).

basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)1245100246
\(s\)963010153
\(t\)52−2001171
\(P\)−2−4−30000

Using the information in the tableau, write down

(a) the objective function, (2)
(b) the three constraints as inequalities with integer coefficients. (3)

Taking the most negative number in the profit row to indicate the pivot column at each stage,

(c) solve this linear programming problem. Make your method clear by stating the row operations you use. (9)
(d) State the final values of the objective function and each variable. (3)

One of the constraints is not at capacity.

(e) Explain how it can be identified. (1)

D1 January 2007 Q7

EdexcelOld spec14 marksLinear Programming

7.

Figure 6: graph with x (Child) from 0 to 14 and y (Adult) from 0 to 12, showing the dotted line x = 10 and the lines y = 10 and y = 2 with rejected regions shaded
Figure 6

The captain of the Malde Mare takes passengers on trips across the lake in her boat.

The number of children is represented by \(x\) and the number of adults by \(y\).

Two of the constraints limiting the number of people she can take on each trip are

\[x \lt 10\]

and

\[2 \leqslant y \leqslant 10\]

These are shown on the graph in Figure 6, where the rejected regions are shaded out.

(a) Explain why the line \(x = 10\) is shown as a dotted line. (1)
(b) Use the constraints to write down statements that describe the number of children and the number of adults that can be taken on each trip. (3)

For each trip she charges £2 per child and £3 per adult. She must take at least £24 per trip to cover costs. The number of children must not exceed twice the number of adults.

(c) Use this information to write down two inequalities. (2)
(d) Add two lines and shading to Diagram 1 in your answer book to represent these inequalities. Hence determine the feasible region and label it R. (4)
(e) Use your graph to determine how many children and adults would be on the trip if the captain takes:
(i) the minimum number of passengers,
(ii) the maximum number of passengers. (4)

D1 January 2007 Q4

EdexcelOld spec7 marksLinear Programming

4. A three-variable linear programming problem in \(x\), \(y\) and \(z\) is to be solved. The objective is to maximise the profit \(P\). The following initial tableau was obtained.

Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)Value
\(r\)2041080
\(s\)14201160
\(P\)\(-2\)\(-8\)\(-20\)000
(a) Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the simplex algorithm, to obtain tableau \(T\). State the row operations that you use. (5)
(b) Write down the profit equation shown in tableau \(T\). (1)
(c) State whether tableau \(T\) is optimal. Give a reason for your answer. (1)

D2 June 2006 Q8

EdexcelOld spec16 marksLinear Programming

8. The tableau below is the initial tableau for a maximising linear programming problem.

Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)710101003600
\(s\)69120103600
\(t\)2340012400
\(P\)−35−55−600000
(a) Write down the four equations represented in the initial tableau above. (4)
(b) Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. State the row operations that you use. (9)
(c) State the values of the objective function and each variable. (3)

D1 June 2006 Q6

EdexcelOld spec16 marksLinear Programming

6. The tableau below is the initial tableau for a maximising linear programming problem.

Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)710101003600
\(s\)69120103600
\(t\)2340012400
\(P\)\(-35\)\(-55\)\(-60\)0000
(a) Write down the four equations represented in the initial tableau above. (4)
(b) Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. State the row operations that you use. (9)
(c) State the values of the objective function and each variable. (3)

D1 January 2006 Q6

EdexcelOld spec18 marksLinear Programming

6. A company produces two types of party bag, Infant and Junior. Both types of bag contain a balloon, a toy and a whistle. In addition the Infant bag contains 3 sweets and 3 stickers and the Junior bag contains 10 sweets and 2 stickers.

The sweets and stickers are produced in the company’s factory. The factory can produce up to 3000 sweets per hour and 1200 stickers per hour. The company buys a large supply of balloons, toys and whistles.

Market research indicates that at least twice as many Infant bags as Junior bags should be produced.

Both types of party bag are sold at a profit of 15p per bag. All the bags are sold.

The company wishes to maximise its profit.

Let \(x\) be the number of Infant bags produced and \(y\) be the number of Junior bags produced per hour.

(a) Formulate the above situation as a linear programming problem. (5)
(b) Represent your inequalities graphically, indicating clearly the feasible region. (6)
(c) Find the number of Infant bags and Junior bags that should be produced each hour and the maximum hourly profit. Make your method clear. (3)

In order to increase the profit further, the company decides to buy additional equipment. It can buy equipment to increase the production of either sweets or stickers, but not both.

(d) Using your graph, explain which equipment should be bought, giving your reasoning. (2)

The manager of the company does not understand why the balloons, toys and whistles have not been considered in the above calculations.

(e) Explain briefly why they do not need to be considered. (2)

D2 June 2005 Q8

EdexcelOld spec15 marksLinear Programming

8. Polly has a bird food stall at the local market. Each week she makes and sells three types of packs \(A\), \(B\) and \(C\).

Pack \(A\) contains 4 kg of bird seed, 2 suet blocks and 1 kg of peanuts.

Pack \(B\) contains 5 kg of bird seed, 1 suet block and 2 kg of peanuts.

Pack \(C\) contains 10 kg of bird seed, 4 suet blocks and 3 kg of peanuts.

Each week Polly has 140 kg of bird seed, 60 suet blocks and 60 kg of peanuts available for the packs.

The profit made on each pack of \(A\), \(B\) and \(C\) sold is £3.50, £3.50 and £6.50 respectively. Polly sells every pack on her stall and wishes to maximise her profit, \(P\) pence.

Let \(x\), \(y\) and \(z\) be the numbers of packs \(A\), \(B\) and \(C\) sold each week.

An initial Simplex tableau for the above situation is

Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)\(4\)\(5\)\(10\)\(1\)\(0\)\(0\)\(140\)
\(s\)\(2\)\(1\)\(4\)\(0\)\(1\)\(0\)\(60\)
\(t\)\(1\)\(2\)\(3\)\(0\)\(0\)\(1\)\(60\)
\(P\)\(-350\)\(-350\)\(-650\)\(0\)\(0\)\(0\)\(0\)
(a) Explain the meaning of the variables \(r\), \(s\) and \(t\) in the context of this question. (2)
(b) Perform one complete iteration of the Simplex algorithm to form a new tableau \(T\). Take the most negative number in the profit row to indicate the pivotal column. (5)
(c) State the value of every variable as given by tableau \(T\). (3)
(d) Write down the profit equation given by tableau \(T\). (2)
(e) Use your profit equation to explain why tableau \(T\) is not optimal. (1)

Taking the most negative number in the profit row to indicate the pivotal column,

(f) identify clearly the location of the next pivotal element. (2)

D1 June 2005 Q7

EdexcelOld spec15 marksLinear Programming

7. Polly has a bird food stall at the local market. Each week she makes and sells three types of packs A, B and C.

Pack A contains 4 kg of bird seed, 2 suet blocks and 1 kg of peanuts.
Pack B contains 5 kg of bird seed, 1 suet block and 2 kg of peanuts.
Pack C contains 10 kg of bird seed, 4 suet blocks and 3 kg of peanuts.

Each week Polly has 140 kg of bird seed, 60 suet blocks and 60 kg of peanuts available for the packs.

The profit made on each pack of A, B and C sold is £3.50, £3.50 and £6.50 respectively. Polly sells every pack on her stall and wishes to maximise her profit, \(P\) pence.

Let \(x\), \(y\) and \(z\) be the numbers of packs A, B and C sold each week.

An initial Simplex tableau for the above situation is

Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)4510100140
\(s\)21401060
\(t\)12300160
\(P\)\(-350\)\(-350\)\(-650\)0000
(a) Explain the meaning of the variables \(r\), \(s\) and \(t\) in the context of this question. (2)
(b) Perform one complete iteration of the Simplex algorithm to form a new tableau \(T\). Take the most negative number in the profit row to indicate the pivotal column. (5)
(c) State the value of every variable as given by tableau \(T\). (3)
(d) Write down the profit equation given by tableau \(T\). (2)
(e) Use your profit equation to explain why tableau \(T\) is not optimal. (1)

Taking the most negative number in the profit row to indicate the pivotal column,

(f) identify clearly the location of the next pivotal element. (2)

D1 January 2005 Q7

EdexcelOld spec18 marksLinear Programming

7. Flatland UK Ltd makes three types of carpet, the Lincoln, the Norfolk and the Suffolk. The carpets all require units of black, green and red wool.

For each roll of carpet,
the Lincoln requires 1 unit of black, 1 of green and 3 of red,
the Norfolk requires 1 unit of black, 2 of green and 2 of red,
and the Suffolk requires 2 units of black, 1 of green and 1 of red.

There are up to 30 units of black, 40 units of green and 50 units of red available each day.
Profits of £50, £80 and £60 are made on each roll of Lincoln, Norfolk and Suffolk respectively. Flatland UK Ltd wishes to maximise its profit.

Let the number of rolls of the Lincoln, Norfolk and Suffolk made daily be \(x\), \(y\) and \(z\) respectively.

(a) Formulate the above situation as a linear programming problem, listing clearly the constraints as inequalities in their simplest form, and stating the objective function. (4)

This problem is to be solved using the Simplex algorithm. The most negative number in the profit row is taken to indicate the pivot column at each stage.

(b) Stating your row operations, show that after one complete iteration the tableau becomes
Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)\(\tfrac{1}{2}\)0\(1\tfrac{1}{2}\)1\(-\tfrac{1}{2}\)010
\(y\)\(\tfrac{1}{2}\)1\(\tfrac{1}{2}\)0\(\tfrac{1}{2}\)020
\(t\)2000\(-1\)110
\(P\)\(-10\)0\(-20\)04001600
(4)
(c) Explain the practical meaning of the value 10 in the top row. (2)
(d)
(i) Perform one further complete iteration of the Simplex algorithm.
(ii) State whether your current answer to part (d)(i) is optimal. Give a reason for your answer.
(iii) Interpret your current tableau, giving the value of each variable. (8)