Questions — OCR D1 (124 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 Mechanics 1 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pure 1 S1 S2 S3 S4 SPS ASFM SPS ASFM Mechanics SPS ASFM Pure SPS ASFM Statistics SPS FM SPS FM Mechanics SPS FM Pure SPS FM Statistics SPS SM SPS SM Mechanics SPS SM Pure SPS SM Statistics Stats 1 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 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 Mechanics 1 PURE Pure 1 S1 S2 S3 S4 Stats 1 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 SPS SPS ASFM SPS ASFM Mechanics SPS ASFM Pure SPS ASFM Statistics SPS FM SPS FM Mechanics SPS FM Pure SPS FM Statistics SPS SM SPS SM Mechanics SPS SM Pure SPS SM Statistics 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
OCR D1 2016 June Q1
1 The arc weights for a network on a complete graph with six vertices are given in the following table.
AB\(C\)DE\(F\)
A-579812
B5-46510
C74-768
D967-510
E8565-10
F121081010-
Apply Prim's algorithm to the table in the Printed Answer Book. Start by crossing out the row for \(A\) and choosing an entry from the column for \(A\). Write down the arcs used in the order that they are chosen. Draw the resulting minimum spanning tree and give its total weight.
OCR D1 2016 June Q2
2 Shaun measured the mass, in kg, of each of 9 filled bags. He then used an algorithm to sort the masses into increasing order. Shaun's list after the first pass through the sorting algorithm is given below. $$\begin{array} { l l l l l l l l l } 32 & 41 & 22 & 37 & 53 & 43 & 29 & 15 & 26 \end{array}$$
  1. Explain how you know that Shaun did not use bubble sort. In fact, Shaun used shuttle sort, starting at the left-hand end of the list.
  2. Write down the two possibilities for the original list.
  3. Write down the list after the second pass through the shuttle sort algorithm.
  4. How many passes through shuttle sort were needed to sort the entire list? Shaun's sorted list is given below. $$\begin{array} { l l l l l l l l l } 15 & 22 & 26 & 29 & 32 & 37 & 41 & 43 & 53 \end{array}$$ Shaun wants to pack the bags into bins, each of which can hold a maximum of 100 kg .
  5. Write the list in decreasing order of mass and then apply the first-fit decreasing method to decide how to pack the bags into bins. Write the weights of the bags in each bin in the order that they are put into the bin.
  6. Find a way to pack all the bags using only 3 bins, each of which can hold a maximum of 100 kg .
OCR D1 2016 June Q3
3 A problem to maximise \(P\) as a function of \(x , y\) and \(z\) is represented by the initial Simplex tableau below.
\(P\)\(x\)\(y\)\(z\)\(s\)\(t\)RHS
1- 1023000
050- 51060
043001100
  1. Write down \(P\) as a function of \(x , y\) and \(z\).
  2. Write down the constraints as inequalities involving \(x , y\) and \(z\).
  3. Carry out one iteration of the Simplex algorithm. After a second iteration of the Simplex algorithm the tableau is as given below.
    \(P\)\(x\)\(y\)\(z\)\(s\)\(t\)RHS
    107.2500.61.75211
    010.75000.2525
    000.751- 0.20.2513
  4. Explain how you know that the optimal solution has been achieved.
  5. Write down the values of \(x , y\) and \(z\) that maximise \(P\). Write down the optimal value of \(P\).
OCR D1 2016 June Q4
4 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. Molly says that she has drawn a graph with exactly five vertices, having vertex orders 1, 2, 3, 4 and 5.
  1. State how you know that Molly is wrong. Holly has drawn a connected graph with exactly six vertices, having vertex orders 2, 2, 2, 2, 4 and 6.
  2. (a) Explain how you know that Holly’s graph is not simply connected.
    (b) Determine whether Holly's graph is Eulerian, semi-Eulerian or neither, explaining how you know which of these it is. Olly has drawn a simply connected graph with exactly six vertices.
  3. (a) State the minimum possible value of the sum of the vertex orders in Olly's graph.
    (b) If Olly's graph is also Eulerian, what numerical values can the vertex orders take? Polly has drawn a simply connected Eulerian graph with exactly six vertices and exactly ten arcs.
  4. (a) What can you deduce about the vertex orders in Polly's graph?
    (b) Draw a graph that fits the description of Polly's graph.
OCR D1 2016 June Q5
5 The network below represents a single-track railway system. The vertices represent stations, the arcs represent railway tracks and the weights show distances in km. The total length of the arcs shown is 60 km .
\includegraphics[max width=\textwidth, alt={}, center]{d783915d-5950-4a97-b6a0-70959214e218-5_442_1152_429_459}
  1. Apply Dijkstra's algorithm to the network, starting at \(G\), to find the shortest distance (in km ) from \(G\) to \(N\) and write down the route of this shortest path. Greg wants to travel from the station represented by vertex \(G\) to the station represented by vertex \(N\). He especially wants to include the track \(K L\) (in either direction) in his journey.
  2. Show how to use your working from part (i) to find the shortest journey that Greg can make that fulfils his requirements. Write down his route. Percy Li needs to check each track to see if any maintenance is required. He wants to start and end at the station represented by vertex \(G\) and travel in one continuous route that passes along each track at least once. The direction of travel along the tracks does not matter.
  3. Apply the route inspection algorithm, showing your working, to find the minimum distance that Percy will need to travel. Write down those arcs that Percy will need to repeat. If he travels this minimum distance, how many times will Percy travel through the station represented by vertex \(L\) ?
OCR D1 2016 June Q6
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).
OCR D1 2016 June Q7
7 A tour guide wants to find a route around eight places of interest: Queen Elizabeth Olympic Park ( \(Q\) ), Royal Albert Hall ( \(R\) ), Statue of Eros ( \(S\) ), Tower Bridge ( \(T\) ), Westminster Abbey ( \(W\) ), St Paul's Cathedral ( \(X\) ), York House ( \(Y\) ) and Museum of Zoology ( \(Z\) ). The table below shows the travel times, in minutes, from each of the eight places to each of the other places.
\(Q\)\(R\)S\(T\)W\(X\)\(Y\)\(Z\)
\(Q\)-30352537404332
\(R\)30-12151520208
S3512-2010182516
\(T\)251520-12161818
W37151012-81420
\(X\)402018168-1722
\(Y\)432025181417-13
Z3281618202213-
  1. Use the nearest neighbour method to find an upper bound for the minimum time to travel to each of the eight places, starting and finishing at \(Y\). Write down the route and give the time in minutes.
  2. The Answer Book lists the arcs by increasing order of weight (reading across the rows). Apply Kruskal's algorithm to this list to find the minimum spanning tree for all eight places. Draw your tree and give its total weight.
  3. (a) Vertex \(Q\) and all arcs joined to \(Q\) are temporarily removed. Use your answer to part (ii) to write down the weight of the minimum spanning tree for the seven vertices \(R , S , T , W , X , Y\) and \(Z\).
    (b) Use your answer to part (iii)(a) to find a lower bound for the minimum time to travel to each of the eight places of interest, starting and finishing at \(Y\). The tour guide allows for a 5 -minute stop at each of \(S\) and \(Y\), a 10 -minute stop at \(T\) and a 30 -minute stop at each of \(Q , R , W , X\) and \(Z\). The tour guide wants to find a route, starting and ending at \(Y\), in which the tour (including the stops) can be completed in five hours (300 minutes).
  4. Use the nearest neighbour method, starting at \(Q\), to find a closed route through each vertex. Hence find a route for the tour, showing that it can be completed in time.
