Transportation Algorithm for Minimization Problem (MODI Method)

 Step 1

Make the transportation table entering the origin capacities a_i, the cost c_ij and destination requirement b_j

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 x_ij, solve the system of equations u_i + v_j = c_ij, for all i, j for which cell (i, j) is in the basis, starting at first with some u_i = 0, compute the values of u_i and v_j on the transportation table

Step 4

Calculate the cost differences d_ij = c_ij - ( u_i + v_j ) for all the non-basic cells

Step 5

Apply optimality test by testing the sign of each d_ij

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

Step 6

Assume the variable x_rs 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 

Answer

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

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 u_i and v_j : -  u_i + v_j  = c_ij

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

Assume u₃ = 0, then

u₃ + v₄= 20 which means 0 + v₄ = 20, so v₄ = 20

u₂ + v₄= 60 which means u₂ + 20 = 60, so u₂ = 40

u₁ + v₄= 10 which means u₁ + 20 = 10, so u₁ = -10

u₂ + v₃= 40 which means 40 + v₃ = 40, so v₃ = 0

u₃ + v₂= 8 which means 0 + v₂ = 8, so v₂ = 8

u₁ + v₁= 19 which means -10 + v₁= 19, so v₁ = 29

4. Computation of cost differences for non basic cells d_ij = c_ij - ( u_i + v_j )

5. Doing Optimality test

d_ij < 0 i.e. d₂₂ = -18

so x₂₂ is entering the basis

6. Creation of loop and allotment of unknown quantity ?

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 x₂₄ is outgoing as it turns out to be zero.

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

7. Enhanced Solution

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