Skip to main content

Test for Optimality MODI Method

The MODI (Modified Distribution) Method, also known as the UV method, is used to check the optimality of an initial feasible solution for a transportation problem and improve it if necessary. It calculates opportunity costs for non-basic cells (cells not currently in the solution) and adjusts allocations based on these costs to find the optimal solution.

Steps for the MODI Method

  1. Obtain an initial feasible solution using any method (e.g., North-West Corner Rule, Least Cost Method, Vogel’s Approximation Method). The solution should satisfy the supply and demand requirements with the minimum number of allocations, which is (m + n - 1), where m is the number of rows and n is the number of columns.

  2. Calculate the values of dual variables (U and V).

    • For each occupied cell (i, j) in the solution, use the formula U_i + V_j = C_ij, where C_ij is the cost for that cell.
    • Set U_1 = 0 (arbitrarily) and calculate the other values of U and V based on the equation for the occupied cells.

  3. Compute the opportunity cost (Δ_ij) for each unoccupied cell.

    • Use the formula: Δ_ij = C_ij - (U_i + V_j).
    • If all Δ_ij values are greater than or equal to zero, the current solution is optimal.

  4. If any Δ_ij is negative, the current solution is not optimal. Identify the cell with the most negative Δ_ij to bring into the solution and adjust the allocations to form a closed loop.

  5. Make the new allocations using the stepping-stone path and repeat the process until all opportunity costs are non-negative.

Example of the MODI Method

Consider a transportation problem with three factories (A, B, C) supplying goods to three warehouses (X, Y, Z). The supply, demand, and transportation costs are given as follows:

X Y Z Supply
A 4 8 8 60
B 2 5 6 70
C 3 8 6 50
Demand 50 80 50

Step 1: Obtain an Initial Feasible Solution

Using the Least Cost Method, we get the following initial feasible solution:

X Y Z Supply
A 50 10 0 60
B 0 70 0 70
C 0 0 50 50
Demand 50 80 50

Step 2: Calculate the U and V Values

We have occupied cells: (A-X), (A-Y), (B-Y), and (C-Z).

  1. Set U_A = 0 (arbitrarily).
  2. Calculate the other U and V values:
    • For (A-X): U_A + V_X = 4 → 0 + V_X = 4 → V_X = 4.
    • For (A-Y): U_A + V_Y = 8 → 0 + V_Y = 8 → V_Y = 8.
    • For (B-Y): U_B + V_Y = 5 → U_B + 8 = 5 → U_B = -3.
    • For (C-Z): U_C + V_Z = 6 → U_C + V_Z = 6. Assume U_C = 0, then V_Z = 6.

Step 3: Compute Opportunity Costs (Δ_ij)

Calculate Δ_ij for each unoccupied cell:

  • For (B-X): Δ_BX = C_BX - (U_B + V_X) = 2 - (-3 + 4) = 2 - 1 = 1.
  • For (B-Z): Δ_BZ = C_BZ - (U_B + V_Z) = 6 - (-3 + 6) = 6 - 3 = 3.
  • For (C-Y): Δ_CY = C_CY - (U_C + V_Y) = 8 - (0 + 8) = 8 - 8 = 0.

Step 4: Check Optimality

Since all opportunity costs are greater than or equal to zero, the current solution is optimal.

Summary

  • The MODI Method is used to check the optimality of an initial feasible solution and adjust it if needed by recalculating allocations based on opportunity costs.
  • If all opportunity costs are non-negative, the current solution is optimal.
  • If any opportunity costs are negative, adjustments need to be made using a stepping-stone path to improve the solution.
Back to top