Graphical optimization with objective line

5 The feasible region of a linear programming problem is defined by $$\begin{aligned} x + y & \leqslant 60 \\ 2 x + y & \leqslant 80 \\ y & \geqslant 20 \\ x & \geqslant 15 \\ y & \geqslant x \end{aligned}$$

1. On the grid opposite, draw a suitable diagram to represent these inequalities and indicate the feasible region.
2. In each of the following cases, use your diagram to find the maximum value of \(P\) on the feasible region. In each case, state the corresponding values of \(x\) and \(y\).
   1. \(P = x + 4 y\)
   2. \(P = 4 x + y\)

7 A builder needs some screws, nails and plugs. At the local store, there are packs containing a mixture of the three items. A DIY pack contains 200 nails, 200 screws and 100 plugs.
A trade pack contains 1000 nails, 1500 screws and 2500 plugs.
A DIY pack costs \(\pounds 2.50\) and a trade pack costs \(\pounds 15\).
The builder needs at least 5000 nails, 6000 screws and 4000 plugs.
The builder buys \(x\) DIY packs and \(y\) trade packs and wishes to keep his total cost to a minimum.

1. Formulate the builder's situation as a linear programming problem.
2. 1. On the grid opposite, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region and the direction of an objective line.
   2. Use your diagram to find the number of each type of pack that the builder should buy in order to minimise his cost.
   3. Find the builder's minimum cost.

6 A recipe for jam states that the weight of sugar used must be between the weight of fruit used and four thirds of the weight of fruit used. Georgia has 10 kg of fruit available and 11 kg of sugar.

1. Define two variables and formulate inequalities in those variables to model this information.
2. Draw a graph to represent your inequalities.
3. Find the vertices of your feasible region and identify the points which would represent the best mix of ingredients under each of the following circumstances.
   (A) There is to be as much jam as possible, given that the weight of jam produced is the sum of the weights of the fruit and the sugar.
   (B) There is to be as much jam as possible, given that it is to have the lowest possible proportion of sugar.
   (C) There is to be as much jam as possible, given that it is to have the highest possible proportion of sugar.
   (D) Fruit costs \(\pounds 1\) per kg, sugar costs 50 p per kg and the objective is to produce as much jam as possible within a budget of \(\pounds 15\).

2 Consider the following linear programming problem.
Maximise $$\mathrm { P } = 6 x + 7 y$$ subject to $$\begin{aligned} & 2 x + 3 y \leqslant 9 \\ & 3 x + 2 y \leqslant 12 \\ & x \geqslant 0 \\ & y \geqslant 0 \end{aligned}$$

1. Use a graphical approach to solve the problem.
2. Give the optimal values of \(x , y\) and P when \(x\) and \(y\) are integers.

4 An air charter company has the following rules for selling seats on a flight.

1. The total number of seats sold must not exceed 120.
2. There must be at least 100 seats sold, or the flight will be cancelled.
3. For every child seat sold there must be a seat sold for a supervising adult.
   1. Define two variables so that the three constraints can be formulated in terms of your variables. Formulate the three constraints in terms of your variables.
   2. Graph your three inequalities from part (i).
   The price for a child seat is \(\pounds 50\) and the price for an adult seat is \(\pounds 100\).
4. Find the maximum income available from the flight, and mark and label the corresponding point on your graph.
5. Find the minimum income available from a full plane, and mark and label the corresponding point on your graph.
6. Find the minimum income available from the flight, and mark and label the corresponding point on your graph.
7. At \(\pounds 100\) for an adult seat and \(\pounds 50\) for a child seat the company would prefer to sell 100 adult seats and no child seats rather than have a full plane with 60 adults and 60 children. What would be the minimum price for a child's seat for that not to be the case, given that the adult seat price remains at \(\pounds 100\) ?

6 A manufacturing company holds stocks of two liquid chemicals. The company needs to update its stock levels. The company has 2000 litres of chemical A and 4000 litres of chemical B currently in stock. Its storage facility allows for no more than a combined total of 12000 litres of the two chemicals. Chemical A is valued at \(\pounds 5\) per litre and chemical B is valued at \(\pounds 6\) per litre. The company intends to hold stocks of these two chemicals with a total value of at least \(\pounds 61000\). Let \(a\) be the increase in the stock level of A, in thousands of litres ( \(a\) can be negative).
Let \(b\) be the increase in the stock level of B , in thousands of litres ( \(b\) can be negative).

