INTRODUCTION
Transportation problems are one of the subclasses of LPPs in which the objective is to transport various quantities of a single homogenous commodity that are initially stored at various origins, to different destinations in such a way that the transportation cost is minimum. In this unit, you will also learn about the test for optimality and degeneracy in transportation, as well as the assignment problem, the objective of which is to assign a number of origins to an equal number of destinations at minimum cost or maximum profit.
UNIT OBJECTIVES
After going through this unit, you will be able to:
Explain and solve transportation problems
Perform the optimality test using the MODI method
Resolve degeneracy in transportation problems
Describe what is unbalanced transportation
Solve assignment problems using the Hungarian Method
TRANSPORTATION PROBLEMS
The transportation problem is one of the subclasses of LPPs in which the objective is to transport various quantities of a single homogeneous commodity that are initially stored at various origins, to different destinations in such a way that the transportation cost is minimum. To achieve this objective we must know the amount and location of available supplies and the quantities demanded. In addition, we must know the costs that result from transporting one unit of commodity from various origins to various destinations.
Mathematical Formulation : Consider a transportation problem with m origins (rows) and n destinations (columns). Let C_{ij} be the cost of transporting one unit of the product from the i^{th} origin to j^{th }destination. a_{i} the quantity of commodity available at origin i, bj the quantity of commodity needed at destination j. x_{ij }is the quantity transported from i^{th} origin to j^{th} destination. This following transportation problem can be stated in the tabular form.
The linear programming model representing the transportation problem is given by
subject to the constraints
The given transportation problem is said to be balanced if
ie., if the total supply is equal to the total demand.
Definitions
Feasible Solution Any set of non-negative allocations (x_{ij}>0) which satisfies the row and column sum (rim requirement) is called a feasible solution.
Basic Feasible Solution A feasible solution is called a basic feasible solution if the number of non-negative allocations is equal to m]n[1, where m is the number of rows and n the number of columns in a transportation table.
Non-degenerate Basic Feasible Solution Any feasible solution to a transportation problem containing m origins and n destinations is said to be nondegenerate, if it contains m]n[1 occupied cells and each allocation is in independent positions.
The allocations are said to be in independent positions, if it is impossible to form a closed path.
Closed path means by allowing horizontal and vertical lines and all the corner cells are occupied.
The allocations in the following tables are not in independent positions.
The allocations in the following tables are in independent positions.
Degenerate Basic Feasible Solution If a basic feasible solution contains less than m]n[1 non-negative allocations, it is said to be degenerate.
Optimal Solution
Optimal solution is a feasible solution (not necessarily basic) which minimizes the total cost. The solution of a transportation problem can be obtained in two stages, namely initial solution and optimum solution.
Initial solution can be obtained by using any one of the three methods, viz,
(i) North west corner rule (NWCR)
(ii) Least cost method or matrix minima method
(iii) Vogel’s approximation method (VAM)
VAM is preferred over the other two methods, since the initial basic feasible solution obtained by this method is either optimal or very close to the optimal solution.
The cells in the transportation table can be classified as occupied cells and unoccupied cells. The allocated cells in the transportation table are called occupied cells and the empty cells in a transportation table are called unoccupied cells.
The improved solution of the initial basic feasible solution is called optimal solution which is the second stage of solution, that can be obtained by MODI (modified distribution method).
North West Corner Rule
Step 1 Starting with the cell at the upper left corner (North west) of the transportation matrix we allocate as much as possible so that either the capacity of the first row is exhausted or the destination requirement of the first column is satisfied i.e., X_{11} = min (a_{1},b_{1}).
Step 2 If b_{1}>a_{1}, we move down vertically to the second row and make the second allocation of magnitude x_{22 }= min(a_{2} b_{1} – x_{11}) in the cell (2, 1).
If b_{1}<a_{1}, move right horizontally to the second column and make the second allocation of magnitude X_{12} = min (a_{1}, X_{11}[b_{1}) in the cell (1, 2).
If b_{1 }= a_{1} there is a tie for the second allocation. We make the second allocations of magnitude x_{12 }= min (a_{1} – a_{1}, b) = 0 in cell (1, 2). or x_{21} = min (a_{2} – a_{1} – b_{1}) = 0 in cell (2, 1).
Step 3 Repeat steps 1 and 2 moving down towards the lower right corner of the transportation table until all the rim requirements are satisfied.
Example 3.1 Obtain the initial basic feasible solution of a transportation problem whose cost and rim requirement table is the following.
Solution Since Σai = 34 = Σbj there exists a feasible solution to the transportation problem. We obtain initial feasible solution as follows.
The first allocation is made in the cell (1, 1) the magnitude being x_{11 }= min (5, 7) = 5. The second allocation is made in the cell (2, 1) and the magnitude of the allocation is given by x_{21} = min (8, 7 – 5) = 2.
The third allocation is made in the cell (2, 2) the magnitude x_{22 }= min (8 – 2, 9) = 6.
The magnitude of fourth allocation is made in the cell (3, 2) given by min (7, 9 – 6) = 3.
The fifth allocation is made in the cell (3, 3) with magnitude x_{33} = min (7 – 3, 14) = 4.
The final allocation is made in the cell (4, 3) with magnitude x_{43} = min (14, 18 – 4) = 14.
Hence, we get the initial basic feasible solution to the given T.P. and is given by X_{11 }= 5; X_{21} = 2; X_{22} = 6; X_{32} = 3; X_{33} = 4; X_{43 }= 14
Total cost = 2 e 5 – 3 e 2 – 3 e 6 – 3 e 4 – 4 e 7 – 2 e 14 =10 – 6 – 18 – 12 – 28 –28 = Rs 102.
Example 3.2 Determine an initial basic feasible solution to the following transportation problem using N.W.C.R
Solution The problem is a balanced TP as the total supply is equal to the total demand. Using the steps involved we find the initial basic feasible1 solution as given in the following table
The solution is given by X_{11} = 6; X_{12} = 8; X_{23} = 14; X_{33} = 1; X_{34} = 4
Total Cost 6 × 6 + 4 × 8 + 2 × 9 + 2 × 14 +6 × 1 + 2 × 4 = Rs 128
Least Cost or Matrix Minima Method
Step 1 Determine the smallest cost in the cost matrix of the transportation table. Let it be C_{ij}. Allocate x_{ij} = min (a_{i}, b_{j}) in the cell (i, j).
Step 2 If x_{ij} = a_{i} cross off the ith row of the transportation table and decrease b_{j }by a_{i}. Then go to step 3.
If x_{ij} = b_{j} cross off the j^{th} column of the transportation table and decrease ai by b_{j}.
Go to step 3.
If x_{ij} = a_{i} = b_{j }cross off either the ith row or the j^{th} column but not both.
Step 3 Repeat steps 1 and 2 for the resulting reduced transportation table until all the rim requirements are satisfied. Whenever the minimum cost is not unique, make an arbitrary choice among the minima.
Example 3.3 Obtain an initial feasible solution to the following TP using Matrix Minima Method.
Solution Since Σa_{i} = Σb_{j }= 24, there exists a feasible solution to the TP using the steps in the least cost method, the first allocation is made in the cell (3, 1) the magnitude being x_{31} = 4. This satisfies the demand at the destination D_{1} and we delete this column from the table as it is exhausted.
The second allocation is made in the cell (2, 4) with magnitude x_{24} = min (6, 8) = 6. Since it satisfies the demand at the destination D_{4}, it is deleted from the table.
From the reduced table, the third allocation is made in the cell (3, 3) with magnitude x_{33} = min (8, 6) = 6. The next allocation is made in the cell (2, 3) with magnitude x_{23} of min (2, 2) = 2. Finally, the allocation is made in the cell (1, 2) with magnitude x_{12} = min (6, 6)\6. Now all the rim requirements have been satisfied and hence, the initial feasible solution is obtained.
The solution is given by x_{12} = 6, x_{23} = 2, X_{24} = 6, X_{31} = 4, X_{33} = 6 Since the total number of occupied cells = 5 < m + n – 1.
We get a degenerate solution.
Total cost = 6 × 2 + 2 × 2 + 6 × 0 + 4 × 0 + 6 × 2 = 12 + 4 + 12 = Rs 28.
Example 3.4 Determine an initial basic feasible solution for the following TP, using the least cost method.
Solution Since Σa_{i} = Σ b_{j}, there exists a basic feasible solution. Using the steps in least cost method we make the first allocation to the cell (1, 3) with magnitude X_{13} = min (14, 15) = 14. (as it is the cell having the least cost).
This allocation exhaust the first row supply. Hence, the first row is deleted.
From the reduced table, the next allocation is made in the next least cost cell (2, 3) which is chosen arbitrarily with magnitude X_{23} = Min (1, 16) = 1. This exhausts the 3rd column destination.
From the reduced table the next least cost cell is (3, 4) for which allocation is made with magnitude min (4, 5) = 4. This exhausts the destination D_{4} requirement.
Delete this fourth column from the table. The next allocation is made in the cell (3, 2) with magnitude X_{32} = Min (1, 10) = 1. This exhausts the 3rd origin capacity.
Hence, the 3rd row is exhausted. From the reduced table the next allocation is given to the cell (2,1) with magnitude X_{21} = min (6, 15) = 6. This exhausts the first column requirement. Hence, it is deleted from the table.
Finally, the allocation is made to the cell (2, 2) with magnitude X_{22} = Min (9, 9) = 9 which satisfies the rim requirement. These allocation are shown in the transportation table as follows.
The following table gives the initial basic feasible solution.
The solution is given by X_{13}=14; X_{21}=6; X_{22}= 9; X_{23}= 1; X_{32}= 1; X_{34}= 4
Transportation cost = 14 ×1 × 6 × 8 + 9 × 9 + 1 × 2 + 3 × 1 + 4 × 2
= Rs 156.