5 A student is solving the following linear programming problem.
$$\begin{array} { l r }
\text { Minimise } & Q = - 4 x - 3 y
\text { subject to } & x + y \leq 520
& 2 x - 3 y \leq 570
\text { and } & x \geq 0 , y \geq 0
\end{array}$$
5
- The student wants to use the simplex algorithm to solve the linear programming problem.
They modify the linear programming problem by introducing the objective function
$$P = 4 x + 3 y$$
and the slack variables \(r\) and \(s\)
State one further modification that must be made to the linear programming problem so that it can be solved using the simplex algorithm.
5
- Complete the initial simplex tableau for the modified linear programming problem.
[0pt]
[2 marks]
| \(P\) | \(x\) | \(y\) | \(r\) | \(S\) | value |
| | | | | |
| | | | | |
| | | | | |
- (ii) Hence, perform one iteration of the simplex algorithm.
| \(P\) | \(x\) | \(y\) | \(r\) | \(s\) | value |
| | | | | |
| | | | | |
| | | | | |
- The student performs one further iteration of the simplex algorithm, which results in the following correct simplex tableau.
| \(P\) | \(x\) | \(y\) | \(r\) | \(s\) | value |
| 1 | 0 | 0 | \(\frac { 18 } { 5 }\) | \(\frac { 1 } { 5 }\) | 1986 |
| 0 | 0 | 1 | \(\frac { 2 } { 5 }\) | \(- \frac { 1 } { 5 }\) | 94 |
| 0 | 1 | 0 | \(\frac { 3 } { 5 }\) | \(\frac { 1 } { 5 }\) | 426 |
- Explain how the student can tell that the optimal solution to the modified linear programming problem can be determined from the above simplex tableau.
5
- (ii) Find the optimal solution of the original linear programming problem.