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}
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
W_{1}
W_{2}
W_{3}
W_{4}
Availability
F_{1}
19
30
50
10
7
F_{2}
70
40
60
9
F_{3}
8
20
18
Requirement
5
14
Answer
1. Put vogel's approximation method for determining the initial basic feasible solution
Penalty
5(19)
(30)
(50)
2(10)
X
(70)
7(40)
2(60)
(40)
8(8)
10(20)
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}
u_{i}
u_{1}= -10
u_{2 }= 40
u_{3 }= 0
v_{j}
v_{1 }= 29
v_{2 }= 8
v_{3 }= 0
v_{4 }= 20
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_{3} = 0, then
u_{3} + v_{4}= 20 which means 0 + v_{4} = 20, so v_{4 }= 20
u_{2} + v_{4}= 60 which means u_{2} + 20 = 60, so u_{2} = 40
u_{1} + v_{4}= 10 which means u_{1} + 20 = 10, so u_{1} = -10
u_{2} + v_{3}= 40 which means 40 + v_{3} = 40, so v_{3} = 0
u_{3} + v_{2}= 8 which means 0 + v_{2} = 8, so v_{2 }= 8
u_{1} + v_{1}= 19 which means -10 + v_{1}= 19, so v_{1} = 29
4. Computation of cost differences for non basic cells d_{ij} = c_{ij} - ( u_{i} + v_{j} )
c_{ij}
u_{i} + v_{j}
-2
-10
69
48
29
0
d_{ij} = c_{ij} - ( u_{i} + v_{j} )
32
1
-18
11
5. Doing Optimality test
d_{ij} < 0 i.e. d_{22} = -18
so x_{22} 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_{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 Solution
u_{2 }= 22
v_{3 }= 18
(60)
51
42
52
As d_{ij} > 0, an optimal solution is achieved with minimal cost of Rs.743
organic chemistry and classification of organic molecules tutorial all along with the key concepts of scope of organic chemistry, uniqueness of carbon atom, representation of organic molecules, classification of organic compounds, heterocyclic compounds
tutorsglobe.com uses of biogas assignment help-homework help by online recycling of waste tutors
tutorsglobe.com triple fusion assignment help-homework help by online double fertilization tutors
Viruses tutorial all along with the key concepts of Features of Viruses, Structure of a virus, Size and Shape of virus, Classification of virus and viral infections in human beings
theory and lecture notes of theory of random access machines all along with the key concepts of random access machines, ultimate risc, stored program computer and ram image. tutorsglobe offers homework help, assignment help and tutor’s assistance on theory of random access machines.
theory of introduction to cpm / pert techniques, cpm/pert or network analysis is the technique is at times called, developed with two parallel streams, one military and the other industrial.
Theory and lecture notes of Externalities and Pollution Problem all along with the key concepts of Negative Externalities, Private Marginal Cost, Optimal Environmental Management, Types of Costs, Efficient Management, Coase Theorem. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Externalities and Pollution Problem.
Get rid of the apprehension of short deadlines and score top grades with Gender and Legal Issues Assignment Help service!
Looking zoology assignment help- zoology homework help, wriitng solutions or papers in zoology? get help online from biology tutors.
Concept of Multiple input programs-Assignment help and Homework help along with the key concepts of Problems of multiple input programs, Party Lamps and The Clocks
Theory and lecture notes of Role of Database Administrator all along with the key concepts of role of database administrator, types of users for a DBMS, END User, Application Programmer, DBA. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Role of Database Administrator.
tutorsglobe.com coordination sphere assignment help-homework help by online terminologies tutors
www.tutorsglobe.com offers sates of matter homework help, sates of matter assignment help, online tutoring assistance, physical chemistry solutions by online qualified tutor's help.
tutorsglobe.com multiple shootlet production assignment help-homework help by online micropropagation tutors
Theory and lecture notes of The QR Method all along with the key concepts of the qr method, linear algebra, assignment help, homework help. Tutorsglobe offers homework help, assignment help and tutor’s assistance on The QR Method.
1962540
Questions Asked
3689
Tutors
1451036
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!