Transportation Problem
Dr. Mohammed Shamim Uddin Khan
Learning objectives:
After completing this chapter, you should be able to:
(i) Give a general description of Transportation Problem.
(ii) Construct and solve Transportation Problem.
Transportation Problem: The transportation problem arises frequently in planning for
the distribution of goods and services from several supply locations to several demand
locations. Typically, the quantity of goods available at each supply location (origin) is
limited, and the quantity of goods needed at each of several demand locations
(destinations) is known. With a variety of shipping routes and differing costs for the
routes, the objective is to determine how many units should be shipped from each origin
to each destination so that all destination demands are satisfied and total transportation
costs are minimized.
Transportation problem is one of the sub-classes of linear programming problem.
But transportation techniques are more simple than simplex. The earliest formulation of
this basic transportation problem was stated by F. L. Hitchcock in 1941 and later
expanded by T. C. Koopmans. In 1953 W. W. Cooper and A. Charnes developed the
stepping-stone method, a special purpose algorithm for solving the transportation
problem. Subsequent improvements led to the computationally easier modified
distribution (MODI) method in 1955.
Characteristics of Transportation Problem:
1. Objective function is to reduce the distribution (transportation) cost to the
minimum.
2. Maximum quantity available at the source (factory) is limited. This is a constraint.
3. Maximum quantity required at the destination (warehouse) is specified. This
cannot be exceeded. This is a second constraint.
4. Transportation cost is specified for each item.
5. Transportation problem deals with a single homogeneous product or commodity.
6. Sum of the products available from all sources put together will be equal to sum
of the products distributed at various destinations.
Uses of Transportation Problem:
1. Reduce distribution and transportation cost.
2. Improve competitiveness of product.
3. Assist proper location of warehouses.
4. Assist proper location of new factories/plant being planned.
5. Close-down warehouses which are found costly and uneconomical.
Solution Methods of Transportation Problem::
1. Initial Feasible Solution:
(a) North-West Corner Rule
(b) Vogel’s Approximation Method (VAM)
(c) Minimum-Cost Method
(d) Row Minimum Method
(e) Column Minimum Method
1
2. Optimal Solution:
(a) MODI(Modified Distribution) method
(b) Stepping Stone Method
Solution Procedure of Minimum-Cost Method:
Step 1: Identify the cell in the transportation tableau with the lowest cost, and allocate as
much flow as possible to this cell. In case of a tie, choose the cell corresponding to the
arc over which the most units can be shipped. If ties still exist, choose any of the tied
cells.
Step 2: Reduce the row supply and the column demand by the amount of flow allocated
to the cell identified in Step 1.
Step 3: If all row supplies and column demands have been exhausted then stop; the
allocations made will provide an initial feasible solution. Otherwise, continue with step 4.
Step 4: If the row supply is now zero, eliminate the row from further consideration by
drawing a line through it. If the column demand is now zero, eliminate the column by
drawing a line through it.
Step 5: Continue with step 1 for all unlined rows and columns.
Question: Find the initial basic feasible solution of the following transportation problem
by Minimum –Cost method:
Solution:
Table1
D/S A B C Total
I 1 2 3 50
II 3 2 1 80
III 4 5 6 75
IV 3 1 2 95
Total 120 80 100 300
Table2
D/S A C Total
III 4 6 75
IV 3 2 15
Total 70 20 90
Table3
D/S A C Total
III 4 6 75
Total 70 5 75
Minimum cost = (80X1) + (80X1) + (50X1) + (15X2) + (70X4) + (5X6) = $550.
Solution Procedure of VAM:
Step 1: Jot down the difference between the lowest and second lowest cost in each row.
Step 2: Repeat for each column.
Step 3: Identify the row or column with greatest difference (resolving ties arbitrarily).
2
Step 4: Identify the cell in the chosen row or column, which has the lowest cost.
Step 5: Put as much as possible in the chosen cell.
Step 6: Repeat the procedure excluding the row or column, which is now satisfied.
Step 7: Continue until the entire amount is transported.
Question: Find the initial basic feasible solution of the following transportation problem:
Warehouse/Factory W1 W2 W3 W4 Factory
capacity
F1 19 30 50 10 7
F2 70 30 40 60 9
F3 40 8 70 20 18
Warehouse 5 8 7 14 34
requirement
Solution:
Table 1
Warehouse/ W1 W2 W3 W4 Factory Penalties
Factory capacity
F1 19 30 50 10 7 9
F2 70 30 40 60 9 10
F3 40 8 70 20 18 12
Warehouse 5 8 7 14 34
requirement
Penalties 21 22 10 10
x32 = 8, c32 = 8
Table 2
Warehouse/ W1 W3 W4 Factory Penalties
Factory capacity
F1 19 50 10 7 9
F2 70 40 60 9 20
F3 40 70 20 10 20
Warehouse 5 7 14 26
requirement
Penalties 21 10 10
x11 = 5, c11 = 19
Table 3
Warehouse/ W3 W4 Factory Penalties
Factory capacity
F1 50 10 2 40
F2 40 60 9 20
F3 70 20 10 50
Warehouse 7 14 21
requirement
Penalties 10 10
3
x34 = 10, c34 = 20
Table 4
Warehouse/ W3 W4 Factory Penalties
Factory capacity
F1 50 10 2 40
F2 40 60 9 20
Warehouse 7 4 11
requirement
Penalties 10 50
x14 = 2, c14 = 10, x24 = 2, c32 = 60, x23 = 7, c23 = 40
The total cost = (5X19) + (8X8) + (2X10) + (2X60) + (10X20) + (7X40) = $779
Question: Find the initial basic feasible solution of the following transportation problem
by VAM:
Warehouse/Factory W1 W2 W3 W4 Factory
capacity
F1 1 6 3 6 20
F2 7 3 1 6 10
F3 9 4 5 4 25
Warehouse 11 13 17 14 55
requirement
Solution:
Table1
Warehouse/ W1 W2 W3 W4 Factory Penalties
Factory capacity
F1 1 6 3 6 20 2
F2 7 3 1 6 10 2
F3 9 4 5 4 25 1
Warehouse 11 13 17 14 55
requirement
Penalties 6 1 2 2
x11 = 11, c11 = 1
Table 2
Warehouse/ W2 W3 W4 Factory Penalties
Factory capacity
F1 6 3 6 9 3
F2 3 1 6 10 2
F3 4 5 4 25 1
Warehouse 13 17 14 44
requirement
Penalties 1 2 2
4
x13 = 9, c13 = 3
Table3
Warehouse/ W2 W3 W4 Factory Penalties
Factory capacity
F2 3 1 6 10 2
F3 4 5 4 25 1
Warehouse 13 8 14 35
requirement
Penalties 1 4 2
x23 = 8, c23 = 1
Table 4
Warehouse/ W2 W4 Factory Penalties
Factory capacity
F2 3 6 2 3
F3 4 4 25 0
Warehouse 13 14 27
requirement
Penalties 1 2
x22 = 2, c22 = 3, x32 = 11, c32 = 4 , x34 = 4, c34 = 14
Total cost = (1X11) + (3X9) + (8X1) + (2X3) + (11X4) + (4X14) = $152
Question: Find the initial basic feasible solution of the following transportation problem by
North-West Corner Rule:
S/D A B C Total
I 1 4 6 1000
II 3 5 9 2000
III 2 7 8 3000
Total 1000 2500 2000
Solution:
Table 1
S/D A B C D Total
I 1 1000 4 6 0 1000
II 3 5 2000 9 0 2000
III 2 7 500 8 2000 0 500 3000
Total 1000 2500 2000 500 6000
Total cost = (1X1000) + (5X2000) + (7X500) + (8X2000) = $30500
Question: Find the initial basic feasible solution of the following transportation problem by
North-West Corner Rule:
5
S/D A B C Total
I 1 4 6 1000
II 3 5 9 2000
III 2 7 8 2000
Total 1000 2500 3000
Solution:
Table 1
S/D A B C Total
I 1 1000 4 6 1000
II 3 5 2000 9 2000
III 2 7 500 8 1500 2000
IV 0 0 0 1500 1500
Total 1000 2500 3000 6500
Total cost = (1X1000) + (5X2000) + (7X500) + (8X1500) = $26500
Comparison of Initial Solution by Different Methods:
1. All solutions are Non-degenerate Basic Feasible.
2. Solutions are not unique.
3. Solution depends on selection of appropriate row for allocation. In case of tie,
such selection is arbitrary. Hence solution differs.
4. Some of the solution (by VAM) appears to be optimum.
Solution Procedure of MODI Method:
The steps to evaluate unoccupied cells are as follows:
Step 1: For an initial basic feasible solution with occupied cells, calculate and
for rows and columns. The initial solution can be obtained by any of the three (North-
West Corner Rule, Least Cost Method and Vogel’s Approximation Method) methods
discussed earlier.
To start with any one of ’s and ’s is given the value zero. It is better to assign
zero for a particular or where there are maximum number of allocations in a row or
column respectively, as it will reduce arithmetic work considerably. Then complete the
calculation of ’s and ’s for other rows and columns by using the relation ; for
all occupied cells (i, j).
Step 2: For unoccupied cells, calculate the opportunity cost by using the relation
; for all i and j.
Step 3: Examine sign of each .
(i) If , then current basic feasible solution is optimal.
(ii) , then current basic feasible solution will remain unaffected but an
alternative solution exists.
(iii) If one or more , then an improved solution can be obtained by entering
unoccupied cell (i, j) in the basis. An unoccupied cell having the largest negative
value of is chosen for entering into the solution mix (new transportation schedule).
6
Step 4: Construct a closed path (or loop) for the unoccupied cell with largest negative
opportunity cost. Start the close path with the selected unoccupied cell and mark a plus
(+) sign in this cell, trace a path along the rows (or columns) to an occupied cell, mark the
corner with minus (-) sign and continue down the column (or row) to an occupied cell
and mark the corner with plus (+) sign and minus (-) sign alternatively. Close the path
back to the selected unoccupied cell.
Step 5: Locate the smallest quantity allocated to a cell marked with a minus sign. Allocate
this value to the selected unoccupied cell and add it to other occupied cells marked with
plus (+) signs and subtract it from the occupied cells marked with minus signs.
Step 6: Obtain a new improved solution by allocating units to the unoccupied cell
according to Step 5 and calculate the new total transportation cost.
Step7: Test the revised solution for optimality.
Remark: The loop starts and ends at the selected unoccupied cell. It consists of
successive horizontal and vertical (connected) lines whose end points must be occupied
cells, except for the end points associated with entering unoccupied cell. This means that
every corner element of the loop must be an occupied cell.
It is immaterial whether the loop is traced in a clock-wise or anti-clockwise
direction. However, for a given solution only one loop can be constructed for each
unoccupied cell.
Question: A Company has factories at F 1, F2 and F3 which supply warehouses at W1, W2
and W3. Weekly factory capacities are 200, 160 and 90 units respectively. Weekly
warehouse requirements are 180, 120 and 150 units respectively. Unit shipping costs (in
TK.) are as follows:
F/W W1 W2 W3 Supply
F1 16 20 12 200
F2 14 8 18 160
F3 26 24 16 90
Demand 180 120 150 450
Determine the optimal distribution for this company to optimize shipping costs.
Solution:
Initial basic feasible solution obtained by North West Corner Rule is given in the following
Table-1.
Table-1
F/W W1 W2 W3 Supply
F1 16 20 12 200
18 2
0 0
F2 14 8 18 160
10 6
0 0
F3 26 24 16 90
9
0
Demand 180 120 150 450
7
The initial solution has allocations. Therefore it is a non-degenerate
solution. The optimality test can therefore be performed. The total transportation cost
associated with this solution is
Determining the values of ’s and ’s as usually by assigning arbitrarily. Given
, the values of other so obtained by using the relation for occupied cells
is shown in Table-2.
The opportunity cost for each of the unoccupied cells is determined by using the relation
as shown below:
The value of in the cell (F1, W3) is indicating that the total transportation cost
can be reduced in the multiple of 18 by introducing this cell in the new transportation
schedule. To how many units of the commodity could be allocated to this cell (route) we
shall form a closed path as shown in Table-2.
The smallest number of units of the commodity which should be allocated to the cell (F 1,
W2) is 20 units because it does not violate the supply and demand restrictions (minimum
allocation among the occupied cells bearing negative sign at the corners of the loop). The
new transportation schedule so obtained shown in Table-3.
Table-2
F/W W1 W2 W3 Supply
F1 16 20 12 200
18 2
(-) (+).
6
0 0
F2 0
14 8 18 160
10
(+) (-)
0
F3 26 24 16 90
9
0
Demand 180 120 150 450
8
Table-3
F/W W1 W2 W3 Supply
F1 16 20 12 200
18 2
0 0
F2 14 8 18 160
12 4
0 0
F3 26 24 16 90
9
0
Demand 180 120 150 450
The total transportation cost associated with this solution is
.
To test the optimality of the new solution shown in Table-3, again calculating the
opportunity cost of each unoccupied cell in the same manner as discussed earlier. The
calculations of ’s, ’s and are shown in Table-4.
The opportunity cost for each of the unoccupied cells is determined by using the relation
as shown below:
The value of in the cell (F2, W1) is indicating that the total transportation cost
can further be reduced in the multiple of 8 by introducing this cell in the new
transportation schedule. The new solution is obtained in the same manner by introducing
40 units of the commodity in the cell (F2, W1) as indicated in Table-4. The new solution is
shown in Table-5.
Table-4
F/W W1 W2 W3 Supply
F1 16 20 12 2 200
18
(+). 0
0 4
(-)
0
9
F2 14 8 18 160
12
(+) (-)
0
F3 26 24 16 90
9
0
Demand 180 120 150 450
Table-5
F/W W1 W2 W3 Supply
F1 16 20 12 200
14 6
0 0
F2 14 8 18 160
4 12
0 0
F3 26 24 16 90
9
0
Demand 180 120 150 450
The total transportation cost associated with this solution is
.
To test the optimality of the new solution shown in Table-5, again calculating the
opportunity cost of each unoccupied cell in the same manner as discussed earlier. The
calculations of ’s, ’s and are shown in Table-6.
The opportunity cost for each of the unoccupied cells is determined by using the relation
as shown below:
10
Table-6
F/W W1 W2 W3 Supply
F1 16 20 12 200
14 6
0 0
F2 14 8 18 160
4 12
0 0
F3 26 24 16 90
9
0
Demand 180 120 150 450
Since none of the unoccupied cells in Table-6 is having a negative opportunity
cost value, therefore total transportation cost cannot be reduced further. Thus the solution
shown in Table-6 is the optimal solution giving optimal transportation schedule with a
total cost of Tk.5920.
11