OCR D1 Specimen Q1
1 The graph \(\mathrm { K } _ { 5 }\) has five nodes, \(A , B , C , D\) and \(E\), and there is an arc joining every node to every other node.
  1. Draw the graph \(\mathrm { K } _ { 5 }\) and state how you know that it is Eulerian.
  2. By listing the arcs involved, give an example of a path in \(\mathrm { K } _ { 5 }\). (Your path must include more than one arc.)
  3. By listing the arcs involved, give an example of a cycle in \(\mathrm { K } _ { 5 }\).
OCR D1 Specimen Q2
2 This question is about a simply connected network with at least three arcs joining 4 nodes. The weights on the arcs are all different and any direct paths always have a smaller weight than the total weight of any indirect paths between two vertices.
  1. Kruskal's algorithm is used to construct a minimum connector. Explain why the arcs with the smallest and second smallest weights will always be included in this minimum connector.
  2. Draw a diagram to show that the arc with the third smallest weight need not always be included in a minimum connector.
OCR D1 Specimen Q3
3
  1. Use the shuttle sort algorithm to sort the list $$\begin{array} { l l l l l } 6 & 3 & 8 & 3 & 2 \end{array}$$ into increasing order. Write down the list that results from each pass through the algorithm.
  2. Shuttle sort is a quadratic order algorithm. Explain briefly what this statement means.
