Linear Programming

3 Solve the following LP problem graphically.
Maximise \(2 x + 3 y\) subject to \(\quad x + y \leqslant 11\) $$\begin{aligned} 3 x + 5 y & \leqslant 39 \\ x + 6 y & \leqslant 39 . \end{aligned}$$

3 A student is solving a maximising linear programming problem. The graph below shows the constraints, feasible region and objective line for the student's linear programming problem. \includegraphics[max width=\textwidth, alt={}, center]{5ff6e3bb-6392-49cf-b64d-23bc595cd92e-03_1248_1184_502_427} Which vertex is the optimal vertex? Circle your answer. \(A\) B
C
D

8 A sweet shop sells three different types of boxes of chocolate truffles. The cost of each type of box and the number of truffles of each variety in each type of box are given in the table below. Narendra wants to buy some boxes of truffles so that in total he has at least 20 milk chocolate, 10 plain chocolate, 16 white chocolate and 12 nutty chocolate truffles.

1. Explain why Narendra needs to buy at least four boxes of truffles.
2. Narendra decides that he will buy exactly four boxes. Determine the minimum number of Assorted boxes that Narendra must buy.
3. For your answer in part (ii),
   Narendra finds that the sweet shop has sold out of Assorted boxes, but he then spots that it also sells small boxes of milk chocolate truffles and small boxes of nutty chocolate truffles. Each small box contains 4 truffles (all of one variety) and costs \(\pounds 0.50\). He decides to buy \(x\) boxes of No Nuts and \(y\) boxes of Speciality, where \(x + y < 4\), so that he has at least 10 plain chocolate and 16 white chocolate truffles. He will then buy as many small boxes as he needs to give a total of at least 20 milk chocolate and 12 nutty chocolate truffles.
4. (a) Set up constraints on the values of \(x\) and \(y\).
   (b) Represent the feasible region graphically.
   (c) Hence determine the cheapest cost for Narendra. www.ocr.org.uk after the live examination series. If OCR has unwittingly failed to correctly acknowledge or clear any third-party content in this assessment material, OCR will be happy to correct its mistake at the earliest possible opportunity. For queries or further information please contact the Copyright Team, First Floor, 9 Hills Road, Cambridge CB2 1GE.
   OCR is part of the

8 Alli is planting garlic cloves and leek seedlings in a garden. The planting density is the number of plants that are planted per \(\mathrm { m } ^ { 2 }\) The planting densities and costs are shown in the table below.

1 Hussain wants to travel by train from Edinburgh to Southampton, leaving Edinburgh after 9 am and arriving in Southampton by 4 pm . He wants to leave Edinburgh as late as possible.
Hussain rings the train company to find out about the train times. Write down a question he might ask that leads to
(A) an existence problem,
(B) an optimisation problem.

9 A factory can make three different kinds of balloon pack: gold, silver and bronze. Each pack contains three different types of balloon: \(A , B\) and \(C\). Each gold pack has 2 type \(A\) balloons, 3 type \(B\) balloons and 6 type \(C\) balloons.
Each silver pack has 3 type \(A\) balloons, 4 type \(B\) balloons and 2 type \(C\) balloons.
Each bronze pack has 5 type \(A\) balloons, 3 type \(B\) balloons and 2 type \(C\) balloons.
Every hour, the maximum number of each type of balloon available is 400 type \(A\), 400 type \(B\) and 400 type \(C\). Every hour, the factory must pack at least 1000 balloons.
Every hour, the factory must pack more type \(A\) balloons than type \(B\) balloons.
Every hour, the factory must ensure that no more than \(40 \%\) of the total balloons packed are type \(C\) balloons. Every hour, the factory makes \(x\) gold, \(y\) silver and \(z\) bronze packs.
Formulate the above situation as 6 inequalities, in addition to \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\), simplifying your answers.
(8 marks)

4. A linear programming problem in \(x , y\) and \(z\) is described as follows. Maximise \(\quad P = - x + y\) subject to $$\begin{gathered} x + 2 y + z \leqslant 15 \\ 3 x - 4 y + 2 z \geqslant 1 \\ 2 x + y + z = 14 \\ x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{gathered}$$

1. 1. Eliminate \(z\) from the first two inequality constraints, simplifying your answers.
   2. Hence state the maximum possible value of \(P\) Given that \(P\) takes the maximum possible value found in (a)(ii),
