Choose one of the network flow models discussed in this week's chapter. Describe a situation in which this model could be used. What quantities would be represented by the arcs? What quantities would be represented by the nodes?

Model:

6.1MINIMUM-COST FLOW PROBLEMS

Before describing the general characteristics of minimum-cost flow problems, let us first look at an example. For clarity, this first example is a tiny one, but otherwise it is typical of the sometimes huge minimum-cost flow problems that arise in practice.

An Example: The Distribution Unlimited Co. Problem The Distribution Unlimited Co. has two factories producing a product that needs to be shipped to two warehouses. Here are some details.

Factory 1 is producing 80 units.

Factory 2 is producing 70 units.

Warehouse 1 needs 60 units.

Warehouse 2 needs 90 units.

(Each unit corresponds to a full truckload of the product.)

Figure 6.1 shows the distribution network available for shipping this product, where F1 and F2 are the two factories, W1 and W2 are the two warehouses, and DC is a distribution center. The arrows show feasible shipping lanes. In particular, there is a rail link from Factory 1 to Warehouse 1 and another from Factory 2 to Warehouse 2. (Any amounts can be shipped along these rail links.) In addition, independent truckers are available to ship up to 50 units from each factory to the distribution center, and then to ship up to 50 units from the distribution center to each warehouse. (Whatever is shipped to the distribution center must subsequently be shipped on to the warehouses.) Management's objective is to determine the shipping plan (how many units to ship along each shipping lane) that will minimize the total shipping cost.

The objective is to minimize the total shipping cost through the distribution networ

FIGURE 6.1

The distribution network for the Distribution Unlimited Co. problem, where each feasible shipping lane is represented by an arrow.