Questions — OCR D1 (127 questions)

Browse by module
All questions AEA AS Paper 1 AS Paper 2 AS Pure C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Extra Pure Further Mechanics Further Mechanics A AS Further Mechanics AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics Further Paper 4 Further Pure Core Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Pure with Technology Further Statistics Further Statistics A AS Further Statistics AS Further Statistics B AS Further Statistics Major Further Statistics Minor Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 H240/01 H240/02 H240/03 M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 S1 S2 S3 S4 Unit 1 Unit 2 Unit 3 Unit 4
Browse by board
AQA AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Paper 1 Further Paper 2 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics M1 M2 M3 Paper 1 Paper 2 Paper 3 S1 S2 S3 CAIE FP1 FP2 Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 4 M1 M2 P1 P2 P3 S1 S2 Edexcel AEA AS Paper 1 AS Paper 2 C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 OCR AS Pure C1 C2 C3 C4 D1 D2 FD1 AS FM1 AS FP1 FP1 AS FP2 FP3 FS1 AS Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Mechanics Further Mechanics AS Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Statistics Further Statistics AS H240/01 H240/02 H240/03 M1 M2 M3 M4 PURE S1 S2 S3 S4 OCR MEI AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further Extra Pure Further Mechanics A AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Pure Core Further Pure Core AS Further Pure with Technology Further Statistics A AS Further Statistics B AS Further Statistics Major Further Statistics Minor M1 M2 M3 M4 Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 Pre-U Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 WJEC Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 Unit 1 Unit 2 Unit 3 Unit 4
Sort by: Default | Easiest first | Hardest first
OCR D1 2005 January Q1
5 marks Easy -1.8
1 Use the shuttle sort algorithm to sort the list $$\begin{array} { l l l l l l } 6 & 5 & 9 & 4 & 5 & 2 \end{array}$$ into increasing order. Write down the list that results from each pass through the algorithm.
OCR D1 2005 January Q2
5 marks Moderate -0.8
2
  1. A graph has six vertices; two are of order 3 and the rest are of order 4. Calculate the number of arcs in the graph, showing your working.
  2. Is the graph Eulerian, semi-Eulerian or neither? Give a reason to support your answer. 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.
  3. Explain why a simple graph with six vertices, two of order 3 and the rest of order 4, must also be a connected graph.
OCR D1 2005 January Q3
7 marks Standard +0.3
3 The diagram shows a network. The weights on the arcs represent distances in miles. The direct path between any two adjacent vertices is never longer than any indirect path. \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-02_490_748_1372_699}
  1. By deleting vertex \(U\) and all arcs connected to \(U\), find a lower bound for the length of the shortest cycle that visits every vertex of this network.
  2. Find a vertex that can be used as the start vertex for the nearest neighbour method to give a cycle that passes through every vertex of this network. Give your cycle and its length.
OCR D1 2005 January Q4
12 marks Moderate -0.3
4 [Answer this question on the insert provided.]
A competition challenges teams to hike across a moor, visiting each of eight peaks, in the quickest possible time. The teams all start at peak \(A\) and finish at peak \(H\), but other than this the peaks may be visited in any order. The estimated journey times, in hours, between peaks are shown in the table. A dash in the table means that there is no direct route between two peaks.
\(A\)\(B\)CD\(E\)\(F\)G\(H\)
A-423----
\(B\)4-1-3---
C21-2-65-
\(D\)3-2---4-
\(E\)-3---8-7
\(F\)--6-8--8
\(G\)--54---9
\(H\)----789-
  1. Use Prim's algorithm on the table in the insert to find a minimum spanning tree. Start by crossing out row \(A\). Show which entries in the table are chosen and indicate the order in which the rows are deleted. What can you deduce from this answer about the quickest possible time needed to complete the challenge?
  2. On the insert, draw a network to represent the information given in the table above. A team decides to visit each peak exactly once on the hike from peak \(A\) to peak \(H\).
  3. Explain why the team cannot use the arc \(A C\).
  4. Explain why the team must use the arc \(E F\).
  5. There are only two possible routes that the team can use. Find both routes and determine which is the quicker route.
