The next diagram 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 tables below the diagram 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. 10.5 to solve this problem.
(c) Formulate and solve a spreadsheet model for this problem.

Transcribed Image Text:

R1 R2 R3 To To To FromA B C FromD E F FromT R1 75 65- A60 45- 120 R2 40 50 60 B 70 55 45 E190 R3 -80 70 C 70 90 F 130