Transportation Problem: North-West Corner, Least Cost, VAM and MODI Method (Solved Example)
Opublikowano October 16, 2026 · autor Simplex Method Calculator Editorial Team
The transportation problem asks how to ship goods from several sources to several destinations at the lowest total cost. It is a linear program, but its special structure allows a much faster method than the general simplex tableau: find a good starting plan, then improve it with the MODI (u-v) method, which is the simplex optimality test written for a cost table.
This guide solves one problem completely. It compares the three standard starting methods (North-West Corner, Least Cost and Vogel’s Approximation Method) and then uses MODI to reach the optimal plan.
The Problem
Three factories (S1, S2, S3) supply four warehouses (D1 to D4). The table shows the cost of shipping one unit on each route, the supply of each factory and the demand of each warehouse.
| 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 |
Total supply (7 + 9 + 18 = 34) equals total demand (5 + 8 + 7 + 14 = 34), so the problem is balanced. If it were not, you would add a dummy source or dummy destination with zero costs to absorb the difference.
A basic feasible solution has at most m + n − 1 = 3 + 4 − 1 = 6 occupied cells.
Method 1: North-West Corner Rule
Start in the top-left cell and allocate as much as possible, then move right when a column’s demand is met or down when a row’s supply is used up.
- S1D1 = 5 (D1 met), S1D2 = 2 (S1 used up)
- S2D2 = 6 (D2 met), S2D3 = 3 (S2 used up)
- S3D3 = 4 (D3 met), S3D4 = 14 (done)
Cost = 5(19) + 2(30) + 6(30) + 3(40) + 4(70) + 14(20) = 1,015
The North-West Corner rule ignores costs completely, so its starting plan is usually expensive.
Method 2: Least Cost Method
Allocate to the cheapest remaining cell each time.
- Cheapest cell S3D2 (8): allocate 8 (D2 met)
- Next S1D4 (10): allocate 7 (S1 used up)
- Next S3D4 (20): allocate 7 (D4 met)
- Next S3D1 (40): allocate 3 (S3 used up)
- Next S2D3 (40): allocate 7 (D3 met)
- Last S2D1 (70): allocate 2 (done)
Cost = 8(8) + 7(10) + 7(20) + 3(40) + 7(40) + 2(70) = 814
Method 3: Vogel’s Approximation Method (VAM)
For every row and column, the penalty is the difference between its two smallest remaining costs. Pick the row or column with the largest penalty and allocate to its cheapest cell. Then recompute the penalties for what is left.
| Step | Largest penalty | Allocation |
|---|---|---|
| 1 | Column D2: 30 − 8 = 22 | S3D2 = 8 (D2 met) |
| 2 | Column D1: 40 − 19 = 21 | S1D1 = 5 (D1 met) |
| 3 | Row S3: 70 − 20 = 50 | S3D4 = 10 (S3 used up) |
| 4 | Column D4: 60 − 10 = 50 | S1D4 = 2 (S1 used up) |
| 5 | Only S2 remains | S2D3 = 7, S2D4 = 2 |
In step 3, columns D1 and D2 are already full, so the only remaining costs in row S3 are 70 (D3) and 20 (D4). Its penalty of 50 is the largest at that point.
VAM plan: S1D1 = 5, S1D4 = 2, S2D3 = 7, S2D4 = 2, S3D2 = 8, S3D4 = 10.
Cost = 5(19) + 2(10) + 7(40) + 2(60) + 8(8) + 10(20) = 779
| Method | Starting cost |
|---|---|
| North-West Corner | 1,015 |
| Least Cost | 814 |
| Vogel’s Approximation | 779 |
VAM gives the best start because penalties measure what you lose by not using the cheapest route.
The MODI Method (u-v Method)
MODI tests whether a plan is optimal and shows how to improve it.
- Give each row a number u_i and each column a number v_j so that u_i + v_j = cost for every occupied cell. Set u1 = 0 to start.
- For every empty cell, compute the opportunity cost d_ij = cost − (u_i + v_j).
- If every d_ij ≥ 0, the plan is optimal. Otherwise the most negative cell enters.
MODI on the VAM Plan
Occupied cells give: u1 = 0, v1 = 19, v4 = 10; from S2D4, u2 = 60 − 10 = 50; from S2D3, v3 = 40 − 50 = −10; from S3D4, u3 = 20 − 10 = 10; from S3D2, v2 = 8 − 10 = −2.
| Empty cell | Cost − (u + v) | d_ij |
|---|---|---|
| S1D2 | 30 − (0 − 2) | 32 |
| S1D3 | 50 − (0 − 10) | 60 |
| S2D1 | 70 − (50 + 19) | 1 |
| S2D2 | 30 − (50 − 2) | −18 |
| S3D1 | 40 − (10 + 19) | 11 |
| S3D3 | 70 − (10 − 10) | 70 |
S2D2 is negative, so shipping on that route would save 18 per unit. It enters.
Improving the Plan
Form a closed loop that starts at S2D2 and turns only at occupied cells: S2D2 (+) → S2D4 (−) → S3D4 (+) → S3D2 (−) and back. The amount moved, θ, is the smallest allocation in a (−) cell: min(S2D4 = 2, S3D2 = 8) = 2.
New plan: S2D2 = 2, S2D4 = 0 (leaves), S3D4 = 12, S3D2 = 6. The cost falls by 18 × 2 = 36, from 779 to 743.
Optimality Check
With the new plan, u1 = 0, v1 = 19, v4 = 10, u3 = 10, v2 = −2, u2 = 30 − (−2) = 32, v3 = 40 − 32 = 8. The opportunity costs of the empty cells are S1D2 = 32, S1D3 = 42, S2D1 = 19, S2D4 = 18, S3D1 = 11 and S3D3 = 52. All are positive, so the plan is optimal.
Optimal Solution
| D1 | D2 | D3 | D4 | Supply | |
|---|---|---|---|---|---|
| S1 | 5 | 2 | 7 | ||
| S2 | 2 | 7 | 9 | ||
| S3 | 6 | 12 | 18 | ||
| Demand | 5 | 8 | 7 | 14 |
Minimum total cost = 5(19) + 2(10) + 2(30) + 7(40) + 6(8) + 12(20) = 743
Common Mistakes
- Not checking balance. An unbalanced problem needs a dummy row or column before you start.
- Wrong number of occupied cells. A basic solution needs m + n − 1 occupied cells. If a step meets a row and a column at the same time, you get fewer (degeneracy); place a zero allocation in a suitable cell to keep the count.
- Loops that turn at empty cells. The improvement loop may only turn at occupied cells.
- Stopping after VAM. VAM is often close to optimal but not always, as this example shows (779 vs 743). Always run the MODI test.
Solving It as a Linear Program
The same problem can be written as a linear program with 12 variables (one per route), 3 supply constraints and 4 demand constraints, and solved with the simplex method. The transportation simplex method calculator accepts the problem in that form. For a 3 × 4 problem that means typing 12 variables, so the table methods above are faster by hand, but the calculator is a useful way to confirm the minimum cost of 743.