Modified Distribution Method

Modified Distribution Method

The Modified Distribution Method, palso known as MODI method or u-v method, which provides a minimum cost solution (optimal solution) to the transportation problem. The following are the steps involved in this method:
Step 1: Find out the basic feasible solution of the transportation problem using any one of the three methods you studied.
Step 2: Introduce dual variables corresponding to the row constraints and the column constraints. If there are m origins and n destinations then there will be m + n dual variables. The dual variables corresponding to the row constraints are represented by ui, i=1,2,…..m whereas the dual variables corresponding to the column constraints are represented by vj, j=1,2,…..n. The values of the dual variables are calculated from the equation given by:
ui + vj = cij , if xij > 0
Step 3: Any basic feasible solution has m + n -1, xij > 0. Thus, there will be m + n -1 equation to determine m + n dual variables. One of the dual variables can be chosen arbitrarily. It is also to be noted that as the primal constraints are equations, the dual variables are unrestricted in sign.
Step 4: If xij=0, the dual variables calculated in Step 3 are compared with the cij values of this allocation
as cij – ui – vj. If al cij – ui – vj ? 0, then by the theorem of complementary slackness it can be shown that the corresponding solution of the transportation problem is optimum. If one or more cij – ui – vj < 0, we select the cell with the least value of cij – ui – vj and allocate as much as possible subject to the row and column constraints. The allocations of the number of adjacent cell are adjusted so that a basic variable becomes non-basic.
Step 5: A fresh set of dual variables are calculated and repeat the entire procedure from Step 1 to Step 5.
Example:
For example consider the transportation problem given below:
Retail
Agency
Factories 1 2 3 4 5 capacity
1 1 9 13 36 51 50
2 24 12 16 20 1 100
3 14 33 1 23 26 150
Demand 100 70 50 40 40 300

Step 1: First we have to determine the basic feasible solution using least cost method.
Retail Agency

Factories 1 2 3 4 5 Capacity
1 1
50 9
13
36
51
50
2 24
12
60 16
20
1
40
100
3 14
50 33
10 1
50 23
40 26

150
Requirement 100 70 50 40 40

The basic feasible solution is
x11=50, x22=60, x25=40, x31=50, x32=10 , x33=50 and x34=40
Z= 50*1+60*12+40*1+50*14+10*33+50*1+40*23=2810

Step 2: The dual variables u1, u2, u3 and v1, v2, v3, v4, v5 can be calculated from the corresponding cij values, that is
u1+v1=1 , u2+v2=12 , u2+v5=1 , u3+v1=14
u3+v2=33 , u3+v3=1 , u3+v4=23 .
Step 3: Choose one of the dual variables arbitrarily is zero that is u3=0 as it occurs most often in the above equations. The values of the variables calculated are
u1= -13, u2= -21, u3=0 .
v1=14, v2=33, v3=1, v4=23, v5=22 .
Step 4: Now we calculate cij – ui – vj values for all the cells that unallocated by the basic feasible solution). That is
Cell(1,2)= c12-u1-v2 = 9+13-33 = -11
Cell(1,3)= c13-u1-v3 = 13+13-1 = 25
Cell(1,4)= c14-u1-v4 = 36+13-23 = 26
Cell(1,5)= c15-u1-v5 = 51+13-22 = 42
Cell(2,1)= c21-u2-v1 = 24+21-14 = 31
Cell(2,3)= c23-u2-v3 = 16+21-1 = 36
Cell(2,4)= c24-u2-v4 = 20+21-23 = 18
Cell(3,5)= c35-u3-v5 = 26-0-22 = 4
Note that in the above calculation all the cij – ui – vj ? 0 except for cell (1, 2) where c12 – u1 – v2 = 9+13-33 = -11.
Thus in the next iteration, x12 will be a basic variable changing one of the present basic variables to non-basic. We see that for allocating one unit in cell (1, 2) we have to reduce one unit in cells (3, 2) and (1, 1) and increase one unit in cell (3, 1). The transportation cost for each unit of such reallocation is 9-1+14-33 = -11.
The maximum that can be allocated to cell (1, 2) is 10 otherwise the allocation in the cell (3, 2) will be negative. Thus, the revised basic feasible solution is
x11=40, x12=10, x22=60, x25=40, x31=60, x33=50, x34=40
Z= 40*1+10*9+60*12+40*1+60*14+50*1+40*23=2700