Home | ARTS | Operations Management | Optimality Checking Of The Initial Basic Feasible Solution: Modi [Modified Distribution Method] Method - Transportation Problem

Operations Management - Transportation / Assignment & Inventory Management

Optimality Checking Of The Initial Basic Feasible Solution: Modi [Modified Distribution Method] Method - Transportation Problem

   Posted On :  23.06.2018 04:11 am

You would have noticed that the initial basic feasible solution obtained by various methods provide different starting solution.

Optimality Checking Of The Initial Basic Feasible Solution: Modi [Modified Distribution Method] Method
 
You would have noticed that the initial basic feasible solution obtained by various methods provide different starting solution. Once you obtain the initial solution by any of the method, the next step is to check the optimality of the solution obtained and if not, improve the solution and obtain the optimal solution. Two popularly known methods are ‘Stepping Stone Method’ and ‘MODI Method or u-v method.
 
In the stepping stone method, we have to draw as many closed paths as equal to the unoccupied cells for their evaluation. To the contrary, in MODI method, only closed path for the unoccupied cell with highest opportunity cost is drawn. Here, we will discuss only the MODI Method, which is more scientific and approaches the optimal solution faster.
 

Modi [Modified Distribution Method] Method - Step-by-step procedure

 
Step1
 
 
Determine an initial basic feasible solution using any one of the three methods:

North West Corner Rule
 
Matrix Minimum Method
 
Vogel Approximation Method
 
 
Step2
 
 
Each row, assign one ‘dual’ variable, say- u1, u2, u3…; for each column, assign on dual variable – say, v1, v2, v3…
 
Now using the basic cells [which are assigned through any one of the three methods], and the transportation costs of those basic cells -Cij, we will determine the values of these ui and vj

Determine the values of dual variables, ui and vj, using ui + vj = Cij Since the net evaluation is zero for all basic cells, it follows that zij - cij = ui +v j - Cij , for all basic cells (i, j). So we can make use of this relation to find the values of ui and vj
 
Step3
 
 
Compute the opportunity cost, for those cells, which are not allocated for any goods to be transported [known as non-basic cells], using (ui + vj) - Cij
 
Step4
 
 
1. Check the sign of each opportunity cost.
 
2. If the opportunity costs of all these unoccupied cells / non-basic cells are either negative or zero, the given solution is the optimal solution.

3. On the other hand, if one or more unoccupied cell has positive entry / opportunity cost, it is an indication that the given solution is not an optimal solution; it can be improved and further savings in transportation cost are possible.
 
Step5
 
 
1. Select the unoccupied cell with the highest positive opportunity cost as the cell to be included in the next solution.

2. This cell has been left out / missed out by the initial solution method.

3. If this cell is allocated, it will bring down the overall transportation cost
 
Step6
 
 
Draw a closed path or loop for the unoccupied cell selected in the previous step. A loop in a transportation table is a collection of basic cells and the cell, which is to be converted as basic cell. It is formed in such a way that, it has only even number cells in any row or column.
 
1.  After identifying the entering variable Xrs, form a loop; this loop starts at the non-basic cell (r, s) connecting only basic cells.
 
2.  Assign alternate plus and minus signs at the unoccupied cells on the corner points of the closed path with a plus sign at the cell being evaluated
 
3.  Determine the maximum number of units that should be shipped to this unoccupied cell.
 
4.  The smallest value with a negative position on the closed path indicates the number of units that can be shipped to the entering cell.

5.  Now, add this quantity to all the cells on the corner points of the closed path marked with plus signs, and subtract it from those cells marked with minus signs.
 
6.  In this way, an unoccupied cell becomes an occupied cell.
 
7.  Other basic cells, the quantity allocated are modified, in such a way that without affecting the row availability and column / market requirements
 
8.  Such a closed path exists and is unique for any non-degenerate solution.
 
Please note that the right angle turn in this path is permitted only at occupied cells and at the original unoccupied cell.
 
Step7
 
 
Repeat the whole procedure until an optimal solution is obtained.
 
----------------------
 
To understand the MODI Method, let us consider the solution obtained by Least Cost Method.
 
Step1



Step2
 
 
For each row, we assign ui and for each column, we will assign vj
 
Let us assume any one of the ui or vj as zero; preferably a row or column having maximum number of basic cells
 
Since there is a tie, we break it arbitrarily.
 
Let us assume, U1= 0
 