1. Explain why \(a \geqslant - 2\), and produce a similar inequality for \(b\).
2. Explain why the value constraint can be written as \(5 a + 6 b \geqslant 27\), and produce, in similar form, the storage constraint.
3. Illustrate all four inequalities graphically.
4. Find the policy which will give a stock value of exactly \(\pounds 61000\), and will use all 12000 litres of available storage space.
5. Interpret your solution in terms of stock levels, and verify that the new stock levels do satisfy both the value constraint and the storage constraint.

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}$$

6 Jean knits items for charity. Each month the charity provides her with 75 balls of wool.
She knits hats and scarves. Hats require 1.5 balls of wool each and scarves require 3 balls each. Jean has 100 hours available each month for knitting. Hats require 4 hours each to make, and scarves require 2.5 hours each. The charity sells the hats for \(\pounds 7\) each and the scarves for \(\pounds 10\) each, and wants to gain as much income as possible. Jean prefers to knit hats but the charity wants no more than 20 per month. She refuses to knit more than 20 scarves each month.

1. Define appropriate variables, construct inequality constraints, and draw a graph representing the feasible region for this decision problem.
2. Give the objective function and find the integer solution which will give Jean's maximum monthly income.
3. If the charity drops the price of hats in a sale to \(\pounds 4\) each, what would be an optimal number of hats and scarves for Jean to knit? Assuming that all hats and scarves are sold, by how much would the monthly income drop?

6 A company manufactures two types of potting compost, Flowerbase and Growmuch. The weekly amounts produced of each are constrained by the supplies of fibre and of nutrient mix. Each litre of Flowerbase requires 0.75 litres of fibre and 1 kg of nutrient mix. Each litre of Growmuch requires 0.5 litres of fibre and 2 kg of nutrient mix. There are 12000 litres of fibre supplied each week, and 25000 kg of nutrient mix. The profit on Flowerbase is 9 p per litre. The profit on Growmuch is 20 p per litre.

1. Formulate an LP to maximise the weekly profit subject to the constraints on fibre and nutrient mix.
2. Solve your LP using a graphical approach.
3. Consider each of the following separate circumstances.
   (A) There is a reduction in the weekly supply of fibre from 12000 litres to 10000 litres. What effect does this have on profit?
   (B) The price of fibre is increased. Will this affect the optimal production plan? Justify your answer.
   [0pt] (C) The supply of nutrient mix is increased to 30000 kg per week. What is the new profit? [1]

5 John is reviewing his lifestyle, and in particular his leisure commitments. He enjoys badminton and squash, but is not sure whether he should persist with one or both. Both cost money and both take time. Playing badminton costs \(\pounds 3\) per hour and playing squash costs \(\pounds 4\) per hour. John has \(\pounds 11\) per week to spend on these activities. John takes 0.5 hours to recover from every hour of badminton and 0.75 hours to recover from every hour of squash. He has 5 hours in total available per week to play and recover.

1. Define appropriate variables and formulate two inequalities to model John's constraints.
2. Draw a graph to represent your inequalities. Give the coordinates of the vertices of your feasible region.
3. John is not sure how to define an objective function for his problem, but he says that he likes squash "twice as much" as badminton. Letting every hour of badminton be worth one "satisfaction point" define an objective function for John's problem, taking into account his "twice as much" statement.
4. Solve the resulting LP problem.
5. Given that badminton and squash courts are charged by the hour, explain why the solution to the LP is not a feasible solution to John's practical problem. Give the best feasible solution.
6. If instead John had said that he liked badminton more than squash, what would have been his best feasible solution?

3 Use a graphical approach to solve the following LP. $$\begin{aligned} & \text { Maximise } \quad 2 x + 3 y \\ & \text { subject to } \quad x + 5 y \leqslant 14 \\ & \quad x + 2 y \leqslant 8 \\ & \quad 3 x + y \leqslant 21 \\ & \quad x \geqslant 0 \\ & y \geqslant 0 \end{aligned}$$ Section B (48 marks)