2. 1. determine the maximum possible value of \(x\)
   2. Hence find a solution to the linear programming problem.

4 [Figure 2, printed on the insert, is provided for use in this question.]
Each year, farmer Giles buys some goats, pigs and sheep.
He must buy at least 110 animals.
He must buy at least as many pigs as goats.
The total of the number of pigs and the number of sheep that he buys must not be greater than 150 .
Each goat costs \(\pounds 16\), each pig costs \(\pounds 8\) and each sheep costs \(\pounds 24\).
He has \(\pounds 3120\) to spend on the animals.
At the end of the year, Giles sells all of the animals. He makes a profit of \(\pounds 70\) on each goat, \(\pounds 30\) on each pig and \(\pounds 50\) on each sheep. Giles wishes to maximize his total profit, \(\pounds P\). Each year, Giles buys \(x\) goats, \(y\) pigs and \(z\) sheep.

1. Formulate Giles's situation as a linear programming problem.
2. One year, Giles buys 30 sheep.
   1. Show that the constraints for Giles's situation for this year can be modelled by $$y \geqslant x , \quad 2 x + y \leqslant 300 , \quad x + y \geqslant 80 , \quad y \leqslant 120$$ (2 marks)
   2. On Figure 2, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region and the direction of the objective line.
      (8 marks)
   3. Find Giles's maximum profit for this year and the number of each animal that he must buy to obtain this maximum profit.
      (3 marks)

8. A headteacher is deciding how to allocate prizes to the students who are leaving at the end of the school year. There are three categories of prize: academic, sport, and leadership.

• Each academic prize costs \(\pounds 14\), each sport prize costs \(\pounds 8\), and each leadership prize costs \(\pounds 12\). The total amount available to spend on all prizes is \(\pounds 976\)
• For every 5 academic prizes there must be at least 2 leadership prizes
• At least half the prizes must be academic
• \(20 \%\) of the prizes must be for sport

The headteacher wishes to maximise the total number of prizes.
Let \(x , y\) and \(z\) represent the number of academic, sport and leadership prizes respectively.

1. Formulate this as a linear programming problem in \(x\) and \(y\) only, stating the objective and listing the constraints as simplified inequalities with integer coefficients. Given that the headteacher awards 16 sport prizes,
2. calculate the corresponding number of leadership prizes that the headteacher awards. You must show your working.

A linear programming problem is set up to maximise \(P = ax + y\) where \(a\) is a constant. \(P\) is maximised subject to three linear constraints which form the triangular feasible region shown in the diagram below. \includegraphics{figure_8} The vertices of the triangle are \((1, 6)\), \((5, 11)\) and \((13, 9)\) \(P\) is maximised at \((5, 11)\) Find the range of possible values for \(P\) [5 marks]

The constraints of a linear programming problem are represented by the graph below. The feasible region is the unshaded region, including its boundaries. \includegraphics{figure_3}

1. Write down the inequalities that define the feasible region. [4]
2. Write down the coordinates of the three vertices of the feasible region. [2]

The objective is to maximise \(2x + 3y\).

1. Find the values of \(x\) and \(y\) at the optimal point, and the corresponding maximum value of \(2x + 3y\). [3]

The objective is changed to maximise \(2x + ky\), where \(k\) is positive.

1. Find the range of values of \(k\) for which the optimal point is the same as in part (iii). [2]

7 A linear programming problem is
Maximise \(P = 4 x + y\) subject to $$\begin{aligned} 3 x - y & \leqslant 30 \\ x + y & \leqslant 15 \\ x - 3 y & \leqslant 6 \end{aligned}$$ and \(x \geqslant 0 , y \geqslant 0\)

1. Use a graphical method to find the optimal value of \(P\), and the corresponding values of \(x\) and \(y\). An additional constraint is introduced.
   This constraint means that the value of \(y\) must be at least \(k\) times the value of \(x\), where \(k\) is a positive constant.
2. 1. Determine the set of values of \(k\) for which the optimal value of \(P\) found in part (a) is unchanged.
   2. Determine, in terms of \(k\), the values of \(x , y\) and \(P\) in the cases when the optimal solution is different from that found in part (a).

6 [Figure 1, printed on the insert, is provided for use in this question.]
Dino is to have a rectangular swimming pool at his villa.
He wants its width to be at least 2 metres and its length to be at least 5 metres.
He wants its length to be at least twice its width.
He wants its length to be no more than three times its width.
Each metre of the width of the pool costs \(\pounds 1000\) and each metre of the length of the pool costs \(\pounds 500\). He has \(\pounds 9000\) available. Let the width of the pool be \(x\) metres and the length of the pool be \(y\) metres.

