Transportation Problems
Transportation Problems
ROW MINIMA METHOD
Step 1.
Check whether ∑ a₁ = ∑bj. If not introduce a dummy origin or a dummy destination with the transportation cost 0, so that they are equal.
Step 2.
Obtain the smallest cost in the first row of the transportation table and let be cij in the cell (i, j). Allocate as much as possible quantity xij = min (ai, bj) in the c (i, j).
Step-3
Case (i): If x ij =ai cross off the ith row of the transportation table and decrease bj by bai Then go to next row.
Case (ii): If x ij =bj cross off the jth column of the transportation table and decrease ai by bj, Then go to next row.
Case (iii): If x ij =ai=bj cross off the first row of the transportation table and move down to the second row.
Step-4
Continue the step-2 and step-3 until, all the rim requirements are satisfied.
COLUMN MINIMA METHOD
Step 1.
Check whether ∑ a₁ = ∑bj. If not introduce a dummy origin or a dummy destination with the transportation cost 0, so that they are equal.
Step 2.
Obtain the smallest cost in the first column of the transportation table and let be cij in the cell (i, j). Allocate as much as possible quantity xij = min (ai, bj) in the c (i, j).
Step-3
Case (i): If x ij =ai cross off the ith row of the transportation table and decrease bj by bai Then go to next column.
Case (ii): If x ij =bj cross off the jth column of the transportation table and decrease ai by bj, Then go to next column.
Case (iii): If x ij =a1=bj cross off the first column of the transportation table and move to second column.
Step-4
Continue the step-2 and step-3 until, all the rim requirements are satisfied.
MATRIX MINIMA OR LEAST COST ENTRY METHOD
Step 1
Determine the smallest cost in the cost matrix of the transportation table. Let it be Cij. Allocate xij = min {ai, b} in the cell (i, j)
Step 2
Case (i):If x ij =ai cross off the ith row of the transportation table and decrease bj by ai, Then go to step3.
Case(ii): If xij=bj, cross off the jth column of the transportation table and decrease ai by bj. Then Go to step3.
Case (iii): If xij = ai = bj cross off either the ih row or the jth 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.
VOGELS APPROXIMATION METHOD (VAM) OR PENALITY METHOD
The steps involved in this method for finding the initial solution are as follows
Step 1
Find the penalty cost, namely the difference between the smallest and next smallest costs in each row and column.
Step 2
Among the penalties as found in step(1) choose the maximum penalty. If this maximum penalty is more than one (ie if there is a tie) choose any one arbitrarily.
Step 3
In the selected row or column as by step(2) find out the cell having the least cost. Allocate to this cell as much as possible depending on the capacity and requirements.
Step 4
Delete the row or column which is fully exhausted. Again compute the column and row penalties for the reduced transportation table and then go to step (2). Repeat the procedure until all the rim requirements are satisfied.
(Note : If the column is exhausted, then there is a change in row penalty and vice versa.)
OPTIMALITY TEST
STEPPING STONE METHOD
Step 1.
Check whether sum of destinations is equal to sum of requirements. If not introduce a dummy origin or a dummy destination with zero costs. So that they are equal.
Step 2.
Determine an initial basic feasible solution by using any one of the methods.
Step 3.
Check whether the number of basic (occupied/allocated) cells are m + n - 1 or not. If there are less than m + n - 1 basic cells, it is problem of degeneracy. In this case introduce a very small positive quantity epsilon ( = 0) in the suitable unoccupied (non-basic) cell so that number of occupied (basic) cells must be exactly m + n - 1.
Step 4.
Select an unoccupied (unallocated) i.e., non-basic cell. Identify a closed loop which starts and ends at the non-basic cells. The cells at the turning points are called stepping stones. Add + and subtract - signs alternatively to all the cells of the loop starting with the non-basic cell.
Step 5.
Examine the non-basic cells for a possible decrease in the transportation cost. One unit is allocated to a non-basic cell. Add and subtract the same in the cells of the loop. If the net result of the change is a decease in the transportation cost, then this solution may be considered as a better solution.
This procedure is done to all non basic cells until there is no further reduction in the transportation cost i.e., we examine which non-basic cell give us highest reduction in the transportation cost. Corresponding solution is called an optimum solution.
MODIFIED DISTRIBUTION METHOD (MODI) OR U-V METHOD
Step 1
Find the initial basic feasible solution of a TP by using any one of the methods.
Step 2
Find out a set of numbers Ui and Vj for each row and column satisfying Ui + Vj = Cij for each occupied cell To start with we assign a number 'O' to any row of column having maximum number of allocations. If this maximum number of allocations is more than one, choose any one arbitrarily.
Step 3
For each empty (unoccupied) cell, we find the sum Ui and Vj written in the bottom left corner of that cell.
Step 4
Find out for each empty cell the net evaluation value Zij -Cij = Ui + Vj - Cij and which is written at the bottom right corner of that cell gives the optimality conclusion,
Case (i) If all Zij -Cij < 0 (ie. all the net evaluation value) the solution is optimum and a unique solution exists.
Case (ii) If Zij -Cij <= 0 then the solution is optimum, but an alternate solution exists.
Case (iii) If at least one Zij -Cij > 0 , the solution is not optimum. In this case we go to the next step, to improve the total transportation cost.
Step 5
Select the empty cell having the most positive value of net evaluations. From this cell we draw a closed path by drawing horizontal and vertical lines with the corner cells occupied. Assign sign + and - alternately and find the minimum allocation from the cell having positive sign. This allocation should be added to the allocation having positive sign and subtracted from the allocation having negative sign.
Step 6
The above step yield a better solution by making one (or more) occupied cell as empty and one empty cell as occupied. For this new set of basic feasible allocations repeat from the step(2) till an optimum basic feasible solution is obtained.
Comments
Post a Comment