Questions D1 (899 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
Edexcel D1 2003 November Q7
7. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 6} \includegraphics[alt={},max width=\textwidth]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-10_1018_1557_342_214}
\end{figure} Figure 6 shows a capacitated, directed network of pipes flowing from two oil fields \(\mathrm { F } _ { 1 }\) and \(\mathrm { F } _ { 2 }\) to three refineries \(\mathrm { R } _ { 1 } , \mathrm { R } _ { 2 }\) and \(\mathrm { R } _ { 3 }\). The number on each arc represents the capacity of the pipe and the numbers in the circles represent a possible flow of 65.
  1. Find the value of \(x\) and the value of \(y\).
  2. On Diagram 1 in the answer book, add a supersource and a supersink, and arcs showing their minimum capacities.
  3. Taking the given flow of 65 as the initial flow pattern, use the labelling procedure on Diagram 2 to find the maximum flow. State clearly your flow augmenting routes.
  4. Show the maximum flow on Diagram 3 and write down its value.
  5. Verify that this is the maximum flow by finding a cut equal to the flow.
Edexcel D1 2003 November Q8
8. A company makes three sizes of lamps, small, medium and large. The company is trying to determine how many of each size to make in a day, in order to maximise its profit. As part of the process the lamps need to be sanded, painted, dried and polished. A single machine carries out these tasks and is available 24 hours per day. A small lamp requires one hour on this machine, a medium lamp 2 hours and a large lamp 4 hours. Let \(x =\) number of small lamps made per day, $$\begin{aligned} & y = \text { number of medium lamps made per day, }
& z = \text { number of large lamps made per day, } \end{aligned}$$ where \(x \geq 0 , y \geq 0\) and \(z \geq 0\).
  1. Write the information about this machine as a constraint.
    1. Re-write your constraint from part (a) using a slack variable \(s\).
    2. Explain what \(s\) means in practical terms. Another constraint and the objective function give the following Simplex tableau. The profit \(P\) is stated in euros.
      Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)Value
      \(r\)3561050
      \(s\)1240124
      \(P\)- 1- 3- 4000
  3. Write down the profit on each small lamp.
  4. Use the Simplex algorithm to solve this linear programming problem.
  5. Explain why the solution to part (d) is not practical.
  6. Find a practical solution which gives a profit of 30 euros. Verify that it is feasible.
Edexcel D1 2004 November Q1
1. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{4bbe6272-3900-42de-b287-599638ca75e4-02_753_1575_486_255}
\end{figure} Figure 1 shows a directed, capacitated network where the number on each arc is its capacity. A possible flow is shown from \(S\) to \(T\) and the value in brackets on each arc is the flow in that arc.
  1. Find the values of \(x , y\) and \(z\).
  2. Find, by inspection, the maximal flow from \(S\) to \(T\) and verify that it is maximal.
    (2)
Edexcel D1 2004 November Q2
2. (a) Define the following terms
  1. planar graph,
  2. Hamiltonian cycle.
    (b) (i) Draw a graph of \(\mathrm { K } _ { 3,2 }\) in such a way as to show that it is planar.
  3. Explain why the planarity algorithm cannot be used when drawing \(\mathrm { K } _ { 3,2 }\) as a planar graph.
Edexcel D1 2004 November Q3
3. Six newspaper reporters Asif (A), Becky (B), Chris (C), David (D), Emma (E) and Fred (F), are to be assigned to six news stories Business (1), Crime (2), Financial (3), Foreign (4), Local (5) and Sport (6). The table shows possible allocations of reporters to news stories. For example, Chris can be assigned to any one of stories 1, 2 or 4.
123456
A\(\checkmark\)
B\(\checkmark\)\(\checkmark\)
C\(\checkmark\)\(\checkmark\)\(\checkmark\)
D\(\checkmark\)
E\(\checkmark\)\(\checkmark\)\(\checkmark\)
F\(\checkmark\)
  1. Show these possible allocations on the bipartite graph on the diagram in the answer book. A possible matching is
    A to 5,
    C to 1 ,
    E to 6,
    F to 4
  2. Show this information, in a distinctive way, on the diagram in the answer book.
    (1)
  3. Use an appropriate algorithm to find a maximal matching. You should list any alternating paths you have used.
  4. Explain why it is not possible to find a complete matching.
