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}$$

(i) 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$ ?\\
(ii) Represent the problem as an initial Simplex tableau.\\
(iii) Show why the pivot for the first iteration of the Simplex algorithm must be the coefficient of $z$ in the third constraint.\\
(iv) 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.\\
(v) Perform a second iteration of the Simplex algorithm and record the values of $x , y , z$ and $P$ at the end of this iteration.\\
(vi) Write down the values of $s , t$ and $u$ from your final tableau and explain what they mean in terms of the original constraints.

\hfill \mbox{\textit{OCR D1 2012 Q4 [14]}}