7.04f Network problems: choosing appropriate algorithm

4 A communications company is conducting a feasibility study into the installation of underground television cables between 5 neighbouring districts. The length of the possible pathways for the television cables between each pair of districts, in miles, is shown in the table. The pathways all run alongside cycle tracks. 4

1. Give a possible reason, in context, why some of the table entries are labelled as ***. 4
2. As part of the feasibility study, Sally, an engineer needs to assess each possible pathway between the districts. To do this, Sally decides to travel along every pathway using a bicycle, starting and finishing in the same district. From past experience, Sally knows that she can travel at an average speed of 12 miles per hour on a bicycle. Find the minimum time, in minutes, that it will take Sally to cycle along every pathway.
   [0pt] [4 marks]

1. Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4. Each task must be assigned to just one worker and each worker must do only one task.

The cost of assigning each worker to each task is shown in the table below.
The total cost is to be minimised.

1. Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the total cost. You must make your method clear and show the table after each stage.
2. State the minimum total cost.
   

4. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network of pipes. The uncircled number on each arc represents the capacity of the corresponding pipe. The numbers in circles represent an initial flow.

1. List the saturated arcs.
2. State the value of the initial flow.
3. Explain why arc FT cannot be full to capacity.
4. State the capacity of cut \(C _ { 1 }\) and the capacity of cut \(C _ { 2 }\)
5. By inspection find one flow-augmenting route to increase the flow by three units. You must state your route.
6. Prove that, once the flow-augmenting route found in part (e) has been applied, the flow is maximal.

This question should be answered on the sheet provided in the answer booklet. \includegraphics{figure_3} Figure 3 shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.

1. State the maximum flow along
   1. SAET,
   2. SBDT,
   3. SCFT.
   [3 marks]
2. Show these maximum flows on Diagram 1 on the answer sheet. [1 mark]
3. Taking your answer to part (b) as the initial flow pattern, use the labelling procedure to find a maximum flow from S to T. Your working should be shown on Diagram 2. List each flow augmenting route you find, together with its flow. [6 marks]
4. Indicate a maximum flow on Diagram 3. [2 marks]
5. Prove that your flow is maximal. [2 marks]

\includegraphics{figure_2} 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. [3]
2. State the maximum flow along
   1. \(W\) \(W_1\) \(A\) \(R_1\) \(R\),
   2. \(W\) \(W_3\) \(C\) \(R_2\) \(R\). [2]
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 flow-augmenting route you use, together with its flow. [5]
4. From your final flow pattern, determine the number of van loads passing through \(B\) each day. [1]

The company has the opportunity to increase the number of vans loads from one of the warehouses \(W_1\), \(W_2\), \(W_3\), to \(A\), \(B\) or \(C\).

1. Determine how the company should use this opportunity so that it achieves a maximal flow. [3]

\includegraphics{figure_4} Figure 4 shows a capacitated directed network. The number on each arc is its capacity. The numbers in circles show a feasible flow from sources \(A\) and \(B\) to sinks \(I\), \(J\) and \(K\). Take this as the initial flow pattern.

1. On Diagram 1 in the answer booklet, add a supersource \(S\) and a supersink \(W\) to obtain a capacitated network with a single source and single sink. State the minimum capacities of the arcs you have added. [3]
2. 1. Use the given initial flow and the labelling procedure on Diagram 2 to find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow.
   2. Verify that your flow is maximal.
   [9]
3. Show your maximum flow pattern on Diagram 3. [2]

\includegraphics{figure_1} Figure 1 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 \(C_1\), \(C_2\) and \(C_3\) are shown on Fig. 1.

1. Find the capacity of each of the three cuts. [3]
2. Verify that the flow of 26 is maximal. [1]

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.

1. By considering both options, explain which one meets the government's aim [3]

\includegraphics{figure_4} Figure 4 shows a capacitated directed network. The number on each arc is its capacity.

1. State the maximum flow along
   1. \(SADT\),
   2. \(SCET\),
   3. \(SBFT\). [2]
2. Show these maximum flows on Diagram 1 in the answer book. [1]

Take your answer to part (b) as the initial flow pattern.

1. 1. Use the labelling procedure to find a maximum flow from \(S\) to \(T\). Your working should be shown on Diagram 2 in the answer book. List each flow-augmenting route you use, together with its flow. [5]
   2. Draw your final flow pattern on Diagram 3 in the answer book. [2]
   3. Prove that your flow is maximal. [3]
2. Give an example of a practical situation that could have been modelled by the original network. [1]

1. Define the terms
   1. cut,
   2. minimum cut,
   as applied to a directed network flow. [2]

\includegraphics{figure_4} Figure 4 shows a capacitated directed network and two cuts \(C_1\) and \(C_2\). The number on each arc is its capacity.

1. State the values of the cuts \(C_1\) and \(C_2\). [3]

Given that one of these two cuts is a minimum cut,

1. Find a maximum flow pattern by inspection, and show it on the diagram in the answer book. [3]
2. Find a second minimum cut for this network. [1]

In order to increase the flow through the network it is decided to add an arc of capacity 100 joining \(D\) either to \(E\) or to \(G\).

1. State, with a reason, which of these arcs should be added, and the value of the increased flow. [2]

