Questions — Edexcel D2 (231 questions)

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 D2 2003 June Q7
7. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-4_759_1529_715_267}
\end{figure} Figure 1 shows a capacitated, directed network. The unbracketed number on each arc indicates the capacity of that arc, and the numbers in brackets show a feasible flow of value 68 through the network.
  1. Add a supersource and a supersink, and arcs of appropriate capacity, to Diagram 1 below. \section*{Diagram 1} \includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-4_684_1531_1816_267}
  2. Find the values of \(x\) and \(y\), explaining your method briefly.
  3. Find the value of cuts \(C _ { 1 }\) and \(C _ { 2 }\). Starting with the given feasible flow of 68,
  4. use the labelling procedure on Diagram 2 to find a maximal flow through this network. List each flow-augmenting route you use, together with its flow. \section*{Diagram 2} \includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-5_647_1506_612_283}
  5. Show your maximal flow on Diagram 3 and state its value. \section*{Diagram 3} \includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-5_654_1511_1567_278}
  6. Prove that your flow is maximal.
Edexcel D2 2003 June Q8
8. The tableau below is the initial tableau for a maximising linear programming problem.
Basic
variable
\(x\)\(y\)\(z\)\(r\)\(s\)Value
\(r\)234108
\(s\)3310110
\(P\)- 8- 9- 5000
  1. For this problem \(x \geq 0 , y \geq 0 , z \geq 0\). Write down the other two inequalities and the objective function.
  2. Solve this linear programming problem. You may not need to use all of these tableaux.
    b.v.\(x\)\(y\)\(z\)\(r\)\(s\)Value
    \(P\)
    b.v.\(x\)\(y\)\(z\)\(r\)\(s\)Value
    \(P\)
    b.v.\(x\)\(y\)\(z\)\(r\)\(s\)Value
    \(P\)
    b.v.\(x\)\(y\)\(z\)\(r\)\(s\)Value
    \(P\)
  3. State the final value of \(P\), the objective function, and of each of the variables.
Edexcel D2 2004 June Q1
  1. In game theory explain what is meant by
    1. zero-sum game,
    2. saddle point.
      (Total 4 marks)
    3. In a quiz there are four individual rounds, Art, Literature, Music and Science. A team consists of four people, Donna, Hannah, Kerwin and Thomas. Each of four rounds must be answered by a different team member. The table shows the number of points that each team member is likely to get on each individual round.
    \cline { 2 - 5 } \multicolumn{1}{c|}{}ArtLiteratureMusicScience
    Donna31243235
    Hannah16101922
    Kerwin19142021
    Thomas18152123
    Use the Hungarian algorithm, reducing rows first, to obtain an allocation which maximises the total points likely to be scored in the four rounds. You must make your method clear and show the table after each stage.
    (Total 9 marks)
Edexcel D2 2004 June Q3
3. The table shows the least distances, in km, between five towns, \(A , B , C , D\) and \(E\). Nassim wishes to find an interval which contains the solution to the travelling salesman problem for this network.
  1. Making your method clear, find an initial upper bound starting at \(A\) and using
    1. the minimum spanning tree method,
    2. the nearest neighbour algorithm.
      \(A\)\(B\)\(C\)\(D\)\(E\)
      \(A\)-15398124115
      \(B\)153-74131149
      \(C\)9874-82103
      \(D\)12413182-134
      \(E\)115149103134-
  2. By deleting \(E\), find a lower bound.
  3. Using your answers to parts (a) and (b), state the smallest interval that Nassim could correctly write down.
    (Total 12 marks)
Edexcel D2 2004 June Q4
4. Emma and Freddie play a zero-sum game. This game is represented by the following pay-off matrix for Emma. \(\left( \begin{array} { r r r } - 4 & - 1 & 3
2 & 1 & - 2 \end{array} \right)\)
  1. Show that there is no stable solution.
  2. Find the best strategy for Emma and the value of the game to her.
  3. Write down the value of the game to Freddie and his pay-off matrix.
