The Texago Corporation has four oil fields, four refineries, and four distribution centers. A major strike involving the transportation industries now has sharply curtailed Texago€™s capacity to ship oil from the oil fields to the refineries and to ship petroleum products from the refineries to the distribution centers. Using units of thousands of barrels of crude oil (and its equivalent in refined products), the following tables show the maximum number of units that can be shipped per day from each oil field to each refinery, and from each refinery to each distribution center. The Texago management now wants to determine a plan for how many units to ship from each oil field to each refinery and from each refinery to each distribution center that will maximize the total number of units reaching the distribution centers.

(a) Draw a rough map that shows the location of Texago€™s oil fields, refineries, and distribution centers. Add arrows to show the flow of crude oil and then petroleum products through this distribution network.
(b) Redraw this distribution network by lining up all the nodes representing oil fields in one column, all the nodes representing refineries in a second column, and all the nodes representing distribution centers in a third column. Then add arcs to show the possible flow.
(c) Modify the network in part (b) as needed to formulate this problem as a maximum flow problem with a single source, a single sink, and a capacity for each arc.
(d) Use the augmenting path algorithm described in Sec. 10.5 to solve this maximum flow problem.
(e) Formulate and solve a spreadsheet model for this problem.

Transcribed Image Text:

Refinery Oil Field New Orleans Charleston Seattle St. Louis Texas California Alaska Middle East 8 4 8 12 4 6 15 9 Distribution Center Refinery Pittsburgh Atlanta Kansas City San Francisco New Orleans Charleston Seattle St. Louis 9 6 9 4 4 12 6 9