OCR D1 Specimen Q4
4 [Answer this question on the insert provided.]
An algorithm involves the following steps.
Step 1: Input two positive integers, \(A\) and \(B\).
Let \(C = 0\)
Step 2: If \(B\) is odd, replace \(C\) by \(C + A\).
Step 3: If \(B = 1\), go to step 6.
Step 4: Replace \(A\) by \(2 A\).
If \(B\) is even, replace \(B\) by \(B \div 2\), otherwise replace \(B\) by ( \(B - 1\) ) ÷ 2 .
Step 5: Go back to step 2.
Step 6: Output the value of \(C\).
  1. Demonstrate the use of the algorithm for the inputs \(A = 6\) and \(B = 13\).
  2. When \(B = 8\), what is the output in terms of \(A\) ? What is the relationship between the output and the original inputs?
OCR D1 Specimen Q5
5 [Answer this question on the insert provided.]
\includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-3_659_1002_324_609} In this network the vertices represent towns, the arcs represent roads and the weights on the arcs show the shortest distances in kilometres.
  1. The diagram on the insert shows the result of deleting vertex \(F\) and all the arcs joined to \(F\). Show that a lower bound for the length of the travelling salesperson problem on the original network is 38 km . The corresponding lower bounds by deleting each of the other vertices are: $$A : 40 \mathrm {~km} , \quad B : 39 \mathrm {~km} , \quad C : 35 \mathrm {~km} , \quad D : 37 \mathrm {~km} , \quad E : 35 \mathrm {~km} \text {. }$$ The route \(A - B - C - D - E - F - A\) has length 47 km .
  2. Using only this information, what are the best upper and lower bounds for the length of the solution to the travelling salesperson problem on the network?
  3. By considering the orders in which vertices \(C , D\) and \(E\) can be visited, find the best upper bound given by a route of the form \(A - B - \ldots - F - A\).
OCR D1 Specimen Q6
6 [Answer part (i) of this question on the insert provided.]
The diagram shows a simplified version of an orienteering course. The vertices represent checkpoints and the weights on the arcs show the travel times between checkpoints, in minutes.
\includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-4_483_931_461_630}
  1. Use Dijkstra's algorithm, starting from checkpoint \(\boldsymbol { A }\), to find the least travel time from \(A\) to \(D\). You must show your working, including temporary labels, permanent labels and the order in which permanent labels were assigned. Give the route that takes the least time from \(A\) to \(D\).
  2. By using an appropriate algorithm, find the least time needed to travel every arc in the diagram starting and ending at \(A\). You should show your method clearly.
  3. Starting from \(A\), apply the nearest neighbour algorithm to the diagram to find a cycle that visits every checkpoint. Use your solution to find a path that visits every checkpoint, starting from \(A\) and finishing at \(D\).