Edexcel D1 2004 November Q4
4. \(45 , \quad 56 , \quad 37 , \quad 79 , \quad 46 , \quad 18 , \quad 90 , \quad 81 , \quad 51\)
  1. Using the quick sort algorithm, perform one complete iteration towards sorting these numbers into ascending order.
    (2)
  2. Using the bubble sort algorithm, perform one complete pass towards sorting the original list into descending order. Another list of numbers, in ascending order, is $$7 , \quad 23 , \quad 31 , \quad 37 , \quad 41 , \quad 44 , \quad 50 , \quad 62 , \quad 71 , \quad 73 , \quad 94$$
  3. Use the binary search algorithm to locate the number 73 in this list. \section*{5.} \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{4bbe6272-3900-42de-b287-599638ca75e4-06_1246_1168_294_427}
    \end{figure} Figure 2 shows a network of roads connecting villages. The length of each road, in km, is shown. Village \(B\) has only a small footbridge over the river which runs through the village. It can be accessed by two roads, from \(A\) and \(D\). The driver of a snowplough, based at \(F\), is planning a route to enable her to clear all the roads of snow. The route should be of minimum length. Each road can be cleared by driving along it once. The snowplough cannot cross the footbridge. Showing all your working and using an appropriate algorithm,
Edexcel D1 2004 November Q8
8. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{4bbe6272-3900-42de-b287-599638ca75e4-10_1042_1847_335_115}
\end{figure} The network in Figure 5 shows activities that need to be undertaken in order to complete a project. Each activity is represented by an arc. The number in brackets is the duration of the activity in hours. The early and late event times are shown at each node. The project can be completed in 24 hours.
  1. Find the values of \(x , y\) and \(z\).
  2. Explain the use of the dummy activity in Figure 5.
  3. List the critical activities.
  4. Explain what effect a delay of one hour to activity \(B\) would have on the time taken to complete the whole project. The company which is to undertake this project has only two full time workers available. The project must be completed in 24 hours and in order to achieve this, the company is prepared to hire additional workers at a cost of \(\pounds 28\) per hour. The company wishes to minimise the money spent on additional workers. Any worker can undertake any task and each task requires only one worker.
  5. Explain why the company will have to hire additional workers in order to complete the project in 24 hours.
  6. Schedule the tasks to workers so that the project is completed in 24 hours and at minimum cost to the company.
  7. State the minimum extra cost to the company.
Edexcel D1 2002 January Q3
  1. State the number of edges in a minimum spanning tree for \(N\). A minimum spanning tree for a connected network has \(n\) edges.
  2. State the number of vertices in the network. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{2f4d2383-823a-4a6f-ad4b-69cf01566052-4_714_1129_380_476}
    \end{figure} Figure 1 shows a network of roads. Erica wishes to travel from \(A\) to \(L\) as quickly as possible. The number on each edge gives the time, in minutes, to travel along that road.
  3. Use Dijkstra's algorithm to find a quickest route from \(A\) to \(L\). Complete all the boxes on the answer sheet and explain clearly how you determined the quickest route from your labelling.
  4. Show that there is another route which also takes the minimum time
Edexcel D1 2004 January Q2
  1. State, giving your reason, whether this tableau represents the optimal solution.
  2. State the values of every variable.
  3. Calculate the profit made on each unit of \(y\). \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{a21a4565-800c-45c0-a513-bb813ef1086f-3_1193_1689_420_201}
    \end{figure} Figure 1 shows a network of roads represented by arcs. The capacity of the road represented by that arc is shown on each arc. The numbers in circles represent a possible flow of 26 from \(B\) to \(L\). Three cuts \(\mathrm { C } _ { 1 } , \mathrm { C } _ { 2 }\) and \(\mathrm { C } _ { 3 }\) are shown on Fig. 1.
  4. Find the capacity of each of the three cuts.
  5. Verify that the flow of 26 is maximal. The government aims to maximise the possible flow from \(B\) to \(L\) by using one of two options.
    Option 1: Build a new road from \(E\) to \(J\) with capacity 5 .
    or
    Option 2: Build a new road from \(F\) to \(H\) with capacity 3.
  6. By considering both options, explain which one meets the government's aim
    (3) \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{a21a4565-800c-45c0-a513-bb813ef1086f-4_780_1002_358_486}
    \end{figure} An engineer needs to check the state of a number of roads to see whether they need resurfacing. The roads that need to be checked are represented by the arcs in Fig. 2. The number on each arc represents the length of that road in km. To check all the roads, he needs to travel along each road at least once. He wishes to minimise the total distance travelled. The engineer's office is at \(G\), so he starts and ends his journey at \(G\).
  7. Use an appropriate algorithm to find a route for the engineer to follow. State your route and its length.
    (6) The engineer lives at \(D\). He believes he can reduce the distance travelled by starting from home and inspecting all the roads on the way to his office at \(G\).
  8. State whether the engineer is correct in his belief. If so, calculate how much shorter his new route is. If not, explain why not.
    (3)
    \includegraphics[max width=\textwidth, alt={}, center]{a21a4565-800c-45c0-a513-bb813ef1086f-5_1561_1568_347_178} Figure 3 describes an algorithm in the form of a flow chart, where \(a\) is a positive integer. List \(P\), which is referred to in the flow chart, comprises the prime numbers \(2,3,5,7,11,13\), 17, ...
  9. Starting with \(a = 90\), implement this algorithm. Show your working in the table in the answer book.
  10. Explain the significance of the output list.
  11. Write down the final value of \(c\) for any initial value of \(a\).
