Questions — Edexcel D1 (480 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 2008 June Q6
6. The tableau below is the initial tableau for a maximising linear programming problem in \(x , y\) and \(z\).
Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)4\(\frac { 7 } { 3 }\)\(\frac { 5 } { 2 }\)10064
\(s\)13001016
\(t\)42200160
\(P\)-5\(\frac { - 7 } { 2 }\)-40000
  1. Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the simplex algorithm. State the row operations you use.
    (9)
  2. Explain how you know that your solution is not optimal.
    (1)
Edexcel D1 2008 June Q7
7. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{be646775-535e-4105-86b4-ffc7eda4fa51-7_769_1385_262_342} \captionsetup{labelformat=empty} \caption{Figure 6}
\end{figure} The network in Figure 6 shows the activities that need to be undertaken to complete a building project. Each activity is represented by an arc. The number in brackets is the duration of the activity in days. The early and late event times are shown at each vertex.
  1. Find the values of \(v , w , x , y\) and \(z\).
  2. List the critical activities.
  3. Calculate the total float on each of activities H and J .
  4. Draw a cascade (Gantt) chart for the project. The engineer in charge of the project visits the site at midday on day 8 and sees that activity E has not yet been started.
  5. Determine if the project can still be completed on time. You must explain your answer. Given that each activity requires one worker and that the project must be completed in 35 days,
  6. use your cascade chart to determine a lower bound for the number of workers needed. You must justify your answer.
Edexcel D1 2008 June Q8
8. Class 8 B has decided to sell apples and bananas at morning break this week to raise money for charity. The profit on each apple is 20 p , the profit on each banana is 15 p . They have done some market research and formed the following constraints.
  • They will sell at most 800 items of fruit during the week.
  • They will sell at least twice as many apples as bananas.
  • They will sell between 50 and 100 bananas.
Assuming they will sell all their fruit, formulate the above information as a linear programming problem, letting \(a\) represent the number of apples they sell and \(b\) represent the number of bananas they sell. Write your constraints as inequalities.
(Total 7 marks)
Edexcel D1 2010 June Q2
2. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{50925a06-9a9b-4e50-869a-2dce6680615c-03_741_1200_212_434} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} Figure 1 represents the distances, in metres, between eight vertices, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H , in a network.
  1. Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
  2. Complete Matrix 1 in your answer book, to represent the network.
  3. Starting at A, use Prim's algorithm to determine a minimum spanning tree. You must clearly state the order in which you considered the vertices and the order in which you included the arcs.
  4. State the weight of the minimum spanning tree.
Edexcel D1 2010 June Q4
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{50925a06-9a9b-4e50-869a-2dce6680615c-05_906_1105_239_479} \captionsetup{labelformat=empty} \caption{Figure 2
[0pt] [The total weight of the network is 73.3 km ]}
\end{figure} Figure 2 models a network of tunnels that have to be inspected. The number on each arc represents the length, in km , of that tunnel.
Malcolm needs to travel through each tunnel at least once and wishes to minimise the length of his inspection route.
He must start and finish at A.
  1. Use the route inspection algorithm to find the tunnels that will need to be traversed twice. You should make your method and working clear.
    (5)
  2. Find a route of minimum length, starting and finishing at A . State the length of your route.
    (3) A new tunnel, CG, is under construction. It will be 10 km long.
    Malcolm will have to include the new tunnel in his inspection route.
  3. What effect will the new tunnel have on the total length of his route? Justify your answer.
    (2)
Edexcel D1 2010 June Q5
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{50925a06-9a9b-4e50-869a-2dce6680615c-06_753_616_246_296} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{50925a06-9a9b-4e50-869a-2dce6680615c-06_751_606_248_1169} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} Figure 3 shows the possible allocations of six people, Amelia, Charlie, Ellie, Gemma, Jimmy and Saskia, to six tasks, 1, 2, 3, 4, 5 and 6.
Figure 4 shows an initial matching.
  1. Use the maximum matching algorithm once to find an improved matching. You must state the alternating path used and your improved matching.
  2. Explain why a complete matching is not possible. After training, Jimmy can be assigned to tasks 4 or 5 and Ellie to tasks 2, 3, 5 or 6.
  3. Starting with your current maximal matching, use the maximum matching algorithm to obtain a complete matching. You must state the alternating path used and your final matching.
