6 Consider the following linear programming problem.
| Maximise | \(P = 5 x + 8 y\), |
| |
| subject to | \(3 x - 2 y \leqslant 12\), |
| \(3 x + 4 y \leqslant 30\), |
| \(3 x - 8 y \geqslant - 24\), |
| \(x \geqslant 0 , y \geqslant 0\). |
- Represent the constraints graphically. Shade the regions where the inequalities are not satisfied and hence identify the feasible region.
- 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.
- 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\). |
- Explain why Tom needed to change the third constraint.
- Represent the problem by an initial Simplex tableau.
- 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.