Consider the problem of finding the maximum flow through a network from a set of supply points to a set of demand points. If there are alternate optima (different ways of maximizing the flow), you want to find the way that minimizes the total shipment cost. Associated with each link in the network is: a lower bound, lij; and upper bound, uij, and a unit cost, cij. An example network follows (Figure 2.54).
The problem is characterized by the inputs shown on the following page. Nodes S1, S2, and S3 are supply points; nodes D9 and D10 are demand points. Nodes 4–8 are transshipment points. Note that no flow is permitted between nodes S1 and 5 or between nodes S3 and 4. However, flow is permitted between nodes S1 and 6 and between nodes S3 and 8.
(a) Show how this problem—that of maximizing the flow from the source nodes to the destination nodes at minimum total cost—can be structured as an out-of-kilter flow problem. That is, draw the network that would be used in an out-of-kilter flow problem, clearly identifying the lower bounds, upper bounds, and unit costs on all links in the original network (such as the one shown above). If you elect to add any nodes or links, clearly label all link costs associated with these links as well.
(b) Suppose you want to find the minimum cost way of shipping as much as possible through the network subject to the condition that no shipment costs more than Cmax
to ship. (That is, all shipments must cost Cmax
or less to ship.) Discuss how this can be formulated as an out-of-kilter flow problem. Be careful here! You may need to change some of the costs in the original network to be sure you get the right answer!
(c) For the network data shown below, find the minimum cost way of shipping the maximum flow from the supply nodes to the demand nodes using the MENU-OKF algorithm.
(d) For the network data shown below, find the minimum cost way of shipping the maximum possible flow subject to the additional condition that no shipment costs more than 25 units.