Edexcel D1 2010 June Q6
6. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{50925a06-9a9b-4e50-869a-2dce6680615c-07_623_1221_230_422} \captionsetup{labelformat=empty} \caption{Figure 5}
\end{figure} Figure 5 shows a network of cycle tracks within a national park. The number on each arc represents the time taken, in minutes, to cycle along the corresponding track.
  1. Use Dijkstra's algorithm to find the quickest route from S to T . State your quickest route and the time it takes.
    (6)
  2. Explain how you determined your quickest route from your labelled diagram.
    (2)
  3. Write down the quickest route from E to T.
    (1)
Edexcel D1 2010 June Q7
7. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{50925a06-9a9b-4e50-869a-2dce6680615c-08_1419_1826_267_121} \captionsetup{labelformat=empty} \caption{Figure 6}
\end{figure} Keith organises two types of children's activity, 'Sports Mad' and 'Circus Fun'. He needs to determine the number of times each type of activity is to be offered. Let \(x\) be the number of times he offers the 'Sports Mad' activity. Let \(y\) be the number of times he offers the 'Circus Fun' activity. Two constraints are
and $$\begin{aligned} & x \leqslant 15
& y > 6 \end{aligned}$$ These constraints are shown on the graph in Figure 6, where the rejected regions are shaded out.
  1. Explain why \(y = 6\) is shown as a dotted line.
    (1) Two further constraints are $$\begin{aligned} 3 x & \geqslant 2 y
    \text { and } \quad 5 x + 4 y & \geqslant 80 \end{aligned}$$
  2. Add two lines and shading to Diagram 1 in the answer book to represent these inequalities. Hence determine the feasible region and label it R . Each 'Sports Mad' activity costs \(\pounds 500\).
    Each 'Circus Fun' activity costs \(\pounds 800\).
    Keith wishes to minimise the total cost.
  3. Write down the objective function, C , in terms of \(x\) and \(y\).
  4. Use your graph to determine the number of times each type of activity should be offered and the total cost. You must show sufficient working to make your method clear.
Edexcel D1 2010 June Q8
8. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{50925a06-9a9b-4e50-869a-2dce6680615c-10_723_1244_239_408} \captionsetup{labelformat=empty} \caption{Figure 7}
\end{figure} A project is modelled by the activity network shown in Figure 7. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest possible time.
  1. Complete Diagram 2 in the answer book to show the early and late event times.
  2. State the critical activities.
  3. On Grid 1 in the answer book, draw a cascade (Gantt) chart for this project.
  4. Use your cascade chart to determine a lower bound for the number of workers needed. You must justify your answer.
Edexcel D1 2012 June Q1
  1. A carpet fitter needs the following lengths, in metres, of carpet.
$$\begin{array} { l l l l l l l l l } 20 & 33 & 19 & 24 & 31 & 22 & 27 & 18 & 25 \end{array}$$ He cuts them from rolls of length 50 m .
  1. Calculate a lower bound for the number of rolls he needs. You must make your method clear.
  2. Use the first-fit bin packing algorithm to determine how these lengths can be cut from rolls of length 50 m .
  3. Carry out a bubble sort to produce a list of the lengths needed in descending order. You need only give the state of the list after each pass.
  4. Apply the first-fit decreasing bin packing algorithm to show how these lengths may be cut from the rolls.
