Transportation Optimality

Improves an initial basic feasible solution of a transportation problem to optimality.

Dual of a Transportation Problem

1 dual variable per supply point ($u_i$) and per demand point ($v_j$). For every basic (occupied) cell:

UV (MODI) Method

• Set $u_1 = 0$ (or any starting value) and solve the $u_i + v_j = c_{ij}$ equations for the occupied cells.
• For every unoccupied cell, compute the opportunity cost $\Delta_{ij} = c_{ij} - u_i - v_j$.
• If every $\Delta_{ij} \ge 0$, the solution is optimal. Stop.
• Otherwise, the most negative $\Delta_{ij}$ marks the entering cell.

Loop in a Transportation Table

A closed path of occupied cells (plus the entering cell) that alternates horizontal and vertical moves, turning only at occupied cells, and returns to the entering cell. Exactly one such loop exists for a given entering cell in a non-degenerate BFS.

• Alternate $+$ and $-$ signs around the loop, starting with $+$ at the entering cell.
• The minimum allocation among $-$ cells is shifted around the loop: added at $+$ cells, subtracted at $-$ cells.
• The $-$ cell with the minimum allocation leaves the basis (becomes 0/unoccupied).

Repeat the UV method on the new solution until every $\Delta_{ij} \ge 0$.

Alternate Optimal Solution

Occurs when an unoccupied cell has $\Delta_{ij} = 0$ at optimality. Any allocation along its loop gives another solution with the same optimal cost.