Lecture_17_Examining the IBFS

17.1 Examining the Initial Basic Feasible Solution for Non - Degenera cy
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
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