Sewerage from a proposed treatment plant is to be pumped through an existing network of pipes leading from the plant to a holding tank. The map in Figure 1 below represents the network of pipes where the nodes (2-14) represent pumping stations and node (1) is the treatment plant and node (15) is the holding tank. The numbers on the ares denote the maximum flow for each pipe in Megalitres per day. Moreover, flow in each pipe is restricted to one way but can be in either direction (see Figure 1 below). 7 10 12 11 6 2 10 5 10 13 18 2 10 en 3 13 1 15 12 12 14 15 17 13 2 2 5 2 3 15 11 11 14 12 11 2 Figure 1: Map of Sewerage pipeline network showing maximum flow restriction in each pipeline section.(a) What is the maximum volume of sewerage (in Megalitres) that can be pumped per day from the treatment plant to the holding tank? (b) Indicate clearly on a diagram the direction in which the sewerage should be pumped in the network in order to maximize the volume of sewerage pumped per day. (c) To satisfy the manufacturers specifications each pumping station must be connected to a network of higher quality pipes. The costs for upgrading each section of pipeline to the higher quality pipeline (in millions of dollars) are shown in Figure 2. The local council proposes to only initially upgrade some of the pipes so that the treatment plant, holding tank and each pumping station, (1) through (15), is linked to every other location by sections consisting of only upgraded pipes. Which pipes should be upgraded if costs are to be minimized? 1.8 1.2 0.3 1.7 0.3 2 5 10 13 0.6 0.8 0.4 1.5 0.6 1.7 0.8 0.8 12 15 0.3 0.7 1.3 0.6 0.7 0.9 0.5 1.4 0.5 0.8 0.7 0.5 11 14 0.6 1.6 0.4 1.5 1.2 Figure 2: Map of sewerage pipeline network showing showing the cost of upgrading each