4 A wall 4 metres long and 3 metres high is to be tiled. Two sizes of tile are available, 10 cm by 10 cm and 30 cm by 30 cm .

1. If \(x\) is the number of boxes of ten small tiles used, and \(y\) is the number of large tiles used, explain why \(10 x + 9 y \geqslant 1200\). There are only 100 of the large tiles available.
   The tiler advises that the area tiled with the small tiles should not exceed the area tiled with the large tiles.
2. Express these two constraints in terms of \(x\) and \(y\). The smaller tiles cost 15 p each and the larger tiles cost \(\pounds 2\) each.
3. Given that the objective is to minimise the cost of tiling the wall, state the objective function. Use the graphical approach to solve the problem.
4. Give two other factors which would have to be taken into account in deciding how many of each tile to purchase.

4 In a factory, two types of motor are made. Each motor of type X takes 10 man hours to make and each motor of type Y takes 12 man hours to make. In each week there are 200 man hours available. To satisfy customer demand, at least 5 of each type of motor must be made each week.
Once a motor has been started it must be completed; no unfinished motors may be left in the factory at the end of each week. When completed, the motors are put into a container for shipping. The volume of the container is \(7 \mathrm {~m} ^ { 3 }\). A type X motor occupies a volume of \(0.5 \mathrm {~m} ^ { 3 }\) and a type Y motor occupies a volume of \(0.3 \mathrm {~m} ^ { 3 }\).

1. Define appropriate variables and from the above information derive four inequalities which must be satisfied by those variables.
2. Represent your inequalities on a graph and shade the infeasible region. The profit on each type X is \(\pounds 100\) and on each type Y is \(\pounds 70\).
3. The weekly profit is to be maximised. Write down the objective function and find the maximum profit.
4. Because of absenteeism, the manager decides to organise the work in the factory on the assumption that there will be only 180 man hours available each week. Find the number of motors of each type that should now be made in order to maximise the profit.

6 Ian the chef is to make vegetable stew and vegetable soup for distribution to a small chain of vegetarian restaurants. The recipes for both of these require carrots, beans and tomatoes. 10 litres of stew requires 1.5 kg of carrots, 1 kg of beans and 1.5 kg of tomatoes.
10 litres of soup requires 1 kg of carrots, 0.75 kg of beans and 1.5 kg of tomatoes. Ian has available 100 kg of carrots, 70 kg of beans and 110 kg of tomatoes.

1. Identify appropriate variables and write down three inequalities corresponding to the availabilities of carrots, beans and tomatoes.
2. Graph your inequalities and identify the region corresponding to feasible production plans. The profit on a litre of stew is \(\pounds 5\), and the profit on a litre of soup is \(\pounds 4\).
3. Find the most profitable production plan, showing your working. Give the maximum profit. Ian can buy in extra tomatoes at \(\pounds 2.50\) per kg .
4. What extra quantity of tomatoes should Ian buy? How much extra profit would be generated by the extra expenditure? \section*{END OF QUESTION PAPER} \section*{OCR}

3 Mary takes over a small café. She will sell two types of hot drink: tea and coffee.
A coffee filter costs her \(\pounds 0.10\), and makes one cup of coffee. A tea bag costs her \(\pounds 0.05\) and makes one cup of tea. She has a total weekly budget of \(\pounds 50\) to spend on coffee filters and tea bags. She anticipates selling at least 500 cups of hot drink per week. She estimates that between \(50 \%\) and \(75 \%\) of her sales of cups of hot drink will be for cups of coffee. Mary needs help to decide how many coffee filters and how many tea bags to buy per week.

1. Explain why the number of tea bags which she buys should be no more than the number of coffee filters, and why it should be no less than one third of the number of coffee filters.
2. Allocate appropriate variables, and draw a graph showing the feasible region for Mary's problem. Mary's partner suggests that she buys 375 coffee filters and 250 tea bags.
3. How does this suggestion relate to the estimated demand for coffee and tea?