OCR D1 2005 January Q5
13 marks Standard +0.8
5 The constraints of a linear programming problem are represented by the graph below. The feasible region is the unshaded region, including its boundaries. \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-04_1118_816_404_662}
  1. Write down four inequalities that define the feasible region. The objective is to maximise \(P = 5 x + 3 y\).
  2. Using the graph or otherwise, obtain the coordinates of the vertices of the feasible region and hence find the values of \(x\) and \(y\) that maximise \(P\), and the corresponding maximum value of \(P\). The objective is changed to maximise \(Q = a x + 3 y\).
  3. For what set of values of \(a\) is the maximum value of \(Q\) equal to 3?
OCR D1 2005 January Q6
13 marks Standard +0.8
6 Consider the linear programming problem:
maximise\(P = 2 x - 5 y - z\),
subject to\(5 x + 3 y - 5 z \leqslant 15\),
\(2 x + 6 y + 8 z \leqslant 24\),
and\(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\).
  1. Using slack variables, \(s\) and \(t\), express the non-trivial constraints as two equations.
  2. Represent the problem as an initial Simplex tableau. Perform one iteration of the Simplex algorithm.
  3. Use the Simplex algorithm to find the values of \(x , y\) and \(z\) for which \(P\) is maximised, subject to the constraints above.
  4. The value 15 in the first constraint is increased to a new value \(k\). As a result the pivot for the first iteration changes. Show what effect this has on the final value of \(y\).
OCR D1 2005 January Q7
17 marks Moderate -0.8
7 [Answer this question on the insert provided.]
The network below represents a simplified map of the centre of a small town. The arcs represent roads and the weights on the arcs represent distances, in units of 100 metres. \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-06_725_1259_495_443}
    1. Use Dijkstra's algorithm on the diagram in the insert to find the length of the shortest route from \(A\) to each of the other vertices. You must show your working, including temporary labels, permanent labels and the order in which the permanent labels were assigned. State the shortest route from \(A\) to \(E\) and the shortest route from \(A\) to \(J\), and give their lengths. [7]
    2. The shortest route from \(E\) to \(J\) that passes through every vertex can be treated as being made up of two parts, one from \(E\) to \(A\) and the other from \(A\) to \(J\). Use your answers to part (i) to write down the length of the shortest such route. List the vertices in the order that they are visited in travelling from \(E\) to \(J\) using this route.
    3. Explain why a similar approach to that used in parts (a)(i) and (a)(ii) would not give the shortest route between \(G\) and \(H\) that passes through every vertex.
  2. By considering pairings of odd nodes, find the length of the shortest route that starts at \(A\) and ends at \(E\) and uses every arc at least once. \section*{OXFORD CAMBRIDGE AND RSA EXAMINATIONS} Advanced Subsidiary General Certificate of Education Advanced General Certificate of Education MATHEMATICS
    4736
    Decision Mathematics 1
    INSERT for Questions 4 and 7
    Wednesday
OCR D1 2005 January Q12
Moderate -1.0
12 JANUARY 2005
Afternoon
1 hour 30 minutes
  • This insert should be used to answer Questions 4 and 7.
  • Write your name, centre number and candidate number in the spaces provided at the top of this page.
  • Write your answers to Questions 4 and 7 in the spaces provided in this insert, and attach it to your answer booklet.
4
  1. \(A\)\(B\)CD\(E\)\(F\)G\(H\)
    A-423----
    \(B\)4-1-3---
    C21-2-65-
    \(D\)3-2---4-
    E-3---8-7
    \(F\)--6-8--8
    \(G\)--54---9
    \(H\)----789-
  2. B \(E\) \(C\) F
    • \(H\) \(A\) •
    • \({ } ^ { \text {F } }\)
    H D
    G
  3. \(\_\_\_\_\)
  4. \(\_\_\_\_\)
  5. \(\_\_\_\_\) 7
      1. \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-11_191_1179_269_482} Do not cross out your working values (temporary labels) \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-11_871_1557_612_335} Shortest route from \(A\) to \(E =\) \(\_\_\_\_\) Length = \(\_\_\_\_\) Shortest route from \(A\) to \(J =\) \(\_\_\_\_\) Length = \(\_\_\_\_\)
      2. Length of route \(=\) \(\_\_\_\_\) Vertices visited in order \(\_\_\_\_\)
      3. Explanation \(\_\_\_\_\)
    2. \(\_\_\_\_\) Length = \(\_\_\_\_\)
