Questions — Edexcel (9685 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 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 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
Edexcel D2 2005 June Q6
16 marks Standard +0.3
6. \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-3_696_1319_1292_374} This figure shows a capacitated directed network. The number on each arc is its capacity. The numbers in circles show a feasible flow through the network. Take this as the initial flow.
  1. On Diagram 1 and Diagram 2 in the answer book, add a supersource \(S\) and a supersink \(T\). On Diagram 1 show the minimum capacities of the arcs you have added. Diagram 2 in the answer book shows the first stage of the labelling procedure for the given initial flow.
  2. Complete the initial labelling procedure in Diagram 2.
  3. Find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow, and state the maximal flow.
  4. Show a maximal flow pattern on Diagram 3.
  5. Prove that your flow is maximal.
  6. Describe briefly a situation for which this network could be a suitable model.
    (Total 16 marks) \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-4_1486_1963_568_50}
Edexcel D2 2005 June Q7
17 marks Standard +0.3
7. (a) Explain briefly what is meant by a zero-sum game. A two person zero-sum game is represented by the following pay-off matrix for player \(A\).
IIIIII
I523
II354
(b) Verify that there is no stable solution to this game.
(c) Find the best strategy for player \(A\) and the value of the game to her.
(d) Formulate the game as a linear programming problem for player \(B\). Write the constraints as inequalities and define your variables clearly.
(Total 17 marks)
Edexcel D2 2005 June Q8
15 marks Standard +0.3
8. Polly has a bird food stall at the local market. Each week she makes and sells three types of packs \(A , B\) and C. Pack \(A\) contains 4 kg of bird seed, 2 suet blocks and 1 kg of peanuts.
Pack \(B\) contains 5 kg of bird seed, 1 suet block and 2 kg of peanuts.
Pack \(C\) contains 10 kg of bird seed, 4 suet blocks and 3 kg of peanuts.
Each week Polly has 140 kg of bird seed, 60 suet blocks and 60 kg of peanuts available for the packs.
The profit made on each pack of \(A , B\) and \(C\) sold is \(\pounds 3.50 , \pounds 3.50\) and \(\pounds 6.50\) respectively. Polly sells every pack on her stall and wishes to maximise her profit, \(P\) pence. Let \(x , y\) and \(z\) be the numbers of packs \(A , B\) and \(C\) sold each week.
An initial Simplex tableau for the above situation is
Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)451100140
\(s\)21401060
\(t\)12300160
\(P\)- 350- 350- 6500000
  1. Explain the meaning of the variables \(r , s\) and \(t\) in the context of this question.
  2. Perform one complete iteration of the Simplex algorithm to form a new tableau \(T\). Take the most negative number in the profit row to indicate the pivotal column.
  3. State the value of every variable as given by tableau \(T\).
  4. Write down the profit equation given by tableau \(T\).
  5. Use your profit equation to explain why tableau \(T\) is not optimal. Taking the most negative number in the profit row to indicate the pivotal column,
  6. identify clearly the location of the next pivotal element.
Edexcel D2 2005 June Q9
14 marks Moderate -0.8
9. \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-6_540_1291_203_411} This diagram shows a capacitated directed network. The number on each arc is its capacity.
  1. State the maximum flow along
    1. SADT,
    2. SCET,
    3. \(S B F T\).
  2. Show these maximum flows on Diagram 1 below. \section*{Diagram 1}
    \includegraphics[max width=\textwidth, alt={}]{be329a47-a709-4719-abe6-41d388a6c631-6_561_1187_1283_721}
    Take your answer to part (b) as the initial flow pattern.
    1. Use the labelling procedure to find a maximum flow from \(S\) to \(T\). Your working should be shown on Diagram 2 below. List each flow-augmenting route you use, together with its flow. \section*{Diagram 2} \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-7_718_1525_205_269}
    2. Draw your final flow pattern on Diagram 3 below. \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-7_611_1196_1082_717}
    3. Prove that your flow is maximal.
  4. Give an example of a practical situation that could have been modelled by the original network.
Edexcel D2 2006 June Q1
4 marks Easy -1.2
  1. (a) State Bellman's principle of optimality.
    (b) Explain what is meant by a minimax route.
    (c) Describe a practical problem that would require a minimax route as its solution.
    (Total 4 marks)
  2. Three workers, \(P , Q\) and \(R\), are to be assigned to three tasks, 1,2 and 3 . Each worker is to be assigned to one task and each task must be assigned to one worker. The cost, in hundreds of pounds, of using each worker for each task is given in the table below. The cost is to be minimised.
