12. \begin{figure}[h] \end{figure} A company has 3 warehouses \(W _ { 1 } , W _ { 2 }\), and \(W _ { 3 }\). It needs to transport the goods stored there to 2 retail outlets \(R _ { 1 }\) and \(R _ { 2 }\). The capacities of the possible routes, in van loads per day, are shown in Fig 2. Warehouses \(W _ { 1 } , W _ { 2 }\) and \(W _ { 3 }\) have 14, 12 and 14 van loads respectively available per day and retail outlets \(R _ { 1 }\) and \(R _ { 2 }\) can accept 6 and 25 van loads respectively per day.

1. On Diagram 1 on the answer sheet add a supersource \(W\), a supersink \(R\) and the appropriate directed arcs to obtain a single-source, single-sink capacitated network. State the minimum capacity of each arc you have added.
2. State the maximum flow along
   1. \(W \quad W _ { 1 } \quad A \quad R _ { 1 } \quad R\),
   2. \(W W _ { 3 } \quad C \quad R _ { 2 } \quad R\).
3. Taking your answers to part (b) as the initial flow pattern, use the labelling procedure to obtain a maximum flow through the network from \(W\) to \(R\). Show your working on Diagram 2. List each flowaugmenting route you use, together with its flow.
4. From your final flow pattern, determine the number of van loads passing through \(B\) each day. \section*{D2 2003 (adapted for new spec)}
   1. A two person zero-sum game is represented by the following pay-off matrix for player \(A\).
5. Explain why a dummy row needs to be added to the table.
6. Complete Table 1 in the answer book.
7. Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the cost of assigning salespersons to department stores. You must make your method clear and show the table after each iteration.
8. Find the minimum cost.
   2. (a) Explain the difference between the classical and the practical travelling salesperson problems. The table below shows the distances, in km, between six data collection points, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\), and F . Vicky must visit each city at least once. She will start and finish at A and wishes to minimise the total cost.
9. Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network.
10. Use your answer to part (a) to help you calculate an initial upper bound for the length of Vicky's route.
11. Show that there are two nearest neighbour routes that start from A . You must make your routes and their lengths clear.
12. State the best upper bound from your answers to (b) and (c).
13. Starting by deleting A , and all of its arcs, find a lower bound for the route length.
    2. A team of four workers, Harry, Jess, Louis and Saul, are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to one task and each task must be done by just one worker. Jess cannot be assigned to task 4.
    The amount, in pounds, that each person would earn while assigned to each task is shown in the table below.
14. Add a dummy demand point and appropriate values to Table 1 in the answer book. Table 2 shows an initial solution given by the north-west corner method.
    Table 3 shows some of the improvement indices for this solution.
15. Calculate the shadow costs and the missing improvement indices and enter them into Table 3 in the answer book.
16. Taking the most negative improvement index to indicate the entering square, use the steppingstone method once to obtain an improved solution. You must make your route clear and state your entering cell and exiting cell.
    3. 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 is obtained. Toby must visit each town at least once. He will start and finish at A and wishes to minimise the total distance.
17. Use the nearest neighbour algorithm, starting at A , to find an upper bound for the length of Toby's route.
18. Starting by deleting A, and all of its arcs, find a lower bound for the route length.
    3. The table below shows the cost, in pounds, of transporting one tonne of concrete from each of three supply depots, \(\mathrm { A } , \mathrm { B }\) and C , to each of four building sites, \(\mathrm { D } , \mathrm { E } , \mathrm { F }\) and G . It also shows the number of tonnes that can be supplied from each depot and the number of tonnes required at each building site. A minimum cost solution is required.
19. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total profit. You must make your method clear and show the table after each stage.
20. State which worker should be allocated to each task and the resulting total profit made.
    2. The table shows the least distances, in km, between six towns, A, B, C, D, E and F. The table shows the least distances, in km, between five hiding places, A, B, C, D and E.
    Agent Goodie has to leave a secret message in each of the hiding places. He will start and finish at A , and wishes to minimise the total distance travelled.
21. Use Prim's algorithm to find a minimum spanning tree for this network. Make your order of arc selection clear.
22. Use your answer to part (a) to determine an initial upper bound for the length of Agent Goodie's route.
23. Show that there are two nearest neighbour routes which start from A . State these routes and their lengths.
24. State the better upper bound from your answers to (b) and (c).
25. Starting by deleting B, and all of its arcs, find a lower bound for the length of Agent Goodie's route.
26. Consider your answers to (d) and (e) and hence state an optimal route. You must ensure that your answers to parts of questions are clearly labelled.
    You should show sufficient working to make your methods clear to the Examiner.
    Answers without working may not gain full credit.
    2. The table shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , to each of three demand points, 1, 2 and 3 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required.
27. Use the north-west corner method to obtain a possible solution. A partly completed table of improvement indices is given in Table 1 in the answer book.
28. Complete Table 1.
29. Taking the most negative improvement index to indicate the entering cell, use the steppingstone method once to obtain an improved solution. You must make your route clear and state your entering cell and exiting cell.
30. State the cost of your improved solution.
    2. (a) Explain the difference between the classical and the practical travelling salesperson problem. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total earnings. You must make your method clear and show the table after each stage.
    2. The table shows the least times, in seconds, that it takes a robot to travel between six points in an automated warehouse. These six points are an entrance, A, and five storage bins, B, C, D, E and F. The robot will start at A , visit each bin, and return to A . The total time taken for the robot's route is to be minimised.
31. Perform one iteration of the Simplex algorithm to obtain a new tableau, \(T\). State the row operations you use.
32. Write down the profit equation given by \(T\) and state the current values of the slack variables.