7.07a Simplex tableau: initial setup in standard format

6 Consider the linear programming problem:

1. Using slack variables, \(s\) and \(t\), express the non-trivial constraints as two equations.
2. Represent the problem as an initial Simplex tableau. Perform one iteration of the Simplex algorithm.
3. Use the Simplex algorithm to find the values of \(x , y\) and \(z\) for which \(P\) is maximised, subject to the constraints above.
4. The value 15 in the first constraint is increased to a new value \(k\). As a result the pivot for the first iteration changes. Show what effect this has on the final value of \(y\).

4

1. Represent the linear programming problem below by an initial Simplex tableau. $$\begin{array} { l l } \text { Maximise } & P = 5 x - 4 y - 3 z , \\ \text { subject to } & 2 x - 3 y + 4 z \leqslant 10 , \\ & 6 x + 5 y + 4 z \leqslant 60 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$
2. Perform one iteration of the Simplex algorithm and write down the values of \(x , y , z\) and \(P\) that result from this iteration.

6 Consider the linear programming problem: $$\begin{array} { l r } \text { maximise } & P = 3 x - 5 y + 4 z , \\ \text { subject to } & x + 2 y - 3 z \leqslant 12 , \\ & 2 x + 5 y - 8 z \leqslant 40 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$

1. Represent the problem as an initial Simplex tableau.
2. Explain why it is not possible to pivot on the \(z\) column of this tableau. Identify the entry on which to pivot for the first iteration of the Simplex algorithm. Explain how you made your choice of column and row.
3. Perform one iteration of the Simplex algorithm. Write down the values of \(x , y\) and \(z\) after this iteration.
4. Explain why \(P\) has no finite maximum. The coefficient of \(z\) in the objective is changed from + 4 to - 40 .
5. Describe the changes that this will cause to the initial Simplex tableau and the tableau that results after one iteration. What is the maximum value of \(P\) in this case? Now consider this linear programming problem: $$\begin{array} { l l } \text { maximise } & Q = 3 x - 5 y + 7 z , \\ \text { subject to } & x + 2 y - 3 z \leqslant 12 , \\ & 2 x - 7 y + 10 z \leqslant 40 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$ Do not use the Simplex algorithm for these parts.
6. By adding the two constraints, show that \(Q\) has a finite maximum.
7. There is an optimal point with \(y = 0\). By substituting \(y = 0\) in the two constraints, calculate the values of \(x\) and \(z\) that maximise \(Q\) when \(y = 0\).

5 Consider the following LP problem. $$\begin{aligned} \text { Minimise } & 2 a - 3 b + c + 18 , \\ \text { subject to } & a + b - c \geqslant 14 , \\ & - 2 a + 3 c \leqslant 50 , \\ \text { and } & a \leqslant 4 a \leqslant 5 b , \\ & a \leqslant 20 , b \leqslant 10 , c \leqslant 8 . \end{aligned}$$

1. By replacing \(a\) by \(20 - x , b\) by \(10 - y\) and \(c\) by \(8 - z\), show that the problem can be expressed as follows. $$\begin{aligned} \text { Maximise } & 2 x - 3 y + z , \\ \text { subject to } & x + y - z \leqslant 8 , \\ & 2 x - 3 z \leqslant 66 , \\ & 4 x - 5 y \leqslant 40 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{aligned}$$
2. Represent the problem as an initial Simplex tableau. Perform one iteration of the Simplex algorithm. Explain how the choice of pivot was made and show how each row was obtained. Write down the values of \(x , y\) and \(z\) at this stage. Hence write down the corresponding values of \(a , b\) and \(c\).
3. If, additionally, the variables \(a , b\) and \(c\) are non-negative, what additional constraints are there on the values of \(x , y\) and \(z\) ?

6 Consider the following LP problem.

1. Since \(a \leqslant 6\) it follows that \(6 - a \geqslant 0\), and similarly for \(b\) and \(c\). Let \(6 - a = x\) (so that \(a\) is replaced by \(6 - x ) , 8 - b = y\) and \(10 - c = z\) to show that the problem can be expressed as $$\begin{array} { l l } \text { Maximise } & 2 x - 4 y + 5 z , \\ \text { subject to } & 3 x + 2 y - z \leqslant 14 , \\ & 2 x - 4 z \leqslant 7 , \\ & - 4 x + y \leqslant 4 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$
2. Represent the problem as an initial Simplex tableau. Perform two iterations of the Simplex algorithm, showing how each row was obtained. Hence write down the values of \(a , b\) and \(c\) after two iterations. Find the value of the objective for the original problem at this stage.
   [0pt] [10]