Cost (in \(\pounds 100\) s)Task 1Task 2Task 3
Worker \(P\)873
Worker \(Q\)956
Worker \(R\)1044
Formulate the above situation as a linear programming problem, defining the decision variables and making the objective and constraints clear.
(Total 7 marks)
Edexcel D2 2006 June Q3
11 marks Moderate -0.5
3. A college wants to offer five full-day activities with a different activity each day from Monday to Friday. The sports hall will only be used for these activities. Each evening the caretaker will prepare the hall by putting away the equipment from the previous activity and setting up the hall for the activity next day. On Friday evening he will put away the equipment used that day and set up the hall for the following Monday. The 5 activities offered are Badminton (B), Cricket nets (C), Dancing (D), Football coaching (F) and Tennis (T). Each will be on the same day from week to week. The college decides to offer the activities in the order that minimises the total time the caretaker has to spend preparing the hall each week. The hall is initially set up for Badminton on Monday.
The table below shows the time, in minutes, it will take the caretaker to put away the equipment from one activity and set up the hall for the next.
\multirow{3}{*}{}To
Time\(B\)CD\(F\)\(T\)
\(B\)-10815064100
\multirow[t]{4}{*}{From}C108-5410460
D15054-150102
\(F\)64104150-68
\(T\)1006010268-
  1. Explain why this problem is equivalent to the travelling salesman problem. A possible ordering of activities is
    MondayTuesdayWednesdayThursdayFriday
    \(B\)\(C\)\(D\)\(F\)\(T\)
  2. Find the total time taken by the caretaker each week using this ordering.
  3. Starting with Badminton on Monday, use a suitable algorithm to find an ordering that reduces the total time spent each week to less than 7 hours.
  4. By deleting \(B\), use a suitable algorithm to find a lower bound for the time taken each week. Make your method clear.
Edexcel D2 2006 June Q4
11 marks Moderate -0.3
4. During the school holidays four building tasks, rebuilding a wall ( \(W\) ), repairing the roof ( \(R\) ), repainting the hall \(( H )\) and relaying the playground \(( P )\), need to be carried out at a Junior School. Four builders, \(A , B , C\) and \(D\) will be hired for these tasks. Each builder must be assigned to one task. Builder \(B\) is not able to rebuild the wall and therefore cannot be assigned to this task. The cost, in thousands of pounds, of using each builder for each task is given in the table below.
Cost\(H\)\(P\)\(R\)\(W\)
\(A\)35119
\(B\)378-
\(C\)25107
\(D\)8376
  1. Use the Hungarian algorithm, reducing rows first, to obtain an allocation that minimises the total cost. State the allocation and its total cost. You must make your method clear and show the table after each stage.
  2. State, with a reason, whether this allocation is unique.
Edexcel D2 2006 June Q5
12 marks Standard +0.3
5. Victor owns some kiosks selling ice cream, hot dogs and soft drinks. The network below shows the choices of action and the profits, in thousands of pounds, they generate over the next four years. The negative numbers indicate losses due to the purchases of new kiosks. \includegraphics[max width=\textwidth, alt={}, center]{83ddfbb1-d035-4fae-b39d-a643c877cfed-3_887_1342_340_365} Use a suitable algorithm to determine the sequence of actions so that the profit over the four years is maximised and state this maximum profit.
(Total 12 marks)
Edexcel D2 2006 June Q6
14 marks Moderate -0.8
6. (a) Explain briefly the circumstances under which a degenerate feasible solution may occur to a transportation problem.
(b) Explain why a dummy location may be needed when solving a transportation problem. The table below shows the cost of transporting one unit of stock from each of three supply points \(A , B\) and \(C\) to each of two demand points 1 and 2 . It also shows the stock held at each supply point and the stock required at each demand point.
12Supply
\(A\)624715
\(B\)614812
\(C\)685817
Demand1611
(c) Complete the table below to show a possible initial feasible solution generated by the north-west corner method.
123
\(A\)
\(B\)0
\(C\)
(d) Use the stepping-stone method to obtain an optimal solution and state its cost. You should make your method clear by stating shadow costs, improvement indices, stepping-stone route, and the entering and exiting squares at each stage.
Edexcel D2 2006 June Q7
16 marks Standard +0.8
7. A two person zero-sum game is represented by the following pay-off matrix for player \(A\).
\(B\) plays 1\(B\) plays 2\(B\) plays 3
\(A\) plays 1572
\(A\) plays 2384
\(A\) plays 3649
  1. Formulate the game as a linear programming problem for player \(A\), writing the constraints as equalities and clearly defining your variables.
  2. Explain why it is necessary to use the simplex algorithm to solve this game theory problem.
  3. Write down an initial simplex tableau making your variables clear.
  4. Perform two complete iterations of the simplex algorithm, indicating your pivots and stating the row operations that you use.
    (8)
    (Total 16 marks)
