OCR D1 (Decision Mathematics 1) 2010 January

1 Answer this question on the insert provided. \includegraphics[max width=\textwidth, alt={}, center]{e1495f6b-c09f-46a1-a6f8-02354e28887a-02_533_1353_342_395}

1. Apply Dijkstra's algorithm to the copy of this network in the insert to find the least weight path from \(A\) to \(F\). State the route of the path and give its weight.
2. Apply the route inspection algorithm, showing all your working, to find the weight of the least weight closed route that uses every arc at least once. Write down a closed route that has this least weight. An extra arc is added, joining \(B\) to \(E\), with weight 2 .
3. Write down the new least weight path from \(A\) to \(F\). Explain why the new least weight closed route, that uses every arc at least once, has no repeated arcs.

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. Explain why there is no simply connected graph with exactly five vertices each of which is connected to exactly three others.
2. A simply connected graph has five vertices \(A , B , C , D\) and \(E\), in which \(A\) has order \(4 , B\) has order 2, \(C\) has order 3, \(D\) has order 3 and \(E\) has order 2. Explain how you know that the graph is semi-Eulerian and write down a semi-Eulerian trail on this graph. A network is formed from the graph in part (ii) by weighting the arcs as given in the table below.

   	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)
   \(A\)	-	5	3	8	2
   \(B\)	5	-	6	-	-
   \(C\)	3	6	-	7	-
   \(D\)	8	-	7	-	9
   \(E\)	2	-	-	9	-

3. Apply Prim's algorithm to the network, showing all your working, starting at vertex \(A\). Draw the resulting tree and state its total weight. A sixth vertex, \(F\), is added to the network using arcs \(C F\) and \(D F\), each of which has weight 6 .
4. Use your answer to part (iii) to write down a lower bound for the length of the minimum tour that visits every vertex of the extended network, finishing where it starts. Apply the nearest neighbour method, starting from vertex \(A\), to find an upper bound for the length of this tour. Explain why the nearest neighbour method fails if it is started from vertex \(F\).

3 Maggie is a personal trainer. She has twelve clients who want to lose weight. She decides to put some of her clients on weight loss programme \(X\), some on programme \(Y\) and the rest on programme \(Z\). Each programme involves a strict diet; in addition programmes \(X\) and \(Y\) involve regular exercise at Maggie's home gym. The programmes each last for one month. In addition to the diet, clients on programme \(X\) spend 30 minutes each day on the spin cycle, 10 minutes each day on the rower and 20 minutes each day on free weights. At the end of one month they can each expect to have lost 9 kg more than a client on just the diet. In addition to the diet, clients on programme \(Y\) spend 10 minutes each day on the spin cycle and 30 minutes each day on free weights; they do not use the rower. At the end of one month they can each expect to have lost 6 kg more than a client on just the diet. Because of other clients who use Maggie's home gym, the spin cycle is available for the weight loss clients for 180 minutes each day, the rower for 40 minutes each day and the free weights for 300 minutes each day. Only one client can use each piece of apparatus at any one time. Maggie wants to decide how many clients to put on each programme to maximise the total expected weight loss at the end of the month. She models the objective as follows. $$\text { Maximise } P = 9 x + 6 y$$

1. What do the variables \(x\) and \(y\) represent?
2. Write down and simplify the constraints on the values of \(x\) and \(y\) from the availability of each of the pieces of apparatus.
3. What other constraints and restrictions apply to the values of \(x\) and \(y\) ?
4. Use a graphical method to represent the feasible region for Maggie's problem. You should use graph paper and choose scales so that the feasible region can be clearly seen. Hence determine how many clients should be put on each programme.

4 Jack and Jill are packing food parcels. The boxes for the food parcels can each carry up to 5000 g in weight and can each hold up to \(30000 \mathrm {~cm} ^ { 3 }\) in volume. The number of each item to be packed, their dimensions and weights are given in the table below. Jill tries to pack the items by weight using the first-fit decreasing method.

1. List the 30 items in order of decreasing weight and hence show Jill's packing. Explain why Jill's packing is not possible. Jack tries to pack the items by volume using the first-fit decreasing method.
2. List the 30 items in order of decreasing volume and hence show Jack's packing. Explain why Jack's packing is not possible.
3. Give another reason why a packing may not be possible.

5 Consider the following LP problem. $$\begin{aligned} \text { Minimise } & 2 a - 3 b + c + 18 ,
\text { subject to } & a + b - c \geqslant 14 ,
& - 2 a + 3 c \leqslant 50 ,
\text { and } & a \leqslant 4 a \leqslant 5 b ,
& a \leqslant 20 , b \leqslant 10 , c \leqslant 8 . \end{aligned}$$

1. By replacing \(a\) by \(20 - x , b\) by \(10 - y\) and \(c\) by \(8 - z\), show that the problem can be expressed as follows. $$\begin{aligned} \text { Maximise } & 2 x - 3 y + z ,
   \text { subject to } & x + y - z \leqslant 8 ,
   & 2 x - 3 z \leqslant 66 ,
   & 4 x - 5 y \leqslant 40 ,
   \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{aligned}$$
2. Represent the problem as an initial Simplex tableau. Perform one iteration of the Simplex algorithm. Explain how the choice of pivot was made and show how each row was obtained. Write down the values of \(x , y\) and \(z\) at this stage. Hence write down the corresponding values of \(a , b\) and \(c\).
3. If, additionally, the variables \(a , b\) and \(c\) are non-negative, what additional constraints are there on the values of \(x , y\) and \(z\) ?

6

1. Greatest number of arcs
   for a network with five vertices \(=\) \(\_\_\_\_\)
   for a network with \(n\) vertices \(=\) \(\_\_\_\_\)
2. (a) For a network with five vertices
   maximum number of passes \(=\) \(\_\_\_\_\)
   maximum number of comparisons
   in the first pass \(=\) \(\_\_\_\_\)
   in the second pass = \(\_\_\_\_\)
   in the third pass = \(\_\_\_\_\)
   maximum total number of comparisons = \(\_\_\_\_\)
   (b) For a network with \(n\) vertices
   maximum total number of comparisons = \(\_\_\_\_\)

3. M1 Vertices in tree	M2 Arcs in tree			M3 Vertices not in tree
   				A B C D E
   DE	D 2 \(E\)			\(A B C\)
   	\includegraphics[max width=\textwidth, alt={}]{e1495f6b-c09f-46a1-a6f8-02354e28887a-11_109_220_1879_786}
   	\includegraphics[max width=\textwidth, alt={}]{e1495f6b-c09f-46a1-a6f8-02354e28887a-11_163_220_2005_786}
   				\multirow{3}{*}{}
   	\includegraphics[max width=\textwidth, alt={}]{e1495f6b-c09f-46a1-a6f8-02354e28887a-11_231_220_2174_786}

   \(\boldsymbol { M 4 }\)
   Sorted list

   \(|\)

   \(D\)	2	\(E\)
   \(A\)	3	\(E\)
   \(A\)	4	\(C\)
   \(C\)	5	\(D\)
   \(B\)	6	\(E\)
   \(B\)	7	\(C\)
   \(A\)	8	\(B\)
   \(C\)	9	\(E\)

4. \(\_\_\_\_\)