--%>
Assignment Help - homework help

  MODI Method - Transportation Algorithm for Minimization Problem

Transportation Algorithm for Minimization Problem (MODI Method)

 Step 1

Make the transportation table entering the origin capacities ai, the cost cij and destination requirement bj

Step 2

Determine an initial basic feasible solution by vogel's technique or by any of the known method.

Step 3

For all the basic variables xij, solve the system of equations ui + vj = cij, for all i, j for which cell (i, j) is in the basis, starting at first with some ui = 0, compute the values of ui and vj on the transportation table

Step 4

Calculate the cost differences dij = cij - ( ui + vj ) for all the non-basic cells

Step 5

Apply optimality test by testing the sign of each dij

  • If all dij ≥ 0, the present basic feasible solution is optimal or best
  • If at least one dij < 0, choose the variable xrs (most negative) to enter the basis.
  • Solution under test is not optimal if any of the dij is negative and subsequent improvement is needed by repeating the above procedure.

 

Step 6

Assume the variable xrs enter the basis. Assign an unknown quantity ? to the cell (r, s). Then make a loop that begins and ends at the cell (r, s) and links some of the basic cells. The amount ? is added to and subtracted from the transition cells of the loop in such a way that the availabilities and necessities remain fulfilled.

 

Step 7

Allocate the largest possible value to the ? in such a manner that the value of at least one basic variable comes out to be zero and the other basic variables remain non-negative. The basic cell whose allotment has been made zero will leave the basis.

 

Step 8

Now, go back to step 3 and repeat the process until an optimal solution is achieved.

Worked Examples

 

Illustration 1

Determine an optimal solution 

 

W1

W2

W3

W4

Availability

F1

19

30

50

10

7

F2

70

30

40

60

9

F3

40

8

70

20

18

Requirement

5

8

7

14

 

 

 

 

 

 

 

Answer

 

1. Put vogel's approximation method for determining the initial basic feasible solution

 

 

W1

W2

W3

W4

Availability

Penalty

F1

5(19)

(30)

(50)

2(10)

X

X

F2

(70)

(30)

7(40)

2(60)

X

X

F3

(40)

8(8)

(70)

10(20)

X

X

Requirement

X

X

X

X

 

 

Penalty

X

X

X

X

 

 

 

 

Minimum transportation cost comes out to be 5 (19) + 2 (10) + 7 (40) + 2 (60) + 8 (8) + 10 (20) = Rs. 779

 

2. Test for Non-degeneracy

The initial fundamental feasible solution has m + n - 1 i.e. 3 + 4 - 1 = 6 allocations in independent positions. Therefore optimality test is fulfilled.

 

3. Computation of ui and vj : -  ui + vj  = cij

 

 

 

 

 

ui

 
  • (19)

 

 
  • (10)

u1= -10

 

 

 
  • (40)
  • (60)

u2 = 40

 

 
  • (8)

 
  • (20)

    u3 = 0

vj

v1 = 29

v2 = 8

v3 = 0

v4 = 20

 

 

 

 

 

 

Allocate a 'u' value to zero. (Convenient rule is to choose the ui, which has the maximum number of allocations in its row)

Assume u3 = 0, then

u3 + v4= 20 which means 0 + v4 = 20, so v4 = 20

u2 + v4= 60 which means u2 + 20 = 60, so u2 = 40

u1 + v4= 10 which means u1 + 20 = 10, so u1 = -10

u2 + v3= 40 which means 40 + v3 = 40, so v3 = 0

u3 + v2= 8 which means 0 + v2 = 8, so v2 = 8

u1 + v1= 19 which means -10 + v1= 19, so v1 = 29

4. Computation of cost differences for non basic cells dij = cij - ( ui + vj )

 

cij

 

ui + vj
  •  

(30)

(50)
  •  

 
  •  

-2

-10
  •  

(70)

(30)
  •  
  •  

 

69

48
  •  
  •  

(40)
  •  

(70)
  •  

 

29
  •  

0
  •  

 

 

dij = cij - ( ui + vj )
  •  

32

60
  •  

1

-18
  •  
  •  

11
  •  

70
  •  

 

5. Doing Optimality test

dij < 0 i.e. d22 = -18

so x22 is entering the basis

 

6. Creation of loop and allotment of unknown quantity ?

 

186_loopong.png

We assign ? to the cell (2, 2). Reallocation is done by transferring the maximum possible amount ? in the marked cell. The value of ? is achieved by equating to zero to the corners of the closed loop. That is min (8-?, 2-?) = 0 which gives ? = 2. Hence x24 is outgoing as it turns out to be zero.

 

5 (19)

 

 

2 (10)

 

2 (30)

7 (40)

 

 

6 (8)

 

12 (20)

 

Minimum transportation cost comes out to be 5 (19) + 2 (10) + 2 (30) + 7 (40) + 6 (8) + 12 (20) = Rs. 743

 

7. Enhanced Solution

 

 

 

 

 

ui

 
  • (19)

 

 
  • (10)

u1= -10

 

 
  • (30)
  • (40)

 

u2 = 22

 

 
  • (8)

 
  • (20)

  u3 = 0

vj

v1 = 29

v2 = 8

v3 = 18

v4 = 20

 

 

 

 

 

 

 

 

cij

 

ui + vj
  •  

(30)

(50)
  •  

 
  •  

-2

8
  •  

(70)
  •  
  •  

(60)

 

51
  •  
  •  

42

(40)
  •  

(70)
  •  

 

29
  •  

18
  •  

 

 

dij = cij - ( ui + vj )
  •  

32

42
  •  

19
  •  
  •  

18

11
  •  

52
  •  

 

As dij > 0, an optimal solution is achieved with minimal cost of Rs.743