Transportation Problems - Elements of Operation research, Business Mathematics and Statistics | Business Mathematics and Statistics - B Com PDF Download

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₁₁ = min (a₁,b₁).

Step 2  If b₁>a₁, we move down vertically to the second row and make the second allocation of magnitude x₂₂ = min(a₂ b₁ – x₁₁) in the cell (2, 1).
If b₁<a₁, move right horizontally to the second column and make the second allocation of magnitude X₁₂ = min (a₁, X₁₁[b₁) in the cell (1, 2).
If b₁ = a₁ there is a tie for the second allocation. We make the second allocations of magnitude x₁₂ = min (a₁ – a₁, b) = 0 in cell (1, 2). or x₂₁ = min (a₂ – a₁ – b₁) = 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₁₁ = min (5, 7) = 5. The second allocation is made in the cell (2, 1) and the magnitude of the allocation is given by x₂₁ = min (8, 7 – 5) = 2.

The third allocation is made in the cell (2, 2) the magnitude x₂₂ = 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₃₃ = min (7 – 3, 14) = 4.
The final allocation is made in the cell (4, 3) with magnitude x₄₃ = min (14, 18 – 4) = 14.
Hence, we get the initial basic feasible solution to the given T.P. and is given by X₁₁ = 5; X₂₁ = 2; X₂₂ = 6; X₃₂ = 3; X₃₃ = 4; X₄₃ = 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₁₁ = 6; X₁₂ = 8; X₂₃ = 14; X₃₃ = 1; X₃₄ = 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₃₁ = 4. This satisfies the demand at the destination D₁ 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₂₄ = min (6, 8) = 6. Since it satisfies the demand at the destination D₄, it is deleted from the table.

From the reduced table, the third allocation is made in the cell (3, 3) with magnitude x₃₃ = min (8, 6) = 6. The next allocation is made in the cell (2, 3) with magnitude x₂₃ of min (2, 2) = 2. Finally, the allocation is made in the cell (1, 2) with magnitude x₁₂ = 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₁₂ = 6, x₂₃ = 2, X₂₄ = 6, X₃₁ = 4, X₃₃ = 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₁₃ = 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₂₃ = 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₄ requirement.

Delete this fourth column from the table. The next allocation is made in the cell (3, 2) with magnitude X₃₂ = 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₂₁ = 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₂₂ = 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₁₃=14; X₂₁=6; X₂₂= 9; X₂₃= 1; X₃₂= 1; X₃₄= 4
Transportation cost  = 14 ×1 × 6 × 8 + 9 × 9 + 1 × 2 + 3 × 1 + 4 × 2
 = Rs 156.