Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 38 ยท Network Flows

The Transportation Problem

Solve the classic transportation problem: model supplies, demands and unit costs as an LP, build starting solutions with northwest corner and least cost, and handle unbalanced cases.

A company has several factories and several customers. Each factory can make a certain amount, each customer needs a certain amount, and moving one unit from factory i to customer j costs c_ij. How should shipments be planned to meet all demand at the lowest total cost? This is the transportation problem, one of the oldest and most widely used LP models. It is a special case of minimum-cost flow with only supply nodes and demand nodes and no intermediate points.

The model

Let x_ij be the quantity shipped from source i to destination j, s_i the supply and d_j the demand:

TEXT
minimize    sum_i sum_j c_ij x_ij
subject to  sum_j x_ij = s_i     (every source ships all it has)
            sum_i x_ij = d_j     (every destination receives its demand)
            x_ij >= 0

The problem is balanced when total supply equals total demand. It has m + n constraints (one redundant) and m * n variables, and a basic solution has at most m + n - 1 nonzero shipments. Because it is a network model, integer supplies and demands give integer shipments.

Python Solve a 3x4 transportation problem with linprog

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check the output: each row adds up to its supply and each column to its demand. At most 3 + 4 - 1 = 6 cells are nonzero.

Starting solutions

The classical transportation simplex method starts from a basic feasible solution and improves it. Two quick ways to build one:

  • Northwest corner rule. Start at the top-left cell, ship as much as possible (min(supply, demand)), cross out the exhausted row or column and move right or down. It ignores costs completely, so the start is usually poor but is always feasible.
  • Least-cost method. Repeatedly pick the cheapest remaining cell and ship as much as possible there. It uses costs and is usually much closer to optimal. (Vogel's approximation method goes further by looking at the penalty of not using the cheapest cell.)
Python Northwest corner versus least cost versus optimum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The northwest corner start is expensive, the least-cost start is close to the optimum, and the LP solver finds the true best. In practice you simply call an LP or network solver; the heuristics still matter for hand calculation and for seeding algorithms.

Optimality: the stepping-stone and MODI ideas

The transportation simplex method checks optimality using dual variables u_i (for sources) and v_j (for destinations). For every used cell u_i + v_j = c_ij. An unused cell has reduced cost c_ij - u_i - v_j. If all reduced costs are non-negative, the plan is optimal. A negative reduced cost means shipping along that cell would lower the cost, and a closed loop of increases and decreases (the "stepping stone" path) moves flow there. The dual variables are shadow prices: u_i is how much total cost changes if one more unit of supply were available at source i (with v_j playing the same role at destinations).

The dual variables are only determined up to a constant shift because one constraint is redundant. Fix one of them, usually u_1 = 0.

Unbalanced problems

If supply exceeds demand, add a dummy destination that absorbs the surplus at zero cost. If demand exceeds supply, add a dummy source. Costs from or to a dummy are 0 for a plain shortage or surplus, or a penalty if unmet demand has a real cost (lost sales, outsourcing).

Python Excess supply handled with a dummy destination

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last column is the surplus: which sources keep goods at home. Here source 1 keeps 30 units and source 2 keeps 10; the total cost is 240.

Extensions

  • Capacitated routes: add x_ij <= u_ij; still a network problem with integer answers.
  • Forbidden routes: give the cell a very large cost, or drop the variable.
  • Transshipment: shipments may pass through intermediate nodes; use the general min-cost flow model.
  • Multi-period or multi-product models: a transportation block per period or product; with shared capacities the structure is lost and fractional values may occur.
  • Degeneracy: fewer than m + n - 1 positive shipments; the simplex method handles it by keeping a zero-valued basic cell.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is a balanced transportation problem?

    Balanced means supply and demand totals match, so every unit can be shipped and every demand met exactly.
  2. 2. How is surplus supply handled?

    A dummy destination takes the unshipped amount; shipping to it costs zero or a holding penalty.
  3. 3. What is the maximum number of positive shipments in a basic solution with m sources and n destinations?

    There are m + n constraints but one is redundant, so a basic solution has m + n - 1 basic variables.
  4. 4. Which starting method uses cost information?

    The northwest corner rule only looks at positions; the least-cost and Vogel methods use the cost matrix.

Summary

  • The transportation problem ships goods from sources to destinations at minimum cost; supplies and demands are equalities in the balanced case.
  • It is a network LP, so integer data give integer shipments, and a basic solution has at most m + n - 1 positive cells.
  • Northwest corner and least-cost give starting solutions; MODI/stepping-stone uses dual variables to test optimality.
  • Unbalanced problems use a dummy destination or source.
  • In practice use an LP or network solver, and read the dual values as shadow prices.

Next: The Assignment Problem