OCR D1 2006 January Q3
6 marks Moderate -0.8
3 Consider the following algorithm.
Step 1: Input a positive integer \(n\).
Step 2 : Draw a graph consisting of \(n\) vertices and no arcs.
Step 3 : Create a new vertex and join it directly to every vertex of order 0.
Step 4: Create a new vertex and join it directly to every vertex of odd order.
Step 5 : Stop.
  1. Draw separate diagrams to show the result of applying this algorithm in the following cases.
    1. \(n = 1\)
    2. \(n = 2\)
    3. \(n = 3\)
    4. \(n = 4\)
    5. State how many arcs are in the graph that results when the algorithm is applied to a set of \(n\) vertices.
OCR D1 2006 January Q4
8 marks Moderate -0.5
4
  1. Represent the linear programming problem below by an initial Simplex tableau. $$\begin{array} { l l } \text { Maximise } & P = 5 x - 4 y - 3 z , \\ \text { subject to } & 2 x - 3 y + 4 z \leqslant 10 , \\ & 6 x + 5 y + 4 z \leqslant 60 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$
  2. Perform one iteration of the Simplex algorithm and write down the values of \(x , y , z\) and \(P\) that result from this iteration.
OCR D1 2006 January Q5
13 marks Moderate -0.8
5 Findlay is trying to get into his local swimming team. The coach will watch him swim and will then make his decision. Findlay must swim at least two lengths using each stroke and must swim at least 8 lengths in total, taking at most 10 minutes. Findlay needs to put together a routine that includes breaststroke, backstroke and butterfly. The table shows how Findlay expects to perform with each stroke.
StrokeStyle marksTime taken
Breaststroke2 marks per length2 minutes per length
Backstroke1 mark per length0.5 minutes per length
Butterfly5 marks per length1 minute per length
Findlay needs to work out how many lengths to swim using each stroke to maximise his expected total number of style marks.
  1. Identify appropriate variables for Findlay's problem and write down the objective function, to be maximised, in terms of these variables.
  2. Formulate a constraint for the total number of lengths swum, a constraint for the time spent swimming and constraints on the number of lengths swum using each stroke. Findlay decides that he will swim two lengths using butterfly. This reduces his problem to the following LP formulation: $$\begin{array} { l c } \text { maximise } & P = 2 x + y , \\ \text { subject to } & x + y \geqslant 6 , \\ & 4 x + y \leqslant 16 , \\ & x \geqslant 2 , y \geqslant 2 , \end{array}$$ with \(x\) and \(y\) both integers.
  3. Use a graphical method to identify the feasible region for this problem. Write down the coordinates of the vertices of the feasible region and hence find the integer values of \(x\) and \(y\) that maximise \(P\).
  4. Interpret your solution for Findlay.
OCR D1 2006 January Q6
16 marks Standard +0.3
6 The network represents a railway system. The vertices represent the stations and the arcs represent the tracks. The weights on the arcs represent journey times between stations, in minutes. The sum of all the weights is 105 minutes. \includegraphics[max width=\textwidth, alt={}, center]{8f17020a-14bf-4459-9241-1807b954a629-5_981_1215_468_477} Norah wants to travel around the system visiting every station. She wants to start and end at \(A\) and she wants to complete her journey in the shortest possible time.
  1. Apply the nearest neighbour method starting at \(A\) to find two suitable tours and calculate the journey time for each of these tours. Which of these answers gives the better upper bound for Norah's journey time?
  2. Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting vertex \(G\) and all the arcs that are directly joined to \(G\). Draw a diagram to show the arcs in your tree. Hence calculate a lower bound for Norah's journey time. Norah now decides that she wants to use every section of track in her journey. She still wants to start and end at \(A\) and to complete her journey in the shortest possible time.
  3. Calculate the journey time for Norah's new problem. Show your working; quickest times between stations may be found by inspection. State which arcs Norah will have to travel twice and how many times she will pass through station \(D\).
