Integer solution optimization

3 The constraints of a linear programming problem are represented by the graph below. The feasible region is the unshaded region, including its boundaries. \includegraphics[max width=\textwidth, alt={}, center]{ccb12789-cd5f-40dc-9f10-f8bb45399580-4_919_917_322_575}

1. Obtain the four inequalities that define the feasible region.
2. Calculate the coordinates of the vertices of the feasible region, giving your values as fractions. The objective is to maximise \(P = x + 4 y\).
3. Calculate the value of \(P\) at each vertex of the feasible region. Hence write down the coordinates of the optimal point, and the corresponding value of \(P\). Suppose that the solution must have integer values for both \(x\) and \(y\).
4. Find the coordinates of the optimal point with integer-valued \(x\) and \(y\), and the corresponding value of \(P\). Explain how you know that this is the optimal solution.

6 Consider the following linear programming problem.

1. Represent the constraints graphically. Shade the regions where the inequalities are not satisfied and hence identify the feasible region.
2. 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.
3. 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\).

4. Explain why Tom needed to change the third constraint.
5. Represent the problem by an initial Simplex tableau.
6. 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.

5. A linear programming problem in \(x\) and \(y\) is described as follows. Maximise \(\quad P = 2 x + 3 y\) subject to $$\begin{aligned} x & \geqslant 25 \\ y & \geqslant 25 \\ 7 x + 8 y & \leqslant 840 \\ 4 y & \leqslant 5 x \\ 5 y & \geqslant 3 x \\ x , y & \geqslant 0 \end{aligned}$$

1. Add lines and shading to Diagram 1 in the answer book to represent these constraints. Hence determine the feasible region and label it R .
2. Use the objective line method to find the optimal vertex, V, of the feasible region. You must clearly draw and label your objective line and the vertex V.
3. Calculate the exact coordinates of vertex V. Given that an integer solution is required,
4. determine the optimal solution with integer coordinates. You must make your method clear.

A linear programming problem in \(x\) and \(y\) is described as follows. Maximise P = \(5x + 3y\) subject to: \(x \geqslant 3\) $$x + y \leqslant 9$$ $$15x + 22y \leqslant 165$$ $$26x - 50y \leqslant 325$$

1. Add lines and shading to Diagram 2 in the answer book to represent these constraints. Hence determine the feasible region and label it R. \hfill [4]
2. Use the objective line method to find the optimal vertex, V, of the feasible region. You must draw and label your objective line and label vertex V clearly. \hfill [2]
3. Calculate the exact coordinates of vertex V and hence calculate the corresponding value of P at V. \hfill [3]

The objective is now to minimise \(5x + 3y\), where \(x\) and \(y\) are integers.

1. Write down the minimum value of \(5x + 3y\) and the corresponding value of \(x\) and corresponding value of \(y\). \hfill [2]