Constraint derivation verification

2 A baker can make apple cakes, banana cakes and cherry cakes.
The baker has exactly enough flour to make either 30 apple cakes or 20 banana cakes or 40 cherry cakes. The baker has exactly enough sugar to make either 30 apple cakes or 40 banana cakes or 30 cherry cakes. The baker has enough apples for 20 apple cakes, enough bananas for 25 banana cakes and enough cherries for 10 cherry cakes. The baker has an order for 30 cakes. The profit on each apple cake is 4 p , on each banana cake is 3 p and on each cherry cake is 2 p . The baker wants to maximise the profit on the order.

1. The availability of flour leads to the constraint \(4 a + 6 b + 3 c \leqslant 120\). Give the meaning of each of the variables \(a , b\) and \(c\) in this constraint.
2. Use the availability of sugar to give a second constraint of the form \(X a + Y b + Z c \leqslant 120\), where \(X , Y\) and \(Z\) are numbers to be found.
3. Write down a constraint from the total order size. Write down constraints from the availability of apples, bananas and cherries.
4. Write down the objective function to be maximised.
   [0pt] [You are not required to solve the resulting LP problem.]

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.)

6 Sandie makes tanning lotions which she sells to beauty salons. She makes three different lotions using the same basic ingredients but in different proportions. These lotions are called amber, bronze and copper. To make one litre of tanning lotion she needs one litre of fluid. This can either be water or water mixed with hempseed oil. One litre of amber lotion uses one litre of water, one litre of bronze lotion uses 0.8 litres of water and one litre of copper lotion uses 0.5 litres of water. Any remainder is made up of hempseed oil. Sandie has 40 litres of water and 7 litres of hempseed oil available.

1. By defining appropriate variables \(a , b\) and \(c\), show that the constraint on the amount of water available can be written as \(10 a + 8 b + 5 c \leqslant 400\).
2. Find a similar constraint on the amount of hempseed oil available. The tanning lotions also use two colourants which give two further availability constraints. Sandie wants to maximise her profit, \(\pounds P\). The problem can be represented as a linear programming problem with the initial Simplex tableau below. In this tableau \(s , t , u\) and \(v\) are slack variables.

   \(P\)	\(a\)	\(b\)	\(c\)	\(s\)	\(t\)	\(u\)	\(v\)	RHS
   1	-8	-7	-4	0	0	0	0	0
   0	10	8	5	1	0	0	0	400
   0	0	2	5	0	1	0	0	70
   0	2	4	1	0	0	1	0	176
   0	5	1	3	0	0	0	1	80

3. Use the initial Simplex tableau to write down two inequalities to represent the availability constraints for the colourants.
4. Write down the profit that Sandie makes on each litre of amber lotion that she sells.
5. Carry out one iteration of the Simplex algorithm, choosing a pivot from the \(a\) column. Show the operations used to calculate each row. After a second iteration of the Simplex algorithm the tableau is as given below.

   \(P\)	\(a\)	\(b\)	\(c\)	\(s\)	\(t\)	\(u\)	\(v\)	RHS
   1	0	0	14.3	0	2.7	0	1.6	317
   0	0	0	-16	1	-3	0	-2	30
   0	0	1	2.5	0	0.5	0	0	35
   0	0	0	-9.2	0	-1.8	1	-0.4	18
   0	1	0	0.1	0	-0.1	0	0.2	9

6. Explain how you know that the optimal solution has been achieved.
7. How much of each lotion should Sandie make and what is her maximum profit? Why might the profit be less than this?
8. If none of the other availabilities change, what is the least amount of water that Sandie needs to make the amounts of lotion found in part (vii)?

6 William is making the bridesmaid dresses and pageboy outfits for his sister's wedding. He expects it to take 20 hours to make each bridesmaid dress and 15 hours to make each pageboy outfit. Each bridesmaid dress uses 8 metres of fabric. Each pageboy outfit uses 3 metres of fabric. The fabric costs \(\pounds 8\) per metre. Additional items cost \(\pounds 35\) for each bridesmaid dress and \(\pounds 80\) for each pageboy outfit. William's sister wants to have at least one bridesmaid and at least one pageboy. William has 100 hours available and must not spend more than \(\pounds 600\) in total on materials. Let \(x\) denote the number of bridesmaids and \(y\) denote the number of pageboys.

