Lecture_18_Examining the IBFS using modified distribution method

18.1 Examining the Initial Basic Feasible Solution for Non - Degeneracy
Examine the initial basic feasible solution for non-degeneracy. If it is said to be non-degenerate then it has the following two properties
• Initial basic feasible solution must contain exactly m + n – 1 number of individual allocations.
• These allocations must be in independent positions Independent Positions

• • •
• • •
• •



• •
• •
• •


Non-Independent Positions








17.2 Transportation Algorithm for Minimization Problem (MODI Method)

Step 1
Construct the transportation table entering the origin capacities ai, the destination requirement bj and the cost cij

Step 2

Find an initial basic feasible solution by vogel’s method or by any of the given 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 initially with some ui = 0, calculate the values of ui and vj on the transportation table

Step 4
Compute the cost differences dij = cij – ( ui + vj ) for all the non-basic cells

Step 5
Apply optimality test by examining the sign of each dij
• If all dij ? 0, the current basic feasible solution is optimal
• If at least one dij < 0, select the variable xrs (most negative) to enter the basis.
• Solution under test is not optimal if any dij is negative and further improvement is required by repeating the above process.

Step 6
Let the variable xrs enter the basis. Allocate an unknown quantity ? to the cell (r, s). Then construct a loop that starts and ends at the cell (r, s) and connects some of the basic cells. The amount ? is added to and subtracted from the transition cells of the loop in such a manner that the availabilities and requirements remain satisfied.

Step 7
Assign the largest possible value to the ? in such a way that the value of at least one basic variable becomes zero and the other basic variables remain non-negative. The basic cell whose allocation has been made zero will leave the basis.

Step 8
Now, return to step 3 and repeat the process until an optimal solution is obtained.













2

17.3 Worked Examples

Example 1
Find an optimal solution

W1 W2 W3 W4 Availability
F1 7
F2 9
F3 18
Requirement 5 8 7 14
Solution
1. Applying vogel’s approximation method for finding the initial basic feasible solution

F1 W1 W2 W3 W4 Availability
X Penalty
X
F2 X X
F3 X X
Requirement Penalty X X X X X X X X


Minimum transportation cost is 5 (19) + 2 (10) + 7 (40) + 2 (60) + 8 (8) + 10 (20) = Rs. 779

2. Check for Non-degeneracy
The initial basic feasible solution has m + n – 1 i.e. 3 + 4 – 1 = 6 allocations in independent positions. Hence optimality test is satisfied.


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






vj v1 = 29 v2 = 8 v3 = 0 v4 = 20



ui u1= -10
u2 = 40
u3 = 0


Assign a ‘u’ value to zero. (Convenient rule is to select the ui, which has the largest number of allocations in its row)
Let u3 = 0, then
u3 + v4= 20 which implies 0 + v4 = 20, so v4 = 20 u2 + v4= 60 which implies u2 + 20 = 60, so u2 = 40 u1 + v4= 10 which implies u1 + 20 = 10, so u1 = -10 u2 + v3= 40 which implies 40 + v3 = 40, so v3 = 0 u3 + v2= 8 which implies 0 + v2 = 8, so v2 = 8
u1 + v1= 19 which implies -10 + v1= 19, so v1 = 29
4. Calculation of cost differences for non basic cells dij = cij – ( ui + vj )