Operations Management and Strategic Management · Transportation

Degeneracy, Unbalanced and Prohibited Routes in Transportation

Updated 10 October 2026 · Fact-checked

Special cases are variations of the standard transportation problem. Balance it with a zero-cost dummy source or destination, convert maximisation to minimisation, give a prohibited route a very large cost M, and add a tiny quantity ε to a degenerate solution so it has m + n − 1 allocations. Then run MODI as usual.

Understand Special Cases: Degeneracy, Unbalanced and Prohibited Routes

The basic transportation method assumes two things: total supply equals total demand, and every route is usable with a known unit cost to minimise. Real questions break these assumptions. The special cases are simply ways to put the problem back into the standard form, so that IBFS and MODI work without change.

Unbalanced problem. If supply is more than demand, goods are left over. Add a dummy destination with demand equal to the excess and zero cost in every cell. If demand is more than supply, add a dummy source with supply equal to the shortage and zero cost. Whatever quantity is allocated to a dummy is not actually shipped. It is unused capacity or unmet demand.

Maximisation. If the figures are profit or revenue, you want the largest total. Subtract every entry from the largest entry in the whole table. This gives an opportunity-loss table, which you then minimise. The optimal allocation is the same. Work out the real profit from the original table.

Prohibited route. If a source cannot supply a destination (road closed, legal bar, no transport), put a very large cost M in that cell. M makes the cell so unattractive that it never enters the solution. In a maximisation problem, convert first, then put M in the loss table.

Degeneracy. A feasible solution needs exactly m + n − 1 occupied (basic) cells, which must not form a closed loop. If you have fewer, the solution is degenerate and MODI cannot find all u and v values. Add a very small quantity ε (nearly zero) to an empty cell so that the cells stay independent and the set of occupied cells connects every row and column. Degeneracy can occur at the start or during iterations, when two or more cells become zero together. Finally, if an empty cell has an opportunity cost of zero at the optimum, there are alternate optimal solutions with the same total cost.

Key rules to remember

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.

How to solve Special Cases: Degeneracy, Unbalanced and Prohibited Routes questions

Use this order for any special-case transportation question. Do not start allocating until the table is in standard form.

1Check whether the objective is minimise cost or maximise profit. If maximise, subtract every entry from the largest entry to get a loss table.
2Add up supply and demand. If they differ, add a dummy row or column with the difference and zero costs.
3Put M in every prohibited cell (after any maximisation conversion).
4Find the initial basic feasible solution by North-West Corner, Least Cost or VAM, as the question asks. Allocate to dummy cells like any other, but never to M cells.
5Count occupied cells. If fewer than m + n − 1, add ε to an independent empty cell (not forming a loop) to restore degeneracy-free form.
6Compute u and v from occupied cells (set one u or v to 0), then find Δij = cij − (ui + vj) for all empty cells.
7If any Δij is negative, draw the closed loop from the most negative cell, shift the smallest quantity on the minus corners, and repeat step 6. If two minus cells become zero together, keep ε in one of them.
8At optimality, drop ε and dummy allocations, state the actual shipments, and compute the cost (or profit from the original table). Mention alternate optima if any empty Δij = 0.

Quickest way: Standard-form-first shortcut

When to use it: For a 3 × 3 or 3 × 4 problem when time is short and the question does not insist on a particular IBFS method.

Write the table once in final form: loss values, dummy line, M cells. Do not redraw it again.
Use VAM or Least Cost for the start, as it usually needs few or no MODI iterations. Allocate zero-cost dummy cells last, because the dummy should absorb the most expensive units.
Immediately count occupied cells against m + n − 1 and place ε before starting MODI.
After finding u and v, scan the Δ values only for negatives. Stop if none.
For the answer, compute cost only from real, non-dummy, non-ε cells.

Common mistakes in Special Cases: Degeneracy, Unbalanced and Prohibited Routes