Edexcel D1 2012 June Q2
2. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4ad45e8f-f50a-4125-866b-a6951f85600f-3_474_593_264_372} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4ad45e8f-f50a-4125-866b-a6951f85600f-3_474_588_267_1096} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure} Figure 1 shows the possible allocations of five workers, Charles (C), David (D), Ellie (E), Freya (F) and Georgi (G), to five tasks, 1, 2, 3, 4 and 5. Figure 2 shows an initial matching.
  1. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. State clearly the alternating path that you use and list your final matching.
    (4)
  2. Find another solution starting from the given initial matching. You should state the alternating path and list the complete matching it gives.
    (3)
Edexcel D1 2012 June Q3
3.
ABCDEFG
A-1519-2224-
B15--813--
C19--12-16-
D-812-10-18
E2213-10-1516
F24-16-15-17
G---181617-
The table shows the lengths, in km, of a network of roads between seven villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) and G.
  1. Complete the drawing of the network in Diagram 1 of the answer book by adding the necessary arcs from vertex D together with their weights.
  2. Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
  3. Draw the minimum spanning tree using the vertices provided in Diagram 2 in the answer book.
  4. State the weight of the minimum spanning tree.
Edexcel D1 2012 June Q4
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4ad45e8f-f50a-4125-866b-a6951f85600f-5_661_1525_292_269} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} \section*{[The total weight of the network is 1436 m ]}
  1. Explain the term valency. Figure 3 models a system of underground pipes. The number on each arc represents the length, in metres, of that pipe. Pressure readings indicate that there is a leak in the system and an electronic device is to be used to inspect the system to locate the leak. The device will start and finish at A and travel along each pipe at least once. The length of this inspection route needs to be minimised.
  2. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You should make your method and working clear.
  3. Find the length of the inspection route. Pipe HI is now found to be blocked; it is sealed and will not be replaced. An inspection route is now required that excludes pipe HI . The length of the inspection route must be minimised.
  4. Find the length of the minimum inspection route excluding HI. Justify your answer.
  5. Given that the device may now start at any vertex and finish at any vertex, find a minimum inspection route, excluding HI.
Edexcel D1 2012 June Q5
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4ad45e8f-f50a-4125-866b-a6951f85600f-6_785_1463_191_301} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} Figure 4 shows a network of roads. The number on each arc represents the length, in miles, of the corresponding road.
  1. Use Dijkstra's algorithm to find the shortest route from S to T . State your shortest route and its length.
    (6)
  2. Explain how you determined your shortest route from your labelled diagram.
    (2) Due to flooding, the roads in and out of D are closed.
  3. Find the shortest route from S to T avoiding D . State your shortest route and its length.
    (2)
Edexcel D1 2012 June Q6
6. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4ad45e8f-f50a-4125-866b-a6951f85600f-7_624_1461_194_301} \captionsetup{labelformat=empty} \caption{Figure 5}
\end{figure} Figure 5 is the activity network relating to a development project. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest possible time.
  1. Complete the precedence table in the answer book.
    (2)
  2. Complete Diagram 1 in the answer book to show the early event times and late event times.
    (4)
  3. Calculate the total float for activity E. You must make the numbers you use in your calculation clear.
    (2)
  4. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
    (2)
  5. Schedule the activities using the minimum number of workers so that the project is completed in the minimum time.
