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

# 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 2350 views