Question: Network Optimization (20 pts)

The diagram below shows the proposed water network of a medium-sized city. There are two sources of water supply, A and B. There are 5 intermediate facilities, C, D, E, F and G, and they act as pumping stations where water passes through. The final destination is the city located in node H. Node H is the sink. City management is considering constructing the pipelines, shown as arcs in the diagram, with the proposed capacities (in cubic meter/min), shown in parenthesis. City management is proposing to get as much water from the sources to the city, restricted only by the capacities of the pipelines.

a. Using Solver, find the flow in each pipeline such that the total flow to the city is maximized. What is the maximum flow from the sources to the sink?

b. Now consider the diagram above. A cut in the network is a set of arcs which when deleted from the network will cause a total disruption of flow between the source(s) and the sink. The cuts K1 and K2 are examples. The cut capacity equals the sum of all capacities of its arcs. For example, the cut capacity of K1 is 120+140+80+60 = 400.

Other than K1 and K2, find 5 cuts and calculate their capacities. Determine the minimum capacity among all the cuts you listed. Is it equal to the maximum flow in part a?