Optimal Solution by MODI Method

The Modified Distribution Method or MODI is an efficient method of checking the optimality of the initial feasible solution. MODI provides 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. This path helps determine the maximum number of units that can be shipped via the best unused route.

1. Transportation Problem: MODI Method


Dr. Deepa Chauhan

Transportation Problems
Modified Distribution Method (MODI)

By
Dr. Deepa Chauhan
Associate Professor,
Applied Science & Humanities Department,
Axis Institute of Technology, Kanpur

2. Transportation Problem: MODI Method


Dr. Deepa Chauhan
Testing the Basic Feasible Solution for Optimal Solution
Modified Distribution Method (MODI)

After getting the initial solution, the next step is to determine whether this solution is the best or least cost solution.
For this we use modified distribution method (MODI) also called (u,v) method. This method helps in comparing the
relative advantage of alternative allocations for all unoccupied cells simultaneously. We see that the number of
positive allocations is equal to the number of rows+columns-1 (m+n-1) or not.
If the number of allocations is less than (m+n-1), the solution is said to be degenerated solution, which is to be solved
later on. If he number of positive allocations is equal to (m+n-1), we try to find better solution of the problem by MODI
method.
TEST FOR OPTIMALITY: MODI METHOD
This method consists of the following steps:
Step 1: For an initial basic feasible solution with m+n-1 occupied cells, calculate ui, and vj for rows and columns. The
initial solution can be obtained by any of the three methods discussed earlier.
To start with, any one of ui's or yj's is assigned the value zero. It is better to assign zero for a particular ui or vj where
there are maximum number of allocations in a row or column respectively, as it will reduce arithmetic work
considerably. Then complete the calculation of ui's and vj's for other rows and columns by using the relation cij = ui+vj
for all occupied cells
Step 2: For unoccupied cells, calculate opportunity cost by using the relationship dij=cij-(ui+vj)
Step 3: Examine sign of each dij. Signs of the values in the cell evaluation matrix indicate whether optimal solution has
been obtained or not. The signs have the following significance:
a) A positive value in an unoccupied cell indicates that a poorer solution will result by allocating units to the cell, , i.e.
if dij>0, the current basic feasible solution is optimal.
b) A zero value in an unoccupied cell indicates that another solution of the same total value can be obtained by
allocating units to this cell, , i.e. if dij=0, the current basic feasible remain unaffected but an alternative solution
exists.
c) A negative value in an unoccupied cell indicates that a better solution can be obtained by allocating units to this
cell, i.e. if dij< 0, then an improved solution can be obtained.
Step 4: Construct a closed path (or loop) for the unoccupied cell with largest negative opportunity cost. Start the
closed path with the selected unoccupied cell and mark a plus sign (+) in this cell, trace a path along the rows (or
columns) to an occupied cell, mark the corner with minus sign (-) and continue down the column (or row) to an

3. Transportation Problem: MODI Method


Dr. Deepa Chauhan
occupied cell and mark the corner with plus sign (+) and minus sign (-) alternatively, Close the path back to the
selected unoccupied cell.
Step 5: Select the smallest quantity amongst the cells marked with minus sign on the comers of closed loop Allocate
this value to the selected unoccupied cell and add it to other occupied cells marked with plus signs and subtract it from
the occupied cells marked with minus signs.
Step 6: Obtain a new improved solution by allocating units to the unoccupied cell according to Step 5 and calculate the
new total transportation cost.
Step 7: Test the revised solution further for optimality. The procedure terminates when all dij≥0 for unoccupied cells.

4. Transportation Problem: MODI Method


Dr. Deepa Chauhan
Example 1: Find the optimum solution for the following transportation problem:
D1 D2 D3 D4 D5 Supply
O1 20 18 18 21 19 100
O2 21 22 23 20 24 125
O3 18 19 21 18 19 175
Demand 60 80 85 105 70 Total=400

Solution:
Step-I: Finding the basic feasible solution
The given problem is a balanced problem because supply is equal to the requirement.
Using Vogel’s method, an initial basic feasible solution to the given transportation problem is given as below:
Table-1
D1 D2 D3 D4 D5 Supply Row
penalties
O1 20 18 18 21 19 100 1
O2 21 22 23 20 24 125 1
O3 18 19 21 18 19 (70) 175 1
Demand 60 80 85 105 70
Column
penalties
2 1 3 2 5

Next reduced table is
Table-2
D1 D2 D3 D4 Supply Row
penalties
O1 20 18 18 (85) 21 100 2
O2 21 22 23 20 125 1
O3 18 19 21 18 105 1
Demand 60 80 85 105
Column
penalties
2 1 3 2

