Simplex tableau interpretation

4 The "Cuddly Friends Company" produces soft toys. For one day's production run it has available \(11 \mathrm {~m} ^ { 2 }\) of furry material, \(24 \mathrm {~m} ^ { 2 }\) of woolly material and 30 glass eyes. It has three soft toys which it can produce: The "Cuddly Aardvark", each of which requires \(0.5 \mathrm {~m} ^ { 2 }\) of furry material, \(2 \mathrm {~m} ^ { 2 }\) of woolly material and two eyes. Each sells at a profit of \(\pounds 3\). The "Cuddly Bear", each of which requires \(1 \mathrm {~m} ^ { 2 }\) of furry material, \(1.5 \mathrm {~m} ^ { 2 }\) of woolly material and two eyes. Each sells at a profit of \(\pounds 5\). The "Cuddly Cat", each of which requires \(1 \mathrm {~m} ^ { 2 }\) of furry material, \(1 \mathrm {~m} ^ { 2 }\) of woolly material and two eyes. Each sells at a profit of \(\pounds 2\). An analyst formulates the following LP to find the production plan which maximises profit. $$\begin{array} { l l } \text { Maximise } & 3 a + 5 b + 2 c \\ \text { subject to } & 0.5 a + b + c \leqslant 11 , \\ & 2 a + 1.5 b + c \leqslant 24 , \\ & 2 a + 2 b + 2 c \leqslant 30 . \end{array}$$

1. Explain how this formulation models the problem, and say why the analyst has not simplified the last inequality to \(a + b + c \leqslant 15\).
2. The final constraint is different from the others in that the resource is integer valued. Explain why that does not impose an additional difficulty for this problem.
3. Solve this problem using the simplex algorithm. Interpret your solution and say what resources are left over. On a particular day an order is received for two Cuddly Cats, and the extra constraint \(c \geqslant 2\) is added to the formulation.
4. Set up an initial simplex tableau to deal with the modified problem using either the big-M approach or two-phase simplex. Do not perform any iterations on your tableau.
5. Show that the solution given by \(a = 8 , b = 2\) and \(c = 5\) uses all of the resources, but that \(a = 6 , b = 6\) and \(c = 2\) gives more profit. What resources are left over from the latter solution?

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.

1. State the column that contains the pivot value for the 1st iteration. You must give a reason for your answer.
2. 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.
3. 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. 1. Explain, using T, how you know that an optimal solution to the original linear programming problem has not been found after the 2nd iteration.
   2. State the values of the basic variables after the 2nd iteration. A student attempts the 3rd iteration of the Simplex algorithm and obtains the tableau below.

      b.v.	\(x\)	\(y\)	\(z\)	\(s _ { 1 }\)	\(S _ { 2 }\)	\(\mathrm { S } _ { 3 }\)	Value
      z	0	0	1	\(\frac { 1 } { 2 }\)	\(- \frac { 1 } { 4 }\)	\(\frac { 1 } { 4 }\)	\(\frac { 43 } { 2 }\)
      \(x\)	1	0	0	\(\frac { 1 } { 4 }\)	\(\frac { 1 } { 8 }\)	\(- \frac { 1 } { 8 }\)	\(\frac { 57 } { 4 }\)
      \(y\)	0	1	0	\(- \frac { 1 } { 2 }\)	\(\frac { 1 } { 4 }\)	\(\frac { 3 } { 4 }\)	\(\frac { 9 } { 2 }\)
      \(P\)	0	1	0	\(\frac { 5 } { 4 }\)	\(\frac { 1 } { 8 }\)	\(\frac { 7 } { 8 }\)	\(\frac { 361 } { 4 }\)

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

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

1. Using the information in the tableau, write down
   1. the objective function,
   2. the three constraints as inequalities.
2. 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.
3. State the final values of the objective function and each variable.

A garden centre sells tulip bulbs in mixed packs. The cost of each pack and the number of tulips of each colour are given in the table. Dirk is designing a floral display in which he will need the number of red tulips to be at most 50 more than the number of white tulips, and the number of white tulips to be less than or equal to twice the number of pink tulips. He has a budget of £240 and wants to find out which packs to buy to maximise the total number of bulbs. Dirk uses the variables \(x\), \(y\) and \(z\) to represent, respectively, how many of pack A, pack B and pack C he buys. He sets up his problem as an initial simplex tableau, which is shown below.

1. Show how the constraint on the number of red tulips leads to one of the rows of the tableau. [3]

The tableau that results after the first iteration is shown below.

1. Which cell was used as the pivot? [1]
2. Explain why row 2 and row 6 are the same. [1]
3. 1. Read off the values of \(x\), \(y\) and \(z\) after the first iteration. [1]
   2. Interpret this solution in terms of the original problem. [2]
4. Identify the variable that has become non-basic. Use the pivot row of the initial tableau to eliminate \(x\) algebraically from the equation represented by Row 1 of the initial tableau. [3]

The feasible region can be represented graphically in three dimensions, with the variables \(x\), \(y\) and \(z\) corresponding to the \(x\)-axis, \(y\)-axis and \(z\)-axis respectively. The boundaries of the feasible region are planes. Pairs of these planes intersect in lines and at the vertices of the feasible region these lines intersect.

1. The planes defined by each of the new basic variables being set equal to 0 intersect at a point. Show how the equations from part (v) are used to find the values \(P\) and \(x\) at this point. [2]