The Transportation Model

Shipping a single commodity from supply points to demand points at least cost. The model has one structural requirement, total supply must equal total demand, and two readings, a cost table and a bipartite network, which answer different questions about the same program.

Definition

A transportation problem ships one commodity from $m$ supply points to $n$ demand points. Supply point $i$ has $s_{i}$ units available, demand point $j$ requires $d_{j}$ units, and shipping one unit from $i$ to $j$ costs $c_{i j}$ . The decision variable $x_{i j}$ is the number of units sent from $i$ to $j$ :

min \sum_{i = 1}^{m} \sum_{j = 1}^{n} c_{i j} x_{i j} subject to \begin{aligned} \sum_{j = 1}^{n} x_{i j} & = s_{i} & i = 1, \dots, m, \\ \sum_{i = 1}^{m} x_{i j} & = d_{j} & j = 1, \dots, n, \\ x_{i j} & \geq 0 . \end{aligned}

The first family of constraints says each supply point ships out exactly what it has; the second says each demand point receives exactly what it needs.

The balance condition. Written with equalities, the model is feasible only when

\sum_{i = 1}^{m} s_{i} = \sum_{j = 1}^{n} d_{j} .

Summing the supply equations gives the total shipped; summing the demand equations gives the same total. If the two sides disagree, no $x$ satisfies both families at once, and the program is infeasible for a structural reason rather than an arithmetic one.

An unbalanced situation is modelled by restoring balance explicitly. Surplus supply adds a dummy demand point with $d_{n + 1} = \sum_{i} s_{i} - \sum_{j} d_{j}$ and zero shipping costs; the units assigned to it are the ones that stay where they are. Surplus demand adds a dummy supply point whose shipments represent unmet demand, and its costs are the penalties for that shortfall, zero only if going unserved is genuinely free.

Structural properties. The constraint matrix has one $+ 1$ per column in a supply row and one $+ 1$ in a demand row, and is totally unimodular. With integer supplies and demands every basic feasible solution is integral, so the linear program returns whole units without any integrality constraint being imposed. Exactly one of the $m + n$ equality constraints is redundant, given balance, so a basis contains $m + n - 1$ variables rather than $m + n$ .

Assumptions and scope

One commodity, and units are interchangeable. A problem shipping several products that compete for the same vehicles is not this model; it needs capacity constraints linking the products.
Costs are linear in quantity. A haulier's bulk discount, a fixed charge for opening a route, or a per-vehicle cost makes the objective nonlinear or the model an integer program.
Supply and demand are certain and known before shipping. Uncertain demand is a different model, and solving the deterministic problem with expected values does not give the plan that minimises expected cost.
Balance is required by the equality form. A situation that is genuinely unbalanced must be balanced with a dummy row or column before the model applies, and the dummy's costs are a modelling decision.
Integrality comes from total unimodularity together with integer data. With fractional supplies the optimum need not be integral, and the property guarantees nothing about a problem whose structure has been altered by adding, say, a route capacity.

Forms this is expressed in

The same content in several forms. Each makes something visible that the others leave implicit, so moving between them is part of understanding the topic rather than a presentation choice.

tabular

An $m \times n$ grid with supply points as rows and demand points as columns. Cell $(i, j)$ carries the unit cost $c_{i j}$ ; the right margin carries the supplies $s_{i}$ and the bottom margin the demands $d_{j}$ . A shipping plan is the same grid filled with quantities $x_{i j}$ , and it is feasible when every row sums to its supply and every column to its demand.

This reading answers questions about quantities and their consistency. Balance is the comparison of the two margin totals, visible without any calculation on the interior. Checking a proposed plan is $m + n$ additions. Comparing the cost of two plans is reading the same cells twice.

It is also the form the transportation simplex works in: a basis is a set of $m + n - 1$ filled cells, and an improving step adds one cell and traces a closed loop through filled cells to rebalance the rows and columns it disturbs.

What the table does not expose is why an optimal plan has the shape it does. Five filled cells in a nine-cell grid appear to be an arbitrary selection, and nothing in the layout says which sets of cells can be a basis and which cannot.

Translates into: diagrammatic

diagrammatic

Depots, shops, and the nine routes between them

A bipartite graph with supply points as left nodes and demand points as right nodes. Each node carries a quantity: left node $i$ emits $s_{i}$ , right node $j$ absorbs $d_{j}$ . Each arc $(i, j)$ carries a unit cost $c_{i j}$ and a flow $x_{i j}$ , and the constraints say that flow out of each left node equals its supply and flow into each right node equals its demand.

This reading answers questions about structure. A basis is $m + n - 1$ arcs forming a spanning tree of the bipartite graph, which is what makes an optimal plan sparse and explains why the count is $m + n - 1$ rather than $m + n$ : a spanning tree on $m + n$ nodes has one fewer edge than nodes. Adding a nonbasic arc creates exactly one cycle, and that cycle is the closed loop the table form traces without explaining.

It is also the reading that generalises. Transshipment through intermediate points adds middle nodes; capacities on routes become arc capacities; a network with several sources and sinks is the same object. Each is a natural change to a graph, and none has a natural place in the table.

What the network does not give is a compact view of the cost data. Comparing routes means reading arc labels one at a time, and the balance check is a sum over node labels rather than a comparison of two margin totals.

Translates into: tabular

Worked material

Contrast

Transportation against a general linear program

The transportation model is a linear program, and the differences are all consequences of its constraint structure.

	Transportation model	General linear program
Feasibility	decided before solving, by comparing two totals	discovered by solving, or by a phase-one procedure
Integral optimum	guaranteed with integer supplies and demands	not guaranteed; needs an integer program
Basis size	$m + n - 1$ , always	the number of constraints, and a basis may be degenerate
Basis structure	a spanning tree of the bipartite graph	any independent column set
Specialised method	transportation simplex, working on the table	general simplex on the tableau

When the model stops applying. A shipping situation fails to be a transportation problem when a cost is not per-unit, when several commodities compete for shared capacity, or when the decision is which routes to open rather than how much to send. Each breaks a different requirement: linearity of the objective, the two-nonzeros column structure, and the continuity of the variable.

What survives being a special case. Everything true of linear programs remains true here. The optimum sits at an extreme point, the simplex method solves it, and duality applies. The dual variables are interpretable as the value of a unit of supply at each depot and a unit of demand at each shop. Nothing about the special structure suspends the general theory; it adds guarantees on top of it.

Why it is worth recognising the shape. Two reasons, and the first is not efficiency. Recognising the model tells you to check balance, which catches a data problem before a solver reports infeasibility with no explanation. The second is that it tells you the answer will be in whole units, so a fractional result signals an error in the data or the formulation rather than a need to round.

Common errors

Common misconception

When total supply and total demand differ, the transportation model still applies as written, and the solver will distribute what it can; the imbalance is a property of the data rather than something the model must be changed to represent.

Common misconception

Filling the cheapest available cell as fully as possible, then the next cheapest, and so on, produces the minimum-cost shipping plan, because every unit was placed on the cheapest route open to it.

The Transportation Model

Assumptions and scope

Forms this is expressed in

Worked material

Transportation against a general linear program

Common errors

Related units

Requires

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history