5 Roland Neede, the baker, is making cupcakes. He makes three sizes of cupcake: miniature, small and standard. Miniature cupcakes are sold in boxes of 24 and each cupcake uses 3 units of topping and 2 decorations. Small cupcakes are sold in boxes of 20 and each cupcake uses 5 units of topping and 3 decorations. Standard cupcakes are sold in boxes of 12 and each cupcake uses 7 units of topping and 4 decorations. Roland has no restriction on the amount of cake mix that he uses but he only has 5000 units of topping and 3000 decorations available. Cupcakes are only sold in complete boxes, and Roland assumes that he can sell all the boxes of cupcakes that he makes. Irrespective of size, each box of cupcakes sold will give Roland a profit of \(\pounds 1\). Roland wants to maximise his total profit. Let \(x\) denote the number of boxes of miniature cupcakes, \(y\) denote the number of boxes of small cupcakes and \(z\) denote the number of boxes of standard cupcakes that Roland makes.

1. Construct an objective function, \(P\), to be maximised.
2. By considering the number of units of topping used, show that \(18 x + 25 y + 21 z \leqslant 1250\).
3. Construct a similar constraint by considering the number of decorations used, simplifying the coefficients so that they are integers with no common factor.
4. Set up an initial Simplex tableau to represent Roland's problem.
5. Perform one iteration of the Simplex algorithm, choosing a pivot from the \(x\) column. Explain how the choice of pivot row was made and show how each row was calculated.
6. Write down the values of \(x , y\) and \(z\) from the first iteration of the Simplex algorithm. Hence find the maximum profit that Roland can make, remembering that cupcakes can only be sold in complete boxes. Calculate the number of units of topping and the number of decorations that are left over with this solution.
7. The constraint from the number of units of topping can be rewritten as \(18 P + 7 y + 3 z \leqslant 1250\). Form a similar expression for the constraint from the number of decorations. Use this to find the number of boxes of small cupcakes which maximises the profit when there are no decorations left over. Find the solution which gives the maximum profit using all the topping and all the decorations, and find the values of \(x , y\) and \(z\) for this solution. {}

5 Consider the linear programming problem:

1. Using slack variables, \(s \geqslant 0\) and \(t \geqslant 0\), express the two non-trivial constraints as equations.
2. Represent the problem as an initial Simplex tableau.
3. Explain why the pivot element must be chosen from the \(x\)-column and show the calculations that are used to choose the pivot.
4. Perform one iteration of the Simplex algorithm. Show how you obtained each row of your tableau and write down the values of \(x , y , z\) and \(P\) that result from this iteration. State whether or not this is the maximum feasible value of \(P\) and describe how you know this from the values in the tableau.

4 Consider the linear programming problem: $$\begin{array} { l l } \text { maximise } & P = 3 x - 5 y , \\ \text { subject to } & x + 5 y \leqslant 12 , \\ & x - 5 y \leqslant 10 , \\ & 3 x + 10 y \leqslant 45 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 . \end{array}$$

1. Represent the problem as an initial Simplex tableau.
2. Identify the entry on which to pivot for the first iteration of the Simplex algorithm. Explain how you made your choice of column and row.
3. Perform oneiteration of the Simplex algorithm. Write down the values of \(\mathrm { x } , \mathrm { y }\) and P after this iteration.
4. Show that \(\mathrm { x } = 11 , \mathrm { y } = 0.2\) is a feasible solution and that it gives a bigger value of P than that in part (iii).

4 Consider the following LP problem.

1. Represent the problem as an initial Simplex tableau. Explain why the pivot can only be chosen from the \(x\) column.
2. Perform one iteration of the Simplex algorithm. Show how each row was obtained and write down the values of \(w , x , y , z\) and \(P\) at this stage.
3. Perform a second iteration of the Simplex algorithm. Write down the values of \(w , x , y , z\) and \(P\) at this stage and explain how you can tell from this tableau that \(P\) can be increased without limit. How could you have known from the LP formulation above that \(P\) could be increased without limit?