1. Show why the constraint \(4 x + 3 y \leqslant 20\) is needed and write down three more constraints on the values of \(x\) and \(y\), other than that they must be integers.
2. Plot the feasible region where all four constraints are satisfied. William's sister wants to maximise the total number of attendants (bridesmaids and pageboys) at her wedding.
3. Use your graph to find the maximum number of attendants.
4. William costs his time at \(\pounds 15\) an hour. Find, and simplify, an expression, in terms of \(x\) and \(y\), for the total cost (for all materials and William's time). Hence find, and interpret, the minimum cost solution to part (iii).

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 Sam is making pies.
There is exactly enough pastry to make 7 large pies or 20 medium pies or 36 small pies, or some mixture of large, medium and small pies. This is represented as a constraint \(180 x + 63 y + 35 z \leqslant 1260\).

1. Write down what \(\mathrm { X } , \mathrm { Y }\) and Z represent. There is exactly enough filling to make 5 large pies or 12 medium pies or 18 small pies, or some mixture of large, medium and small pies.
2. Express this as a constraint of the form \(a x + b y + c z \leqslant d\), where \(a , b , c\) and \(d\) are integers. The number of small pies must equal the total number of large and medium pies.
3. Show that making exactly 9 small pies is inconsistent with the constraints.
4. Determine the maximum number of large pies that can be made.

7. Ian plans to produce two types of book, hardbacks and paperbacks. He will use linear programming to determine the number of each type of book he should produce. Let \(x\) represent the number of hardbacks Ian will produce. Let \(y\) represent the number of paperbacks Ian will produce. Each hardback takes 1 hour to print and 15 minutes to bind.
Each paperback takes 35 minutes to print and 24 minutes to bind.
The printing machine must be used for at least 14 hours. The binding machine must be used for at most 8 hours.

1. 1. Show that the printing time restriction leads to the constraint \(12 x + 7 y \geqslant k\), where \(k\) is a constant to be determined.
   2. Write the binding time restriction in a similar simplified form. Ian decides to produce at most twice as many hardbacks as paperbacks.
2. Write down an inequality to model this constraint in terms of \(x\) and \(y\).
3. Add lines and shading to Diagram 1 in the answer book to represent the constraints found in (a) and (b). Hence determine, and label, the feasible region R. Ian wishes to maximise \(\mathrm { P } = 60 x + 36 y\), where P is the total profit in pounds.
4. 1. Use the objective line (ruler) method to find the optimal vertex, V, of the feasible region. You must draw and clearly label your objective line and the vertex V .
   2. Determine the exact coordinates of V. You must show your working.
5. Given that P is Ian's expected total profit, in pounds, find the number of each type of book that he should produce and his maximum expected profit.

7. You are in charge of buying new cupboards for a school laboratory. The cupboards are available in two different sizes, standard and large.
The maximum budget available is \(\pounds 1800\). Standard cupboards cost \(\pounds 150\) and large cupboards cost \(\pounds 300\).
Let \(x\) be the number of standard cupboards and \(y\) be the number of large cupboards.

1. Write down an inequality, in terms of \(x\) and \(y\), to model this constraint.
   (2) The cupboards will be fitted along a wall 9 m long. Standard cupboards are 90 cm long and large cupboards are 120 cm long.
2. Show that this constraint can be modelled by $$3 x + 4 y \leqslant 30$$ You must make your reasoning clear. Given also that \(y \geqslant 2\),
3. explain what this constraint means in the context of the question. The capacity of a large cupboard is \(40 \%\) greater than the capacity of a standard cupboard. You wish to maximise the total capacity.
4. Show that your objective can be expressed as $$\text { maximise } 5 x + 7 y$$
5. Represent your inequalities graphically, on the axes in your answer booklet, indicating clearly the feasible region, R.
6. Find the number of standard cupboards and large cupboards that need to be purchased. Make your method clear.

7. \begin{figure}[h] \end{figure} A company is going to hire out two types of car, standard and luxury. Let \(x\) be the number of standard cars it should buy.
Let \(y\) be the number of luxury cars it should buy. Figure 6 shows three constraints, other than \(x , y \geqslant 0\) Two of these are \(x \geqslant 20\) and \(y \geqslant 8\)

1. Write, as an inequality, the third constraint shown in Figure 6. The company decides that at least \(\frac { 1 } { 6 }\) of the cars must be luxury cars.
2. Express this information as an inequality and show that it simplifies to $$5 y \geqslant x$$ You must make the steps in your working clear. Each time the cars are hired they need to be prepared. It takes 5 hours to prepare a standard car and it takes 6 hours to prepare a luxury car. There are 300 hours available each week to prepare the cars.
3. Express this information as an inequality.
4. Add two lines and shading to Diagram 1 in the answer book to illustrate the constraints found in parts (b) and (c).
5. Hence determine the feasible region and label it R . The company expects to make \(\pounds 80\) profit per week on each car.
   It therefore wishes to maximise \(\mathrm { P } = 80 x + 80 y\), where P is the profit per week.
6. Use the objective line (ruler) method to find the optimal vertex, V, of the feasible region. You must clearly draw and label your objective line and the vertex V.
7. Given that P is the expected profit, in pounds, per week, find the number of each type of car that the company should buy and the maximum expected profit.

6 An online magazine consists of an editorial, articles, reviews and advertisements.
The magazine must have a total of at least 12 pages. The editorial always takes up exactly half a page. There must be at least 3 pages of articles and at most 1.5 pages of reviews. At least a quarter but fewer than half of the pages in the magazine must be used for advertisements. Let \(x\) be the number of pages used for articles, \(y\) be the number of pages used for reviews and \(z\) be the number of pages used for advertisements. The constraints on the values of \(x , y\) and \(z\) are: $$\begin{aligned} & x + y + z \geqslant 11.5 \\ & x \geqslant 3 \\ & y \leqslant 1.5 \\ & 2 x + 2 y - 2 z + 1 \geqslant 0 \\ & 2 x + 2 y - 6 z + 1 \leqslant 0 \\ & y \geqslant 0 \end{aligned}$$

1. (a) Explain why \(x + y + z \geqslant 11.5\).
   (b) Explain why only one non-negativity constraint is needed.
   (c) Show that the requirement that at least one quarter of the pages in the magazine must be used for advertisements leads to the constraint \(2 x + 2 y - 6 z + 1 \leqslant 0\). Advertisements bring in money but are not popular with the subscribers. The editor decides to limit the number of pages of advertisements to at most four.
2. Graph the feasible region in the case when \(z = 4\) using the axes in the Printed Answer Booklet. To be successful the magazine needs to maximise the number of subscribers.
   The editor has found that when \(z \leqslant 4\) the expected number of subscribers is given by \(P = 300 x + 400 y\).
3. (a) What is the maximum expected number of subscribers when \(z = 4\) ?
   (b) By first considering the feasible region for \(z = k\), where \(k \leqslant 4\), find an expression for the maximum number of subscribers in terms of \(k\). \section*{END OF QUESTION PAPER} \section*{OCR} \section*{Oxford Cambridge and RSA}

7. A tailor makes two types of garment, \(A\) and \(B\). He has available \(70 \mathrm {~m} ^ { 2 }\) of cotton fabric and \(90 \mathrm {~m} ^ { 2 }\) of woollen fabric. Garment \(A\) requires \(1 \mathrm {~m} ^ { 2 }\) of cotton fabric and \(3 \mathrm {~m} ^ { 2 }\) of woollen fabric. Garment \(B\) requires \(2 \mathrm {~m} ^ { 2 }\) of each fabric. The tailor makes \(x\) garments of type \(A\) and \(y\) garments of type \(B\).

1. Explain why this can be modelled by the inequalities $$\begin{aligned} & x + 2 y \leq 70 \\ & 3 x + 2 y \leq 90 \\ & x \geq 0 , y \geq 0 \end{aligned}$$ (2 marks)
   The tailor sells type \(A\) for \(\pounds 30\) and type \(B\) for \(\pounds 40\). All garments made are sold. The tailor wishes to maximise his total income.
2. Set up an initial Simplex tableau for this problem.
   (3 marks)
3. Solve the problem using the Simplex algorithm.
   (8 marks) Figure 4 shows a graphical representation of the feasible region for this problem. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-004_452_828_995_356} \captionsetup{labelformat=empty} \caption{Fig. 4}
   \end{figure}