OCR D1 Specimen Q7
7 Consider the linear programming problem: $$\begin{array} { l l } \text { maximise } & P = 4 y - x ,
\text { subject to } & x + 4 y \leqslant 22 ,
& x + y \leqslant 10 ,
& - x + 2 y \leqslant 8 ,
\text { and } & x \geqslant 0 , y \geqslant 0 . \end{array}$$
  1. Represent the constraints graphically, shading out the regions where the inequalities are not satisfied. Calculate the value of \(x\) and the value of \(y\) at each of the vertices of the feasible region. Hence find the maximum value of \(P\), clearly indicating where it occurs.
  2. By introducing slack variables, represent the problem as an initial Simplex tableau and use the Simplex algorithm to solve the problem.
  3. Indicate on your diagram for part (i) the points that correspond to each stage of the Simplex algorithm carried out in part (ii). \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, 5 and 6
    Specimen Paper
    • This insert should be used to answer Questions 4, 5 and 6
    • .
    • Write your Name, Centre Number and Candidate Number in the spaces provided at the top of this page.
    • Write your answers to Questions 4, 5 and 6
    • in the spaces provided in this insert, and attach it to your answer booklet.
    4
  4. STEPA\(B\)C
    1
    2
  5. STEPA\(B\)C
    1
    2
    5

  6. \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-7_661_1004_285_557}
  7. Upper bound = \(\_\_\_\_\) km Lower bound = \(\_\_\_\_\) km
  8. \(\_\_\_\_\)
    Best upper bound = \(\_\_\_\_\) km 6

  9. \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-8_668_1406_292_406}
    \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-8_307_1342_1014_424}
    Least travel time = \(\_\_\_\_\) minutes Route: A- \(\_\_\_\_\) \(- D\)
OCR D1 2006 June Q6
  1. Calculate the shortest distance that the mole must travel if it starts and ends at vertex \(A\).
  2. The pipe connecting \(B\) to \(H\) is removed for repairs. By considering every possible pairing of odd vertices, and showing your working clearly, calculate the shortest distance that the mole must travel to pass along each pipe on this reduced network, starting and finishing at \(A\).
OCR D1 2006 January Q1
1 Answer this question on the insert provided.
\includegraphics[max width=\textwidth, alt={}]{8f17020a-14bf-4459-9241-1807b954a629-2_956_1203_349_493}
This diagram shows a network. The insert has a copy of this network together with a list of the arcs, sorted into increasing order of weight. Use Kruskal's algorithm on the insert to find a minimum spanning tree for this network. Draw your tree and give its total weight.
OCR D1 2006 January Q2
2 Answer this question on the insert provided.
\includegraphics[max width=\textwidth, alt={}]{8f17020a-14bf-4459-9241-1807b954a629-2_659_1136_1720_530}
This diagram shows part of a network. There are other arcs connecting \(D\) and \(E\) to other parts of the network. Apply Dijkstra's algorithm starting from \(A\), as far as you are able, showing your working. Note: you will not be able to give permanent labels to all the vertices shown.
OCR D1 2007 January Q5
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.
OCR D1 2009 January Q3
3 Answer this question on the insert provided. \includegraphics[max width=\textwidth, alt={}, center]{43fe5fd5-4b98-4c3a-90ca-a1bd5cf065fe-3_492_1006_356_568}
  1. This diagram shows a network. The insert has a copy of this network together with a list of the arcs, sorted into increasing order of weight. Use Kruskal's algorithm on the insert to find a minimum spanning tree for this network. Draw your tree and give its total weight.
  2. Use your answer to part (i) to find the weight of a minimum spanning tree for the network with vertex \(E\), and all the arcs joined to \(E\), removed. Hence find a lower bound for the travelling salesperson problem on the original network.
  3. Show that the nearest neighbour method, starting from vertex \(A\), fails on the original network.
  4. Apply the nearest neighbour method, starting from vertex \(B\), to find an upper bound for the travelling salesperson problem on the original network.
  5. Apply Dijkstra's algorithm to the copy of the network in the insert to find the least weight path from \(A\) to \(G\). State the weight of the path and give its route.
  6. The sum of the weights of all the arcs is 300 . 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. The weights of least weight paths from vertex \(A\) should be found using your answer to part (v); the weights of other such paths should be determined by inspection.