\includegraphics{figure_7} In solving a network flow problem using the labelling procedure, the diagram in Figure 7 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 Diagram 2 in the answer book, and complete the labelling procedure for these arcs. (3)
2. Write down the value of the initial flow shown in Figure 7. (1)
3. Use Diagram 2, 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. (5)
4. Show your flow on Diagram 3 and state its value. (3)
5. Prove that your flow is maximal. (2)

(Total 14 marks)

\includegraphics{figure_4} Figure 4 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 2 in the answer booklet. [2]
2. Find the values of \(x\) and \(y\), explaining your method briefly. [2]
3. Find the value of cuts \(C_1\) and \(C_2\). [3]

Starting with the given feasible flow of 68,

1. use the labelling procedure on Diagram 3 to find a maximal flow through this network. List each flow-augmenting route you use, together with its flow. [6]
2. Show your maximal flow on Diagram 4 and state its value. [3]
3. Prove that your flow is maximal. [2]

\includegraphics{figure_3} Figure 3 shows a capacitated directed network. The number on each arc is its capacity. \includegraphics{figure_4} Figure 4 shows a feasible initial flow through the same network.

1. Write down the values of the flow \(x\) and the flow \(y\). [2]
2. Obtain the value of the initial flow through the network, and explain how you know it is not maximal. [2]
3. Use this initial flow and the labelling procedure on Diagram 1 in this answer book to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow. [5]
4. Show your maximal flow pattern on Diagram 2. [2]
5. Prove that your flow is maximal. [2]

\includegraphics{figure_6} Figure 6 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. [2]

Diagram 2 in the answer book shows the first stage of the labelling procedure for the given initial flow.

1. Complete the initial labelling procedure in Diagram 2. [2]
2. 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. [6]
3. Show a maximal flow pattern on Diagram 3. [2]
4. Prove that your flow is maximal. [2]
5. Describe briefly a situation for which this network could be a suitable model. [2]

(Total 16 marks)

\includegraphics{figure_5} Figure 5 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 Figure 5.

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 Diagram 1 by entering values along arcs AC, CD, DE and DT. [2]
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. [5]
4. Show your maximal flow pattern on Diagram 2. [2]
5. Prove that your flow is maximal. [2]

\includegraphics{figure_6} Figure 6 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.

1. State the value of the initial flow. [1]
2. State the capacities of cuts \(C_1\) and \(C_2\). [2]

Diagram 3 in the answer book shows the labelling procedure applied to the above network.

1. Using Diagram 3, increase the flow by a further 19 units. You must list each flow-augmenting path you use, together with its flow. [5]
2. Prove that the flow is now maximal. [2]

(Total 10 marks)

\includegraphics{figure_5} 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 \(C_1\), \(C_2\) and \(C_3\) are shown on The diagram above.

1. Find the capacity of each of the three cuts. [3]
2. Verify that the flow of 26 is maximal. [1]

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.

1. By considering both options, explain which one meets the government's aim [3]

1. State Bellman's principle of optimality. [1]
2. Explain what is meant by a minimax route. [1]
3. Describe a practical problem that would require a minimax route as its solution. [2]

(Total 4 marks)

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\)	3	5	11	9
\(B\)	3	7	8	--
\(C\)	2	5	10	7
\(D\)	8	3	7	6

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. [9]
2. State, with a reason, whether this allocation is unique. [2]

(Total 11 marks)

1. Explain briefly the circumstances under which a degenerate feasible solution may occur to a transportation problem. [2]
2. Explain why a dummy location may be needed when solving a transportation problem. [1]

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.

	1	2	Supply
\(A\)	62	47	15
\(B\)	61	48	12
\(C\)	68	58	17
Demand	16	11

1. Complete the table below to show a possible initial feasible solution generated by the north-west corner method.

   	1	2	3
   \(A\)
   \(B\)			0
   \(C\)

   [1]
2. 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. [10]

(Total 14 marks)

\includegraphics{figure_9} 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 \(AC\), \(CD\), \(DE\) and \(DT\). \includegraphics{figure_9b} [2]
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. [5]
4. Show your maximal flow pattern on the diagram below. \includegraphics{figure_9d} [2]
5. Prove that your flow is maximal. [2]

(Total 14 marks)

Four athletes are put forward for selection for a mixed stage relay race at a local competition. They may each be selected for a maximum of one stage and only one athlete can be entered for each stage. The average time, in seconds, for each athlete to complete each stage is given below, based on past performances.

	Stage
	1	2	3
Alex	19	69	168
Darren	22	64	157
Leroy	20	72	166
Suraj	23	66	171

Use the Hungarian algorithm to find an optimal allocation which will minimise the team's total time. Your answer should show clearly how you have applied the algorithm. [11 marks]

A transportation problem has costs, in pounds, and supply and demand, in appropriate units, as given in the transportation tableau below.

	D	E	F	Supply
A	13	11	14	20
B	10	9	12	15
C	15	6	8	25
Demand	30	5	25

1. Find the initial solution given by the north-west corner rule and state why it is degenerate. [3 marks]
2. Use the stepping-stone method to obtain an optimal solution minimising total cost. State the resulting transportation pattern and its total cost. [15 marks]