OCR D1 2006 January Q7
18 marks Easy -1.2
7 Mr Rank and Miss File need to sort a pile of examination scripts into increasing order of mark. Mr Rank first goes through the pile of scripts and puts each script into one of two piles, depending on whether the mark is below 50 or not. He then sorts the scripts in the 'below 50 ' pile and Miss File sorts the scripts in the '50 and above' pile. At the end they put the two sorted piles together again.
  1. The scripts in the 'below 50' pile have the following marks, starting from the top of the pile. $$\begin{array} { l l l l l l l l } 34 & 42 & 27 & 31 & 12 & 48 & 24 & 37 \end{array}$$ Use bubble sort to sort this list into increasing order. Clearly indicate the list that results at the end of each pass through the algorithm. Give the number of swaps and the number of comparisons that were used in sorting this list.
  2. The scripts in the '50 and above' pile have the following marks, starting from the top of the pile. $$\begin{array} { l l l l l l l l } 95 & 74 & 61 & 87 & 71 & 82 & 53 & 57 \end{array}$$ Use shuttle sort to sort this list into increasing order. Clearly indicate the list that results at the end of each pass through the algorithm. List the number of swaps and number of comparisons that were used in sorting this list.
  3. Explain why splitting the original list into two piles is a linear order algorithm.
  4. Both bubble sort and shuttle sort are quadratic order algorithms. Mr Rank and Miss File use their method to sort a pile of 100 scripts. It takes about 50 seconds to split the pile and about 250 seconds to do each sort. As the sorts are done at the same time, this gives a total time taken of about 300 seconds, or 6 minutes. Approximately how long would Mr Rank and Miss File take to split a pile of 500 scripts into two roughly equal piles and sort the piles? Show all your working.
    [0pt] [4]
OCR D1 2007 January Q1
7 marks Easy -1.3
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 ):
Mr Adams:1042
Mrs Adams:1337524
Sarah Adams:5825
Tim Adams:105353
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.
OCR D1 2007 January Q2
8 marks Moderate -0.8
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.]
OCR D1 2007 January Q3
9 marks Moderate -0.8
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.
    1. What is the sum of the orders of the vertices?
    2. Explain why if the graph has two vertices of order 5 it cannot have any vertices of order 1.
    3. Explain why the graph cannot have three vertices of order 5 .
    4. 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.
    5. Draw an example of a simply connected graph with 6 vertices and 9 arcs that is also Eulerian.
OCR D1 2007 January Q4
14 marks Moderate -0.5
4
  1. ↓
    \(A\)\(B\)\(C\)\(D\)\(E\)\(F\)\(G\)
    A0453256
    \(B\)4012476
    C5103467
    \(D\)3230264
    \(E\)2442066
    \(F\)57666010
    \(G\)66746100
    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: \(\_\_\_\_\)
OCR D1 2007 January Q6
18 marks Standard +0.8
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\).
OCR D1 2009 January Q1
6 marks Easy -1.8
1 The flow chart shows an algorithm for which the input is a three-digit positive integer. \includegraphics[max width=\textwidth, alt={}, center]{43fe5fd5-4b98-4c3a-90ca-a1bd5cf065fe-2_1294_1493_356_328}
  1. Trace through the algorithm using the input \(A = 614\) to show that the output is 297 . Write down the values of \(A , B , C\) and \(D\) in each pass through the algorithm.
  2. What is the output when \(A = 616\) ?
  3. Explain why the counter \(C\) is needed.
OCR D1 2009 January Q2
6 marks Moderate -0.8
2
  1. Draw a graph with five vertices of orders 1, 2, 2, 3 and 4 .
  2. State whether the graph from part (i) is Eulerian, semi-Eulerian or neither. Explain how you know which it is.
  3. Explain why a graph with five vertices of orders \(1,2,2,3\) and 4 cannot be a tree.
OCR D1 2010 January Q2
10 marks Moderate -0.3
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\)-5382
    \(B\)5-6--
    \(C\)36-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\).
OCR D1 2010 January Q3
11 marks Moderate -0.8
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.
OCR D1 2010 January Q4
11 marks Moderate -0.8
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.
Item type\(A\)\(B\)\(C\)\(D\)
Number to be packed15834
Length (cm)10402010
Width (cm)10305040
Height (cm)10201010
Volume ( \(\mathrm { cm } ^ { 3 }\) )100024000100004000
Weight (g)1000250300400
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.
OCR D1 2010 January Q5
16 marks Standard +0.8
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\) ?
OCR D1 2010 January Q6
13 marks Easy -1.8
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. \(\_\_\_\_\)