The transportation problem deals with the distribution of goods from several points of supply (origins or sources) to a number of points of demand (destinations). Usually, we are given a capacity (supply) of goods at each source, a requirement (demand) for goods at each destination, and the shipping cost per unit from each source to each destination. An example is shown in Figure 9.1. The objective of such a problem is to schedule shipments so that total transportation costs are minimized. At times, production costs are also included.
Transportation models can also be used when a firm is trying to decide where to locate a new facility. Before opening a new warehouse, factory, or sales office, it is good practice to consider a number of alternative sites. Good financial decisions concerning the facility location also attempt to minimize total transportation and production costs for the entire system.
The Executive Furniture Corporation is faced with the transportation problem shown in Figure 9.1. The company would like to minimize the transportation costs while meeting the demand at each destination and not exceeding the supply at each source. In formulating this as a linear program, there are three supply constraints (one for each source) and three demand constraints (one for each destination). The decisions to be made involve the number of units to ship on each route, so there is one decision variable for each arc (arrow) in the network. Let
where
The LP formulation is
subject to
The solution is found using computer software, and the optimal shipping schedule is the following:
100 units from Des Moines to Albuquerque
200 units from Evansville to Boston
100 units from Evansville to Cleveland
200 units from Ft. Lauderdale to Albuquerque
100 units from Ft. Lauderdale to Cleveland
The total cost is $3,900. The following section will illustrate how this solution was found.
The solution to this transportation problem modeled as an LP problem could be found by using Solver in Excel 2016, as illustrated in Chapter 7; by using QM for Windows; or by using Excel QM in Excel 2016. When using Excel 2016 and Solver, the constraints could be entered in rows, as discussed in Chapter 7. However, the special structure for this problem allows for an easier and more intuitive input in Excel 2016 with Solver, and Excel QM will be used for this example to illustrate this.
Program 9.1 provides the input data and the solution for this example. Click the Excel QM tab and select the Alphabetical menu from the Excel QM ribbon. When the menu appears, scroll down and select Transportation. In the input window that opens, enter the number of Origins or sources (3 in this example) and the number of Destinations (3 in this example), select Minimize, and click OK. A worksheet appears and you enter the costs, supplies, and demands shown in the data table. Then click the Data tab, select Solver from the Data ribbon, and click Solve in the Solver input window. You do not have to write any formulas or change any of the parameters.
In this example, there were sources and destinations. The LP had variables and constraints. In general, for a transportation problem with m sources and n destinations, the number of variables is mn, and the number of constraints is For example, if there are 5 (i.e., ) constraints and 8 (i.e., ) variables, the linear program would have variables and constraints.
The use of the double subscripts on the variables makes the general form of the linear program for a transportation problem with m sources and n destinations easy to express. Let
The linear programming model is
subject to
The transportation method has proved to be especially useful in helping a firm decide where to locate a new factory or warehouse. Since a new location is an issue of major financial importance to a company, several alternative locations must ordinarily be considered and evaluated. Even though a wide variety of subjective factors is considered, including quality of labor supply, presence of labor unions, community attitude and appearance, utilities, and recreational and educational facilities for employees, a final decision also involves minimizing total shipping and production costs. This means that each alternative facility location should be analyzed within the framework of one overall distribution system.
To determine which of two locations should be selected for a new production facility, linear programming models will be developed for two transportation problems—one for each location. (If three or more locations were being considered, a transportation problem modeled as a linear programming model would be developed for each of these.) The existing sources and destinations will be used in each of these, and one new source will be included as well. This will find the minimum cost for the distribution system if that one source is added to the system. This will be repeated for the second source, and the minimum costs for these two problems will be compared to find which one is better. This will be illustrated in the following example.
The Hardgrave Machine Company produces computer components at its plants in Cincinnati, Salt Lake City, and Pittsburgh. These plants have not been able to keep up with demand for orders at Hardgrave’s four warehouses in Detroit, Dallas, New York, and Los Angeles. As a result, the firm has decided to build a new plant to expand its productive capacity. The two sites being considered are Seattle and Birmingham; both cities are attractive in terms of labor supply, municipal services, and ease of factory financing.
Table 9.1 presents the production costs and output requirements for each of the three existing plants, demand at each of the four warehouses, and estimated production costs of the new proposed plants. Transportation costs from each plant to each warehouse are summarized in Table 9.2.
WAREHOUSE | MONTHLY DEMAND (UNITS) | PRODUCTION PLANT | MONTHLY SUPPLY | COST TO PRODUCE ONE UNIT ($) |
---|---|---|---|---|
Detroit | 10,000 | Cincinnati | 15,000 | 48 |
Dallas | 12,000 | Salt Lake City | 6,000 | 50 |
New York | 15,000 | Pittsburgh | 14,000 | 52 |
Los Angeles | 9,000 | 35,000 | ||
46,000 | ||||
Supply needed from new plant units per month |
ESTIMATED PRODUCTION COST PER UNIT AT PROPOSED PLANTS | |
---|---|
Seattle | $53 |
Birmingham | $49 |
TO FROM | DETROIT | DALLAS | NEW YORK | LOS ANGELES |
---|---|---|---|---|
CINCINNATI | $25 | $55 | $40 | $60 |
SALT LAKE CITY | 35 | 30 | 50 | 40 |
PITTSBURGH | 36 | 45 | 26 | 66 |
SEATTLE | 60 | 38 | 65 | 27 |
BIRMINGHAM | 35 | 30 | 41 | 50 |
The important question that Hardgrave now faces is this: Which of the new locations will yield the lower cost for the firm in combination with the existing plants and warehouses? Note that the cost of each individual plant-to-warehouse route is found by adding the shipping costs (in the body of Table 9.2) to the respective unit production costs (from Table 9.1). Thus, the total production plus shipping cost of one computer component from Cincinnati to Detroit is $73 ($25 for shipping plus $48 for production).
To determine which new plant (Seattle or Birmingham) shows the lower total systemwide cost of distribution and production, we solve two transportation problems—one for each of the two possible combinations. The first linear program will be for the Seattle location, and the second will be for Birmingham. To evaluate the Seattle location, the variables are defined as follows:
where
The linear program formulation has an objective of minimizing the total cost—transportation cost plus production cost.
subject to
When this is solved, the total cost with the Seattle location is found to be $3,704,000.
For the second transportation model, the linear program is modified and the Birmingham location replaces the Seattle location. Now in the linear program, represents Birmingham instead of Seattle, the last constraint is for Birmingham instead of Seattle, and the costs for these four variables in the objective function are now 84 for for for and 99 for Nothing else in the problem changes. When this is solved, the total cost with the Birmingham location is $3,741,000. Thus, the Seattle location results in an overall lower cost and would be the preferred location based on cost.
Excel QM will be used for this example, and Program 9.2 provides the solution for the problem with the Seattle location. To enter the problem, click the Excel QM tab, select the Alphabetical menu from the Excel QM ribbon, and when the menu appears, scroll down to select Transportation. An input window opens and you simply enter the number of Origins (sources) and the number of Destinations, select Minimize, and click OK. A worksheet is then developed and you enter the numbers for the costs, the supplies, and the demands shown in the Data table in Program 9.2. Once all inputs have been entered, click the Data tab, select Solver, and click Solve from the Solver input window. No other input for Solver is necessary. The shipments for the optimal solution are shown in the Shipments table. Program 9.3 provides the Excel QM results for the Birmingham location.