A relief agency is urgently trying to get the maximum possible quantity of supplies from its base at Alto to the volcano-ravaged city of Epi.

One available road goes via Billi. The agency estimates that the Alto-to-Billi part of that road can carry 500 tons per day, and the Billi-to-Epi segment, 320 tons. A second route goes via Chau and Domo, with the Alto-to-Chau part having capacity 650 tons, the Chau-to-Domo section, 470, and the Domo-to-Epi segment, 800. There is also a small mountain road with capacity 80 tons that connects Billi to Domo.

(a) Formulate this problem as a maximum flow model by sketching the associated digraph. Indicate the source, the sink, and all capacities.

(b) Solve your maximum flow problem by inspection.

(c) Show how to modify your digraph of part

(a) as in Figure 10.25 to represent the model as a minimum cost network flow problem.