OR(Operation Research) | Transportation problem | its Methds

Transportation problem

The Transportation problems are one of the types of the L.P.P in which objective is to transport various quantities of a single homogeneous commodity, to different destination  in such a way that the total transportation cost is minimum.

Terminology used in Transportation problem

Feasible solution  feasible solution is a set of non negative values (x>=0) which satisfies the row and column sum conditions is called a feasible solution

Basic feasible solution If the total number of positive allocations is exactly equal to m+n-1 i.e. one less than the sum of number of rows(m) and columns (n) that solution is called a basic feasible solution.

Optimal solution A feasible solution is said to be optimal of it minimizes the total transportation problem

Balanced Transportation problem A Transportation problem. In which the total supply from all the sources equal the total demand in all the destinations.

Unbalanced Transportation problem A Transportation problem In which the total supply from all the sources are not equal the total demand in all the destinations.

Degenerate Basic feasible solution A basic feasible solution that contains less than (m+n-1) non negative allocations.

Non degenerate Basic feasible solution If the total number of positive allocation is exactly equal to ( m+n-1) and these allocation are in independent positions that BFS solution is called non degenerate BFS.

Methods for initial basic feasible solution (IBFS)

North West Corner Method ( NWCM)

Lowest Cost Entry Method (LCM )

Vogel’s Approximation Method  ( VAM)

North West Corner Method ( NWCM)

The idea is to obtain IBFS i.e.  a set of allocations that satisfies the totals of row and column. The methods simply consist of making allocations to each row in turn. Apportioning as much as possible to its first cell and proceeding in this manner to its following cells until the row is exhausted. The algorithm involved under NWCM consists of the following steps

• The method starts at the north west corner cell of the table i.e. upper left corner of the requirement table or top most left corner of the table i.e. cell (1, 1) and allocate the maximum possible amount and adjust the associated amount of supply and demand by subtracting the allocated amount.
• Move to the cell (1’2) towards right hand side, if there is still any quantity available left. Otherwise move towards down to cell ( 2,1 )  and allocate the maximum possible amount. Move to the cell (2,2), if supply equals demand at cell (1,1)
• Repeat steps 1 and 2 moving down towards the lower right corner of the transportation cost table until the rim requirements are satisfied.

Lowest Cost Entry Method (LCM )

This method give better starting solution them NWCM  as it reduces the computation cost and amount of time necessary to get optimal solution.

Steps to be followed

• Select the cell with the lowest transportation cost  in the whole matrix arbitrarily.
• Allocate an many units as possible to the cell determined instep 1 and eliminate that row/ column in which either supply is exhausted or demand is satisfied.
• Re- select the cell with the lowest transportation cost from the remaining cost matrix or reduced table and repeated the step 2 , till the rim requirement is satisfied.

Vogel’s Approximation Method  ( VAM)

VAM is also known as UNIT COS TPENALTY METHOD  . In this method, transportation problem can be solved in lesser time and solution to it may be considered as the appropriate solution as compared to the methods i.e. it is an algorithm used to find out relatively efficient IFS by considering the ‘PENALTY COST’  of not using the cheapest available route. This method is better than earlier, methods and is usually used to get a better starting point to the solution of the problem

Steps to be followed

• From the transportation cost table we determine the penalty for each row and each column. These penalties are calculated for each row(column) by subtracting the least cost element in that row (column) from the second lowest cost element in the same row (column).
• After this we identify the row or column with the largest penalty among all the rows and columns. In case the penalties corresponding to two or more rows or columns are equal then we use any arbitrary tie breaking choice.
• In the largest penalty row(column) identify the least cost cell if it happens to be in ith row and jth column then we allocate maximum possible number of units keeping the row and column constraints in mind. Let the number of units allocated be X_ij then X_ij is min{s_i, d_j} in the cell (i,j).Remove the row (or column) from further consideration for making allocation for which supply (or demand) is exhausted in making allocations at a stage.
• Again compute row and column penalties for the reduced transportation table, go to step 2 . Repeat the procedure until all the requirements are satisfied

Optimality test

After finding IFS by any initial basic feasible solution method , the next important step is to see, can we decrease the total cost further by making changes in the occupied cells ? This is known as testing optimality