5. Transportation Problem: MODI Method


Dr. Deepa Chauhan
Next reduced table is
Table-3
D1 D2 D4 Supply Row
penalties
O1 20 18 21 15 2
O2 21 22 20 125 1
O3 18 (60) 19 18 105 1
Demand 60 80 105
Column
penalties
2↑ 1 2

Next reduced table is
Table-4
D2 D4 Supply Row
penalties
O1 18 (15) 21 15 3←
O2 22 20 125 2
O3 19 18 45 1
Demand 80 105
Column
penalties
1 2

Next reduced table is
Table-5
D2 D4 Supply Row
penalties
O2 22 (20) 20(105) 125 2
O3 19 (45) 18 45 1
Demand 65 105
Column
penalties
3↑ 2

6. Transportation Problem: MODI Method


Dr. Deepa Chauhan
All allocations made during the above procedure are shown in below in the allocation matrix
D1 D2 D3 D4 D5 Supply
O1 20 18 (15) 18 (85) 21 19 100
O2 21 22 (20) 23 20 (105) 24 125
O3 18 (60) 19 (45) 21 18 19
(70)
175
Demand 60 80 85 105 70

The total transportation cost corresponding to this BFS, Z= ₹ 7605
Here m+n-1=5+3-1=7
No. of allocations=7
Since m+n-1= No. of allocations
Hence the optimality test can be performed.
Step-II: Introduce dual variables
Introduce dual variables corresponding to the supply and demand constraints. If there are m origins (supply) and n
destinations (demands), there will be m+n dual variables let ui (i=1,2,….m) and vj (j=1,2,….,n) be the dual variables
corresponding to supply and demand constraints. Variables ui and vj are such that ui+vj=cij, for occupied cells.
Thus,
u1+v2=18
u1+v3=18
u2+v2=22
u2+v4=20
u3+v1=18
u3+v2=19
u3+v5=19
Since the third column contains maximum number of allocations, we choose v2=0
So that: u1=18, u2=22, u3=19, v1=-1, v2=0, v3=0, v4=-2, v5=0

7. Transportation Problem: MODI Method


