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*{Answer Book}
   1. (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.
   (2) The table below shows the distances, in km, between six data collection points, A, B, C, D, E, and F. \section*{Table 1}
9. You may not need to use all of these tables 3. Maximum income: \(\_\_\_\_\) Vicky must visit each city at least once. She will start and finish at A and wishes to minimise the total cost.
10. Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network.
    (2)
11. Use your answer to part (a) to help you calculate an initial upper bound for the length of Vicky's route.
    (1)
12. Show that there are two nearest neighbour routes that start from A . You must make your routes and their lengths clear.
13. State the best upper bound from your answers to (b) and (c).
14. 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.
16. 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. \begin{table}[h] Table of least distances
17. Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the cost. You must make your method clear and show the table after each stage.
18. Find the minimum cost.
    2. The table shows the least distances, in km, between six towns, A, B, C, D, E and F.
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.
    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.
29. 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.
30. Complete Table 1.
31. 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.
32. State the cost of your improved solution.
    2. (a) Explain the difference between the classical and the practical travelling salesperson problem. \begin{table}[h]
    \captionsetup{labelformat=empty} \caption{(a)}

    	P	Q	R	S	Supply
    A					13
    B					4
    C					12
    D					11
    Demand	11	10	11	8

    \end{table}
33. \begin{table}[h] 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, \(\mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { 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.
34. Perform one iteration of the Simplex algorithm to obtain a new tableau, \(T\). State the row operations you use.
    (5)
35. Write down the profit equation given by \(T\) and state the current values of the slack variables.
    2. Rani and Greg play a zero-sum game. The pay-off matrix shows the number of points that Rani scores for each combination of strategies.
36. You may not need to use all these tableaux

    b.v.	\(x\)	\(y\)	z	\(r\)	\(s\)	\(t\)	Value	Row Ops

    b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops

    b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops

    b.v.	\(x\)	\(y\)	z	\(r\)	\(s\)	\(t\)	Value	Row Ops

    b.v.	\(X\)	\(y\)	Z	\(r\)	\(s\)	\(t\)	Value	Row Ops

    2.

    	Greg plays 1	Greg plays 2	Greg plays 3
    Rani plays 1	- 3	1	2
    Rani plays 2	0	2	1
    Rani plays 3	2	4	- 5

    3
    3.

    	A	B	C	D	E	F	G
    A	-	x	41	43	38	21	30
    B	\(x\)	-	27	38	19	29	51
    C	41	27	-	24	37	35	40
    D	43	38	24	-	44	52	25
    E	38	19	37	44	-	20	28
    F	21	29	35	52	20	-	49
    G	30	51	40	25	28	49	-

    	A	B	C	D	E	F	G
    A	-	\(x\)	41	43	38	21	30
    B	\(x\)	-	27	38	19	29	51
    C	41	27	-	24	37	35	40
    D	43	38	24	-	44	52	25
    E	38	19	37	44	-	20	28
    F	21	29	35	52	20	-	49
    G	30	51	40	25	28	49	-

    4. .
37. Leave
    \includegraphics[max width=\textwidth, alt={}, center]{195b1c1f-5ce3-4762-80c3-34c26382b88b-269_844_1431_1886_463}
    5.

    	P	Q	R	Supply
    A	20	5	13	74
    B	7	15	8	58
    C	9	14	21	63
    D	22	16	10	85
    Demand	145	57	78

    	\(P\)	\(Q\)	\(R\)
    \(A\)
    \(B\)
    \(C\)
    \(D\)

    	\(P\)	\(Q\)	\(R\)
    \(A\)
    \(B\)
    \(C\)
    \(D\)

    	\(P\)	\(Q\)	\(R\)
    \(A\)
    \(B\)
    \(C\)
    \(D\)

    	\(P\)	\(Q\)	\(R\)
    \(A\)
    \(B\)
    \(C\)
    \(D\)

    	\(P\)	\(Q\)	\(R\)
    \(A\)
    \(B\)
    \(C\)
    \(D\)

    	\(P\)	\(Q\)	\(R\)
    \(A\)
    \(B\)
    \(C\)
    \(D\)

    	P	Q	R
    A
    B
    C
    D

    	\(P\)	\(Q\)	\(R\)
    \(A\)
    \(B\)
    \(C\)
    \(D\)

    	\(P\)	\(Q\)	\(R\)
    \(A\)
    \(B\)
    \(C\)
    \(D\)

    \section*{6. (a)} You may not need to use all the rows of this table

    Stage	State	Action	Dest.	Value

    Stage	State	Action	Dest.	Value

38. Weight:
39. Route:
41. (ii)