4 Consider the following linear programming problem. $$\begin{array} { l r } \text { Maximise } & P = - 5 x - 6 y + 4 z , \\ \text { subject to } & 3 x - 4 y + z \leqslant 12 , \\ & 6 x + 2 z \leqslant 20 , \\ & - 10 x - 5 y + 5 z \leqslant 30 , \\ & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$

1. Use slack variables \(s , t\) and \(u\) to rewrite the first three constraints as equations. What restrictions are there on the values of \(s , t\) and \(u\) ?
2. Represent the problem as an initial Simplex tableau.
3. Show why the pivot for the first iteration of the Simplex algorithm must be the coefficient of \(z\) in the third constraint.
4. Perform one iteration of the Simplex algorithm, showing how the elements of the pivot row were calculated and how this was used to calculate the other rows.
5. Perform a second iteration of the Simplex algorithm and record the values of \(x , y , z\) and \(P\) at the end of this iteration.
6. Write down the values of \(s , t\) and \(u\) from your final tableau and explain what they mean in terms of the original constraints.

6 Consider the following linear programming problem.

1. Represent the constraints graphically. Shade the regions where the inequalities are not satisfied and hence identify the feasible region.
2. Calculate the coordinates of the vertices of the feasible region, apart from the origin, and calculate the value of \(P\) at each vertex. Hence find the optimal values of \(x\) and \(y\), and state the maximum value of the objective.
3. Suppose that, additionally, \(x\) and \(y\) must both be integers. Find the maximum feasible value of \(y\) for every feasible integer value of \(x\). Calculate the value of \(P\) at each of these points and hence find the optimal values of \(x\) and \(y\) with this additional restriction. Tom wants to use the Simplex algorithm to solve the original (non-integer) problem. He reformulates it as follows.

   Maximise	\(\quad P = 5 x + 8 y\),
   subject to	\(3 x - 2 y \leqslant 12\),
   	\(3 x + 4 y \leqslant 30\),
   	\(- 3 x + 8 y \leqslant 24\),
   	\(x \geqslant 0 , y \geqslant 0\).

4. Explain why Tom needed to change the third constraint.
5. Represent the problem by an initial Simplex tableau.
6. Perform one iteration of the Simplex algorithm, choosing your pivot from the \(\boldsymbol { y }\) column. Show how the pivot row was used to calculate the other rows. Write down the values of \(x , y\) and \(P\) that result from this iteration. Perform a second iteration of the Simplex algorithm to achieve the optimum point.

4 A farmer has 40 acres of land that can be used for growing wheat, potatoes and soya beans. The farmer can expect a profit of \(\pounds 80\) for each acre of wheat, \(\pounds 31\) for each acre of potatoes and \(\pounds 100\) for each acre of soya beans. Land that is left unplanted incurs no cost and generates no profit. The farmer wants to choose how much land to use for growing each crop to maximise the profit. It takes 4 hours to plant each acre of wheat, 2 hours to plant each acre of potatoes and 1 hour to plant each acre of soya beans. There are 60 hours available in total for planting. At most 25 acres can be used for wheat and at most 10 acres can be used for soya beans.
Let \(x\) denote the number of acres used for wheat, \(y\) denote the number of acres used for potatoes and \(z\) denote the number of acres used for soya beans.

1. Express the profit, \(\pounds P\), as a function of \(x , y\) and \(z\).
2. Explain why the constraint \(4 x + 2 y + z \leqslant 60\) is needed. Write down three more constraints on the values of \(x , y\) and \(z\), other than that they must be non-negative.
3. Set up an initial Simplex tableau to represent the farmer's problem. Perform one iteration of the Simplex algorithm, choosing a pivot from the column with the most negative value in the objective row. Show how each row that has changed was calculated. Julie uses the Simplex algorithm to solve the farmer's problem. Her final tableau is given below. The order of the rows and the use of the slack variables in Julie's tableau may be different from yours.

   P	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	\(v\)	RHS
   1	0	9	0	20	0	80	0	2000
   0	1	0.5	0	0.25	0	-0.25	0	12.5
   0	0	-0.5	0	-0.25	1	0.25	0	12.5
   0	0	0	1	0	0	1	0	10
   0	0	0.5	0	-0.25	0	-0.75	1	17.5

