OCR D1 (Decision Mathematics 1) 2014 June

1 Sangita needs to move some heavy boxes to her new house. She has borrowed a van that can carry at most 600 kg . She will have to make several deliveries to her new house. The masses of the boxes have been recorded in kg as: $$\begin{array} { l l l l l l l l l l l } 120 & 120 & 120 & 100 & 150 & 200 & 250 & 150 & 200 & 250 & 120 \end{array}$$

1. Use the first-fit method to show how Sangita could pack the boxes into the van. How many deliveries does this solution require?
2. Use the first-fit decreasing method to show how Sangita could pack the boxes into the van. There is no need to use a sorting algorithm, but you should write down the sorted list before showing the packing. How many deliveries does this solution require? Sangita then realises that she cannot fit more than four boxes in the van at a time.
3. Find a way to pack the boxes into the van so that she makes as few deliveries as possible.

2 A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex. A simply connected graph is one that is both simple and connected.

1. (a) Draw a simply connected graph that has exactly four vertices and exactly five arcs. Is your graph Eulerian, semi-Eulerian or neither? Explain how you know.
   (b) By considering the sum of the vertex orders, show that there is only one possible simply connected graph with exactly four vertices and exactly five arcs.
2. Draw five distinct simply connected graphs each with exactly five vertices and exactly five arcs.

3 The following algorithm finds two positive integers for which the sum of their squares equals a given input, when this is possible. The function \(\operatorname { INT } ( X )\) gives the largest integer that is less than or equal to \(X\). For example: \(\operatorname { INT } ( 6.9 ) = 6\), \(\operatorname { INT } ( 7 ) = 7 , \operatorname { INT } ( 7.1 ) = 7\).

1. Apply the algorithm to the input \(N = 500\). You only need to write down values when they change and there is no need to record the use of lines \(30,60,70\) or 90 .
2. Apply the algorithm to the input \(N = 7\).
3. Explain why lines 70 and 110 are needed. The algorithm has order \(\sqrt { N }\).
4. If it takes 0.7 seconds to run the algorithm when \(N = 3000\), roughly how long will it take when \(N = 12000\) ?

4 The network below represents a treasure trail. The arcs represent paths and the weights show distances in units of 100 metres. The total length of the paths shown is 4200 metres.
\includegraphics[max width=\textwidth, alt={}, center]{cdad4fbe-4b94-4c8f-bb42-24d20eeaab4d-4_681_1157_450_459}

1. Apply Dijkstra's algorithm to the network, starting at \(A\), to find the shortest distance (in metres) from \(A\) to each of the other vertices. Alex wants to hunt for the treasure. His current location is marked on the network as \(A\). The clues to the location of the treasure are located on the paths. Every path has at least one clue and some paths have more than one. This means that Alex will need to search along the full length of every path to find all the clues.
2. Showing your working, find the length of the shortest route that Alex can take, starting and ending at \(A\), to find every clue. The clues tell Alex that the treasure is located at the point marked as \(H\) on the network.
3. Write down the shortest route from \(A\) to \(H\). Zac also starts at \(A\) and searches along every path to find the clues. He also uses a shortest route to do this, but without returning to \(A\). Instead he proceeds directly to the treasure at \(H\).
4. Calculate the length of the shortest route that Zac can take to search for all the clues and reach the treasure.

5 This question uses the same network as question 4.
The network below represents a treasure trail. The arcs represent paths and the weights show distances in units of 100 metres.
\includegraphics[max width=\textwidth, alt={}, center]{cdad4fbe-4b94-4c8f-bb42-24d20eeaab4d-5_680_1154_431_459} Gus wants to hunt for the treasure. He assumes that the treasure is located at a vertex, but he does not know which one.

1. (a) Use the nearest neighbour method starting at \(G\) to find an upper bound for the length of the shortest closed route through every vertex.
   (b) Gus follows this route, but starting at \(A\). Write down his route, starting and ending at \(A\).
2. Use Prim's algorithm on the network, starting at \(A\), to find a minimum spanning tree. You should write down the arcs in the order they are included, draw the tree and give its total weight (in units of 100 metres).
3. (a) Vertex \(H\) and all arcs joined to \(H\) are removed from the original network. Write down the weight of the minimum spanning tree for vertices \(A , B , C , D , E , F\) and \(G\) in the resulting reduced network.
   (b) Use this minimum spanning tree for the reduced network to find a lower bound for the length of the shortest closed route through every vertex in the original network.
4. Find a route that passes through every vertex, starting and ending at \(A\), that is longer than the lower bound from part (iii)(b) but shorter than the upper bound from part (i)(a). Give the length of your route, in metres. Assume that Gus travels along paths at a rate of \(x\) minutes for every 100 metres and that he spends \(y\) minutes at each vertex hunting for the treasure. Gus starts by hunting for the treasure at \(A\). He then follows the route from part (iv), starting and finishing at \(A\) and hunting for the treasure at each vertex. Unknown to Gus, the treasure is found before he gets to it, so he has to search at every vertex. Gus can take at most 2 hours from when he starts searching at \(A\) to when he arrives back at \(A\).
5. Use this information to write down a constraint on \(x\) and \(y\). The treasure was at \(H\) and was found 40 minutes after Gus started. This means that Gus takes more than 40 minutes to get to \(H\).
6. Use this information to write down a second constraint on \(x\) and \(y\).

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