1. Show that one of the constraints leads to the inequality $$2 x + y \leqslant 18$$
2. Find four further inequalities.
3. On Figure 1, draw a suitable diagram to show the feasible region.
4. Use your diagram to find the maximum width of the pool. State the corresponding length of the pool.

2 A landscape gardener is designing a garden. Part of the garden will be decking, part will be flowers and the rest will be grass. Let d be the area of decking, f be the area of flowers and g be the area of grass, all measured in \(\mathrm { m } ^ { 2 }\). The total area of the garden is \(120 \mathrm {~m} ^ { 2 }\) of which at least \(40 \mathrm {~m} ^ { 2 }\) must be grass. The area of decking must not be greater than the area of flowers. Also, the area of grass must not be more than four times the area of decking. Each square metre of grass will cost \(\pounds 5\), each square metre of decking will cost \(\pounds 10\) and each square metre of flowers will cost \(\pounds 20\). These costs include labour. The landscape gardener has been instructed to come up with the design that will cost the least.

1. Write down a constraint in d , f and g from the total area of the garden.
2. Explain why the constraint \(\mathrm { g } \leqslant 4 \mathrm {~d}\) is required.
3. Write down a constraint from the requirement that the area of decking must not be greater than the area of flowers.
4. Write down a constraint from the requirement that at least \(40 \mathrm {~m} ^ { 2 }\) of the garden must be grass and write down the minimum feasible values for each of \(d\) and \(f\).
5. Write down the objective function to be minimised.
6. Write down the resulting LP problem, using slack variables to express the constraints from parts (ii) and (iii) as equations.
   (You are not required to solve the resulting LP problem.)

3 Neil is refurbishing a listed building. There are two types of paint that he can use for the inside walls. One costs \(\pounds 1.45\) per \(\mathrm { m } ^ { 2 }\) and the other costs \(\pounds 0.95\) per \(\mathrm { m } ^ { 2 }\). He must paint the lower half of each wall in the more expensive paint. He has \(350 \mathrm {~m} ^ { 2 }\) of wall to paint. He has a budget of \(\pounds 400\) for wall paint. The more expensive paint is easier to use, and so Neil wants to use as much of it as possible. Initially, the following LP is constructed to help Neil with his purchasing of paint.
Let \(x\) be the number of \(\mathrm { m } ^ { 2 }\) of wall painted with the expensive paint.
Let \(y\) be the number of \(\mathrm { m } ^ { 2 }\) of wall painted with the less expensive paint. $$\begin{array} { l l } \text { Maximise } & P = x + y \\ \text { subject to } & 1.45 x + 0.95 y \leqslant 400 \\ & y - x \leqslant 0 \\ & x \geqslant 0 \\ & y \geqslant 0 \end{array}$$

1. Explain the purpose of the inequality \(y - x \leqslant 0\).
2. The formulation does not include the inequality \(x + y \geqslant 350\). State what this constraint models and why it has been omitted from the formulation.
3. Use the simplex algorithm to solve the LP. Pivot first on the "1" in the \(y\) column. Interpret your solution. The solution shows that Neil needs to buy more paint. He negotiates an increase in his budget to \(\pounds 450\).
4. Find the solution to the LP given by changing \(1.45 x + 0.95 y \leqslant 400\) to \(1.45 x + 0.95 y \leqslant 450\), and interpret your solution. Neil realises that although he now has a solution, that solution is not the best for his requirements.
5. Explain why the revised solution is not optimal for Neil. In order to move to an optimal solution Neil needs to change the objective of the LP and add another constraint to it.
6. Write down the new LP and the initial tableau for using two-stage simplex to solve it. Give a brief description of how to use two-stage simplex to solve it. \includegraphics[max width=\textwidth, alt={}, center]{d254fbd2-7443-4b6d-87ba-f0d71fce5e17-5_497_558_269_751}
   1. Solve the route inspection problem in the network above, showing the methodology you used to ensure that your solution is optimal. Show your route.
   2. Floyd's algorithm is applied to the same network to find the complete network of shortest distances. After three iterations the distance and route matrices are as follows.

      \cline { 2 - 6 } \multicolumn{1}{c|}{}	\(\mathbf { 1 }\)	\(\mathbf { 2 }\)	\(\mathbf { 3 }\)	\(\mathbf { 4 }\)	\(\mathbf { 5 }\)
      \(\mathbf { 1 }\)	48	24	28	11	15
      \(\mathbf { 2 }\)	24	8	4	11	16
      \(\mathbf { 3 }\)	28	4	8	7	12