4. Write down the values of \(x , y\) and \(z\) from Julie's final tableau. Hence advise the farmer on how many acres to use for each crop and how much land should be left unplanted.

3 A problem to maximise \(P\) as a function of \(x , y\) and \(z\) is represented by the initial Simplex tableau below.

1. Write down \(P\) as a function of \(x , y\) and \(z\).
2. Write down the constraints as inequalities involving \(x , y\) and \(z\).
3. Carry out one iteration of the Simplex algorithm. After a second iteration of the Simplex algorithm the tableau is as given below.

   \(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	RHS
   1	0	7.25	0	0.6	1.75	211
   0	1	0.75	0	0	0.25	25
   0	0	0.75	1	- 0.2	0.25	13

4. Explain how you know that the optimal solution has been achieved.
5. Write down the values of \(x , y\) and \(z\) that maximise \(P\). Write down the optimal value of \(P\).

7 Consider the linear programming problem: $$\begin{array} { l l } \text { maximise } & P = 4 y - x , \\ \text { subject to } & x + 4 y \leqslant 22 , \\ & x + y \leqslant 10 , \\ & - x + 2 y \leqslant 8 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 . \end{array}$$

1. Represent the constraints graphically, shading out the regions where the inequalities are not satisfied. Calculate the value of \(x\) and the value of \(y\) at each of the vertices of the feasible region. Hence find the maximum value of \(P\), clearly indicating where it occurs.
2. By introducing slack variables, represent the problem as an initial Simplex tableau and use the Simplex algorithm to solve the problem.
3. Indicate on your diagram for part (i) the points that correspond to each stage of the Simplex algorithm carried out in part (ii). \section*{OXFORD CAMBRIDGE AND RSA EXAMINATIONS} Advanced Subsidiary General Certificate of Education Advanced General Certificate of Education MATHEMATICS
   4736
   Decision Mathematics 1
   INSERT for Questions 4, 5 and 6
   Specimen Paper
   • This insert should be used to answer Questions 4, 5 and 6
   • .
   • Write your Name, Centre Number and Candidate Number in the spaces provided at the top of this page.
   • Write your answers to Questions 4, 5 and 6
   • in the spaces provided in this insert, and attach it to your answer booklet.
   4

4. STEP	A	\(B\)	C
   1
   2

5. STEP	A	\(B\)	C
   1
   2

   5
6. \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-7_661_1004_285_557}
7. Upper bound = \(\_\_\_\_\) km Lower bound = \(\_\_\_\_\) km
8. \(\_\_\_\_\) Best upper bound = \(\_\_\_\_\) km 6
9. \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-8_668_1406_292_406} \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-8_307_1342_1014_424}
   Least travel time = \(\_\_\_\_\) minutes Route: A- \(\_\_\_\_\) \(- D\)

7. A leisure company owns boats of each of the following types: 2-person boats which are 4 metres long and weigh 50 kg .
4-person boats which are 3 metres long and weigh 20 kg .
8-person boats which are 14 metres long and weigh 100 kg .
The leisure company is willing to donate boats to a local sports club to accommodate up to 40 people at any one time. However, storage facilities mean that a maximum combined length of the boats must not be more than 75 metres. Also, it must be possible to transport all the boats on a single trailer which has a maximum load capacity of 600 kg . The club intends to hire the boats out to help with the cost of maintaining them. It plans to charge \(\pounds 10 , \pounds 12\) and \(\pounds 8\) per day, for the 2 -, 4 - and 8 -person boats respectively and wishes to maximise its daily revenue ( \(\pounds R\) ). Let \(x , y\) and \(z\) represent the number of 2-, 4- and 8-person boats respectively given to the club.

1. Model this as a linear programming problem simplifying your expressions so that they have integer coefficients.
   (4 marks)
2. Show that the initial tableau, when using the simplex algorithm, can be written as:

   Basic Variable	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	Value
   \(s\)	1	2	4	1	0	0	20
   \(t\)	4	3	14	0	1	0	75
   \(u\)	5	2	10	0	0	1	60
   \(R\)	\({ } ^ { - } 10\)	\({ } ^ { - } 12\)	\({ } ^ { - } 8\)	0	0	0	0

