- +1-530-264-8006
- info@tutorsglobe.com

18,76,764

Questions

Asked

21,311

Experts

9,67,568

Questions

Answered

Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!

Submit Assignment2015 © Tutors Globe. All rights reserved.

## MODI Method - Transportation Algorithm for Minimization Problem

Transportation Algorithm for Minimization Problem (MODI Method)Make the transportation table entering the origin capacities a

_{i}, the cost c_{ij}and destination requirement b_{j}Step 2Determine 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 tableStep 4

Calculate the cost differences d

_{ij}= c_{ij}- ( u_{i}+ v_{j}) for all the non-basic cellsStep 5

Apply optimality test by testing the sign of each d

_{ij}_{ij}≥ 0, the present basic feasible solution is optimal or best_{ij}< 0, choose the variable x_{rs}(most negative) to enter the basis._{ij}is negative and subsequent improvement is needed by repeating the above procedure.Step 6Assume 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 7Allocate 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 8Now, go back to step 3 and repeat the process until an optimal solution is achieved.

Worked ExamplesIllustration 1Determine an optimal solutionW

_{1}W

_{2}W

_{3}W

_{4}Availability

F

_{1}19

30

50

10

7

F

_{2}70

30

40

60

9

F

_{3}40

8

70

20

18

Requirement

5

8

7

14

Answer1.

Put vogel's approximation method for determining the initial basic feasible solutionW

_{1}W

_{2}W

_{3}W

_{4}Availability

Penalty

F

_{1}5(19)(30)

(50)

2(10)X

X

F

_{2}(70)

(30)

7(40)2(60)X

X

F

_{3}(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-degeneracyThe 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}u

_{i}u

_{1}= -10u

_{2 }= 40u

_{3 }= 0v

_{j}v

_{1 }= 29v

_{2 }= 8v

_{3 }= 0v

_{4 }= 20Allocate 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

_{3}= 0, thenu

_{3}+ v_{4}= 20 which means 0 + v_{4}= 20, so v_{4 }= 20u

_{2}+ v_{4}= 60 which means u_{2}+ 20 = 60, so u_{2}= 40u

_{1}+ v_{4}= 10 which means u_{1}+ 20 = 10, so u_{1}= -10u

_{2}+ v_{3}= 40 which means 40 + v_{3}= 40, so v_{3}= 0u

_{3}+ v_{2}= 8 which means 0 + v_{2}= 8, so v_{2 }= 8u

_{1}+ v_{1}= 19 which means -10 + v_{1}= 19, so v_{1}= 294.

Computation of cost differences for non basic cells d_{ij}= c_{ij}- ( u_{i}+ v_{j})c

_{ij}u

_{i}+ v_{j}(30)

(50)

-2

-10

(70)

(30)

69

48

(40)

(70)

29

0

d

_{ij}= c_{ij}- ( u_{i}+ v_{j})32

60

1

-1811

70

5.

DoingOptimality testd

_{ij}< 0 i.e. d_{22}= -18so x

_{22}is entering the basis6. C

reation 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

_{24}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 Solutionu

_{i}u

_{1}= -10u

_{2 }= 22u

_{3 }= 0v

_{j}v

_{1 }= 29v

_{2 }= 8v

_{3 }= 18v

_{4 }= 20c

_{ij}u

_{i}+ v_{j}(30)

(50)

-2

8

(70)

(60)

51

42

(40)

(70)

29

18

d

_{ij}= c_{ij}- ( u_{i}+ v_{j})32

42

19

18

11

52

As d

_{ij}> 0, an optimal solution is achieved with minimal cost of Rs.743