Strategic Cost Management · Transportation

Degeneracy, Dummy Routes and Maximization in Transportation Problems

Updated 11 October 2026 · Fact-checked

These are the special cases of the transportation problem. Balance an unbalanced problem with a dummy row or column at zero cost. Give a prohibited route a very large cost M. Convert maximization to minimization using opportunity loss. If basic cells are fewer than m + n − 1, add a tiny ε to fix degeneracy.

Understand Special Cases: Degeneracy, Unbalanced and Maximization

The standard transportation method assumes three things: total supply equals total demand, every route is allowed, and the objective is to minimise cost. Exam questions often break one of these. Each special case has a simple fix that brings the problem back to the standard form.

Unbalanced problem. If supply is more than demand, add a dummy destination with demand equal to the excess. If demand is more than supply, add a dummy source with supply equal to the shortfall. Dummy cells normally carry zero cost, because nothing is actually shipped. Units sent to a dummy destination stay unused at the source. Units taken from a dummy source are demand that goes unmet. Always say this in your final answer.

Prohibited route. Sometimes a source cannot serve a destination because of a road, a legal bar or a contract. Give that cell a very large cost, written M. The method then avoids it. In the final answer, make sure no units sit in that cell.

Maximization. When the table shows profit or revenue per unit, you want the largest total. Subtract every entry from the largest entry in the table. The result is the opportunity loss table. Minimise on that table, then compute the real profit using the original figures. Dummy cells carry zero in the original table. After conversion they become the largest value minus zero, so convert the dummy cells too.

Degeneracy. A basic feasible solution needs exactly m + n − 1 occupied cells, where m is the number of sources and n the number of destinations. If fewer cells are occupied, the solution is degenerate. This usually happens when a row and a column are exhausted at the same time. MODI needs m + n − 1 occupied cells to find all u and v values, so you add a very small quantity ε (nearly zero) to an unoccupied cell. Choose a cell that does not form a closed loop with the occupied cells. Then continue normally and drop ε at the end.

Multiple optimal solutions. When the MODI test shows every Δ ≥ 0 and some unoccupied cell has Δ = 0, the solution is optimal but not unique. Bringing that cell in gives another plan with the same total cost or profit.

Key rules to remember

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.

How to solve Special Cases: Degeneracy, Unbalanced and Maximization questions

Use this order for any special-case transportation question. Fix the table first, then solve it in the usual way.

1Add total supply and total demand. If they differ, add a dummy row or column for the difference and fill it with zero cost (or the penalty given).
2If the question asks for maximum profit, subtract every entry (including dummy entries) from the largest entry to get the opportunity loss table.
3Put M in each prohibited cell. Remember to treat M as a very large number when ranking costs.
4Find an initial solution with North-West Corner, Least Cost or VAM. Count the occupied cells.
5If occupied cells are fewer than m + n − 1, add ε to an unoccupied cell that does not form a closed loop. A cheap cell in the same row or column as the isolated allocation is a sensible choice.
6Calculate u and v from occupied cells (set one u to 0), then find Δ for every unoccupied cell. Skip M cells.
7If any Δ is negative, trace the closed loop, shift the smallest unit quantity on the minus corners and repeat. Stop when all Δ ≥ 0.
8Write the plan, remove ε, and calculate the total cost or profit from the original table. State the unused stock or unmet demand shown by the dummy, and mention an alternate optimum if any Δ is zero.

Quickest way: Dummy-first, then check the count

When to use it: Use it when the table has unequal totals, a profit table or an M cell, and you have limited time.

Write the total supply and total demand at once. Add the dummy at this stage so you do not forget it.
For profit tables, build the loss table in one pass: largest value minus each cell. Dummy cells become the largest value.
Start with Least Cost or VAM. M cells are naturally left for last. In a cost-minimization table, zero-cost dummy cells are allotted early. In a converted profit table, dummy cells hold the largest loss and are left for last.
After the first allocation, count the occupied cells. If one is missing, put ε at once and note it.
Do MODI only once. If all Δ are non-negative, stop. Compute the total from the original figures.

Common mistakes in Special Cases: Degeneracy, Unbalanced and Maximization

Putting a high cost instead of zero in the dummy row or column.
Students treat the dummy like a real route and think it must be expensive.
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.
The dummy row or column is added after the conversion, or ignored during it.
Fix: Balance first, then convert every cell, including dummies, to opportunity loss. Finally report profit from the original table.
Reporting the loss table total as the maximum profit.
The solving ends on the converted table and the student forgets to go back.
Fix: Multiply the final allocations with the original unit profits and add.
Ignoring degeneracy and running MODI with fewer than m + n − 1 cells.
u and v cannot all be found, so the student gets stuck or guesses.
Fix: Count occupied cells after the initial solution. Add ε to an unoccupied cell that forms no closed loop, and remove it at the end.
Leaving units in a prohibited cell or computing Δ for it.
The M cell looks cheap during the NWC method, which ignores costs.
Fix: With NWC, if the next cell is an M cell, skip it. Prefer Least Cost or VAM. Never allocate in an M cell, and skip it when testing Δ.
Declaring the solution unique without looking for zero Δ.
Students stop at 'all Δ ≥ 0'.
Fix: Check unoccupied cells for Δ = 0. If one exists, state that an alternate optimal solution exists with the same total.

Worked examples

Example 1

A firm has two plants, A (supply 40 units) and B (supply 30 units). Three markets need X 20, Y 35 and Z 25 units. Profit per unit (₹): A to X 12, Y 10, Z 8; B to X 9, Y 14, Z 11. Find the allocation that maximises total profit and state any unmet demand.