Edexcel D1 2012 June Q7
7. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4ad45e8f-f50a-4125-866b-a6951f85600f-8_2491_1570_175_299} \captionsetup{labelformat=empty} \caption{Figure 6}
\end{figure} A company is going to hire out two types of car, standard and luxury. Let \(x\) be the number of standard cars it should buy.
Let \(y\) be the number of luxury cars it should buy. Figure 6 shows three constraints, other than \(x , y \geqslant 0\)
Two of these are \(x \geqslant 20\) and \(y \geqslant 8\)
  1. Write, as an inequality, the third constraint shown in Figure 6. The company decides that at least \(\frac { 1 } { 6 }\) of the cars must be luxury cars.
  2. Express this information as an inequality and show that it simplifies to $$5 y \geqslant x$$ You must make the steps in your working clear. Each time the cars are hired they need to be prepared. It takes 5 hours to prepare a standard car and it takes 6 hours to prepare a luxury car. There are 300 hours available each week to prepare the cars.
  3. Express this information as an inequality.
  4. Add two lines and shading to Diagram 1 in the answer book to illustrate the constraints found in parts (b) and (c).
  5. Hence determine the feasible region and label it R . The company expects to make \(\pounds 80\) profit per week on each car.
    It therefore wishes to maximise \(\mathrm { P } = 80 x + 80 y\), where P is the profit per week.
  6. Use the objective line (ruler) method to find the optimal vertex, V, of the feasible region. You must clearly draw and label your objective line and the vertex V.
  7. Given that P is the expected profit, in pounds, per week, find the number of each type of car that the company should buy and the maximum expected profit.
Edexcel D1 2013 June Q1
1. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{1493d74b-e9ef-4c9a-91f6-877c1eaa74e2-02_533_551_365_402} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{1493d74b-e9ef-4c9a-91f6-877c1eaa74e2-02_529_545_365_1098} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure} Figure 1 shows the possible allocations of six people, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , to six tasks, 1, 2, 3, 4, 5 and 6. Figure 2 shows an initial matching.
  1. Starting from the given initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path you used, and your improved matching.
  2. Explain why it is not possible to find a complete matching. After training, task 4 is added to F's possible allocation and task 6 is added to E's possible allocation.
  3. Starting from the improved matching found in (a), use the maximum matching algorithm to find a complete matching. You should list the alternating path you used and your complete matching.
Edexcel D1 2013 June Q2
2.
ABCDEF
A-85110160225195
B85-100135180150
C110100-215200165
D160135215-235215
E225180200235-140
F195150165215140-
The table shows the average journey time, in minutes, between six towns, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F .
  1. Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network. You must list the arcs that form your tree in the order in which you selected them.
  2. Draw your tree using the vertices given in Diagram 1 in the answer book.
  3. Find the weight of your minimum spanning tree. Kruskal's algorithm may also be used to find a minimum spanning tree.
  4. State three differences between Prim's algorithm and Kruskal's algorithm.
Edexcel D1 2013 June Q3
3. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{1493d74b-e9ef-4c9a-91f6-877c1eaa74e2-04_549_1347_258_360} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} A project is modelled by the activity network shown in Figure 3. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest possible time.
  1. Complete Diagram 1 in the answer book to show the early event times and late event times.
  2. Calculate the total float for activity H. You must make the numbers you use in your calculation clear.
  3. Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time. Show your calculation. Diagram 2 in the answer book shows a partly completed scheduling diagram for this project.
  4. Complete the scheduling diagram, using the minimum number of workers, so that the project is completed in the minimum time.
Edexcel D1 2013 June Q4
4.
  1. Sam (S)
  2. Janelle (J)
  3. Haoyu (H)
  4. Alfie (A)
  5. Cyrus (C)
  6. Komal (K)
  7. Polly (P)
  8. David (D)
  9. Tom (T)
  10. Lydia (L)
A binary search is to be performed on the names in the list above to locate the name Lydia.
  1. Using an appropriate algorithm, rearrange the list so that a binary search can be performed, showing the state of the list after each complete iteration. State the name of the algorithm you have used.
  2. Use the binary search algorithm to locate the name Lydia in the list you obtained in (a). You must make your method clear.
Edexcel D1 2013 June Q5
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{1493d74b-e9ef-4c9a-91f6-877c1eaa74e2-06_712_1520_246_267} \captionsetup{labelformat=empty} \caption{Figure 4
[0pt] [The total weight of the network is 181 miles]}
\end{figure} Figure 4 represents a network of power cables that have to be inspected. The number on each arc represents the length, in km , of that cable. A route of minimum length that traverses each cable at least once and starts and finishes at A needs to be found.
  1. Use the route inspection algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
  2. Write down a possible shortest inspection route, giving its length. It is now decided to start and finish the inspection route at two distinct vertices. The route must still traverse each cable at least once.
  3. Determine possible starting and finishing points so that the length of the route is minimised. You must give reasons for your answer.