7. The payoff matrix for player \(A\) in a two-person zero-sum game is shown below.

2 In a game two players are each dealt five cards from a set of ten different cards.
Player 1 is dealt cards A, B, F, G and J.
Player 2 is dealt cards C, D, E, H and I. Each player chooses a card to play.
The players reveal their choices simultaneously. The pay-off matrix below shows the points scored by player 1 for each combination of cards. Pay-off for player 1 \begin{table}[h] \end{table}

1. Determine the play-safe strategy for player 1, ignoring any effect on player 2. The pay-off matrix below shows the points scored by player 2 for each combination of cards.
   Pay-off for player 2 Player 1 \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Player 2}

   		C	D	E	H
   \cline { 2 - 6 } A	2	2	0	1	I
   \cline { 2 - 6 } B	3	1	2	1	2
   \cline { 2 - 6 } F	3	2	2	1	0
   \cline { 2 - 6 } G	1	3	0	0	0
   \cline { 2 - 6 } J	2	1	0	3	1
   \cline { 2 - 6 }
   \cline { 2 - 6 }

   \end{table}
2. Use a dominance argument to delete two columns from the pay-off matrix. You must show all relevant comparisons.
3. Explain, with reference to specific combinations of cards, why the game cannot be converted to a zero-sum game.

7. A two-person zero-sum game is represented by the following pay-off matrix for player A. Formulate the game as a linear programming problem for player A. Write the constraints as inequalities. Define your variables clearly.
(Total 7 marks)

1. Jonathan makes two types of information pack for an event, Standard and Value.

Each Standard pack contains 25 posters and 500 flyers.
Each Value pack contains 15 posters and 800 flyers.
He must use at least 150000 flyers.
Between \(35 \%\) and \(65 \%\) of the packs must be Standard packs.
Posters cost 20p each and flyers cost 4p each.
Jonathan wishes to minimise his costs.
Let x and y represent the number of Standard packs and Value packs produced respectively.
Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. You should not attempt to solve the problem. \section*{(Total for Question 5 is 5 marks)} TOTAL IS 40 MARKS

The Young Enterprise Company "Decide", is going to produce badges to sell to decision maths students. It will produce two types of badges. Badge 1 reads "I made the decision to do maths" and Badge 2 reads "Maths is the right decision". "Decide" must produce at least 200 badges and has enough material for 500 badges. Market research suggests that the number produced of Badge 1 should be between 20% and 40% of the total number of badges made. The company makes a profit of 30p on each Badge 1 sold and 40p on each Badge 2. It will sell all that it produced, and wishes to maximise its profit. Let \(x\) be the number produced of Badge 1 and \(y\) be the number of Badge 2.

1. Formulate this situation as a linear programming problem, simplifying your inequalities so that all the coefficients are integers. [6]
2. On the grid provided in the answer book, construct and clearly label the feasible region. [5]
3. Using your graph, advise the company on the number of each badge it should produce. State the maximum profit "Decide" will make. [3]

3. Donald plans to bake and sell cakes. The three types of cake that he can bake are brownies, flapjacks and muffins. Donald decides to bake 48 brownies and muffins in total.
Donald decides to bake at least 5 brownies for every 3 flapjacks.
At most \(40 \%\) of the cakes will be muffins.
Donald has enough ingredients to bake 60 brownies or 45 flapjacks or 35 muffins.
Donald plans to sell each brownie for \(\pounds 1.50\), each flapjack for \(\pounds 1\) and each muffin for \(\pounds 1.25\) He wants to maximise the total income from selling the cakes. Let \(x\) represent the number of brownies, let \(y\) represent the number of flapjacks and let \(z\) represent the number of muffins that Donald will bake. Formulate this as a linear programming problem in \(x\) and \(y\) only, stating the objective function and listing the constraints as simplified inequalities with integer coefficients. You should not attempt to solve the problem.

4.
.
\section*{Question 4 continued} \section*{Grid 1}