Show the solution

Total supply = 40 + 30 = 70. Total demand = 20 + 35 + 25 = 80. Add a dummy plant D with supply 10 and profit 0 in every cell.
Largest profit is 14. Opportunity loss: A = 2, 4, 6; B = 5, 0, 3; D = 14, 14, 14.
Least cost method: B–Y has loss 0, so allot 30 (B exhausted). A–X loss 2: allot 20 (X met). A–Y loss 4: allot 5 (Y met, needs 35 in total). A–Z loss 6: allot 15 (A exhausted). D–Z: allot 10.
Occupied cells = 5 = m + n − 1 = 3 + 3 − 1, so there is no degeneracy.
MODI: u(A) = 0, so v(X) = 2, v(Y) = 4, v(Z) = 6. From B–Y: u(B) = −4. From D–Z: u(D) = 8.
Δ for unoccupied cells: B–X = 5 − (−4 + 2) = 7; B–Z = 3 − (−4 + 6) = 1; D–X = 14 − (8 + 2) = 4; D–Y = 14 − (8 + 4) = 2. All are positive, so the solution is optimal and unique.
Profit from the original table: A–X 20 × 12 = 240; A–Y 5 × 10 = 50; A–Z 15 × 8 = 120; B–Y 30 × 14 = 420. Total = 240 + 50 + 120 + 420 = 830.

Answer: Send A: 20 to X, 5 to Y, 15 to Z. Send B: 30 to Y. Maximum profit = ₹830. Market Z receives only 15 from A and 10 from the dummy, so its demand is short by 10 units.

Example 2

Three warehouses S1, S2, S3 hold 20, 30 and 25 units. Three shops D1, D2, D3 need 20, 35 and 20 units. Unit transport cost (₹): S1 to D1 4, D2 6, D3 3; S2 to D1 5, D2 3, D3 7; S3 to D1 6, D2 5, D3 not possible (road closed). Find the minimum cost plan.

Show the solution

Total supply = 75 = total demand, so the problem is balanced. Put M in S3–D3.
Least cost method: S2–D2 (cost 3): allot 30. S2 is exhausted and D2 still needs 5. S1–D3 (cost 3): allot 20. S1 and D3 are both exhausted at once.
Remaining: S3 has 25; D1 needs 20 and D2 needs 5. S3–D1 (6): allot 20. S3–D2 (5): allot 5.
Occupied cells = 4, but m + n − 1 = 5. The solution is degenerate, because S1–D3 sits alone in its row and column.
Add ε to S1–D1 (cost 4). It joins S1–D3 to S3–D1 without forming a loop. Occupied cells are now S1–D1 (ε), S1–D3, S2–D2, S3–D1, S3–D2.
MODI: u(S1) = 0, so v(D1) = 4 and v(D3) = 3. From S3–D1: u(S3) = 2. From S3–D2: v(D2) = 3. From S2–D2: u(S2) = 0.
Δ: S1–D2 = 6 − (0 + 3) = 3; S2–D1 = 5 − (0 + 4) = 1; S2–D3 = 7 − (0 + 3) = 4. S3–D3 is prohibited and is not tested. All Δ > 0, so the plan is optimal and unique.
Cost = 20 × 3 + 30 × 3 + 20 × 6 + 5 × 5 = 60 + 90 + 120 + 25 = 295. ε adds nothing.

Answer: S1 sends 20 to D3; S2 sends 30 to D2; S3 sends 20 to D1 and 5 to D2. Minimum total cost = ₹295. No units use the closed S3–D3 road.

Exam tips

Write the total supply and demand first. A one-line check shows whether a dummy is needed and saves a full wrong solution.
Say what the dummy means in words. Units to a dummy destination are unused stock. Units from a dummy source are unmet demand. Examiners give marks for this interpretation.
For maximization, show the loss table separately and give the final profit from the original table. Both steps carry marks.
Show the count of occupied cells against m + n − 1 in one line. It proves you checked for degeneracy.
If a Δ is zero in an unoccupied cell, mention the alternate optimum. Case-based MCQs often test this exact point.

Practice questions from Transportation

Special Cases: Degeneracy, Unbalanced and Maximization in other exams

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

CMA IntermediateSpecial Cases: Degeneracy, Unbalanced and Prohibited Routes

Special Cases: Degeneracy, Unbalanced and Maximization: frequently asked questions

How do you resolve degeneracy in a transportation problem?

Count the occupied cells. If there are fewer than m + n − 1, add a very small quantity ε to an unoccupied cell that forms no closed loop with the occupied cells. Solve with MODI as usual. At the end, treat ε as zero.

What is a dummy row or column and what cost does it carry?

It is an imaginary source or destination added to balance total supply and demand. Its cost is zero unless the question gives a shortage or storage penalty. Allocations to it are not real shipments.

How do you solve a transportation problem for maximum profit?

Subtract every cell from the largest profit in the table to get the opportunity loss table, including any dummy cells. Minimise on that table. Then find total profit using the original unit profits.

How do you handle a prohibited route?

Put a very large cost M in that cell so that the method never allocates there. Do not test it during MODI. Confirm that the final plan has no units in it.

How do you know if a transportation problem has multiple optimal solutions?

After the optimality test, if all Δ ≥ 0 and at least one unoccupied cell has Δ = 0, the solution is optimal but not unique. Allotting units to that cell gives another plan with the same total cost or profit.