TEST FOR OPTIMALITY
Dr. Prasad Kulkarni
TEST FOR OPTIMALITY
• Once an initial solution is obtained, the next step is to check its optimality in terms of
feasibility of the solution and total minimum transportation cost. The test of
optimality begins by calculating an opportunity cost associated with each unoccupied
cell (represents unused route) in the transportation table. An unoccupied cell with the
largest negative opportunity cost is selected to include in the new set of transportation
routes (allocations). This value indicates the per unit cost reduction that can be
achieved by making appropriate allocation in the unoccupied cell. This cell is also
known as an incoming cell (or variable). The outgoing cell (or variable) from the
current solution is the occupied cell (basic variable) where allocation will become
zero as allocation is made in the unoccupied cell with the largest negative opportunity
cost. Such an exchange reduces the total transportation cost. The process is continued
until there is no negative opportunity cost. That is, the current solution is an optimal
solution. The Modified-distribution (MODI) method (also called u-v method or
method of multipliers) is used to calculate opportunity cost associated with each
unoccupied cell and then improving the current solution leading to an optimal
solution.
Steps of MODI Method (Transportation Algorithm)
• Step 1: For an initial basic feasible solution with m + n – 1 occupied cells, calculate ui and vj for rows and
columns. The initial solution can be obtained by any of the three methods discussed earlier.
• To start with, any one of uis or vjs is assigned the value zero. It is better to assign zero to a particular ui or vj
where there are maximum number of allocations in a row or column respectively, as this will reduce the
considerably arithmetic work. The value of uis and vjs for other rows and columns is calculated by using the
relationship.
cij = ui + vj , for all occupied cells (i, j).
• Step 2: For unoccupied cells, calculate the opportunity cost by using the relationship
• dij = cij – (ui + vj) , for all i and j.
• Step 3: Examine sign of each dij
• (i) If dij > 0, then the current basic feasible solution is optimal.
• (ii) If dij = 0, then the current basic feasible solution will remain unaffected but an alternative solution exists.
• (iii) If one or more dij < 0, then an improved solution can be obtained by entering an unoccupied cell (i, j)
into the solution mix (basis). An unoccupied cell having the largest negative value of dij is chosen for
entering into the solution mix (new transportation schedule).
• Step 4: Construct a closed-path (or loop) for the unoccupied cell with largest negative value of dij. Start the
closed path with the selected unoccupied cell and mark a plus sign (+) in this cell. Trace a path along the rows
(or columns) to an occupied cell, mark the corner with a minus sign (–) and continue down the column (or
row) to an occupied cell. Then mark the corner with plus sign (+) and minus sign (–) alternatively. Close the
path back to the selected unoccupied cell.
• Step 5: Select the smallest quantity amongst the cells marked with minus sign on the corners of closed loop.
Allocate this value to the selected unoccupied cell, add it to occupied cells marked with plus signs, and
subtract it from the occupied cells marked with minus signs.
• Step 6: Obtain a new improved solution by allocating units to the unoccupied cell according to Step5 and
calculate the new total transportation cost.
• Step 7: Test optimality of the revised solution. The procedure terminates when all dij ≥ 0 for
unoccupiedcells.
• Remarks 1. The closed-loop (path) starts and ends at the selected unoccupied cell. It consists of successive
horizontal and vertical (connected) lines whose end points must be occupied cells, except an end point
associated with entering unoccupied cell. This means that every corner element of the loop must be an
occupied cell.
Loop Examples
Example
Initial solution using VAM
• Test the optimality of the revised solution once
again in the same way as discussed in earlier steps.
• The values of uis, vjs and dijs are shown in Table
Since each of dijs is positive, therefore, the
• current basic feasible solution is optimal with a
mi]nimum total transportation cost of Rs 743.
Example 2