Edexcel D2 2006 June Q8
16 marks Standard +0.8
8. The tableau below is the initial tableau for a maximising linear programming problem.
Basic variable\(x\)\(y\)\(z\)r\(s\)\(t\)Value
\(r\)710101003600
\(s\)69120103600
\(t\)2340012400
\(P\)-35-55-600000
  1. Write down the four equations represented in the initial tableau above.
    (4)
  2. Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. State the row operations that you use.
  3. State the values of the objective function and each variable.
    b.v.\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)ValueRow Operations
    b.v.\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)ValueRow Operations
    b.v.\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)ValueRow Operations
    b.v.\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)ValueRow Operations
    b.v.\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)ValueRow Operations
Edexcel D2 2006 June Q9
14 marks Moderate -0.5
9.
\includegraphics[max width=\textwidth, alt={}]{83ddfbb1-d035-4fae-b39d-a643c877cfed-6_945_1484_255_285}
The figure above shows a capacitated, directed network. The capacity of each arc is shown on each arc. The numbers in circles represent an initial flow from \(S\) to \(T\). Two cuts \(C _ { 1 }\) and \(C _ { 2 }\) are shown on the figure.
  1. Write down the capacity of each of the two cuts and the value of the initial flow.
    (3)
  2. Complete the initialisation of the labelling procedure on the diagram below by entering values along arcs \(A C , C D , D E\) and \(D T\). \includegraphics[max width=\textwidth, alt={}, center]{83ddfbb1-d035-4fae-b39d-a643c877cfed-7_2372_1131_121_475}
  3. Hence use the labelling procedure to find a maximal flow through the network. You must list each flow-augmenting path you use, together with its flow.
  4. Show your maximal flow pattern on the diagram below. \includegraphics[max width=\textwidth, alt={}, center]{83ddfbb1-d035-4fae-b39d-a643c877cfed-8_757_1472_210_294}
  5. Prove that your flow is maximal.
    (Total 14 marks)
Edexcel D2 2007 June Q1
11 marks Moderate -0.8
  1. The network above shows the distances, in miles, between seven gift shops, \(A , B\), \(C , D , E , F\) and \(G\).
The area manager needs to visit each shop. She will start and finish at shop A and wishes to minimise the total distance travelled.
  1. By inspection, complete the two copies of the table of least distances below. \includegraphics[max width=\textwidth, alt={}, center]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-1_666_1136_141_863}
    A\(B\)C\(D\)\(E\)\(F\)\(G\)
    A-15365323
    B-1738498049
    C1517-216232
    D363821-1142
    E4911-3161
    \(F\)5380624231-30
    \(G\)2349326130-
    (4)
    \(A\)\(B\)\(C\)\(D\)\(E\)\(F\)\(G\)
    \(A\)-15365323
    \(B\)-1738498049
    \(C\)1517-216232
    \(D\)363821-1142
    \(E\)4911-3161
    \(F\)5380624231-30
    \(G\)2349326130-
  2. Starting at A, and making your method clear, find an upper bound for the route length, using the nearest neighbour algorithm.
    (3)
  3. By deleting A, and all of its arcs, find a lower bound for the route length.
    (4) (Total 11 marks)
Edexcel D2 2007 June Q2
13 marks Moderate -0.5
2. Denis (D) and Hilary (H) play a two-person zero-sum game represented by the following pay-off matrix for Denis.
H plays 1H plays 2H plays 3
D plays 12- 13
D plays 2- 34- 4
  1. Show that there is no stable solution to this game.
  2. Find the best strategy for Denis and the value of the game to him.
    (10) (Total 13 marks)
