Transportation: formula sheet

Key formulas

Objective function

Minimise Z = ΣΣ cij × xij (i = 1 to m, j = 1 to n)

cij is the unit cost from origin i to destination j. xij is the quantity shipped. Z is total transportation cost.

Supply constraints

Σj xij = ai for each origin i

Shipments from an origin equal its supply. In an unbalanced case with a dummy, this holds after balancing.

Demand constraints

Σi xij = bj for each destination j

Receipts at a destination equal its demand.

Non-negativity

xij ≥ 0 for all i, j

You cannot ship a negative quantity.

Balance condition

Σ ai = Σ bj

Balanced if true. If Σ ai > Σ bj add a dummy destination; if Σ ai < Σ bj add a dummy origin.

Number of variables and constraints

Variables = m × n; constraints = m + n

m origins and n destinations, after balancing.

Basic feasible solution size

Allocated cells = m + n − 1

A non-degenerate basic feasible solution has exactly this many occupied cells. Fewer means degeneracy.

Balanced problem condition

Σ supply = Σ demand

If supply and demand differ, add a dummy destination or source with zero cost to balance.

Number of occupied cells in a basic feasible solution

m + n − 1

m = number of sources, n = number of destinations. Fewer occupied cells means degeneracy, so add a zero allocation.

Allocation in a chosen cell

Allocation = min(remaining supply of row, remaining demand of column)

Applies in all three methods. Cross out the row or column that is exhausted.

VAM penalty

Penalty = second-lowest cost − lowest cost (in a row or column)

Compute it only on rows and columns still open. Recompute after every allocation.

Total transportation cost

Total cost = Σ (units allocated × unit cost) over occupied cells

Use it to compare methods and to report the IBFS cost.

Basic feasible solution requirement

Number of allocated cells = m + n − 1

m = sources, n = destinations. Check this before you start. If fewer cells are allocated, the solution is degenerate and u-v values cannot be found until you add a zero allocation in a suitable cell.

u-v equation for allocated cells

uᵢ + vⱼ = cᵢⱼ

Applies only to allocated cells. Set one u (usually the row with the most allocations) to 0 and solve the rest.

Opportunity cost of an empty cell

dᵢⱼ = cᵢⱼ − (uᵢ + vⱼ)

Computed for empty cells only.

Optimality condition (minimisation)

All dᵢⱼ ≥ 0

If any dᵢⱼ < 0, the solution can be improved. Enter the cell with the most negative d. If any empty cell has d = 0 and the rest are positive, an alternate optimum exists.

Optimality condition (maximisation, with c as profit)

All dᵢⱼ ≤ 0, where dᵢⱼ = cᵢⱼ − (uᵢ + vⱼ)

The rule reverses. Alternatively, convert profit to loss by subtracting every profit from the largest profit and then use the minimisation rule.

Reallocation quantity

θ = smallest allocation among the cells marked '−' in the loop

Add θ to '+' cells and subtract it from '−' cells. The cell that falls to zero leaves the solution.

Change in total cost

Change in cost = dᵢⱼ × θ

Use this to check each iteration. With a negative d, the cost falls by |d| × θ.

Balance condition

Σ supply = Σ demand

If not equal, add a dummy destination (excess supply) or a dummy source (excess demand). Dummy cost is zero unless the question gives a penalty.

Number of occupied cells

Occupied cells = m + n − 1

Fewer than this means degeneracy. Add ε to an unoccupied cell that forms no closed loop. This count includes the dummy row or column.

Prohibited route

c(ij) = M (very large)

M is larger than any real cost. Never leave units in an M cell in the final plan.

Maximization conversion

Opportunity loss = (largest profit in table) − (profit in cell)

Minimise the loss table. Compute the final profit from the original profit table.

MODI index for unoccupied cells

Δ(ij) = c(ij) − (u(i) + v(j))

For minimization, optimal when all Δ ≥ 0. A Δ of zero in an unoccupied cell signals an alternate optimum.

Quick revision

• A balanced problem has total supply equal to total demand.
• A basic feasible solution has exactly m + n − 1 allocated cells in non-degenerate cases.
• NWCR starts at the top-left cell and ignores costs, so it is quick but usually costly.
• Least cost method allocates first to the cheapest cell, then the next cheapest.
• VAM: find row and column penalties (difference of two lowest costs), pick the highest penalty, allocate to its cheapest cell.
• MODI: for allocated cells, u + v = cost.
• For empty cells, opportunity cost = cost − (u + v).
• For minimization, the solution is optimal when no empty cell has a negative value.
• If a negative value exists, pick the most negative cell, draw a closed loop, and shift the smallest quantity on the minus cells.
• Unbalanced problem: add a dummy destination or source with zero cost to balance it.
• Degeneracy: allocated cells fewer than m + n − 1; place ε in an independent empty cell and treat it as allocated.
• Maximization: subtract every profit from the highest profit, or maximize with reversed optimality test, and then solve as minimization; compute final value from the original profits.

Common mistakes

• Solving an unbalanced problem without adding a dummy Fix: Always total supply and demand first. Never begin allocation until the table is balanced.
• Adding the dummy on the wrong side Fix: Surplus supply means unsold stock, so add a dummy destination (column). Shortage means unmet demand, so add a dummy origin (row).
• Starting without balancing the problem. Fix: Add the totals first. If unequal, add a dummy row or column with zero cost and the difference as its quantity.
• Calculating VAM penalty as highest minus lowest cost. Fix: Use the two smallest costs in the row or column: second-lowest minus lowest.
• Starting MODI with fewer or more than m + n − 1 allocated cells. Fix: Always count allocated cells first. Add a zero allocation in an independent empty cell if the count is short. 'Independent' means it does not close a loop with the allocated cells.
• Calculating d for allocated cells, or using u + v − c instead of c − (u + v). Fix: Allocated cells satisfy u + v = c, so their d is always 0. Compute d = c − (u + v) only for empty cells. Keep one sign convention throughout.
• Putting a high cost instead of zero in the dummy row or column. Fix: Use zero unless the question states a shortage or storage penalty. Then use the given penalty.
• Subtracting from the largest value but forgetting the dummy cells in a maximization problem. Fix: Balance first, then convert every cell, including dummies, to opportunity loss. Finally report profit from the original table.

Exam tips

• In MCQs, the first thing examiners test is the balance check. Add totals before reading anything else.
• In a case scenario, look for prohibited routes, storage costs or shortage penalties. These change the dummy costs and the M entries.
• When asked to formulate, write the objective function and all constraints, not just the table. Marks are given for each part.
• State the type of problem (balanced or unbalanced) and the dummy you added in one clear line. This is easy credit.
• Present the table neatly with labelled rows, columns, supply and demand, because later steps depend on it.
• Show every allocation, the crossed-out lines and the final cost line. Marks are given for the method as well as the answer.
• In VAM, write the penalty rows and columns for each round clearly. Examiners follow your logic from them.
• Always check balance and the m + n − 1 count. Quote both in your answer.