The Transportation Model


[Page 223 ( continued )]

The transportation model is formulated for a class of problems with the following unique characteristics: (1) A product is transported from a number of sources to a number of destinations at the minimum possible cost; and (2) each source is able to supply a fixed number of units of the product, and each destination has a fixed demand for the product. Although the general transportation model can be applied to a wide variety of problems, it is this particular application to the transportation of goods that is most familiar and from which the problem draws its name .

In a transportation problem , items are allocated from sources to destinations at a minimum cost .


The following example demonstrates the formulation of the transportation model. Wheat is harvested in the Midwest and stored in grain elevators in three different citiesKansas City, Omaha, and Des Moines. These grain elevators supply three flour mills, located in Chicago, St. Louis, and Cincinnati. Grain is shipped to the mills in railroad cars, each car capable of holding 1 ton of wheat. Each grain elevator is able to supply the following number of tons (i.e., railroad cars ) of wheat to the mills on a monthly basis:

Grain Elevator

Supply

1. Kansas City

150

2. Omaha

175

3. Des Moines

275

Total

600 tons


Each mill demands the following number of tons of wheat per month:

Mill

Demand

A. Chicago

200

B. St. Louis

100

C. Cincinnati

300

Total

600 tons


The cost of transporting 1 ton of wheat from each grain elevator (source) to each mill (destination) differs , according to the distance and rail system. (For example, the cost of shipping 1 ton of wheat from the grain elevator at Omaha to the mill at Chicago is $7.) These costs are shown in the following table:


[Page 224]
 

Mill

Grain Elevator

A. C HICAGO

B. S T . L OUIS

C. C INCINNATI

1. Kansas City

$6

$8

$10

2. Omaha

7

11

11

3. Des Moines

4

5

12


The problem is to determine how many tons of wheat to transport from each grain elevator to each mill on a monthly basis to minimize the total cost of transportation. A diagram of the different transportation routes, with supply and demand, is given in Figure 6.1.

The linear programming model for a transportation problem has constraints for supply at each source and demand at each destination .


Figure 6.1. Network of transportation routes for wheat shipments


The linear programming model for this problem is formulated as follows :

In this model the decision variables , x ij , represent the number of tons of wheat transported from each grain elevator, i (where i = 1, 2, 3), to each mill, j (where j = A, B, C). The objective function represents the total transportation cost for each route. Each term in the objective function reflects the cost of the tonnage transported for one route. For example, if 20 tons are transported from elevator 1 to mill A, the cost ($6) is multiplied by x 1A (= 20), which equals $120.


[Page 225]

The first three constraints in the linear programming model represent the supply at each elevator; the last three constraints represent the demand at each mill. As an example, consider the first supply constraint, x 1A + x 1B + x 1C = 150. This constraint represents the tons of wheat transported from Kansas City to all three mills: Chicago ( x 1A ), St. Louis ( x 1B ), and Cincinnati ( x 1C ). The amount transported from Kansas City is limited to the 150 tons available. Note that this constraint (as well as all others) is an equation (=) rather than a inequality because all the tons of wheat available will be needed to meet the total demand of 600 tons. In other words, the three mills demand 600 total tons, which is the exact amount that can be supplied by the three grain elevators. Thus, all that can be supplied will be , in order to meet demand. This type of model, in which supply exactly equals demand, is referred to as a balanced transportation model .

In a balanced transportation model in which supply equals demand, all constraints are equalities .


Realistically, however, an unbalanced problem , in which supply exceeds demand or demand exceeds supply, is a more likely occurrence. In our wheat transportation example, if the demand at Cincinnati is increased from 300 tons to 350 tons, a situation is created in which total demand is 650 tons and total supply is 600 tons. This would result in the following change in our linear programming model of this problem:

One of the demand constraints will not be met because there is not enough total supply to meet total demand. If, instead, supply exceeds demand, then the supply constraints would be .

Sometimes one or more of the routes in the transportation model may be prohibited . That is, units cannot be transported from a particular source to a particular destination. When this situation occurs, we must make sure that the variable representing that route does not have a value in the optimal solution. This can be accomplished by assigning a very large relative cost as the coefficient of this prohibited variable in the objective function. For example, in our wheat-shipping example, if the route from Kansas City to Chicago is prohibited (perhaps because of a rail strike), the variable x 1A is given a coefficient of 100 instead of 6 in the objective function, so x 1A will equal zero in the optimal solution because of its high relative cost. Alternatively the prohibited variable can be deleted from the model formulation.

Time Out: For Frank L. Hitchcock and Tjalling C. Koopmans

Several years before George Dantzig formalized the linear programming technique, in 1941 Frank L. Hitchcock formulated the transportation problem as a method for supplying a product from several factories to a number of cities, given varying freight rates. In 1947 T. C. Koopmans independently formulated the same type of problem. Koopmans, an American economist originally from the Netherlands and a professor at Chicago and Yale, was awarded the Nobel Prize in 1975.



[Page 226]

Management Science Application: Transportation Models at Nu-kote International

Nu-kote International, located near Nashville, Tennessee, is the largest independent manufacturer and distributor of supplies for home and office printing equipment, including ink-jet, laser, and toner cartridges; ribbons ; and thermal fax supplies. It produces more than 2,000 products for use in more than 30,000 different types of imaging devices, and it serves more than 5,000 customers (e.g., commercial dealers and retail stores) around the world.

Nu-kote's transportation network includes five plants and four warehouses in China; Chatsworth, California; Rochester, New York; Connellsville, Pennsylvania; and Franklin, Tennessee. Almost 80% of Nu-kote's products are manufactured in its Chatsworth plant or imported from China through the port of Long Beach. Nu-kote originally shipped most of its orders to its customers from its Franklin warehouse, which is within 500 miles of 50% of the U.S. population and within 1,000 miles of 80% of its customers. The other three U.S. warehouses were used for storing materials for manufacturing and for storing finished goods before shipping them to Franklin.

Nu-kote developed an Excel spreadsheet linear programming model to determine the optimal (least-cost) shipments of items from its vendors and plants to its warehouses and from its warehouses to its customers. Different linear programming models were tested for different warehouse configurations; they included between 5,000 and 9,700 variables and 2,450 constraints. Decision variables were defined for the units of each product shipped from each vendor and plant to each warehouse and from each warehouse to each customer; constraints included capacities and demand at each facility. Nu-kote used the models to determine that it was more cost-effective to ship products to customers from two warehouses than from one, so it expanded its Chatsworth warehouse to ship finished products to customers from it, in addition to shipping from its Franklin warehouse. This new two-warehouse system reduced shipping times to its customers and saved approximately $1 million in annual transportation and inventory costs.

Source: L. J. LeBlanc, J. A. Hill, G. W. Greenwell, and A. O. Czesnat, "Nu-kote's Spreadsheet Linear-Programming Models for Optimizing Transportation," Interfaces 34, no. 2 (MarchApril 2004): 139146.





Introduction to Management Science
Introduction to Management Science (10th Edition)
ISBN: 0136064361
EAN: 2147483647
Year: 2006
Pages: 358

Similar book on Amazon

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net