3. Explain the purpose of the variables \(s\), \(t\) and \(u\).
4. By increasing the value of \(y\) first, work out the next two complete tableaus.
5. Explain how you know that your final tableau gives an optimal solution and state this solution in practical terms. Sheet for answering question 3
   NAME \section*{Please hand this sheet in for marking}
   3. \includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-08_2017_1051_462_244}
      \section*{Please hand this sheet in for marking}
   4. \(F \quad \bullet\)
      H •
      I •
      J •
      Complete matching:
      F •
      \section*{Sheet for answering question 5} NAME \section*{Please hand this sheet in for marking}
      \includegraphics[max width=\textwidth, alt={}]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-10_2398_643_248_1224}
      Sheet for answering question 6
      NAME \section*{Please hand this sheet in for marking}
   5. \(\_\_\_\_\)
   6. \(\_\_\_\_\)
   7. \(\_\_\_\_\)
   8. \includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-11_592_1292_1078_312}
      Sheet for answering question 6 (cont.) \includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-12_595_1299_351_312} \includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-12_597_1298_1409_308}

7. A fitness centre runs introductory courses aimed at the following groups of customers: Pensioners, who will be charged \(\pounds 4\) for a 2 -hour session.
Other adults, who will be charged \(\pounds 10\) for a 4 -hour session.
Children, who will be charged \(\pounds 2\) for a 1 -hour session.
Let the number of pensioners, other adults, and children be \(x , y\) and \(z\) respectively.
Regulations state that the number of pensioners, \(x\), must be at most 5 more than the number of adults, \(y\). There must also be at least twice as many adults, \(y\), as there are children, \(z\). The centre is able to supervise up to 40 person-hours each day at the centre and wishes to maximise the revenue \(( \pounds R )\) that can be earned each day from these sessions. You may assume that the places on any courses that the centre runs will be filled.

1. Modelling this situation as a linear programming problem, write down the constraints and objective function in terms of \(x , y\) and \(z\). Using the Simplex algorithm, the following initial tableau is obtained.
2. \(\_\_\_\_\)

4 A linear programming problem involving variables \(x , y\) and \(z\) is to be solved. The objective function to be maximised is \(P = 2 x + 4 y + 3 z\). The initial Simplex tableau is given below.

1. 1. What name is given to the variables \(s , t\) and \(u\) ?
   2. Write down an equation involving \(x , y , z\) and \(s\) for this problem.
2. 1. By choosing the first pivot from the \(\boldsymbol { y }\)-column, perform one iteration of the Simplex method.
   2. Explain how you know that the optimal value has not been reached.
3. 1. Perform one further iteration.
   2. Interpret the final tableau, stating the values of \(P , x , y\) and \(z\).

4 The Simplex method is to be used to maximise \(P = 3 x + 2 y + z\) subject to the constraints $$\begin{aligned} - x + y + z & \leqslant 4 \\ 2 x + y + 4 z & \leqslant 10 \\ 4 x + 2 y + 3 z & \leqslant 21 \end{aligned}$$ The initial Simplex tableau is given below.

1. 1. The first pivot is to be chosen from the \(x\)-column. Identify the pivot and explain why this particular value is chosen.
   2. Perform one iteration of the Simplex method and explain how you know that the optimal value has not been reached.
2. 1. Perform one further iteration.
   2. Interpret the final tableau and write down the initial inequality that still has slack.
      \includegraphics[max width=\textwidth, alt={}]{172c5c92-4254-4593-b741-1caa83a1e833-11_2486_1714_221_153}

4 A linear programming problem consists of maximising an objective function \(P\) involving three variables, \(x , y\) and \(z\), subject to constraints given by three inequalities other than \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\). Slack variables \(s , t\) and \(u\) are introduced and the Simplex method is used to solve the problem. One iteration of the method leads to the following tableau.

1. 1. State the column from which the pivot for the next iteration should be chosen. Identify this pivot and explain the reason for your choice.
   2. Perform the next iteration of the Simplex method.
2. 1. Explain why you know that the maximum value of \(P\) has been achieved.
   2. State how many of the three original inequalities still have slack.
3. 1. State the maximum value of \(P\) and the values of \(x , y\) and \(z\) that produce this maximum value.
   2. The objective function for this problem is \(P = k x - 2 y + 3 z\), where \(k\) is a constant. Find the value of \(k\).
      
      \includegraphics[max width=\textwidth, alt={}]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-11_2486_1714_221_153}