4. Obtain the coordinates of the points A, \(C\) and \(D\).
5. Relate each stage of the Simplex algorithm to the corresponding point in Fig. 4.
   (3 marks) Answer Book (AB12)
   Graph Paper (ASG2) Items included with question papers Answer booklet

7. A tailor makes two types of garment, \(A\) and \(B\). He has available \(70 \mathrm {~m} ^ { 2 }\) of cotton fabric and \(90 \mathrm {~m} ^ { 2 }\) of woollen fabric. Garment \(A\) requires \(1 \mathrm {~m} ^ { 2 }\) of cotton fabric and \(3 \mathrm {~m} ^ { 2 }\) of woollen fabric. Garment \(B\) requires \(2 \mathrm {~m} ^ { 2 }\) of each fabric. The tailor makes \(x\) garments of type \(A\) and \(y\) garments of type \(B\).

1. Explain why this can be modelled by the inequalities $$\begin{aligned} & x + 2 y \leq 70 \\ & 3 x + 2 y \leq 90 \\ & x \geq 0 , y \geq 0 \end{aligned}$$ The tailor sells type \(A\) for \(\pounds 30\) and type \(B\) for \(\pounds 40\). All garments made are sold. The tailor wishes to maximise his total income.
2. Set up an initial Simplex tableau for this problem.
3. Solve the problem using the Simplex algorithm. Figure 4 shows a graphical representation of the feasible region for this problem. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-008_686_1277_1319_453} \captionsetup{labelformat=empty} \caption{Fig. 4}
   \end{figure}