We know that U1+V1= 8 [ui+vj= Cij for all the basic cells]
 
 
These findings are incorporated in the following table



Step3
 
 
Let us compute the opportunity cost, for those cells, which are not allocated for any goods to be transported [known as non-basic cells], using (ui + vj) - Cij
 
For example, cell (1, 3)
 
Net evaluation for cell (1, 3)
 
=   ui+vj-Cij = u1+v3-C13 = [0 + 12-10] = 2 

Net evaluation for cell (1, 4)
 
=  ui+vj-Cij = u1+v4-C14 = [0 + 1-9] = -8
 
 
Similarly for all other cells, the net evaluation / opportunity cost is computed and placed in left hand top corner of each non-basic cell; the table is placed below;



Step4
 
 
Since all the net evaluation / opportunity costs are not negative, it is an indication of the solution is not in the optimum stage; it can be improved
 
Among the positive entries, the maximum positive appears in the cell (1, 3), which is 2. So this cell to be converted as a basic cell.
 
Step5
 
 
1.  After identifying the entering variable Xrs, form a loop; this loop starts at the non-basic cell (r, s) connecting only basic cells.
 
2.  Assign alternate plus and minus signs at the unoccupied cells on the corner points of the closed path with a plus sign at the cell being evaluated
 
3.  Determine the maximum number of units that should be shipped to this unoccupied cell.
 
4.  The smallest value with a negative position on the closed path indicates the number of units that can be shipped to the entering cell.
 
5.  Now, add this quantity to all the cells on the corner points of the closed path marked with plus signs, and subtract it from those cells marked with minus signs.
 
6.  In this way, an unoccupied cell becomes an occupied cell.
 
Other basic cells, the quantity allocated are modified, in such a way that without affecting the row availability and column / market requirements. The loop formed is shown below;



In the loop, between the cells with negative sign, lowest quantity allocated is 15, in the cell (1, 1); it should be shifted to the cell (1, 3), where there is a positive sign.



Thus, wherever there is a positive sign, the quantity is added; in the negative signed cell, it is subtracted.
 
Also, when we move the quantities, we should not move to 3 cells in a row or column; the movement of goods will be always in terms of even numbers.
 
You may notice in the above table, while moving the goods, we skipped the basic cell (1, 2) from the loop. Other allocations remain as such; we will now compute the cost of this allocation.
 

Now the allocations are:

 

X12 = 20

X23= 5

X13 = 15

X33 = 10

X21 = 45

X34 = 30


 The total transportation cost
 
=  (20 X 6) + (15 X 10) + (45 X 9) + (5 X 13) + (10 X 16) + (30 X 5)
 
=  120 + 150 + 405 + 65 + 160 + 150
 
=  1050
 
 
You may note that Least Cost method which has an initial cost of allocation as 1080, reduced by Rupees 30 by MODI / u-v method.
 
Once again, we check, whether the solution is optimum or not; we start again to compute the ui and vj for each row and column;



We assume V3 = 0, since it has 3 basic cells in the column and repeat the same process.
 
Now we will compute the Net evaluation / opportunity cost for the non-basic cells and try to form the loop, if there are positive opportunity cost in any of the cells.



The maximum positive appears in the cell (3, 2); it should be converted as basic cell and the loop is shown in the above table. The modified distribution is shown below and the cost is computed.



You may note that the cost of allocation is
 
=(10X 6) + (25X 10) + (45 X 9) + (5 X 13) + (10 X 9) + (30 X 5)
 
=   60 + 250 + 405 + 65 + 90 + 150
 
=       1020
 
Thus, the total cost is reduced by modifying the distribution / allocations made earlier. Now once again, we will check whether the solution is optimum or not.
 
Table-6 Finding ui / vj and checking optimality of the solution



Since, the net evaluation / opportunity cost is negative for all the non-basic cells, it is indication that the solution is in the optimum stage.
 

Variations in the Transportation Models

 
Unbalanced Transportation Models: If the demand is not equal to supply, the transportation problems are known as unbalanced transportation problems.
 
You have to add a dummy row / column with zero as transportation cost with the shortfall (difference between supply and demand) as the quantity available in the origin or marketing requirements.
 
Then, in the usual manner, using any one of the initial solution methods will be applied and initial solution will be obtained.

Tags : Operations Management - Transportation / Assignment & Inventory Management
Last 30 days 1663 views

OTHER SUGEST TOPIC