Procedure to Solve the transportation problem is as follows:
Step 1: Formulate the Problem
Formulate the given problem and set up in a matrix form. Check whether the problem is a balanced or unbalanced transportation problem. If unbalanced, add dummy source (row) or dummy destination (column) as required.
Step 2: Obtain the Initial Feasible Solution
The initial feasible solution can be obtained by any of the following three methods:
1. Northwest Corner Method (NWC)
2. Least Cost Method (LCM)
3. Vogel’s Approximation Method (VAM)
The transportation cost of the initial basic feasible solution through Vogel’s approximation method, VAM will be the least when compared to the other two methods which gives the value nearer to the optimal solution or optimal solution itself.
Step 3: Test for Optimality
The solution is tested for optimality using the Modified Distribution (MODI) method (also known as U-V method).
Once an initial solution is obtained, the next step is to test its optimality. An optimal solution is one in which there are no other transportation routes that would reduce the total transportation cost, for which we have to evaluate each unoccupied cell in the table in terms of opportunity cost. In this process, if there is no negative opportunity cost, the solution is an optimal solution.
(i) Row 1, row 2,…, row i of the cost matrix are assigned with variables U 1, U2, …,Ui and the column 1, column 2,…, column j are assigned with variables V1, V2, …,Vj respectively.
(ii) Initially, assume any one of Ui values as zero and compute the values for U1, U2, …,Ui and V1, V2, …,Vj by applying the formula for occupied cell.
(iii) Obtain all the values of Cij for unoccupied cells by applying the formula for unoccupied cell.
Step 4: Procedure for Shifting of Allocations
Select the cell which has the most negative Cij value and introduce a positive quantity called ‘q’ in that cell. To balance that row,
allocate a ‘– q’ to that row in occupied cell. Again, to balance that column put a positive ‘q’ in an occupied cell and similarly a ‘–q’ to that row. Connecting all the ‘q’s and ‘–q’s, a closed loop is formed.
Two cases are represented in Table 4.10(a) and 4.10(b). In Table 4.10(a) if all the q allocations are joined by horizontal and vertical lines, a closed loop is obtained.
Conditions for forming a loop are as follow:
(i) The start and end points of a loop must be the same
(ii) The lines connecting the cells must be horizontal and vertical.
(iii) The turns must be taken at occupied cells only.
(iv) Take a shortest path possible (for easy calculations).
Remarks on forming a loop are as follow:
(i) Every loop has an even number of cells and at least four cells
(ii) Each row or column should have only one ‘+’ and ‘–’ sign.
(iii) Closed loop may or may not be square in shape. It can also be a rectangle or a stepped shape.
(iv) It doesn’t matter whether the loop is traced in a clockwise or anti-clockwise direction.
Step 5: Calculate the Total Transportation Cost
Since all the Cij values are positive, optimality is reached and hence the present allocations are the optimum allocations. Calculate the total transportation cost by summing the product of allocated units and unit costs.