QUESTION 2 [TOTAL MARKS: 25] The network in Figure 1 represents the transfer of oil from three refineries, R1, R2 and R3, via pumping stations, P1 and P2, to the oil terminals, T1 and T2, where it is stored prior to distribution. The pipelines along which the oil travels have varying maximum capacity, each being able to only transfer a certain number of barrels of oil per day. These capacities are indicated on the arcs in thousands of barrels per day. R 5 T 4 3 R 6 5 T2 6 RS 6 Figure 1: Diagram of links between refineries, pumping stations and terminals. Q 2(a) [5 Marks] With the exception of the pumping station P1, all the other pumping stations can, if necessary, deal with the maximum amount of oil that its supply pipes can deliver. Pumping station P1 is being upgraded and at present can only deal with 8 thousand barrels per day Show how the network can be redrawn to convert it into a standard network with a single source, single sink and unrestricted nodes. Q 2(b) [5 Marks] In relation to an algorithm/method for finding the maximum flow permissible through a capacitated network, such as the one depicted in your answer to Q 2(a) above, discuss what is meant by a residual network and an augmenting path and how these aid the solution procedure. Q 2(c) [10 Marks] Determine the maximum flow through this network and determine how many barrels of oil each refinery should produce and each of the terminals should store. Q 2(d) [5 Marks] Discuss, with the aid of a suitable network diagram, what changes would be required to this problem to represent and solve it as a minimum cost flow problem. [End of Question 2] QUESTION 2 [TOTAL MARKS: 25] The network in Figure 1 represents the transfer of oil from three refineries, R1, R2 and R3, via pumping stations, P1 and P2, to the oil terminals, T1 and T2, where it is stored prior to distribution. The pipelines along which the oil travels have varying maximum capacity, each being able to only transfer a certain number of barrels of oil per day. These capacities are indicated on the arcs in thousands of barrels per day. R 5 T 4 3 R 6 5 T2 6 RS 6 Figure 1: Diagram of links between refineries, pumping stations and terminals. Q 2(a) [5 Marks] With the exception of the pumping station P1, all the other pumping stations can, if necessary, deal with the maximum amount of oil that its supply pipes can deliver. Pumping station P1 is being upgraded and at present can only deal with 8 thousand barrels per day Show how the network can be redrawn to convert it into a standard network with a single source, single sink and unrestricted nodes. Q 2(b) [5 Marks] In relation to an algorithm/method for finding the maximum flow permissible through a capacitated network, such as the one depicted in your answer to Q 2(a) above, discuss what is meant by a residual network and an augmenting path and how these aid the solution procedure. Q 2(c) [10 Marks] Determine the maximum flow through this network and determine how many barrels of oil each refinery should produce and each of the terminals should store. Q 2(d) [5 Marks] Discuss, with the aid of a suitable network diagram, what changes would be required to this problem to represent and solve it as a minimum cost flow problem. [End of Question 2]