Edexcel D2 2007 June Q3
13 marks Moderate -0.5
3. To raise money for charity it is decided to hold a Teddy Bear making competition. Teams of four compete against each other to make 20 Teddy Bears as quickly as possible. There are four stages: first cutting, then stitching, then filling and finally dressing.
Each team member can only work on one stage during the competition. As soon as a stage is completed on each Teddy Bear the work is passed immediately to the next team member. The table shows the time, in seconds, taken to complete each stage of the work on one Teddy Bear by the members \(A , B , C\) and \(D\) of one of the teams.
cuttingstitchingfillingdressing
\(A\)661018536
\(B\)66987438
\(C\)63977134
\(D\)671027835
  1. Use the Hungarian algorithm, reducing rows first, to obtain an allocation that minimises the time taken by this team to produce one Teddy Bear. You must make your method clear and show the table after each iteration.
  2. State the minimum time it will take this team to produce one Teddy Bear. Using the allocation found in (a),
  3. calculate the minimum total time this team will take to complete 20 Teddy Bears. You should make your reasoning clear and state your answer in minutes and seconds.
    (Total 13 marks)
Edexcel D2 2007 June Q4
16 marks Moderate -0.8
4. A group of students and teachers from a performing arts college are attending the Glasenburgh drama festival. All of the group want to see an innovative modern production of the play 'The Decision is Final'. Unfortunately there are not enough seats left for them all to see the same performance. There are three performances of the play, 1,2 , and 3 . There
AdultStudent
Performance 1\(\pounds 5.00\)\(\pounds 4.50\)
Performance 2\(\pounds 4.20\)\(\pounds 3.80\)
Performance 3\(\pounds 4.60\)\(\pounds 4.00\)
are two types of ticket, Adult and Student. Student tickets will be purchased for the students and Adult tickets for the teachers. The table below shows the price of tickets for each performance of the play. There are 18 teachers and 200 students requiring tickets. There are 94,65 and 80 seats available for performances 1,2 , and 3 espectively.
  1. Complete the table below.
    AdultStudentDummySeats available
    Performance 1£5.00£4.50
    Performance 2£4.20£3.80
    Performance 3£4.60£4.00
    Tickets needed
  2. Explain why a dummy column was added to the table above.
  3. Use the north-west corner method to obtain a possible solution.
  4. Taking the most negative improvement index to indicate the entering square, use the stepping stone method once to obtain an improved solution. You must make your shadow costs and improvement indices clear. After a further iteration the table becomes:
    AdultStudentDummy
    Performance 17321
    Performance 21847
    Performance 380
  5. Demonstrate that this solution gives the minimum cost, and find its value.
    (Total 16 marks)
Edexcel D2 2007 June Q5
14 marks Standard +0.3
5. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-3_1026_1609_772_169}
\end{figure} In solving a network flow problem using the labelling procedure, the diagram in Figure 1 was created.
The arrow on each arc indicates the direction of the flow along that arc.
The arrows above and below each arc show the direction and value of the flow as indicated by the labelling procedure.
  1. Add a supersource S , a supersink T and appropriate arcs to the diagram above, and complete the labelling procedure for these arcs.
  2. Write down the value of the initial flow shown in Figure 1.
  3. Use Figure 2 below, the initial flow and the labelling procedure to find the maximal flow of 124 through this network. List each flow-augmenting path you use, together with its flow.
  4. Show your flow on the diagram below and state its value. \includegraphics[max width=\textwidth, alt={}, center]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-4_967_1520_114_214}
  5. Prove that your flow is maximal.
    (2)
    (Total 14 marks)
Edexcel D2 2007 June Q6
8 marks Standard +0.8
6. Anna (A) and Roland (R) play a two-person zero-sum game which is represented by the following pay-off matrix for Anna.
R plays 1R plays 2R plays 3
A plays 16- 2- 3
A plays 2- 312
A plays 354- 1
Formulate the game as a linear programming problem for player \(\mathbf { R }\). Write the constraints as inequalities. Define your variables clearly.
(Total 8 marks)
Edexcel D2 2007 June Q7
14 marks Standard +0.3
7. \includegraphics[max width=\textwidth, alt={}, center]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-5_965_1657_210_121} Agent Goodie has successfully recovered the stolen plans from Evil Doctor Fiendish and needs to take them from Evil Doctor Fiendish's secret headquarters at X to safety at Y . To do this he must swim through a network of underwater tunnels. Agent Goodie has no breathing apparatus, but knows that there are twelve points, \(A , B , C , D , E , F , G , H , I , J , K\) and \(L\), at which there are air pockets where he can take a breath. The network is modelled above, and the number on each arc gives the time, in seconds, it takes Agent Goodie to swim from one air pocket to the next. Agent Goodie needs to find a route through this network that minimises the longest time between successive air pockets.
  1. Use dynamic programming to complete the table below and hence find a suitable route for Agent Goodie. Unfortunately, just as Agent Goodie is about to start his journey, tunnel XA becomes blocked.
  2. Find an optimal route for Agent Goodie avoiding tunnel XA.