Dr. Deepa Chauhan
Step-III: Fill the vacant cells with (dij=cij-(ui+vj)
D1 D2 D3 D4 D5 ui
O1 20-(18-1) 21-(18-2) 19-(18+0) 18
O2 21-(22-1) 23-(22+0) 24-(22+0) 22
O3 21-(19+0) 18-(19-2) 19
vj -1 0 0 -2 0

D1 D2 D3 D4 D5
O1 3 5 1
O2 0 1 2
O3 2 1


The resulting matrix is called cell evaluation matrix.
Since all dij≥0, the initial basic feasible solution is optimal solution.
In the present example since all unoccupied cell are of positive sign, dij>0, the initial basic feasible solution is optimal,
and the problem has unique optimal BFS.
Therefore Zmin= ₹ 7605

8. Transportation Problem: MODI Method


Dr. Deepa Chauhan
Example 2:
Using lowest cost entry method, find the initial basic feasible solution to the following transportation problem and
hence find optimal solution

D1 D2 D3 Supply
O1 7 3 4 2
O2 2 1 3 3
O3 3 4 6 5
Demand 4 1 5
Solution: The above problem is a balanced problem because demand is equal to the supply. By Least
Cost method, allocations are as follows
D1 D2 D3 Supply
O1 7 3 4 (2) 2
O2 2 (2) 1 (1) 3 3
O3 3 (2) 4 6 (3) 5
Demand 4 1 5

Given initial basic feasible solution is non-degenerated as m+n-1 (3+3-1=5) =No of allocation=5
Total Transportation Cost= 4x2+2x2+1+3x2+6x3=₹37
No. of allocations=5
Since m+n-1= No. of allocations
Hence the optimality test can be performed.
Now we determine a set of values ui and vj such that cij=ui+vj for each occupied cell
Thus,
u1+v3=4
u2+v1=2
u2+v2=1
u3+v1=3
u3+v3=6
Let v1=0. Therefore from the above equations
u2=2, u3=3, v2= -1, v3=3, u1=1

9. Transportation Problem: MODI Method


Dr. Deepa Chauhan
Fill the vacant cells with dij=cij-(ui+vj)






Clearly, cell (2,3)=-2<0. Therefore, the initial basic feasible solution is not optimal. So, we improve it as
follows:
Write down again the initial basic feasible solution that is to be improved and make * mark in the identified cell
(2,3).

D1 D2 D3
O1 2
O2 2 1 *
O3 2 3


Trace a closed path in matrix. Mark the identified cell as positive and each occupied cell at corners of the path
alternately-ve, +ve, -ve and so on

D1 D2 D3 Supply
O1 7 3 4 (2) 2
O2 2 1 (1) 3 (2) 3
O3 3 (4) 4 6 (1) 5
Demand 4 1 5



The total transportation cost corresponding to this BFS is:
Z=4x2+1x1+3x2+3x4+6x1=₹33

Since m+n-1= No. of allocations=5
v1=0 v2=-1 v3=3
D1 D2 D3 Supply
u1=1 O1 6 3 2
u2=2 O2 -2 3
u3=3 O3 4 2 5
Demand 4 1 5

10. Transportation Problem: MODI Method


Dr. Deepa Chauhan
Hence the optimality test can be performed.
Now we determine a set of values ui and vj such that cij=ui+vj for each occupied cell
Thus,
u1+v3=4
u1+v2=1
u2+v3=3
u3+v1=3
u3+v3=6

11. Operations Research Unit-II: Transportation Problem


Dr. Deepa Chauhan
Let v3=0. Therefore from the above equations
u1=4, u2=3, u3=6, v2=-3, v1=-3
Fill the vacant cells with dij=cij-(ui+vj)






Since all the cell values are positive, the second feasible solution is the optimal solution.
Zmin = ₹33
Example 3: Find the initial basic feasible solution by Vogel’s method and hence find optimum
solution for the following transportation problem:
1 2 3 4 Supply
1 2 3 11 7 6
2 1 0 6 1 1
3 5 8 15 9 10
Requirement 7 5 3 2 Total=17

Solution :
Step-I: Finding the basic feasible solution
The given problem is a balanced problem because supply is equal to the requirement. We are using
Vogel’s method to find initial feasible solution of given transportation problem.
1 2 3 4 Supply Row
Penalties
1 2 3 11 7 6 3-2=1
2 1 0 6 (1) 1(1) 1 1-0=1
3 5 8 15 9 10 8-5=3
v1=-3 v2=-3 v3=0
D1 D2 D3 Supply
u1=4 O1 6 2 2
u2=3 O2 2 3
u3=6 O3 1 5
Demand 4 1 5

12. Operations Research Unit-II: Transportation Problem


Dr. Deepa Chauhan
Requirement 7 5 3 2 Total=17
Column
Penalties
2-1=1 3-0=3 11-6=5 7-1=6

Now, reduced table is:
1 2 3 4 Supply Row
Penalties
1 2 3 (5) 11 7 6 1
3 5 8 15 9 10 3
Requirement 7 5 3 1 Total=17
Column
Penalties
3 5 4 2

Reduced table is:
1 3 4 Supply Row
Penalties
1 2 (1) 11 7 1 5
3 5 15 9 10 4
Requirement 7 3 1 Total=17
Column
Penalties
3 4 2

Reduced table is:
1 3 4 Supply
3 5 (6) 15 (3) 9 (1) 10
Requirement 6 3 1 Total=17

13. Operations Research Unit-II: Transportation Problem


Dr. Deepa Chauhan
All allocations made during the above procedure are shown in below in the allocation matrix
1 2 3 4 Supply
1 2 (1) 3 (5) 11 7 6
2 1 0 6 1 (1) 1
3 5 (6) 8 15 (3) 9 (1) 10
Requirement 7 5 3 2 Total=17
The transportation cost associated with the above solution is
Z=2+15+1+30+45+9= ₹102
Here m+n-1=3+4-1=6
No. of allocations=6
Since m+n-1= No. of allocations
Hence the optimality test can be performed.
Step-II: Introduce dual variables
Now we determine a set of values ui and vj such that cij=ui+vj for each occupied cell
Thus,
u1+v1=2
u1+v2=3
u2+v4=1
u3+v1=5
u3+v3=15
u3+v4=9
Let v1=0. Therefore from the above equations
u1=2, v2=1, u3=5, v3=10, v4=4, u2= -3

14. Operations Research Unit-II: Transportation Problem


Dr. Deepa Chauhan
Fill the vacant cells with dij=cij-(ui+vj)
1 2 3 4
1 --- --- -1 1
2 4 2 -1 ---
3 --- 2 --- ---

The resulting matrix is called cell evaluation matrix.
Step-V: Signs of the values in the cell evaluation matrix indicate whether optimal solution has been
obtained or not.
In the present example since two cell evaluations are negative, it is possible to obtain a better
solution by making these cells as basic cells.
Sub-Step-1:
From the cell evaluation matrix, identify the cell with the most negative cell evaluation.
This is the rate by which total transportation cost can be reduced if one unit is allocated to this cell.
In case of tie in the cell evaluation, the cell wherein maximum allocation can be made is selected.
This cell is now called the identified cell
1 2 3 4 Supply
1 --- --- -1 1 6
2 4 2 -1 --- 1
3 --- 2 --- --- 10
Requirement 7 5 3 2

In the present problem both tied cells have the same allocation of -1. Hence the cell (1,3) is selected.

Sub-Step-2:
Write down again the initial basic feasible solution that is to be improved. Make * mark in the
identified cell.

15. Operations Research Unit-II: Transportation Problem


Dr. Deepa Chauhan
1 2 3 4 Supply
1 1 5 * 6
2 1 1
3 6 3 1 10
Requirement 7 5 3 2 Total=17

Trace a closed path in matrix. Mark the identified cell as positive and each occupied cell at corners
of the path alternately-ve, +ve, -ve and so on

1 2 3 4 Supply
1
- 1

5

* +
6
2 1 1
3
+ 6

3 -
1 10
Requirement 7 5 3 2 Total=17

Make a new allocation in the identified cell by entering the smallest allocation on the path that has
been assigned a –ve sign. Add and subtract this new allocation from the cells at the corner of
the path, maintain the row and column requirements.


1 2 3 4 Supply
1 1-1 5 +1 6
2 1 1
3 6+1 3-1 1 10
Requirement 7 5 3 2 Total=17

16. Operations Research Unit-II: Transportation Problem


Dr. Deepa Chauhan
1 2 3 4 Supply
1 5 1 6
2 1 1
3 7 2 1 10
Requirement 7 5 3 2 Total=17

The total transportation cost for this 2
nd feasible solution is
Z=3x5+11x1+1x1+7x5+2x15+1x9= ₹101
2
nd Feasible Solution: Check for Optimality
Here m+n-1=3+4-1=6
No. of allocations=6
Since m+n-1= No. of allocations
Hence the optimality test can be performed.
Setup the cost matrix containing costs associated with cells for which allocations have been made
1 2 3 4
1 3 11
2 1
3 5 15 9

Now find the values of ui and vj such that
u1+v2=3
u1+v3=11
u2+v4=1
u3+v1=5
u3+v3=15
u3+v4=9

17. Operations Research Unit-II: Transportation Problem


Dr. Deepa Chauhan
Let v1=0
u3=5, v3=10, v4=4, u1=1, v2=2, u2=-3
Fill the vacant cell with dij (dij=cij-(ui+vj))
1 2 3 4
1 1 --- --- 2
2 4 1 -1 --
3 -- 1 -- --

This matrix is called cell evaluation matrix
Since one cell value is –ve, the 2
nd feasible solution is not optimal.
Iteration towards an optimal solution
In the cell evaluation matrix, identify the cell with most negative entry. It is the cell (2,3)
Write down again the feasible solution
1 2 3 4 Supply
1 5
1
6
2

+ * -1

1
3 7
-2 1+
10
Requirement 7 5 3 2 Total=17


1 2 3 4 Supply
1 5 1 6
2 +1 1-1 1
3 7

2-1 1+1 10

18. Operations Research Unit-II: Transportation Problem


Dr. Deepa Chauhan
Requirement 7 5 3 2 Total=17
1 2 3 4 Supply
1 5 1 6
2 1 1
3 7

1 2 10
Requirement 7 5 3 2 Total=17

Third feasible solution:
Z=5x3+1x11+1x6+1x15+2x9+7x5= ₹100

3
rd Feasible Solution: Check for Optimality
Here m+n-1=3+4-1=6
No. of allocations=6
Since m+n-1= No. of allocations
Hence the optimality test can be performed.
Setup the cost matrix containing costs associated with cells for which allocations have been made
1 2 3 4
1 3 11
2 6
3 5 15 9

Now find the values of ui and vj such that

19. Transportation Problem: MODI Method

Dr. Deepa Chauhan
u1+v2=3
u1+v3=11
u2+v3=6
u3+v1=5
u3+v3=15
u3+v4=9
Let v1=0
Then,
u3=5, v3=10, v4=4, u2= - 4, u1=1, v2=2
Fill the vacant cell with dij (dij=cij-(ui+vj)), the resulting matrix is shown in table

1 2 3 4
1 1 2
2 5 2 1
3 1

Since all the cell values are positive, the third feasible solution is the optimal solution.
Zmin = ₹100