Edexcel D2 2004 June Q5
5. (a) Describe a practical problem that could be solved using the transportation algorithm. A problem is to be solved using the transportation problem. The costs are shown in the table. The supply is from \(A , B\) and \(C\) and the demand is at \(d\) and \(e\).
\cline { 2 - 4 } \multicolumn{1}{c|}{}\(d\)\(e\)Supply
\(A\)5345
\(B\)4635
\(C\)2440
Demand5060
(b) Explain why it is necessary to add a third demand \(f\).
(c) Use the north-west corner rule to obtain a possible pattern of distribution and find its cost.
\cline { 2 - 5 } \multicolumn{1}{c|}{}\(d\)\(e\)\(f\)Supply
\(A\)5345
\(B\)4635
\(C\)2440
Demand5060
(d) Calculate shadow costs and improvement indices for this pattern.
(e) Use the stepping-stone method once to obtain an improved solution and its cost.
(Total 16 marks)
Edexcel D2 2004 June Q6
6. Joan sells ice cream. She needs to decide which three shows to visit over a three-week period in the summer. She starts the three-week period at home and finishes at home. She will spend one week at each of the three shows she chooses travelling directly from one show to the next. Table 1 gives the week in which each show is held. Table 2 gives the expected profits from visiting each show. Table 3 gives the cost of travel between shows. \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Table 1}
Week123
ShowsA, B, CD, EF, G, H
\end{table} Table 2 \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Table 1}
ShowA\(B\)\(C\)\(D\)\(E\)\(F\)\(G\)\(H\)
Expected Profit \(( \pounds )\)900800100015001300500700600
\end{table} \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Table 3}
Travel costs (£)ABCDEFGH
Home7080150809070
A180150
B140120
C200210
D200160120
E170100110
\end{table} It is decided to use dynamic programming to find a schedule that maximises the total expected profit, taking into account the travel costs.
  1. Define suitable stage, state and action variables.
  2. Determine the schedule that maximises the total profit. Show your working in a table.
  3. Advise Joan on the shows that she should visit and state her total expected profit.
    (3) (Total 18 marks)
Edexcel D2 2004 June Q7
7. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{343fdcef-660e-4e8c-bd9c-a7f929dc668e-3_526_903_1455_575}
\end{figure} Figure 1 shows a capacitated directed network. The number on each arc is its capacity. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{343fdcef-660e-4e8c-bd9c-a7f929dc668e-3_499_967_2231_548}
\end{figure} Figure 2 shows a feasible initial flow through the same network.
  1. Write down the values of the flow \(x\) and the flow \(y\).
  2. Obtain the value of the initial flow through the network, and explain how you know it is not maximal.
  3. Use this initial flow and the labelling procedure on Diagram 1 below to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow. \section*{Diagram 1} \includegraphics[max width=\textwidth, alt={}, center]{343fdcef-660e-4e8c-bd9c-a7f929dc668e-4_1920_1175_742_450}
    d) Show your maximal flow pattern on Diagram 2. \section*{Diagram 2} \includegraphics[max width=\textwidth, alt={}, center]{343fdcef-660e-4e8c-bd9c-a7f929dc668e-5_679_1102_315_479}
    (2)
  4. Prove that your flow is maximal.
    (2)
    (Total 13 marks)
Edexcel D2 2004 June Q8
8. A three-variable linear programming problem in \(x , y\) and \(z\) is to be solved. The objective is to maximise the profit P . The following tableau was obtained.
Basic variable\(x\)\(y\)\(Z\)\(r\)\(s\)\(t\)Value
S30201\(- \frac { 2 } { 3 }\)\(\frac { 2 } { 3 }\)
\(r\)40\(\frac { 7 } { 2 }\)108\(\frac { 9 } { 2 }\)
\(y\)5170037
P30200863
  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\).
Edexcel D2 2004 June Q9
9.
\includegraphics[max width=\textwidth, alt={}, center]{343fdcef-660e-4e8c-bd9c-a7f929dc668e-6_1088_1509_219_285} The diagram above 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 The diagram above.
  1. Find the capacity of each of the three cuts.
  2. 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.
  3. By considering both options, explain which one meets the government's aim