4. Obtain the coordinates of the points A, \(C\) and \(D\).
5. Relate each stage of the Simplex algorithm to the corresponding point in Fig. 4. 6689 Decision Mathematics 1 (New Syllabus) Order of selecting edges
   Final tree
   (b) Minimum total length of cable
   Question 4 to be answered on this page
   (a) \(A\)
   Question 5 to be answered on this page
   Key
   (a) Early
   Time
   Late
   Time \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-011_433_227_534_201} \(F ( 3 )\) \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-011_117_222_1016_992}
   H(4) K(6)
   (b) Critical activities
   Length of critical path \(\_\_\_\_\) (c) \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-011_492_1604_1925_266} Question 6 to be answered on pages 4 and 5
   (a) (i) SAET \(\_\_\_\_\) (ii) SBDT \(\_\_\_\_\) (iii) SCFT \(\_\_\_\_\) (b) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-012_691_1307_893_384} \captionsetup{labelformat=empty} \caption{Diagram 1}
   \end{figure} (c) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-013_699_1314_167_382} \captionsetup{labelformat=empty} \caption{Diagram 2}
   \end{figure} Flow augmenting routes
   (d) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-013_693_1314_1368_382} \captionsetup{labelformat=empty} \caption{Diagram 3}
   \end{figure} (e) \(\_\_\_\_\)

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.

8 [Figure 2, printed on the insert, is provided for use in this question.]
A company makes two types of boxes of chocolates, executive and luxury.
Every hour the company must make at least 15 of each type and at least 35 in total.
Each executive box contains 20 dark chocolates and 12 milky chocolates.
Each luxury box contains 10 dark chocolates and 18 milky chocolates.
Every hour the company has 600 dark chocolates and 600 milky chocolates available.
The company makes a profit of \(\pounds 1.50\) on each executive box and \(\pounds 1\) on each luxury box.
The company makes and sells \(x\) executive boxes and \(y\) luxury boxes every hour.
The company wishes to maximise its hourly profit, \(\pounds P\).

1. Show that one of the constraints leads to the inequality \(2 x + 3 y \leqslant 100\).
2. Formulate the company's situation as a linear programming problem.
3. On Figure 2, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region and an objective line.
4. Use your diagram to find the maximum hourly profit.

8 Nerys runs a cake shop. In November and December she sells Christmas hampers. She makes up the hampers herself, in two sizes: Luxury and Special. Each day, Nerys prepares \(x\) Luxury hampers and \(y\) Special hampers.
It takes Nerys 10 minutes to prepare a Luxury hamper and 15 minutes to prepare a Special hamper. She has 6 hours available, each day, for preparing hampers. From past experience, Nerys knows that each day:

• she will need to prepare at least 5 hampers of each size
• she will prepare at most a total of 32 hampers
• she will prepare at least twice as many Luxury hampers as Special hampers.

Each Luxury hamper that Nerys prepares makes her a profit of \(\pounds 15\); each Special hamper makes a profit of \(\pounds 20\). Nerys wishes to maximise her daily profit, \(\pounds P\).

1. Show that \(x\) and \(y\) must satisfy the inequality \(2 x + 3 y \leqslant 72\).
2. In addition to \(x \geqslant 5\) and \(y \geqslant 5\), write down two more inequalities that model the constraints above.
3. On the grid opposite draw a suitable diagram to enable this problem to be solved graphically. Indicate a feasible region and the direction of an objective line.
4. 1. Use your diagram to find the number of each type of hamper that Nerys should prepare each day to achieve a maximum profit.
   2. Calculate this profit.
      \includegraphics[max width=\textwidth, alt={}]{fb95068f-f76d-492a-b385-bce17b26ae30-27_2490_1719_217_150}
      \section*{DO NOT WRITE ON THIS PAGE ANSWER IN THE SPACES PROVIDED}