6. The manager of a new leisure complex needs to maximise the Revenue \(( \pounds R )\) from providing the following two weekend programmes. The following restrictions apply to each weekend.
No more than 90 participants can be accommodated.
There must be at most 40 adults.
A maximum of 600 person-hours of windsurfing can be offered.
A maximum of 300 person-hours of sailing can be offered.

1. Formulate the above information as a linear programming problem, listing the constraints as inequalities and stating the objective function \(R\).
2. On graph paper, illustrate the constraints, indicating clearly the feasible region.
3. Solve the problem graphically, stating how many adults and how many children should be accepted each weekend and what the revenue will be. The manager is considering buying more windsurfing equipment at a cost of \(\pounds 2000\). This would increase windsurfing provision by \(10 \%\).
4. State, with a reason, whether such a purchase would be cost effective.

5 Greetings cards are sold in luxury, standard and economy packs.
The table shows the cost of each pack and number of cards of each kind in the pack. Alice needs 25 cards, of which at least 8 must be handmade cards, at least 8 must be cards with flowers and at least 4 must be cards with animals.

1. Explain why Alice will need to buy at least two packs of cards. Alice does not want to spend more than \(\pounds 12\) on the cards.
2. (a) List the combinations of packs that satisfy all Alice's requirements.
   (b) Which of these is the cheapest? Ben offers to buy any cards that Alice buys but does not need. He will pay 12 pence for each handmade card and 5 pence for any other card. Alice does not want her net expenditure (the amount she spends minus the amount that Ben pays her) on the cards to be more than \(\pounds 12\).
3. Show that Alice could now buy two luxury packs. Alice decides to buy exactly 2 packs, of which \(x\) are luxury packs, \(y\) are standard packs and the rest are economy packs.
4. Give an expression, in terms of \(x\) and \(y\) only, for the number of cards of each type that Alice buys. Alice wants to minimise her net expenditure.
5. Find, and simplify, an expression for Alice's minimum net expenditure in pence, in terms of \(x\) and \(y\). You may assume that Alice buys enough cards to satisfy her own requirements.
6. Find Alice's minimum net expenditure.

6 Beth wants to buy some tokens for use in a game.
Each token is either a silver token or a gold token.
Silver tokens and gold tokens have different points values in the game.
Silver tokens have a value of 1.5 points each.
Gold tokens have a value of 4 points each.
Beth already has 2 silver tokens and 1 gold token.
She also has \(\pounds 10\) that can be spent on buying more tokens.
Silver tokens can be bought for \(\pounds 2\) each.
Gold tokens can be bought for \(\pounds 6\) each.
After buying some tokens, Beth has \(x\) silver tokens and \(y\) gold tokens.
She now has a total of at least 5 tokens and no more than 8 tokens.

1. Set up an LP formulation in \(x\) and \(y\) for the problem of maximising the points value of tokens that she finishes with.
2. Use a graphical method to determine how many tokens of each type Beth should buy to maximise the points value of her tokens.

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

6. Jonathan is going to make hats to sell at a fete. He can make red hats and green hats. Jonathan can use linear programming to determine the number of each colour of hat that he should make. Let \(x\) be the number of red hats he makes and \(y\) be the number of green hats he makes.
One of the constraints is that there must be at least 30 hats.

1. Write down an inequality, in terms of \(x\) and \(y\), to model this constraint. Two further constraints are $$\begin{aligned} & 2 y + x \geqslant 40 \\ & 2 y - x \geqslant - 30 \end{aligned}$$
2. Write down two more constraints which apply.
3. Represent all these constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region R . The cost of making a green hat is three times the cost of making a red hat. Jonathan wishes to minimise the total cost.
4. Use the objective line (ruler) method to determine the number of red hats and number of green hats that Jonathan should make. You must clearly draw and label your objective line. Given that the minimum total cost of making the hats is \(\pounds 107.50\)
5. determine the cost of making one green hat and the cost of making one red hat. You must make your method clear.

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

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 draw and label your objective line and label vertex V clearly.
3. Calculate the exact coordinates of vertex V and hence calculate the corresponding value of P at V . The objective is now to minimise \(5 x + 3 y\), where \(x\) and \(y\) are integers.
4. Write down the minimum value of \(5 x + 3 y\) and the corresponding value of \(x\) and corresponding value of \(y\).