Edexcel D1 2013 June Q6
6.
ActivityImmediately preceding activities
A-
B-
CA
DA
EB
FC D
GD
HF G
IH
JH
KI J
  1. Draw the activity network described in the precedence table, using activity on arc and exactly two dummies.
    (5)
  2. Explain why each of the two dummies is necessary.
    (2)
Edexcel D1 2013 June Q7
7. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{1493d74b-e9ef-4c9a-91f6-877c1eaa74e2-08_748_1563_251_242} \captionsetup{labelformat=empty} \caption{Figure 5}
\end{figure} Figure 5 represents a network of roads. The number on each arc represents the length, in miles, of the corresponding road. A large crane is required at J and it may be transported from either \(\mathrm { C } _ { 1 }\) or \(\mathrm { C } _ { 2 }\). A route of minimum length is required. It is decided to use Dijkstra's algorithm to find the shortest routes between \(\mathrm { C } _ { 1 }\) and J and between \(\mathrm { C } _ { 2 }\) and J .
  1. Explain why J , rather than \(\mathrm { C } _ { 1 }\) or \(\mathrm { C } _ { 2 }\), should be chosen as the starting vertex.
    (1)
  2. Use Dijkstra's algorithm to find the shortest route needed to transport the crane. State your route and its length.
    (6)
Edexcel D1 2013 June Q8
8. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{1493d74b-e9ef-4c9a-91f6-877c1eaa74e2-09_1118_1134_214_486} \captionsetup{labelformat=empty} \caption{Figure 6}
\end{figure} A company makes two types of garden bench, the 'Rustic' and the 'Contemporary'. The company wishes to maximise its profit and decides to use linear programming. Let \(x\) be the number of 'Rustic' benches made each week and \(y\) be the number of 'Contemporary' benches made each week. The graph in Figure 6 is being used to solve this linear programming problem.
Two of the constraints have been drawn on the graph and the rejected region shaded out.
  1. Write down the constraints shown on the graph giving your answers as inequalities in terms of \(x\) and \(y\). It takes 4 working hours to make one 'Rustic' bench and 3 working hours to make one 'Contemporary' bench. There are 120 working hours available in each week.
  2. Write down an inequality to represent this information. Market research shows that 'Rustic' benches should be at most \(\frac { 3 } { 4 }\) of the total benches made each week.
  3. Write down, and simplify, an inequality to represent this information. Your inequality must have integer coefficients.
  4. Add two lines and shading to Diagram 1 in your answer book to represent the inequalities of (b) and (c). Hence determine and label the feasible region, R. The profit on each 'Rustic' bench and each 'Contemporary' bench is \(\pounds 45\) and \(\pounds 30\) respectively.
  5. Write down the objective function, P , in terms of \(x\) and \(y\).
  6. Determine the coordinates of each of the vertices of the feasible region and hence use the vertex method to determine the optimal point.
  7. State the maximum weekly profit the company could make.
    (Total 16 marks)
Edexcel D1 2013 June Q1
1. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{5b32eb57-c9cd-46ec-a328-12050148bdf7-2_766_570_324_342} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{5b32eb57-c9cd-46ec-a328-12050148bdf7-2_755_570_331_1146} \captionsetup{labelformat=empty} \caption{Figure 2}
\end{figure} Figure 1 shows the possible allocations of six people, Alex (A), Ben (B), Harriet (H), Izzy (I), Leo (L) and Rowan (R), to six tasks, \(1,2,3,4,5\) and 6.
  1. Write down the technical name given to the type of diagram shown in Figure 1. Figure 2 shows an initial matching.
  2. Starting from the given initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating paths you use, and state your improved matching after each iteration.
    (6)