Two Methods for testing optimality

Stepping stone Method

Stepping stone method It is an interactive technique from moving an initial feasible solution to an optimal feasible solution.

Steps to be followed

• Write the transportation table incorporating the original supply, demand and costs of transportation
• Determine an initial basic feasible solution by using any one of the methods discussed earlier.(prefer VAM ,as it provide either optimum or the nearest the optimum solution)
• Make sure that the number of allocations are  m+n-1 allocations should be in independent positions.
• Evaluate cost change of shipping goods via each unoccupied cell, which can be done as follows:   

  I. Select an unoccupied cell to be evaluated    
  II.  Starting from this unoccupied cell, trace a closed loop using the most direct route through at least three allocated cells used in the solution and then come back to the starting unoccupied cell. In the process of moving from one occupied cell to another,(i) move only vertically or horizontally but never diagonally, (ii) both empty or occupied cells may be skipped over, (iii) an even number of at least four cells must participate in a closed path. The calls at the turning points are known as stepping stones.   

 III. After tracing the closed path, place (+) and (-) sign alternatively in the cells on each turn of the loop, beginning with a plus (+) sign in the empty cell.   
 IV.   Find the ‘net effect on the cost’ along the closed loop. For this purpose add the unit cost figures found in each cell containing a plus sign and then subtracting the unit costs in each cell having the minus sign.    
  V. Calculate the net change in cost for all the empty cells.

• Check the sign of each of the net cost changes. If all the net cost changes are greater than or equal to zero(>=0) ; it indicate that solution is optimum, if at least one net cost change is negative, it is possible to improve the current solution bt decreasing total transportation cost
• Choose the empty  cell having the most negative net cost change and determine the  maximum quantity that can be assigned to a cell marked with minus sign on the closed path.add this quantity to the empty cell and to all other cells marked with a (+) sign. Subtract this quantity from the cells with a minus(-) sign
• Go back to step 3 and repeat the procedure until an optimum solution is obtained

MODI (Modified Distribution Method)

This method allow us to compute improvement indices quickly for each unbalalnced square without drawing all of the closed paths. modi method provide a new means of finding the unused route with the largest negative improvement index. Once the largest index is identified we are required to trace only one closed path, just as with the stepping stone approach , this path helps to determine the maximum number of units that can be shipped via the best unused route.

1.From the given data construct a transportation table with the given cost of transportation and rim conditions.

2. Determine in initial basic feasible solution using a suitable method(i.e. NWCM, LCEM or VAM)

3.For the current basic feasible solution with m+n-1 occupied cells, calculate index numbers R_i =(i=1,2….m) and K_j=(j=1,2….n) for rows and columns respectively.

For calculating values of R_i  and K_{j ,} the following relationship for occupied cells is used,

C_ij = R_{i   +}  K_j             for all I,j

4.For occupied cells, the opportunity cost by using the formula

D_ij = C_ij - R_{i   +}  K_j             for all I,j

5. Now the opportunity cost of an unoccupied cell is determined by using the formula

Opportunity cost = actual cost – implied cost

D_ij = C_ij – (R_{i   +}  K_j )

6.Examine unoccupied cells evaluation for D_ij

• If D_ij >0 then the cost of transportation will increase, i.e. and optimal solution has been arrived at.
• If D_ij =0 then the cost of transportation will remain unchanged. But there exists an alternative solution.
• If D_ij <0 then an improved solution can be obtained by introducing cell (I,j) in the basis and go to step 7

7.Select an unoccupied cell with largest negative opportunity cost among all   unoccupied cells.

8. Construct a closed path for the unoccupied cell determined in step 7 and assign plus(+) and minus (-) sign alternatively beginning  with plus sign for the selected unoccupied cell in clockwise or other direction

9. Assign  as many units as possible to the unoccupied cell satisfying rim conditions.the smallest allocation in a cell with negative sign on the closed pathnindicated the number of units that can be transportation to the unoccupied cells. This quantity is added to all the occupied cells on the pathnmarked with minus sign

10.Go to step 4 and repeat procedure until all dij >+0 i.e. an optimal solution is reached. Calculate the association total  transportation cost