5. Michael and his team are making toys to give to children at a summer fair. They make two types of toy, a soft toy and a craft set. Let \(x\) be the number of soft toys they make and \(y\) be the number of craft sets they make.
Each soft toy costs \(\pounds 3\) to make and each craft set costs \(\pounds 5\) to make. Michael and his team have a budget of \(\pounds 1000\) to spend on making the toys for the summer fair.

1. Write down an inequality, in terms of \(x\) and \(y\), to model this constraint. Two further constraints are: $$\begin{gathered} y \leqslant 2 x \\ 4 y - x \geqslant 210 \end{gathered}$$
2. Add lines and shading to Diagram 1 in the answer book to represent all of these constraints. Hence determine the feasible region and label it R . Michael's objective is to make as many toys as possible.
3. State the objective function.
4. Determine the exact coordinates of each of the vertices of the feasible region, and hence use the vertex method to find the optimal number of soft toys and craft sets Michael and his team should make. You should make your method clear.

5. A school awards two types of prize, junior and senior. The school decides that it will award at least 25 junior prizes and at most 60 senior prizes.
Let \(x\) be the number of junior prizes that the school awards and let \(y\) be the number of senior prizes that the school awards.

1. Write down two inequalities to model these constraints.
   (2) Two further constraints are $$\begin{aligned} & 2 x + 5 y \geqslant 250 \\ & 5 x - 3 y \leqslant 150 \end{aligned}$$
2. Add lines and shading to Diagram 1 in the answer book to represent all four of these constraints. Hence determine the feasible region and label it \(R\). The cost of a senior prize is three times the cost of a junior prize. The school wishes to minimise the cost of the prizes.
3. State the objective function, giving your answer in terms of \(x\) and \(y\).
4. Determine the exact coordinates of the vertices of the feasible region. Hence use the vertex method to find the number of junior prizes and the number of senior prizes that the school should award. You should make your working clear.

7. \begin{figure}[h] \end{figure}

1. Phil sells boxed lunches to travellers at railway stations. Customers can select either the vegetarian box or the non-vegetarian box.

Phil decides to use graphical linear programming to help him optimise the numbers of each type of box he should produce each day. Each day Phil produces \(x\) vegetarian boxes and \(y\) non-vegetarian boxes.
One of the constraints limiting the number of boxes is $$x + y \geqslant 70$$ This, together with \(x \geqslant 0 , y \geqslant 0\) and a fourth constraint, has been represented in Figure 7. The rejected region has been shaded.

1. Write down the inequality represented by the fourth constraint. Two further constraints are: $$\begin{aligned} & x + 2 y \leqslant 160 \\ & \text { and } y > 60 \end{aligned}$$
2. Add two lines and shading to Diagram 4 in your answer book to represent these inequalities.
3. Hence determine and label the feasible region, R .
4. Use your graph to determine the minimum total number of boxes he needs to prepare each day. Make your method clear. Phil makes a profit of \(\pounds 1.20\) on each vegetarian box and \(\pounds 1.40\) on each non-vegetarian box. He wishes to maximise his profit.
5. Write down the objective function.
6. Use your graph to obtain the optimal number of vegetarian and non-vegetarian boxes he should produce each day. You must make your method clear.
7. Find Phil's maximum daily profit.

6. \begin{figure}[h] \end{figure} The graph in Figure 6 is being used to solve a linear programming problem. Two of the constraints have been drawn on the graph and the rejected regions shaded out.

1. Write down the constraints shown on the graph. Two further constraints are $$\begin{aligned} x + y & \geqslant 30 \\ \text { and } \quad 5 x + 8 y & \leqslant 400 \end{aligned}$$
2. Add two lines and shading to Graph 1 in your answer book to represent these constraints. Hence determine the feasible region and label it R . The objective is to $$\text { minimise } 15 x + 10 y$$
3. Draw a profit line on Graph 1 and use it to find the optimal solution. You must label your profit line clearly.
   (3)