3. Three depots, F, G and H, supply petrol to three service stations, S, T and U. The table gives the cost, in pounds, of transporting 1000 litres of petrol from each depot to each service station. F, G and H have stocks of 540000,789000 and 673000 litres respectively.
S, T and U require 257000,348000 and 412000 litres respectively. The total cost of transporting the petrol is to be minimised. Formulate this problem as a linear programming problem. Make clear your decision variables, objective function and constraints.

4 The diagram shows the feasible region of a linear programming problem. \includegraphics[max width=\textwidth, alt={}, center]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-04_1349_1395_408_294}

1. On the feasible region, find:
   1. the maximum value of \(2 x + 3 y\);
   2. the maximum value of \(3 x + 2 y\);
   3. the minimum value of \(- 2 x + y\).
2. Find the 5 inequalities that define the feasible region.

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.

0 \leqslant x & \leqslant 27

The tableau below is the initial tableau for a maximising linear programming problem.

1. Write down the four equations represented in the initial tableau above. [4]
2. Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. State the row operations that you use. [9]
3. State the values of the objective function and each variable. [3]

5. The tableau below is the initial tableau for a three-variable linear programming problem in \(x , y\) and \(z\). The objective is to maximise the profit, \(P\).

1. Using the information in the tableau, write down
   1. the objective function,
   2. the three constraints as inequalities.
2. Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. Make your method clear by stating the row operations you use.
3. State the final values of the objective function and each variable.

4. \begin{figure}[h] \end{figure} Figure 3 shows the constraints of a linear programming problem in \(x\) and \(y\). The unshaded area, including its boundaries, forms the feasible region, \(R\). An objective line has been drawn and labelled on the graph.

1. State the inequalities that define the feasible region. The maximum value of the objective function is \(\frac { 160 } { 3 }\) The minimum value of the objective function is \(\frac { 883 } { 41 }\)
2. Determine the objective function, showing your working clearly.

3 Consider the following linear programming problem:
Maximise \(\quad 3 x + 4 y\) subject to \(\quad 2 x + 5 y \leqslant 60\) \(x + 2 y \leqslant 25\) \(x + y \leqslant 18\)

1. Graph the inequalities and hence solve the LP.
2. The right-hand side of the second inequality is increased from 25 . At what new value will this inequality become redundant?

3. \begin{figure}[h] \end{figure} Figure 3 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region. The equations of two of the lines have been given.

1. Determine the inequalities that define the feasible region.
2. Find the exact coordinates of the vertices of the feasible region. The objective is to maximise \(P\), where \(P = k x + y\).
3. For the case \(k = 2\), use point testing to find the optimal vertex of the feasible region.
4. For the case \(k = 2.5\), find the set of points for which \(P\) takes its maximum value.

7. \begin{figure}[h] \end{figure} Figure 5 shows the constraints of a linear programming problem in \(x\) and \(y\) where \(R\) is the feasible region. The objective is to maximise \(P = x + k y\), where \(k\) is a positive constant.
The optimal vertex of \(R\) is to be found using the Simplex algorithm.

1. Set up an initial tableau for solving this linear programming problem using the Simplex algorithm. After two iterations of the Simplex algorithm a possible tableau \(T\) is

   b.v.	\(x\)	\(y\)	\(S _ { 1 }\)	\(s _ { 2 }\)	\(S _ { 3 }\)	\(s _ { 4 }\)	Value
   \(s _ { 1 }\)	0	0	1	\(- \frac { 3 } { 5 }\)	0	\(\frac { 1 } { 5 }\)	1
   \(x\)	1	0	0	\(\frac { 1 } { 5 }\)	0	\(- \frac { 2 } { 5 }\)	2
   \(S _ { 3 }\)	0	0	0	\(- \frac { 11 } { 5 }\)	1	\(\frac { 12 } { 5 }\)	22
   \(y\)	0	1	0	\(\frac { 2 } { 5 }\)	0	\(\frac { 1 } { 5 }\)	5
   \(P\)	0	0	0	\(\frac { 1 } { 5 } + \frac { 2 } { 5 } k\)	0	\(- \frac { 2 } { 5 } + \frac { 1 } { 5 } k\)	\(5 k + 2\)

2. State the value of each variable after the second iteration.
   (1) It is given that \(T\) does not give an optimal solution to the linear programming problem.
   After a third iteration of the Simplex algorithm the resulting tableau does give an optimal solution to the problem.
3. Perform the third iteration of the Simplex algorithm and hence determine the range of possible values for \(P\). You should state the row operations you use and make your method and working clear.
   (9)