Transcript Transportation Problem: Moving towards Optimality

Transportation Problem
Moving towards Optimality
ATISH KHADSE
Once an initial solution is obtained, the next step is to check its
optimality. An optimal solution is one where there is no other
set of transportation routes (allocations) that will further reduce
the total transportation cost. Thus, we have to evaluate each
un-occupied cell in the transportation table in terms of an
opportunity of reducing total transportation cost.
If we have a B.F.S. consisting of (m+ n–1) independent
positive allocations and a set of arbitrary number ui and vj
(i=1,2,...m; j=1,2,...n) such that cij = ui+vj for all occupied cells
(i, j) then the evaluation dij corresponding to each empty
cell (i, j) is given by :
dij = cij – (ui+ vj)
This evaluation is also called the opportunity cost for unoccupied cells.
Modified Distribution (MODI) or u-v Method
Step 1: Start with B.F.S. consisting of (m+ n–1) allocations in
independent positions.
Step 2: Determine a set of m+n numbers ui (i=1,2,....m) and
vj (j=1,2,...n) for all the rows and columns such that for each
occupied cell (i,j), the following condition is satisfied :
cij = ui+vj
Step 3: Calculate cell evaluations (opportunity cost) dij for
each empty cell (i,j) by using the formula :
dij = cij – ( ui+vj ) for all i & j.
Step 4: Examine the matrix of cell evaluation dij for negative
entries and conclude that
(i) If all dij > 0 , then solution is optimal and unique.
(ii)If at least one dij = 0 , then solution is optimal and alternate
solution also exists.
(iii)If at least one dij < 0 ,then solution is not optimal and an
improved solution can be obtained.
In this case, the un-occupied cell with the largest negative
value of dij is considered for the new transportation schedule.
Step 5: Construct a closed path (loop) for the unoccupied cell
having largest negative opportunity cost. Mark a (+) sign in this
cell and move along the rows (or columns) to find an occupied
cell. Mark a (-) sign in this cell and find out another occupied
cell. Repeat the process and mark the occupied cells with (+)
and (-) signs alternatively. Close the path back to the selected
unoccupied cell.
Step 6: Select the smallest quantity amongst the cells
marked with (-) sign. Allocate this value to the unoccupied
cell of the loop and add and subtract it in the occupied cells
as per their signs.
Thus an improved solution is obtained by calculating the
total transportation cost by this method.
Step 7: Test the revised solution further for optimality. The
procedure terminates when all dij ≥ 0 , for unoccupied cells.