Putting a non-zero cost in dummy cells
Students treat the dummy like a real route.
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
It is confused with the Hungarian method row reduction.
Fix: Subtract every entry from the single largest value in the whole table, then minimise.
Counting the dummy or ε in the final cost or shipments
These cells appear in the table, so they get added in.
Fix: Dummy allocations are not shipped and ε is zero. Compute cost only from real allocations and the original costs.
Placing ε in a cell that forms a closed loop with occupied cells
The student picks any empty cell without checking independence.
Fix: Place ε so that all rows and columns are connected, like a tree. If u and v cannot all be computed, the ε position is wrong.
Allocating to an M cell, or giving M a small value
M is replaced by a number such as 99 which is not large enough, or the cell is used in IBFS.
Fix: Treat M as larger than any other cost and never allocate to it. After the final table, confirm that no M cell is occupied.
Ignoring a zero Δ in an empty cell at the optimum
The student stops when no negatives appear.
Fix: Check for zeros. A zero means another allocation with the same cost exists, which the question may ask you to state.

Worked examples

Example 1

Three plants S1, S2, S3 have capacities of 50, 40 and 60 units. Three markets D1, D2, D3 need 30, 40 and 50 units. Unit transport costs (₹): S1: 4, 6, 8; S2: 5, 3, ✕; S3: 7, 5, 4. Plant S2 cannot supply D3. Find the minimum cost plan.

Show the solution

Total supply = 150 and total demand = 120, so the problem is unbalanced. Add a dummy destination D4 with demand 30 and zero cost in every row.
S2 to D3 is prohibited, so set that cost to M. The table is: S1: 4, 6, 8, 0; S2: 5, 3, M, 0; S3: 7, 5, 4, 0.
Initial solution: S2→D2 40 (cost 3, S2 and D2 both exhausted); S3→D3 50 (cost 4); S1→D1 30 (cost 4). The remaining supply is S1 20 and S3 10, which go to the dummy D4. Allocations: S1D1 30, S1D4 20, S2D2 40, S3D3 50, S3D4 10.
Occupied cells = 5, but m + n − 1 = 3 + 4 − 1 = 6. The solution is degenerate. S2D2 is not connected to the rest, so place ε in S2D4 (cost 0), which connects S2 to D4.
MODI: take u1 = 0. S1D1: v1 = 4. S1D4: v4 = 0. S3D4: u3 = 0. S3D3: v3 = 4. S2D4: u2 = 0. S2D2: v2 = 3.
Opportunity costs of the empty cells: S1D2 = 6 − 3 = 3; S1D3 = 8 − 4 = 4; S2D1 = 5 − 4 = 1; S3D1 = 7 − 4 = 3; S3D2 = 5 − 3 = 2. S2D3 is M. All are positive, so the solution is optimal and unique.
Real shipments: S1→D1 30 units, S2→D2 40 units, S3→D3 50 units. The dummy allocations (S1 keeps 20 units idle, S3 keeps 10 units idle) are not shipped.
Cost = 30 × 4 + 40 × 3 + 50 × 4 = 120 + 120 + 200 = ₹440.

Answer: Minimum cost is ₹440: S1→D1 30, S2→D2 40, S3→D3 50. S1 has 20 units and S3 has 10 units of unused capacity. This is the only optimal plan, since no empty cell has zero opportunity cost.

Example 2

A firm has three factories with 30, 40 and 30 units available and three customers needing 20, 50 and 30 units. Unit profit (₹): F1: 16, 12, 10; F2: 14, 15, 11; F3: 9, 13, 12. Find the allocation that maximises total profit.

Show the solution