OCR D1 2009 January Q4
2 marks
4 Answer this question on the insert provided. The list of numbers below is to be sorted into decreasing order using shuttle sort. $$\begin{array} { l l l l l l l l l } 21 & 76 & 65 & 13 & 88 & 62 & 67 & 28 & 34 \end{array}$$
  1. How many passes through shuttle sort will be required to sort the list? After the first pass the list is as follows. $$\begin{array} { l l l l l l l l l } 76 & 21 & 65 & 13 & 88 & 62 & 67 & 28 & 34 \end{array}$$
  2. State the number of comparisons and the number of swaps that were made in the first pass.
  3. Write down the list after the second pass. State the number of comparisons and the number of swaps that were used in making the second pass.
  4. Complete the table in the insert to show the results of the remaining passes, recording the number of comparisons and the number of swaps made in each pass. You may not need all the rows of boxes printed. When the original list is sorted into decreasing order using bubble sort there are 30 comparisons and 17 swaps.
  5. Use your results from part (iv) to compare the efficiency of these two methods in this case. Katie makes and sells cookies. Each batch of plain cookies takes 8 minutes to prepare and then 12 minutes to bake. Each batch of chocolate chip cookies takes 12 minutes to prepare and then 12 minutes to bake. Each batch of fruit cookies takes 10 minutes to prepare and then 12 minutes to bake. Katie can only bake one batch at a time. She has the use of the kitchen, including the oven, for at most 1 hour.
    [0pt]
  6. Each batch of cookies must be prepared before it is baked. By considering the maximum time available for baking the cookies, explain why Katie can make at most 4 batches of cookies. [2] Katie models the constraints as $$\begin{gathered} x + y + z \leqslant 4
    4 x + 6 y + 5 z \leqslant 24
    x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{gathered}$$ where \(x\) is the number of batches of plain cookies, \(y\) is the number of batches of chocolate chip cookies and \(z\) is the number of batches of fruit cookies that Katie makes.
  7. Each batch of cookies that Katie prepares must be baked within the hour available. By considering the maximum time available for preparing the cookies, show how the constraint \(4 x + 6 y + 5 z \leqslant 24\) was formed.
  8. In addition to the constraints, what other restriction is there on the values of \(x , y\) and \(z\) ? Katie will make \(\pounds 5\) profit on each batch of plain cookies, \(\pounds 4\) on each batch of chocolate chip cookies and \(\pounds 3\) on each batch of fruit cookies that she sells. Katie wants to maximise her profit.
  9. Write down an expression for the objective function to be maximised. State any assumption that you have made.
  10. Represent Katie's problem as an initial Simplex tableau. Perform one iteration of the Simplex algorithm, choosing to pivot on an element from the \(x\)-column. Show how each row was obtained. Write down the number of batches of cookies of each type and the profit at this stage. After carrying out market research, Katie decides that she will not make fruit cookies. She also decides that she will make at least twice as many batches of chocolate chip cookies as plain cookies.
  11. Represent the constraints for Katie's new problem graphically and calculate the coordinates of the vertices of the feasible region. By testing suitable integer-valued coordinates, find how many batches of plain cookies and how many batches of chocolate chip cookies Katie should make to maximise her profit. Show your working.
