Transportation Problem Calculator with Steps (up to 21×21)

This calculator generates a feasible allocation matrix and computes the minimum total transportation cost. It can create an initial solution (VAM, Northwest Corner, Least Cost, Row/Column Minima, Russell) and then improve/prove optimality using MODI (u–v method) or Stepping Stone. It also handles unbalanced transportation problems by automatically adding a dummy row or column.

A transportation problem is balanced when total supply equals total demand. It’s unbalanced when totals differ. To solve an unbalanced problem, a dummy destination (if supply > demand) or a dummy source (if demand > supply) is added with zero costs to balance totals. Dummy allocations help the math work but typically represent “unused supply” or “unmet demand,” not real routes.

VAM is a strong method for finding a near-optimal initial feasible solution. It computes row and column penalties (difference between the two smallest costs), then allocates to the cheapest cell in the row/column with the highest penalty. VAM often produces a starting plan closer to optimal than Northwest Corner or Least Cost, reducing the number of optimization iterations needed.

MODI (Modified Distribution / u–v method) is an optimization method that tests if a feasible transportation plan is optimal. It assigns potentials $u_i$ui​ and $v_j$vj​ to basic cells, then computes reduced costs $d_{ij}=c_{ij}-(u_i+v_j)$dij​=cij​−(ui​+vj​) for unused routes. If all reduced costs are nonnegative, the solution is optimal. If any are negative, MODI pivots along a loop to reduce total cost.

The Stepping Stone method checks each unused route by forming a closed loop through allocated cells and computing an opportunity cost ${\mathrm{\Delta }}_{ij}$Δij​. If ${\mathrm{\Delta }}_{ij}$Δij​ is negative, shifting shipments along that loop reduces total cost. MODI and Stepping Stone usually reach the same optimum; MODI uses potentials and reduced costs, while Stepping Stone explains improvements directly using loop opportunity costs.

A solution is optimal when the optimality test finds no improving move. In MODI, this means every unused route has reduced cost $d_{ij}\ge 0$dij​≥0. In Stepping Stone, it means every unused route has opportunity cost ${\mathrm{\Delta }}_{ij}\ge 0$Δij​≥0. If any value is negative, the plan can be improved by pivoting shipments along a valid loop until no negatives remain.

Degeneracy happens when the number of basic allocations is less than $m+n-1$m+n−1 (sources + destinations − 1). That can prevent MODI/Stepping Stone from computing potentials or loops correctly. Solvers fix it by placing an epsilon (ε) placeholder in a carefully chosen empty cell to complete a valid basis. ε does not change totals or real shipments; it’s a bookkeeping device to keep the algorithm stable.

Total transportation cost is computed as ${\sum }_i{\sum }_j{c}_{ij}{x}_{ij}$∑i​∑j​cij​xij​: multiply each shipped quantity $x_{ij}$xij​ by its route cost $c_{ij}$cij​, then sum across all routes. Only cells with positive shipments contribute. If the model is unbalanced and a dummy row/column is added with zero costs, dummy allocations usually don’t change total cost but do affect interpretation.

Use the bulk paste/import section. Paste the cost matrix with rows on new lines and values separated by tabs, spaces, or commas (copy/paste from Sheets usually works because it’s tab-separated). Then paste supply (one value per source) and demand (one value per destination). If the paste fails, check for extra blank lines, merged cells, or mismatched counts versus the selected number of sources/destinations.