Supply = demand = 100, so no dummy is needed. The objective is maximisation, so convert to loss by subtracting every entry from the largest profit, 16. Loss table: F1: 0, 4, 6; F2: 2, 1, 5; F3: 7, 3, 4.
Least Cost IBFS: F1C1 20 (cost 0); F2C2 40 (cost 1); F3C2 10 (cost 3); F3C3 20 (cost 4); F1C3 10 (cost 6). Occupied cells = 5 = 3 + 3 − 1, so no degeneracy at the start. Loss = 0 + 40 + 30 + 80 + 60 = 210.
MODI: u1 = 0, so v1 = 0 and v3 = 6. F3C3: u3 = −2. F3C2: v2 = 5. F2C2: u2 = −4.
Empty cells: F1C2 = 4 − (0 + 5) = −1; F2C1 = 2 − (−4 + 0) = 6; F2C3 = 5 − (−4 + 6) = 3; F3C1 = 7 − (−2 + 0) = 9. F1C2 is negative, so it enters.
Loop: F1C2 (+), F1C3 (−), F3C3 (+), F3C2 (−). The minus cells hold 10 and 10, so θ = 10. New: F1C2 10, F1C3 0, F3C3 30, F3C2 0. Two cells became zero together, so the solution is degenerate. Keep ε in F1C3 so there are 5 connected occupied cells.
Occupied: F1C1 20, F1C2 10, F2C2 40, F3C3 30, F1C3 ε. MODI: u1 = 0, v1 = 0, v2 = 4, v3 = 6; u2 = −3; u3 = −2.
Empty cells: F2C1 = 2 − (−3) = 5; F2C3 = 5 − (−3 + 6) = 2; F3C1 = 7 − (−2) = 9; F3C2 = 3 − (−2 + 4) = 1. All are positive, so the solution is optimal and unique.
Profit from the original table: 20 × 16 + 10 × 12 + 40 × 15 + 30 × 12 = 320 + 120 + 600 + 360 = ₹1,400. Check: 1,600 − loss 200 = 1,400.

Answer: Maximum profit is ₹1,400: F1→C1 20 units, F1→C2 10 units, F2→C2 40 units, F3→C3 30 units. The ε was only a technical device and carries no units.

Exam tips

In MCQs, the usual traps are the dummy cost (always 0), the cells needed (m + n − 1) and the maximisation conversion (subtract from the largest value in the table). Know these cold.
In written answers, show the balancing step, the M cell, the count of occupied cells against m + n − 1, and the u and v values. These are the step marks.
State clearly at the end which allocations are real, and compute cost or profit from the original table, not the converted one.
If the question asks about multiple optimal solutions, check for a zero Δ in an empty cell at the optimum and mention it explicitly.
If two minus cells in a loop reach zero together, show ε in one of them so the next MODI check is valid.

Practice questions from Transportation

Special Cases: Degeneracy, Unbalanced and Prohibited Routes in other exams

The same ground in other exams, if you are preparing for more than one or want another angle on it.

CMA FinalSpecial Cases: Degeneracy, Unbalanced and Maximization

Special Cases: Degeneracy, Unbalanced and Prohibited Routes: frequently asked questions

How do you resolve degeneracy in a transportation problem?

Count the occupied cells. If they are fewer than m + n − 1, add a very small quantity ε to an empty cell that does not form a closed loop with the occupied cells, so all u and v values can be found. Treat ε as an allocation in MODI and treat it as zero in the final answer.

What do you do in an unbalanced transportation problem?

Add a dummy destination if supply is greater than demand, or a dummy source if demand is greater than supply. Its quantity equals the difference and all its costs are zero. Then solve normally, and treat dummy allocations as unused capacity or unmet demand.

How do you handle a prohibited route in a transportation problem?

Assign that cell a very large cost M so it never enters the solution. Do not allocate to it in the initial solution. In a maximisation problem, convert profits to losses first and then put M in the prohibited cell.

How do you know there are multiple optimal solutions?

At the optimal MODI table, if any empty cell has an opportunity cost of zero, you can bring it into the solution without changing the total cost. That gives an alternate optimal solution with the same cost or profit.

Do you convert a maximisation problem back at the end?

You do not convert the allocation, since it is the same. You compute the total profit using the original profit figures for the occupied real cells.