The diagram to the right depicts a system of aqueducts that originate at three rivers (nodes R1, R2, and R3) and terminate at a major city

(node T), where the other nodes are junction points in the system.

Using units of thousands of acre feet, the following tables show the maximum amount of water that can be pumped through each aqueduct per day The city water manager wants to determine a flow plan that will maximize the flow of water to the city.

(a) Formulate this problem as a maximum flow problem by identifying a source, a sink, and the transshipment nodes, and then drawing the complete network that shows the capacity of each arc.

(b) Use the augmenting path algorithm described in Sec. 9.5 to solve this problem.

C

(c) Formulate and solve a spreadsheet model for this problem.