Transportation: formula sheet

Key formulas

Objective function

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

cij is the unit cost from source i to destination j. xij is the number of units shipped on that route.

Supply constraints

Σj xij = ai for each source i

Units sent out of a source equal its supply. In a balanced problem, all supply is used.

Demand constraints

Σi xij = bj for each destination j

Units received at a destination equal its demand.

Non-negativity

xij ≥ 0 for all i, j

You cannot ship a negative quantity.

Balance condition

Σ ai = Σ bj

If true, the problem is balanced. If not, add a dummy row or column.

Number of allocated cells in a basic feasible solution

m + n − 1

A non-degenerate basic feasible solution has exactly this many occupied cells. It is used in the later solution methods.

Balanced condition

Σ supply = Σ demand

If not equal, add a dummy row or column with zero cost to balance it before starting.

Number of allocations in a basic solution

Occupied cells = m + n − 1

m = number of sources, n = number of destinations. Fewer cells means degeneracy.

Allocation rule

Allocation = min(remaining supply, remaining demand)

Used in all three methods. After allocating, cross out the exhausted row or column.

VAM penalty

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

Choose the row or column with the largest penalty, then allocate to its lowest-cost cell.

Total transportation cost

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

Report the cost in rupees, with the unit of cost per unit.

Basic cells condition

Number of allocated cells = m + n − 1

m = sources, n = destinations. Fewer cells means degeneracy, and you cannot solve for all u and v until you fix it.

u-v equation for allocated cells

uᵢ + vⱼ = cᵢⱼ

Use only for allocated cells. Set one u (usually the row with most allocations) to 0, then solve for the rest.

Opportunity cost of an empty cell

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

Compute for every unallocated cell. Keep the sign.

Optimality rule (minimisation)

All Δᵢⱼ ≥ 0 ⇒ optimal

If any Δ = 0 for an empty cell, an alternative optimal solution exists with the same cost. If all are strictly positive, the solution is unique.

Optimality rule (maximisation)

All Δᵢⱼ ≤ 0 ⇒ optimal

Here c is profit. Enter the cell with the largest positive Δ. Or convert profits to losses and minimise.

Change in cost on reallocation

Total cost reduction = |Δ of entering cell| × θ

θ = smallest quantity in the minus cells of the loop. Use this to check your new total cost.

Number of basic cells

Occupied cells = m + n − 1 (m sources, n destinations)

If fewer, the solution is degenerate. If you have more, or a closed loop exists, something is wrong.

Balancing rule

Total supply ≠ total demand → add dummy with quantity |Σ supply − Σ demand| and cost 0

Excess supply: dummy column. Excess demand: dummy row.

Maximisation conversion

Loss cij = (largest profit in table) − (profit pij)

Minimise the loss table. Profit = (largest value × total units) − minimum total loss, for a balanced table.

Prohibited route

cij = M (very large positive number)

M must never carry an allocation in the final answer. If it does, the problem has no feasible solution.

Opportunity cost of an empty cell

Δij = cij − (ui + vj), with ui + vj = cij for occupied cells

Minimisation: optimal when all Δij ≥ 0. Any Δij = 0 in an empty cell at optimum means alternate optimal solutions.

Degeneracy fix

Place ε in an independent empty cell so cells = m + n − 1; ε → 0 in the final answer

Choose a cell, preferably low cost, that does not form a closed loop with the occupied cells.

Quick revision

• A transportation problem minimises total shipping cost subject to supply and demand constraints.
• A problem is balanced when total supply equals total demand.
• An unbalanced problem is balanced by adding a dummy source or destination with zero cost.
• A non-degenerate basic feasible solution has exactly m + n − 1 allocations.
• NWCR starts at the top-left cell and ignores costs, so it is fast but often far from optimal.
• Least Cost Method allocates first to the cell with the lowest unit cost.
• VAM uses penalties (difference of two lowest costs in each row and column) and usually gives the best starting solution.
• In MODI, set one u or v to 0 and use u + v = cost for allocated cells.
• Opportunity cost of an empty cell = cost − (u + v); for minimisation, the solution is optimal when all are zero or positive.
• Improve a solution by drawing a closed loop from the most negative empty cell and shifting the smallest quantity on the minus corners.
• Degeneracy arises when allocations are fewer than m + n − 1; add ε to an independent empty cell.
• For a prohibited route, assign a very large cost so it receives no allocation.

Common mistakes

• Not checking whether total supply equals total demand. Fix: Always total both sides first and write the result on the matrix.
• Adding the dummy on the wrong side. Fix: Excess supply needs a dummy destination (column). Excess demand needs a dummy source (row).
• Starting without checking that supply equals demand Fix: Total the supply and demand first. If unequal, add a dummy row or column with zero costs and state that you have done so.
• Allocating the wrong quantity Fix: Always write min(supply, demand) beside the cell and update both remaining figures.
• Computing u and v using empty cells as well as allocated cells Fix: Use the equation only for allocated cells. Empty cells get Δ = c − (u + v) instead.
• Starting MODI when allocated cells are fewer than m + n − 1 Fix: Count cells first. Add ε to an empty cell that does not make a closed loop, and treat it as allocated. Drop ε at the end.
• Putting a non-zero cost in dummy cells Fix: A dummy represents unused capacity or unmet demand, so every cell in it costs zero (unless the question gives shortage or storage penalties).
• Subtracting from the row or column maximum in a maximisation problem Fix: Subtract every entry from the single largest value in the whole table, then minimise.

Exam tips

• Write the totals check as the first line of your answer. It earns marks even if later steps go wrong.
• In MCQs, expect questions on the dummy rule, the assumptions and the m + n − 1 rule. Learn these cold.
• Draw the matrix neatly with supply and demand labelled. Examiners give marks for correct presentation.
• If the question mentions a penalty, storage cost or prohibited route, use it in the dummy or cell. Do not default to zero.
• Draw the table neatly and show each allocation round by round. Examiners give step marks for the method even if the final cost slips.
• Always state the check: total supply = total demand, and occupied cells = m + n − 1.
• For MCQs, know the one-line features: NWCR ignores cost, LCM picks the lowest cost cell, VAM uses penalties and is usually closest to optimal.
• If the question gives an unbalanced table, add the dummy with zero cost first. Then solve as normal.