What is a transportation problem Briefly discuss the decisio

What is a transportation problem?

Briefly discuss the decision variables, the objective function and constraint requirements in a transportation problem.

Give a real world example of the transportation problem.

Solution

The Transportation Problem was one of the original applications of linear programming models. The story goes like this. A firm produces goods at m diferent supply centers. Label these i = 1;:::;m. The supply produced at supply center i is Si . The demand for the good is spread out at n diferent demand centers. Label these j = 1;:::;n. The demand at the jth demand center is Dj . The problem of the firm is to get goods from supply centers to demand centers at minimum cost. Assume that the cost of shipping one unit from supply center i to demand center j is cij and that shipping cost is linear. That means that if you shipped xij units from supply center i to demand center j, then the cost would be cij xij .

I have already done one of the steps of formulating the problem: I have introduced variables. Let me be explicit. Define xij to be the number of units shipped from supply center i to demand center j. The problem is to identify the minimum cost shipping schedule. The constraints are that you must (at least) meet demand at each demand center and cannot exceed supply at each supply center.

The cost of the schedule, by the linearity assumption, is given by minXm i=1 Xn j=1 xij cij

CONSRAINTS

Now let\'s gure out the constraints. Consider supply center i. The total amount shipped out of supply center i is Pn j=1 xij . Think about this expression. xij is what you ship from i to j. From i you can ship to any demand center (j = 1;:::;n). The sum above just adds up the total shipment from supply center i. This quantity cannot exceed the supply available. Hence we have the constraint

Xn j=1 xij Si for all i = 1; : : : ; m:

Similarly, the constraints that guarantee that you meet the demand at each of the demand centers look like:

Xm i=1 xij Dj for all j = 1; : : : ; n:

Consider the feasibility of the problem. The only way that the problem can be feasible is if total supply exceeds total demand (Pn j=1 Dj Pm i=1 Si . If this equation did not hold, then there would be excess demand. There would be no way to meet all of the demand with available supply. If there is enough supply, then you should be able to convince yourself that you can satisfy the constraints of the problem. That is, the problem is feasible unless there is excess demand. It is conventional to assume that the total supply is equal to the total demand. If so, that is, if

Xn j=1 Dj = Xm i=1 Si

then all of the constraints in the problem must hold as equations (that is, when total supply equals total demand, then a feasible transportation plan exactly meets demand at each demand center and uses up all of the supply at each supply center). (In cases where there is excess supply, you can transform the problem into one in which supply is equal to demand by assuming that you can freely dispose of the extra supply.)

EXAMPLE

A lumber company has three sources of wood and ve markets where wood is demanded. The annual quantity of wood available in the three sources of supply are 15, 20, and 15 million board feet respectively. The amount that can be sold at the ve markets is 11, 12, 9, 10, and 8 million board feet, respectively. The company currently transports all of the wood by train. It wishes to evaluate its transportation schedule, possibly shifting some or all of its transportation to ships. The unit cost of shipment (in $10,000 along the various routes using both methods is described in the table below.

Supply Market 1 Market 2 Market 3 Market 4 Market 5

A 51 62 35 45 56

B 59 68 50 39 46

C 49 56 53 51 37

Cost per Unit of Rail Transport

Supply Market 1 Market 2 Market 3 Market 4 Market 5

A 48 68 48 none 54

B 66 75 55 49 57

C none 61 64 59 50

Cost per Unit of Ship Transport

The management needs to decide to what extent to continue to rely on rail transportation. Evaluate the following options and make a recommendation about what to do.

1. How much does it cost use rail transport exclusively?

2. How much does it cost to use ships exclusively?

3. How much does it cost to use the cheapest available mode of transportation on each route?

4. Suppose that there is an annual cost of $100,000 to operate any ships (but that this cost does not vary with the number of shipping lines kept open). What is the optimal transportation plan?

5. How would your answer change if you learned that the supply at Center B and the demand at market 3 were both expected to increase by 10 million board feet?