Complete Simplex solution

3
Maximise \(\quad P = 2 x - 3 y + 4 z\) subject to \(\quad x + 2 y + z \leqslant 20\) \(x - y + 3 z \leqslant 24\) \(3 x - 2 y + 2 z \leqslant 30\) and \(\quad x \geqslant 0 , y \geqslant 0 , z \geqslant 0\).

1. Display the linear programming problem in a Simplex tableau.
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. Perform one further iteration.
3. Interpret your final tableau and state the values of your slack variables.
   [0pt] [3 marks]

5. A linear programming problem in \(x , y\) and \(z\) is described as follows. Maximise \(P = 2 x + 3 y + z\) subject to \(\quad 2 y - 3 z \leqslant 30\) $$\begin{array} { r } - 3 x + y + z \leqslant 60 \\ x + 4 y - z \leqslant 80 \end{array}$$

1. Complete the initial tableau in the answer book for this linear programming problem.
   (3)
2. 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)
3. Write down the profit equation given by T and state the values of the slack variables given by T . The following tableau is obtained after further iterations.

   Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	0	2	-3	1	0	0	30
   \(s\)	0	13	-2	0	1	3	300
   \(x\)	1	4	-1	0	0	1	80
   \(P\)	0	5	-3	0	0	2	160

4. Explain why no optimal solution can be found by applying the simplex algorithm to the above tableau.

Kassi and Theo are discussing how much oil and how much vinegar to use to dress their salad. They agree to use between 5 and 10ml of oil and between 3 and 6ml of vinegar and that the amount of oil should not exceed twice the amount of vinegar. Theo prefers to have more oil than vinegar. He formulates the following problem to maximise the proportion of oil: Maximise \(\frac{x}{x + y}\) subject to \(0 \leq x \leq 10\), \(0 \leq y \leq 6\), \(x - 2y \leq 0\).

1. Explain why this problem is not an LP. [1]
2. Use the simplex method to solve the following LP. Maximise \(x - y\) subject to \(0 \leq x \leq 10\), \(0 \leq y \leq 6\), \(x - 2y \leq 0\). [7]
3. Kassi prefers to have more vinegar than oil. She formulates the following LP. Maximise \(y - x\) subject to \(5 \leq x \leq 10\), \(3 \leq y \leq 6\), \(x - 2y \leq 0\). Draw separate graphs to show the feasible regions for this problem and for the problem in part (ii). [5]
4. Explain why the formulation in part (ii) produced a solution for Theo's problem, and why it is more difficult to use the simplex method to solve Kassi's problem in part (iii). [2]
5. Produce an initial tableau for using the two-stage simplex method to solve Kassi's problem. Explain briefly how to proceed. [5]

A linear programming problem is \begin{align} \text{Maximise } P &= 4x - y - 2z
\text{subject to } x + 5y + 3z &\leq 60
2x - 5y &\leq 80
2y + z &\leq 10
x \geq 0, y &\geq 0, z \geq 0 \end{align}

1. Use the simplex algorithm to solve the problem. [7]

In the case when \(z = 0\) the feasible region can be represented graphically. \includegraphics{figure_1} The vertices of the feasible region are \((0, 0)\), \((40, 0)\), \((46.67, 2.67)\), \((35, 5)\) and \((0, 5)\), where non-integer values are given to 2 decimal places. The linear programming problem is given the additional constraint that \(x\) and \(y\) are integers.

1. Use branch-and-bound, branching on \(x\) first, to show that the optimum solution with this additional constraint is \(x = 45, y = 2\). [7]