Transportation Problem for GATE MA: Start With VAM, Check Degeneracy
A transportation problem asks for the cheapest way to ship supply to demand. For GATE Mathematics, start with Vogel's method, count occupied cells against m+n−1, then test with the modified distribution method.
By Sunil Bansal, Founder · Updated 7 Nov 2026
Key takeaways
- Unless the question names a starting method, start every GATE Mathematics transportation problem with Vogel's approximation method (VAM), then test the result with the modified distribution method (MODI) before you trust it.
- Count occupied cells against m+n−1 (rows plus columns minus one) before computing anything. Fewer cells means the grid is degenerate, and ε goes only in an empty cell that forms no closed loop with the occupied cells.
- In our test of 5,000 random 3×4 problems, VAM ended optimal 76.3% of the time, least cost 42.2% and north-west corner 4.9%, so no starting solution is the answer by itself.
- VAM gives each row and column a penalty, the gap between its two smallest costs. It fills the cheapest cell in the line with the largest penalty, which is why it beats methods that look at one cost at a time.
In this article
- 1What is the transportation problem, and where does GATE Mathematics test it?
- 2What seven checks solve a transportation problem without stalling?
- 3Which starting method should you use: north-west corner, least cost or VAM?
- 4How does one grid go from VAM's starting cost of 779 to the optimal 743?
- 5What makes a transportation grid degenerate, and where does ε go?
- 6How do we help GATE candidates with linear programming?
- 7Frequently asked questions
Three methods can build a starting solution, and the choice decides how much work is left. On random cost grids they finish far apart, and every method gets worse as the grid grows: north-west corner is optimal on 11.2% of 3×3 grids and 0.1% of 5×6 grids.
For a GATE (Graduate Aptitude Test in Engineering) Mathematics candidate the choice matters because the topic is named in the syllabus, together with the optimality test that follows it. The usual way to lose time is not the arithmetic. It is reaching the test with too few occupied cells, so the test values cannot be solved.
This page gives a seven-check routine with a pass or fail result at each step, a worked grid with every number shown, and the results of a test we ran on thousands of random problems to compare the starting methods. Everything here is meant to be worked with pen and paper in the time an exam allows.
What is the transportation problem, and where does GATE Mathematics test it?
A transportation problem is a linear programming problem that decides how many units to ship from each source to each destination at the lowest total cost, with every supply used and every demand met exactly. In GATE Mathematics it sits in Section 11, Linear Programming.
In symbols: minimise Z = Σ c_ij x_ij, subject to Σ_j x_ij = a_i for each source i, Σ_i x_ij = b_j for each destination j, and x_ij ≥ 0. The problem is balanced when total supply Σ a_i equals total demand Σ b_j.
The GATE 2027 Mathematics syllabus from IIT Madras reads: "Balanced and unbalanced transportation problems, Initial basic feasible solution of balanced transportation problems (least cost method, north-west corner rule, Vogel's approximation method); Optimal solution, modified distribution method; Solving assignment problems, Hungarian method." The full topic list is in our GATE MA Syllabus 2027 page. The transportation problem is a special linear programme, and MODI is the simplex method specialised to the grid, which makes it far quicker by hand.
CSIR NET (Council of Scientific and Industrial Research National Eligibility Test) is different. The CSIR common syllabus for Mathematical Sciences (file dated November 2018) lists "Linear programming problem, simplex methods, duality" with queuing and inventory models, in the final unit. That is the unit statistics candidates answer, while mathematics candidates are directed to Units I to III. Transportation problems are not named there. Confirm against the notification for your exam cycle.
What seven checks solve a transportation problem without stalling?
Seven checks, in this order, take a raw cost table to a proven minimum cost. Each has a pass condition and a fixed action when it fails. Here m is the number of sources (rows) and n the number of destinations (columns).
u_i and v_j are the row and column multipliers (potentials) that MODI solves for, one per row and column. A reduced cost is the change in total cost per unit moved into an empty cell, so a negative one means moving units there makes the plan cheaper. A closed loop is a path of alternating horizontal and vertical steps that starts and ends at one cell and turns only at occupied cells.
| # | Check | Pass | If it fails |
|---|---|---|---|
| 1 | Total supply equals total demand | Equal | Add a dummy destination (supply larger) or a dummy source (demand larger) with all costs 0 |
| 2 | Starting solution (use VAM) | Every row total equals its supply and every column total its demand | Redo; you left a row or column unfinished |
| 3 | Occupied cells equal m+n−1 | Exactly m+n−1 | Fewer: degenerate. Add ε to one empty cell (see below) |
| 4 | Solve u and v: set u₁ = 0, then c_ij = u_i + v_j on every occupied cell | Every u and v found | Not all found: recount check 3, and look for a closed loop among the occupied cells |
| 5 | Reduced cost c_ij − u_i − v_j for every empty cell | All ≥ 0, so the cost is minimal | Any negative: the cell with the most negative value enters |
| 6 | Closed loop through the entering cell, alternating + and −. θ is the smallest allocation on a − cell | Every row and column total unchanged after the shift | A total changed: the loop is wrong; redraw it |
| 7 | Cost update | New cost = old cost + (reduced cost × θ), and equals Σ c·x | The two disagree: recompute the grid |
Repeat checks 3 to 7 until check 5 passes.
Which starting method should you use: north-west corner, least cost or VAM?
Use VAM. It ended on the exact optimum far more often than the other two in every setting we tested, and where it missed, it missed by the least.
The three methods differ in what they look at:
- North-west corner ignores cost and fills from the top-left cell.
- Least cost fills the cheapest cell first.
- Vogel's approximation method (VAM) computes, for each row and column, the penalty (the gap between its two smallest costs), takes the largest penalty, and fills the cheapest cell in that row or column.
If the question names a method, use that one and report its cost.
Our test. In November 2026 we generated random balanced problems, solved each with all three methods, and compared every start with the exact optimum from a linear-programming solver (SciPy's HiGHS). Ties between equal VAM penalties went to the earliest row, then the earliest column; equal costs and ties in the other methods went to the first minimum in row order. "Optimal" means the starting cost equalled the exact optimum.
| Grid and costs (problems) | North-west corner | Least cost | VAM |
|---|---|---|---|
| 3×3, costs 1–20 (2,000) | 11.2% optimal; 26.3% above optimum | 54.4%; 3.6% | 84.5%; 0.7% |
| 3×4, costs 1–20 (5,000) | 4.9%; 33.0% | 42.2%; 4.9% | 76.3%; 1.2% |
| 3×4, costs 1–50 (2,000) | 4.0%; 35.9% | 39.7%; 5.3% | 75.1%; 1.1% |
| 4×5, costs 1–20 (2,000) | 0.8%; 48.9% | 20.1%; 6.8% | 49.4%; 2.5% |
| 5×6, costs 1–30 (2,000) | 0.1%; 65.8% | 8.4%; 9.5% | 27.4%; 4.2% |
Each cell shows the share of problems ending optimal, then the average percentage by which the starting cost exceeds the optimum. The percentages move a little with the cost range and the tie rule, but the order never changed in any of the five settings. These are random grids, not exam questions.
Our reading: VAM is the right start, but on a 4×5 grid it is optimal in under half the cases. The optimality test is not optional, and on exam-sized grids you should expect to run it.
How does one grid go from VAM's starting cost of 779 to the optimal 743?
VAM gives 779; one MODI step drops it by 36 to 743; north-west corner (1,015) and least cost (814) start higher. We worked this grid in November 2026 and confirmed 743 against the exact solver.
| Source | D1 | D2 | D3 | D4 | Supply |
|---|---|---|---|---|---|
| S1 | 19 | 30 | 50 | 10 | 7 |
| S2 | 70 | 30 | 40 | 60 | 9 |
| S3 | 40 | 8 | 70 | 20 | 18 |
| Demand | 5 | 8 | 7 | 14 | 34 |
Supply and demand both total 34, so check 1 passes.
Starting costs. North-west corner gives 5·19 + 2·30 + 6·30 + 3·40 + 4·70 + 14·20 = 1,015. Least cost gives 814. VAM gives 779.
VAM steps.
- Column 2 has the largest penalty (30 − 8 = 22), so S3 sends 8 to D2.
- Column 1 has penalty 21, so S1 sends 5 to D1.
- Row 3 has penalty 50 (70 − 20), so S3 sends its remaining 10 to D4.
- Column 4 has penalty 50, so S1 sends its last 2 to D4.
- Row 2 takes what is left: 7 to D3 and 2 to D4.
That is 6 occupied cells, and m+n−1 = 3+4−1 = 6, so check 3 passes. The cost is 95 + 20 + 280 + 120 + 64 + 200 = 779.
MODI. With u₁ = 0 the occupied cells give u = (0, 50, 10) and v = (19, −2, −10, 10). The reduced costs of the empty cells are (1,2) = 32, (1,3) = 60, (2,1) = 1, (2,2) = −18, (3,1) = 11 and (3,3) = 70. Only (2,2) is negative.
Loop. The loop runs (2,2)+ → (2,4)− → (3,4)+ → (3,2)−. The − cells hold 2 and 8, so θ = 2. The new cost is 779 + (−18 × 2) = 743, and the shifted grid costs 95 + 20 + 280 + 60 + 240 + 48 = 743.
What makes a transportation grid degenerate, and where does ε go?
A grid is degenerate when it has fewer than m+n−1 occupied cells, and MODI cannot then solve for every u and v. The fix is to add ε, an allocation so small it changes no cost, to an empty cell that forms no closed loop with the occupied cells.
The count is m+n−1 rather than m+n because the m+n supply and demand equations carry one redundant equation when the problem is balanced. A degenerate start appears when a partial sum of supplies equals a partial sum of demands, which exhausts a row and a column at the same step.
A small case: supplies 20 and 30, demands 20 and 30. The north-west corner puts 20 in (1,1) and 30 in (2,2), which is 2 occupied cells where 3 are needed. Both empty cells, (1,2) and (2,1), are loop-free, so ε goes in whichever costs less.
A common shortcut, placing ε in the cheapest empty cell, fails when that cell completes a closed loop with occupied cells. Occupied cells that contain a loop leave u and v undetermined. Try cells from cheapest upward and take the first that forms no loop.
In our 3×4 test (costs 1–20, 5,000 problems), 8.7% (north-west corner), 8.8% (least cost) and 9.4% (VAM) of starting solutions were degenerate, meaning they had fewer than m+n−1 positive allocations. So about one random 3×4 grid in eleven needed ε.
How do we help GATE candidates with linear programming?
Our CSIR-NET and GATE Mathematics 2027 course lists Linear Programming among its subjects, alongside Linear Algebra, Abstract Algebra, Real Analysis, Complex Analysis, Ordinary Differential Equations, Partial Differential Equations and Numerical Analysis. It is taught in Hindi and English.
The course includes live classes with recorded access, handwritten notes and PDFs, chapter-wise assignments, previous-year-question discussion, full-length mock tests with analytics, and weekly doubt sessions or personal mentoring. As of November 2026 it costs ₹15,999 one-time, or four instalments of ₹3,999.75 (₹15,999 in total), and access runs through 30 June 2027.
Our advice for this topic: work the Section 11 questions in our GATE Mathematics previous-year papers with the seven checks above, and write the occupied-cell count next to each grid before you start MODI.
Our digital products carry a no-refund policy. If transportation problems are why you are considering the course, ask us which topics you need covered before you pay. Support details: sbtechmath@gmail.com, +91 81265 45455 (9am to 7pm, Monday to Saturday), or our contact form, which we answer within 24 hours.
Prepare for GATE Mathematics 2027 with SBTech Math
Frequently asked questions
Sources
- 1.GATE 2027 Mathematics (MA) syllabus, Section 11, Linear Programming, IIT Madras
- 2.CSIR-UGC NET common syllabus for Parts B and C, Mathematical Sciences (file dated November 2018), CSIR Human Resource Development Group
- 3.Introduction to Operations Research, transportation simplex method chapter, for the basis and degeneracy rules, Hillier, F. S. and Lieberman, G. J.
- 4.Operations Research: An Introduction, transportation model chapter, for the basis and degeneracy rules, Taha, H. A.
- 5.CSIR-NET and GATE Mathematics 2027 course page, for subjects, features, price and access as of November 2026, SBTech Math
- 6.Our own calculations, November 2026: the starting-method comparison, the degeneracy rates and the worked grid, computed in Python against the exact optimum from SciPy's HiGHS linear-programming solver. Costs are uniform random integers over the stated range. Supplies and demands are random positive splits of a common total (40 to 100 for the 3×4, costs 1–20 run of 5,000 with seed 2026; 60 to 150 for the four 2,000-problem settings with seed 7). VAM penalty ties go to the earliest row, then the earliest column; other ties go to the first minimum in row order.