Edexcel D2 2004 June Q10
10. Flatland UK Ltd makes three types of carpet, the Lincoln, the Norfolk and the Suffolk. The carpets all require units of black, green and red wool. For each roll of carpet, the Lincoln requires 1 unit of black, 1 of green and 3 of red, the Norfolk requires 1 unit of black, 2 of green and 2 of red, and the Suffolk requires 2 units of black, 1 of green and 1 of red. There are up to 30 units of black, 40 units of green and 50 units of red available each day.
Profits of \(\pounds 50 , \pounds 80\) and \(\pounds 60\) are made on each roll of Lincoln, Norfolk and Suffolk respectively. Flatland UK Ltd wishes to maximise its profit. Let the number of rolls of the Lincoln, Norfolk and Suffolk made daily be \(x , y\) and \(z\) respectively.
  1. Formulate the above situation as a linear programming problem, listing clearly the constraints as inequalities in their simplest form, and stating the objective function. This problem is to be solved using the Simplex algorithm. The most negative number in the profit row is taken to indicate the pivot column at each stage.
  2. Stating your row operations, show that after one complete iteration the tableau becomes
    Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
    \(r\)\(\frac { 1 } { 2 }\)0\(1 \frac { 1 } { 2 }\)1\(- \frac { 1 } { 2 }\)010
    \(y\)\(\frac { 1 } { 2 }\)1\(\frac { 1 } { 2 }\)0\(\frac { 1 } { 2 }\)020
    \(t\)2000-1110
    \(P\)-100-2004001600
    You may not need to use all of the tableaux.
    Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)ValueRow operations
    \(r\)
    \(S\)
    \(t\)
    \(P\)
    Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)ValueRow operations
  3. Explain the practical meaning of the value 10 in the top row.
    1. Perform one further complete iteration of the Simplex algorithm.
      Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)ValueRow operations
      Basic variable\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)ValueRow operations
    2. State whether your current answer to part (d)(i) is optimal. Give a reason for your answer.
    3. Interpret your current tableau, giving the value of each variable.
      (8)
Edexcel D2 2005 June Q1
  1. Freezy Co. has three factories \(A , B\) and \(C\). It supplies freezers to three shops \(D , E\) and \(F\). The table shows the transportation cost in pounds of moving one freezer from each factory to each outlet. It also shows the number of freezers available for delivery at each factory and the number of freezers required at each shop. The total number of freezers required is equal to the total number of freezers available.
\cline { 2 - 5 } \multicolumn{1}{c|}{}\(D\)\(E\)\(F\)Available
\(A\)21241624
\(B\)18231732
\(C\)15192514
Required203020
\cline { 1 - 4 }
\cline { 1 - 4 }
  1. Use the north-west corner rule to find an initial solution.
  2. Obtain improvement indices for each unused route.
  3. Use the stepping-stone method once to obtain a better solution and state its cost.
Edexcel D2 2005 June Q2
2.
\includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-1_613_1269_1318_392} The network in the diagram shows the distances, in km , of the cables between seven electricity relay stations \(A , B , C , D , E , F\) and \(G\). An inspector needs to visit each relay station. He wishes to travel a minimum distance, and his route must start and finish at the same station. By deleting C, a lower bound for the length of the route is found to be 129 km .
  1. Find another lower bound for the length of the route by deleting \(F\). State which is the better lower bound of the two.
  2. By inspection, complete the table of least distances. The table can now be taken to represent a complete network.
  3. Using the nearest-neighbour algorithm, starting at \(F\), obtain an upper bound to the length of the route. State your route.
    (4) (Total 11 marks)
Edexcel D2 2005 June Q3
3. Three warehouses \(W , X\) and \(Y\) supply televisions to three supermarkets \(J , K\) and \(L\). The table gives the cost, in pounds, of transporting a television from each warehouse to each supermarket. The warehouses have stocks of 34, 57 and 25 televisions respectively, and the supermarkets require 20, 56 and 40 televisions respectively. The total cost of transporting the televisions is to be minimised.
\(J\)\(K\)\(L\)
\(W\)363
\(X\)584
\(Y\)257
Formulate this transportation problem as a linear programming problem. Make clear your decision variables, objective function and constraints.
(Total 7 marks)
Edexcel D2 2005 June Q4
4. (a) Explain what is meant by a maximin route in dynamic programming, and give an example of a situation that would require a maximin solution.
(3)
\includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-2_700_1392_1069_338} A maximin route is to be found through the network shown in the diagram.
(b) Complete the table in the answer book, and hence find a maximin route.
(9)
(c) List all other maximin routes through the network.
(Total 14 marks)
Edexcel D2 2005 June Q5
5. Four salesperson \(A , B , C\) and \(D\) are to be sent to visit four companies \(1,2,3\) and 4 . Each salesperson will visit exactly one company, and all companies will be visited. Previous sales figures show that each salesperson will make sales of different values, depending on the company that they visit. These values (in \(\pounds 10000\) s) are shown in the table below.
\cline { 2 - 5 } \multicolumn{1}{c|}{}1234
Ann26303030
Brenda30232629
Connor30252724
Dave30272521
  1. Use the Hungarian algorithm to obtain an allocation that maximises the sales. You must make your method clear and show the table after each stage.
  2. State the value of the maximum sales.
  3. Show that there is a second allocation that maximises the sales.
    (Total 15 marks)
Edexcel D2 2005 June Q6
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
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
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
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.
  3. Give an example of a practical situation that could have been modelled by the original network.
Edexcel D2 2006 June Q1
  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
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
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
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
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.