Edexcel D2 2007 June Q8
18 marks Standard +0.8
8. The tableau below is the initial tableau for a linear programming problem in \(x , y\) and \(z\). The objective is to maximise the profit, \(P\).
basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
\(r\)1245100246
\(s\)963010153
\(t\)52- 2001171
\(P\)- 2- 4- 30000
Using the information in the tableau, write down
  1. the objective function,
  2. the three constraints as inequalities with integer coefficients. Taking the most negative number in the profit row to indicate the pivot column at each stage,
  3. solve this linear programming problem. Make your method clear by stating the row operations you use.
    b.v.xyzrstValueRow operations
    b.v.xyzrstValueRow operations
    b.v.xyzrstValueRow operations
    b.v.xyzrstValueRow operations
  4. State the final values of the objective function and each variable.
  5. One of the constraints is not at capacity. Explain how it can be identified.
Edexcel D2 2007 June Q9
10 marks Easy -1.2
9. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-7_931_1651_196_118} \captionsetup{labelformat=empty} \caption{Figure 1 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.}
\end{figure}
  1. State the value of the initial flow.
  2. State the capacities of cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\). Figure 2 shows the labelling procedure applied to the above network.
  3. Using Figure 2, increase the flow by a further 19 units. You must list each flow-augmenting path you use, together with its flow.
  4. Prove that the flow is now maximal. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-8_2146_1038_127_422} \captionsetup{labelformat=empty} \caption{Figure 2}
    \end{figure}
Edexcel D2 2008 June Q1
11 marks Moderate -0.8
1.
\includegraphics[max width=\textwidth, alt={}]{151644c7-edef-448e-ac2a-b374d79f264c-1_746_1413_262_267}
The diagram above shows a capacitated, directed network of pipes. The number on each arc represents the capacity of that pipe. The numbers in circles represent a feasible flow.
  1. State the values of \(x\) and \(y\).
  2. List the saturated arcs.
  3. State the value of the feasible flow.
  4. State the capacities of the cuts \(\mathrm { C } _ { 1 } , \mathrm { C } _ { 2 }\), and \(\mathrm { C } _ { 3 }\).
  5. By inspection, find a flow-augmenting route to increase the flow by one unit. You must state your route.
  6. Prove that the new flow is maximal.
Edexcel D2 2008 June Q2
4 marks Easy -1.8
2. Explain what is meant, in a network, by (a) a walk, (b) a tour.
(2) (2) (Total 4 marks)
Edexcel D2 2008 June Q3
13 marks Moderate -0.8
3. Jameson cars are made in two factories A and B. Sales have been made at the two main showrooms in London and Edinburgh. Cars are to be transported from the factories to the showrooms. The table below shows the cost, in pounds, of transporting one car from each factory to each showroom. It also shows the number of cars available at each factory and the number required at each showroom.
London (L)Edinburgh (E)Supply
A807055
B605045
Demand3560
It is decided to use the transportation algorithm to obtain a minimal cost solution.
  1. Explain why it is necessary to add a dummy demand point.
  2. Complete the table below.
    LEDummySupply
    A807055
    B605045
    Demand3560100
  3. Use the north-west corner rule to obtain a possible pattern of distribution.
    (1)
  4. Taking the most negative improvement index to indicate the entering square, use the stepping-stone method to obtain an optimal solution. You must make your shadow costs and improvement indices clear and demonstrate that your solution is optimal.
    (7)
  5. State the cost of your optimal solution.
    (1) (Total 13 marks)
Edexcel D2 2008 June Q4
12 marks Standard +0.3
4. (a) Explain the difference between a maximin route and a minimax route in dynamic programming.
(2) \includegraphics[max width=\textwidth, alt={}, center]{151644c7-edef-448e-ac2a-b374d79f264c-2_533_1356_667_376} A maximin route from L to R is to be found through the staged network shown above.
(b) Use dynamic programming to complete a table below and hence find a maximin route.
(10) (Total 12 marks)