Problem:
Read the referenced article (below) that fully describes the management science study summarized in the application vignette presented in Section 6.1.
Briefly describe how the model for a special type of minimum-cost flow problem was applied in this study. Then list the various financial and nonfinancial benefits that resulted from this study.
Section 6.1:
Before describing the general characteristics of minimum-cost flow problems, let us first look at a typical example.
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 shipping costs differ considerably among these shipping lanes. The cost per unit shipped through each lane is shown above the corresponding arrow in the network in Figure 6.2.
The objective is to minimize the total shipping cost through the distribution network.
To make the network less crowded, the problem usually is presented even more compactly, as shown in Figure 6.3. The number in square brackets next to the location of each facility indicates the net number of units (outflow minus inflow) generated there. Thus, the number of units terminating at each warehouse is shown as a negative number.
The number at the distribution center is 0 since the number of units leaving minus the number of units arriving must equal 0. The number on top of each arrow shows the unit shipping cost along that shipping lane.
Any number in square brackets underneath an arrow gives the maximum number of units that can be shipped along that shipping lane. (The absence of a number in square brackets underneath an arrow implies that there is no limit on the shipping amount there.) This network provides a complete representation of the problem, including all the necessary data, so it constitutes a network model for this minimum-cost flow problem.
Figure 6.1 The distribution network for the Distribution Unlimited Co. problem, where each feasible shipping lane is represented by an arrow.
(80 Units Produced) F1--------------------->W1 (60 Units Needed)
DC
(70 Units Produced)F2---------------------->W (90 Units Needed)
Page 258Figure 6.2 The data for the distribution network for the Distribution Unlimited Co. problem.
$700/unit
(80 Units Produced) F1--------------------->W1 (60 Units Needed)
(F1->DC=$300/unit 50 units max) DC (W1->DC $200/unit 50 units max)
(F2->DC=$500/unit 50 units max) (W2->DC $400/unit 50 units max)
(70 Units Produced) F2-------------------->W2 (90 Units Needed)
Since this is such a tiny problem, you probably can see what the optimal solution must be. (Try it.) This solution is shown in Figure 6.4, where the shipping amount along each shipping lane is given in parentheses. (To avoid confusion, we delete the unit shipping costs and shipping capacities in this figure.) Combining these shipping amounts with the unit shipping costs given in Figures 6.2 and 6.3, the total shipping cost for this solution (when starting by listing the costs from F1, then from F2, and then from DC) is
images
Figure 6.3 illustrates how a minimum-cost flow problem can be completely depicted by a network.
Figure 6.3 A network model for the Distribution Unlimited Co. problem as a minimum-cost flow problem.
[80] F1-------------------$700----------------->W1 [-60]
F1 to DC $300 [50] DC W1toDC $200[50]
F2 to DC $500 [50] W2 to DC $400 [50]
[70] F2------------------$1,000--------------->W2 [-90]
Figure 6.4 The optimal solution for the Distribution Unlimited Co. problem, where the shipping amounts are shown in parentheses over the arrows.
[80]F1-------------------(30)----------------->W1 [-60]
F1 to DC (50)/F2 to DC (30) DC(0) W1 to DC (30)/W2 to DC (50)
[70]F2-------------------(40)------------------>W2 [-90]