OCR D1 2010 January Q1
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.
OCR D1 2007 June Q5
5 Answer this question on the insert provided. The network below represents a simplified map of a building. The arcs represent corridors and the weights on the arcs represent the lengths of the corridors, in metres. The sum of the weights on the arcs is 765 metres.
\includegraphics[max width=\textwidth, alt={}, center]{dbf782dd-879c-4f0f-b532-246a0db9f130-5_1271_1539_584_303}
  1. Janice is the cleaning supervisor in the building. She is at the position marked as J when she is called to attend a cleaning emergency at B. On the network in the insert, use Dijkstra's algorithm, starting from vertex J and continuing until B is given a permanent label, to find the shortest path from J to B and the length of this path.
  2. In her job J anice has to walk along each of the corridors represented on the network. This requires finding a route that covers every arc at least once, starting and ending at J. Showing all your working, find the shortest distance that J anice must walk to check all the corridors. The labelled vertices represent 'cleaning stations'. J anice wants to visit every cleaning station using the shortest possible route. She produces a simplified network with no repeated arcs and no arc that joins a vertex to itself.
  3. On the insert, complete Janice's simplified network. Which standard network problem does Janice need to solve to find the shortest distance that she must travel?
OCR D1 2007 June Q6
6 Answer this question on the insert provided. The table shows the distances, in miles, along the direct roads between six villages, \(A\) to \(F\). A dash ( - ) indicates that there is no direct road linking the villages.
ABCDEF
A-63---
B6-56-14
C35-8410
D-68-38
E--43--
F-14108--
  1. On the table in the insert, use Prim's algorithm 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. Draw your minimum spanning tree and state its total weight.
  2. By deleting vertex B and the arcs joined to vertex B, calculate a lower bound for the length of the shortest cycle through all the vertices.
  3. A pply the nearest neighbour method to the table above, starting from \(F\), to find a cycle that passes through every vertex and use this to write down an upper bound for the length of the shortest cycle through all the vertices.
    \href{http://physicsandmathstutor.com}{physicsandmathstutor.com}
OCR D1 2009 June Q4
4 Answer this question on the insert provided. The vertices in the network below represent the junctions between main roads near Ayton ( \(A\) ). The arcs represent the roads and the weights on the arcs represent distances in miles.
\includegraphics[max width=\textwidth, alt={}, center]{fe06fa02-9f5d-4082-8e96-feea705d3fa2-4_812_1198_443_475}
  1. On the diagram in the insert, use Dijkstra's algorithm to find the shortest path from \(A\) to \(H\). You must show your working, including temporary labels, permanent labels and the order in which permanent labels are assigned. Write down the route of the shortest path from \(A\) to \(H\) and give its length in miles. Simon is a highways surveyor. He needs to check that there are no potholes in any of the roads. He will start and end at Ayton.
  2. Which standard network problem does Simon need to solve to find the shortest route that uses every arc? The total weight of all the arcs is 67.5 miles.
  3. Use an appropriate algorithm to find the length of the shortest route that Simon can use. Show all your working. (You may find the lengths of shortest paths between nodes by using your answer to part (i) or by inspection.) Suppose that, instead, Simon wants to find the shortest route that uses every arc, starting from \(A\) and ending at \(H\).
  4. Which arcs does Simon need to travel twice? What is the length of the shortest route that he can use? There is a set of traffic lights at each junction. Simon's colleague Amber needs to check that all the traffic lights are working correctly. She will start and end at the same junction.
  5. Show that the nearest neighbour method fails on this network if it is started from \(A\).
  6. Apply the nearest neighbour method starting from \(C\) to find an upper bound for the distance that Amber must travel.
  7. Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting node \(A\) and all the arcs that are directly joined to node \(A\). Start building your tree at node B. (You do not need to represent the network as a matrix.) Mark the arcs in your tree on the diagram in the insert. Give the order in which nodes are added to your tree and calculate the total weight of your tree. Hence find a lower bound for the distance that Amber must travel.