Operations Research

Transportation Problem: Northwest Corner, Least Cost and Vogel

Operations Research Study guides

The transportation problem ships goods from sources to destinations at minimum cost. Learn balancing, the three starting methods and how to check optimality.

The transportation problem has m sources with supplies and n destinations with demands, and a cost per unit for each route. The goal is to choose how much to ship on each route so that all supplies and demands are met at minimum total cost. The problem must be balanced: total supply equals total demand. If supply is larger, add a dummy destination with zero costs; if demand is larger, add a dummy source.

Three methods give an initial basic feasible solution. The northwest corner method starts at the top-left cell and allocates as much as possible, then moves right or down, ignoring costs, so it is quick but usually far from optimal. The least cost method allocates first to the cheapest cell, then the next cheapest, and gives a better start. Vogel approximation method computes for each row and column the penalty (difference between the two smallest costs), allocates in the row or column with the biggest penalty at its cheapest cell, and usually gives the best starting solution.

A basic feasible solution has m + n - 1 allocated cells. If fewer, the solution is degenerate and you add a zero allocation. To test optimality use the MODI (u-v) method: set u1 = 0, find u and v from the allocated cells (ui + vj = cij), then compute the opportunity cost cij - ui - vj for each empty cell. If all are non-negative, the solution is optimal; otherwise the most negative cell enters and you re-allocate around a closed loop.

Key points

  • Balance the problem with a dummy source or destination.
  • Northwest corner ignores cost. Least cost and Vogel use cost.
  • Vogel uses row and column penalties and is usually closest to optimal.
  • Basic solution has m + n - 1 allocations.
  • MODI: optimal when all cij - ui - vj are non-negative.

Worked example

Two sources with supplies 20 and 30, and two destinations with demands 25 and 25. Costs: S1 to D1 = 4, S1 to D2 = 6, S2 to D1 = 5, S2 to D2 = 3. Total supply 50 equals total demand 50, so it is balanced. Northwest corner: S1 to D1 = 20, then S2 to D1 = 5, S2 to D2 = 25. Cost = 20 x 4 + 5 x 5 + 25 x 3 = 80 + 25 + 75 = 180. There are 3 allocations, which equals m + n - 1 = 3.

Common questions

What if supply does not equal demand?

Add a dummy destination or source with zero cost to balance it.

Which initial method gives the best start?

Usually the Vogel approximation method.

Related topics

BASMAGLY is an independent student project, not an official Delta University site. Check lectures and your instructor for the final word.