5

1. Display the following linear programming problem in a Simplex tableau.
   Maximise \(\quad P = x - 2 y + 3 z\) subject to $$\begin{array} { r } x + y + z \leqslant 16 \\ x - 2 y + 2 z \leqslant 17 \\ 2 x - y + 2 z \leqslant 19 \end{array}$$ and \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\).
2. 1. The first pivot to be chosen is from the \(z\)-column. Identify the pivot and explain why this particular value is chosen.
   2. Perform one iteration of the Simplex method.
3. 1. Perform one further iteration.
   2. Interpret the tableau that you obtained in part (c)(i) and state the values of your slack variables.

3

1. Given that \(k\) is a constant, display the following linear programming problem in a Simplex tableau. $$\begin{array} { l l } \text { Maximise } & P = 6 x + 5 y + 3 z \\ \text { subject to } & x + 2 y + k z \leqslant 8 \\ & 2 x + 10 y + z \leqslant 17 \\ & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
2. 1. Use the Simplex method to perform one iteration of your tableau for part (a), choosing a value in the \(x\)-column as pivot.
   2. Given that the maximum value of \(P\) has not been achieved after this first iteration, find the range of possible values of \(k\).
3. In the case where \(k = - 1\), perform one further iteration and interpret your final tableau.
   
   \includegraphics[max width=\textwidth, alt={}]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-07_2484_1707_223_155}

4 A linear programming problem involving variables \(x , y\) and \(z\) is to be solved. The objective function to be maximised is \(P = 2 x + 6 y + k z\), where \(k\) is a constant. The initial Simplex tableau is given below.

1. In addition to \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\), write down three inequalities involving \(x , y\) and \(z\) for this problem.
2. 1. By choosing the first pivot from the \(\boldsymbol { y }\)-column, perform one iteration of the Simplex method.
   2. Given that the optimal value has not been reached, find the possible values of \(k\).
3. In the case when \(k = 20\) :
   1. perform one further iteration;
   2. interpret the final tableau and state the values of the slack variables.

6

1. Display the following linear programming problem in a Simplex tableau.
   Maximise \(\quad P = 4 x + 3 y + z\) subject to $$\begin{aligned} & 2 x + y + z \leqslant 25 \\ & x + 2 y + z \leqslant 40 \\ & x + y + 2 z \leqslant 30 \end{aligned}$$ and \(x \geqslant 0 , \quad y \geqslant 0 , \quad z \geqslant 0\).
2. The first pivot to be chosen is from the \(x\)-column. Perform one iteration of the Simplex method.
3. 1. Perform one further iteration.
   2. Interpret your final tableau and state the values of your slack variables.

9. T42 Co. Ltd produces three different blends of tea, Morning, Afternoon and Evening. The teas must be processed, blended and then packed for distribution. The table below shows the time taken, in hours, for each stage of the production of a tonne of tea. It also shows the profit, in hundreds of pounds, on each tonne. The total times available each week for processing, blending and packing are 35, 20 and 24 hours respectively. T42 Co. Ltd wishes to maximise the weekly profit. Let \(x , y\) and \(z\) be the number of tonnes of Morning, Afternoon and Evening blend produced each week.

1. Formulate the above situation as a linear programming problem, listing clearly the objective function, and the constraints as inequalities.
   (4) An initial Simplex tableau for the above situation is

   Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	3	2	4	1	0	0	35
   \(s\)	1	3	2	0	1	0	20
   \(t\)	2	4	3	0	0	1	24
   \(P\)	- 4	- 5	- 3	0	0	0	0

2. Solve this linear programming problem using the Simplex algorithm. Take the most negative number in the profit row to indicate the pivot column at each stage. T42 Co. Ltd wishes to increase its profit further and is prepared to increase the time available for processing or blending or packing or any two of these three.
3. Use your answer to part (b) to advise the company as to which stage(s) it should increase the time available.

10. While solving a maximizing linear programming problem, the following tableau was obtained.

1. Explain why this is an optimal tableau.
2. Write down the optimal solution of this problem, stating the value of every variable.
3. Write down the profit equation from the tableau. Use it to explain why changing the value of any of the non-basic variables will decrease the value of \(P\).