OCR D1 (Decision Mathematics 1) 2007 January

1 An airline allows each passenger to carry a maximum of 25 kg in luggage. The four members of the Adams family have bags of the following weights (to the nearest kg ): The bags need to be grouped into bundles of 25 kg maximum so that each member of the family can carry a bundle of bags.

1. Use the first-fit method to group the bags into bundles of 25 kg maximum. Start with the bags belonging to Mr Adams, then those of Mrs Adams, followed by Sarah and finally Tim.
2. Use the first-fit decreasing method to group the same bags into bundles of 25 kg maximum.
3. Suggest a reason why the grouping of the bags in part (i) might be easier for the family to carry.

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

3 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 connected, directly or indirectly, to every other vertex. A simply connected graph is one that is both simple and connected.

1. A simply connected graph is drawn with 6 vertices and 9 arcs.
   (a) What is the sum of the orders of the vertices?
   (b) Explain why if the graph has two vertices of order 5 it cannot have any vertices of order 1.
   (c) Explain why the graph cannot have three vertices of order 5 .
2. Draw an example of a simply connected graph with 6 vertices and 9 arcs in which one of the vertices has order 5 and all the orders of the vertices are odd numbers.
3. Draw an example of a simply connected graph with 6 vertices and 9 arcs that is also Eulerian.

4

1. ↓
   	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)
   A	0	4	5	3	2	5	6
   \(B\)	4	0	1	2	4	7	6
   C	5	1	0	3	4	6	7
   \(D\)	3	2	3	0	2	6	4
   \(E\)	2	4	4	2	0	6	6
   \(F\)	5	7	6	6	6	0	10
   \(G\)	6	6	7	4	6	10	0

   Order in which rows were deleted: \(\_\_\_\_\) \(A\) Minimum spanning tree: A
   • \(D\)
   F
   B E
   \includegraphics[max width=\textwidth, alt={}, center]{8a1232ae-6a6e-4afb-8757-fffe4fc9570f-10_33_28_1302_1101} III
   o D C
   \includegraphics[max width=\textwidth, alt={}, center]{8a1232ae-6a6e-4afb-8757-fffe4fc9570f-10_38_38_1297_1491}
   • G Total weight: \(\_\_\_\_\)
2. \(\_\_\_\_\)
3. \(\_\_\_\_\)
   Lower bound: \(\_\_\_\_\)
4. Tour: \(\_\_\_\_\)
   Upper bound: \(\_\_\_\_\)

5 Answer part (i) of this question on the insert provided. Rhoda Raygh enjoys driving but gets extremely irritated by speed cameras.
The network represents a simplified map on which the arcs represent roads and the weights on the arcs represent the numbers of speed cameras on the roads. The sum of the weights on the arcs is 72 .
\includegraphics[max width=\textwidth, alt={}, center]{8a1232ae-6a6e-4afb-8757-fffe4fc9570f-05_874_1484_664_333}

1. Rhoda lives at Ayton ( \(A\) ) and works at Kayton ( \(K\) ). Use Dijkstra's algorithm on the diagram in the insert to find the route from \(A\) to \(K\) that involves the least number of speed cameras and state the number of speed cameras on this route.
2. In her job Rhoda has to drive along each of the roads represented on the network to check for overhanging trees. This requires finding a route that covers every arc at least once, starting and ending at Kayton (K). Showing all your working, find a suitable route for Rhoda that involves the least number of speed cameras and state the number of speed cameras on this route.
3. If Rhoda checks the roads for overhanging trees on her way home, she will instead need a route that covers every arc at least once, starting at Kayton and ending at Ayton. Calculate the least number of speed cameras on such a route, explaining your reasoning.

6 Consider the linear programming problem: $$\begin{array} { l r } \text { maximise } & P = 3 x - 5 y + 4 z ,
\text { subject to } & x + 2 y - 3 z \leqslant 12 ,
& 2 x + 5 y - 8 z \leqslant 40 ,
\text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$

1. Represent the problem as an initial Simplex tableau.
2. Explain why it is not possible to pivot on the \(z\) column of this tableau. Identify the entry on which to pivot for the first iteration of the Simplex algorithm. Explain how you made your choice of column and row.
3. Perform one iteration of the Simplex algorithm. Write down the values of \(x , y\) and \(z\) after this iteration.
4. Explain why \(P\) has no finite maximum. The coefficient of \(z\) in the objective is changed from + 4 to - 40 .
5. Describe the changes that this will cause to the initial Simplex tableau and the tableau that results after one iteration. What is the maximum value of \(P\) in this case? Now consider this linear programming problem: $$\begin{array} { l l } \text { maximise } & Q = 3 x - 5 y + 7 z ,
   \text { subject to } & x + 2 y - 3 z \leqslant 12 ,
   & 2 x - 7 y + 10 z \leqslant 40 ,
   \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$ Do not use the Simplex algorithm for these parts.
6. By adding the two constraints, show that \(Q\) has a finite maximum.
7. There is an optimal point with \(y = 0\). By substituting \(y = 0\) in the two constraints, calculate the values of \(x\) and \(z\) that maximise \(Q\) when \(y = 0\).