The figure shows an oil field with eight wells spaced uniformly
around the perimeter of a circle. The amount of oil produced at
each well is shown in the brackets. Oil is to be collected at
the wells and delivered to the tanks, at the center of the circle,
by a pipeline system.
The cost function for using pipes 1 through 8 is shown at
the right. It is a concave-piecewise-linear function. All the
arcs indexed from 1 through 8 have the same cost function. The
cost of using the pipes on the outside is lineare with the unit
cost of $5. Flow can go in either direction. Find the flow distribution
that minimizes total cost.