Edexcel D1 2002 June Q4
  1. Use Dijkstra's algorithm to find the shortest route from \(A\) to \(I\). Show all necessary working in the boxes in the answer booklet and state your shortest route and its length.
    (5) The park warden wishes to check each of the paths to check for frost damage. She has to cycle along each path at least once, starting and finishing at \(A\).
    1. Use an appropriate algorithm to find which paths will be covered twice and state these paths.
    2. Find a route of minimum length.
    3. Find the total length of this shortest route.
      (5)
Edexcel D1 2002 November Q4
  1. Use the Route Inspection algorithm to find which paths, if any, need to be traversed twice. It is decided to start the inspection at node \(C\). The inspection must still traverse each pipe at least once but may finish at any node.
  2. Explaining your reasoning briefly, determine the node at which the inspection should finish if the route is to be minimised. State the length of your route.
    (3)
Edexcel D1 2004 November Q5
  1. find the route the driver should follow, starting and ending at \(F\), to clear all the roads of snow. Give the length of this route. The local authority decides to build a road bridge over the river at \(B\). The snowplough will be able to cross the road bridge.
  2. Reapply the algorithm to find the minimum distance the snowplough will have to travel (ignore the length of the new bridge). \section*{6.} \section*{Figure 3}
    \includegraphics[max width=\textwidth, alt={}]{4bbe6272-3900-42de-b287-599638ca75e4-07_1131_1118_347_502}
    Peter wishes to minimise the time spent driving from his home \(H\), to a campsite at \(G\). Figure 3 shows a number of towns and the time, in minutes, taken to drive between them. The volume of traffic on the roads into \(G\) is variable, and so the length of time taken to drive along these roads is expressed in terms of \(x\), where \(x \geq 0\).
  3. On the diagram in the answer book, use Dijkstra's algorithm to find two routes from \(H\) to \(G\) (one via \(A\) and one via \(B\) ) that minimise the travelling time from \(H\) to \(G\). State the length of each route in terms of \(x\).
  4. Find the range of values of \(x\) for which Peter should follow the route via \(A\). \section*{7.} \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{4bbe6272-3900-42de-b287-599638ca75e4-08_1495_1335_322_392}
    \end{figure} The company EXYCEL makes two types of battery, X and Y . Machinery, workforce and predicted sales determine the number of batteries EXYCEL make. The company decides to use a graphical method to find its optimal daily production of X and Y . The constraints are modelled in Figure 4 where $$\begin{aligned} & x = \text { the number (in thousands) of type } \mathrm { X } \text { batteries produced each day, }
    & y = \text { the number (in thousands) of type } \mathrm { Y } \text { batteries produced each day. } \end{aligned}$$ The profit on each type X battery is 40 p and on each type Y battery is 20 p . The company wishes to maximise its daily profit.
  5. Write this as a linear programming problem, in terms of \(x\) and \(y\), stating the objective function and all the constraints.
  6. Find the optimal number of batteries to be made each day. Show your method clearly.
  7. Find the daily profit, in \(\pounds\), made by EXYCEL.
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 MEI D1 2006 January Q2
  1. Complete the table in the insert showing the outcome of applying the algorithm to the following two lists: $$\begin{array} { l r l l l l l } \text { List 1: } & 2 , & 34 , & 35 , & 56 & &
    \text { List 2: } & 13 , & 22 , & 34 , & 81 , & 90 , & 92 \end{array}$$
  2. What does the algorithm achieve?
  3. How many comparisons did you make in applying the algorithm?
  4. If the number of elements in List 1 is \(x\), and the number of elements in List 2 is \(y\), what is the maximum number of comparisons that will have to be made in applying the algorithm, and what is the minimum number?
Edexcel D1 Q6
  1. Draw a bipartite graph to model this situation. Initially it is decided to run the Office application on computer \(F\), Animation on computer \(H\), and Data on computer \(I\).
  2. Starting from this matching, use the maximum matching algorithm to find a complete matching. Indicate clearly how the algorithm has been applied.
  3. Computer \(H\) is upgraded to allow it to run CAD. Find an alternative matching to that found in part (b).
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.
OCR MEI D1 Q2
2 Answer this question on the insert provided.
  1. Use Dijkstra's algorithm to find the least weight route from A to G in the network shown in Fig. 2.1. Show the order in which you label vertices, give the route and its weight. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{5d8d35b7-e4ba-4bc0-93a1-0cae58093a02-003_458_586_525_758} \captionsetup{labelformat=empty} \caption{Fig. 2.1}
    \end{figure}
  2. Fig. 2.2 shows a partially completed application of Kruskal's algorithm to find a minimum spanning tree for the network. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{5d8d35b7-e4ba-4bc0-93a1-0cae58093a02-003_417_524_1309_786} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
    \end{figure} Complete the algorithm and give the total weight of your minimum spanning tree.