U-V Method Optimality Test

Posted in Operations and Supply Chain Terms, Total Reads: 1658

Definition: U-V Method Optimality Test

U-V Method Optimality Test is used to check the optimality of a basic feasible solution 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 cii= ui+vj for all occupied cells (i,j) . The evaluation dij corresponding to each empty cell (I, j) is given by:

dii = cii – (ui + vj)

The steps of this test are as:

1.The initial basic feasible solution (B.F.S) is calculated using any three methods:

  • North west corner rule
  • Matrix minimum method
  • Vogel approximation method

2. Determine the set of dual variables 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:


3.Calculate the opportunity cost cij –(ui+vj) =dij for each empty cell (i,j)

4. The sign of each unoccupied cell is checked. If it is either positive or zero, then the given solution is optimal else steps 5 to 7 are followed.

5. The unoccupied cell with the smallest negative opportunity cost is selected as the cell to be included in the next solution and a closed path or loop for the unoccupied cell is drawn.

6. Alternate plus and minus signs are assigned to the unoccupied cells on the corner points of the closed path with a plus sign at the cell being evaluated.

7. Determine the maximum number of units that should be shipped to this unoccupied cell. The smallest value with a negative position on the closed path indicates the number of units that can be shipped to the entering cell. Now, add this quantity to all the cells on the corner points of the closed path marked with plus signs and subtract it from those cells marked with minus signs. In this way an unoccupied cell becomes an occupied cell. Until the optimal solution is obtained, the whole procedure is repeated.


Looking for Similar Definitions & Concepts, Search Business Concepts