The Transportation Model

Three warehouses hold stock. Three shops need it. Every warehouse-shop pair has a known cost per unit. The question is which routes to use and how much to send on each.

This is a linear program, and writing it as one is straightforward. What makes the model worth naming is that its structure settles two things a general linear program leaves open: whether the data admits any solution at all, and whether the answer comes back in whole units.

The first is a condition on the numbers before any solving begins. The second is a property of the constraint matrix that removes the need for integer programming. A guarantee with precise limits, which are part of what there is to learn here.

Beyond the program itself, what is worth fixing is what each index ranges over and what one variable counts.

The variable. $x_{ij}$ is a quantity of the commodity, in the units the supplies and demands are stated in, moving from supply point $i$ to demand point $j$ over the planning period. It is not a decision about whether to use route $(i,j)$, that would be a binary variable and a different model. A route is used when , which is a reading of the answer rather than something the model decides directly.

Why the constraints are equalities. Writing $\sum _j{x}_{ij}\le s_i$ would permit a warehouse to hold stock back. That is a reasonable model of a different situation, and it is no longer balanced in the sense used here. The equality form says every available unit is assigned somewhere, which is what makes the dummy demand point meaningful: unshipped stock is assigned to it.

Counting variables and constraints. An $m\times n$ problem has $mn$ variables and $m+n$ equality constraints. Given balance, one constraint is implied by the others, so the rank is $m+n-1$ and a basis holds $m+n-1$ variables. For $m=n=3$ that is nine variables, six constraints, and five basic variables, so an optimal plan uses at most five of the nine routes.

What the cost coefficients must be. $c_{ij}$ is the cost of moving one unit. A quoted price per lorry-load, a fixed charge for opening a route, or a discount above some volume is not a $c_{ij}$, because each makes total cost something other than $c_{ij}{x}_{ij}$. Converting a per-lorry price into a per-unit price is only valid when partial loads cost proportionally.

The condition. With equality constraints on both sides, the model is feasible only when total supply equals total demand. This is checked before solving, by adding two columns of numbers.

Restoring balance when it fails. The imbalance is not an error in the data; most real situations are unbalanced. It is restored by adding a row or a column, and which side depends on which is short.

The costs are a modelling decision. Setting a dummy row to zero asserts that a shortfall costs nothing, which is rarely true, unmet demand usually carries a lost margin, a contractual penalty, or a cost of emergency purchase, and these may differ by destination. A dummy column at zero asserts that holding surplus stock is free, which is a defensible approximation over a short horizon and wrong if storage is charged.

Using zeros is not a neutral default. It is a claim about the situation, and where it is wrong the optimal plan will be wrong in a specific direction: with zero shortfall costs the model is indifferent about which demand goes unserved, and will leave whichever destination is most expensive to reach unserved regardless of how much that matters.

Why the dummy does not distort the rest of the answer. Adding a zero-cost dummy column leaves every real route's cost unchanged, so among plans serving the same real demands the model still prefers the cheapest. The dummy only records where the slack went.

Using the data above: supplies $(30,40,30)$, demands $(35,25,40)$, costs

Step 1: check balance. Supply totals $30+40+30=100$; demand totals $35+25+40=100$. Balanced, so the equality model applies with no dummy.

Step 2: a first feasible plan by the northwest-corner rule. Start at the top-left cell and assign the most the row and column allow, then move right when a column fills and down when a row empties.

Cell $(A,1)$: $min(30,35)=30$; Depot A is empty, move down. Cell $(B,1)$: Shop 1 still needs $5$, assign $5$; the column fills, move right. Cell $(B,2)$: $min(35,25)=25$; the column fills, move right. Cell $(B,3)$: Depot B has $10$ left, assign $10$; the row empties, move down. Cell $(C,3)$: assign the remaining $30$.

Five basic cells, matching $m+n-1=5$. The rule never looks at a cost, so there is no reason to expect the result to be good; it is a starting point.

Step 3: a plan by taking the cheapest cell first. Fill the lowest-cost cell as much as possible, then the next, and so on.

Cheapest is $(A,2)$ at 6: $min(30,25)=25$. Next $(A,1)$ at 8: Depot A has $5$ left, assign $5$. Next $(B,1)$ at 9: Shop 1 needs $30$ more, assign $30$. Next $(C,2)$ at 9: Shop 2 is full, assign $0$. Next $(A,3)$ at 10: Depot A is empty. Next $(B,2)$ at 12: full. Next $(B,3)$ at 13: Depot B has $10$ left, assign $10$. Next $(C,1)$ at 14: full. Last $(C,3)$ at 16: assign the remaining $30$.

Better than 1195, and using costs did help. The question is whether it is optimal.

Step 4: the optimum. It is

Check feasibility: rows sum to $30$, $40$, $30$; columns to $35$, $25$, $40$. Five basic cells again.

Step 5: what the comparison shows. The greedy plan costs $1070$ against the optimum's $985$, 8.6% more, from a rule that used the cost data at every step and looks locally sensible.

The reason is visible in the optimal plan. It sends all 30 units of Depot A to Shop 3 at cost 10, ignoring A's cheapest route $(A,2)$ at 6 entirely. Taking that cheap cell first forces Shop 3 to be served from Depots B and C at 13 and 16, and those later costs exceed what the early saving was worth. A cell's cost is not the cost of using it, because using it changes which cells remain available to everyone else.

A note on the numbers. Every entry is a whole number, and nothing required that. No integrality constraint was imposed and none was needed, which is the structural property the next block accounts for.

Balance is forced by the equalities. Sum the supply constraints over $i$:

Sum the demand constraints over $j$:

The left sides are the same quantity, every variable appears once in each, so any feasible $x$ makes the two right sides equal. If $\sum _i{s}_i\ne \sum _j{d}_j$, no feasible $x$ exists.

The same calculation shows the redundancy. Given balance, the sum of the supply equations equals the sum of the demand equations, so one constraint is a linear combination of the others. The rank is $m+n-1$, which is why a basis holds $m+n-1$ variables.

Integrality follows from the constraint matrix. Each variable $x_{ij}$ appears in exactly two constraints: supply row $i$ and demand row $j$, with coefficient $1$ in both. So each column of the constraint matrix has exactly two nonzero entries, both $+1$, one in a supply row and one in a demand row.

A matrix is totally unimodular when every square submatrix has determinant $0$, $+1$ or $-1$. A matrix whose columns each have at most two nonzeros, of value $+1$, whose rows split into two groups such that each column's nonzeros fall one in each group, satisfies this. The row set splits into the supply rows and the demand rows, which is exactly that condition.

The consequence: for a totally unimodular $A$ and integer $b$, every basic solution of $Ax=b$ is integral. A basic solution is $x_B=A_B^{-1}b$, and by Cramer's rule each entry is a ratio of determinants with $det{A}_B$ in the denominator. Total unimodularity makes $det{A}_B=\pm 1$, so each entry is a determinant of an integer matrix: an integer.

Since the simplex method returns a basic feasible solution, an optimum of a transportation problem with integer supplies and demands is a plan in whole units, with no integrality constraint imposed.

The limits of the guarantee. Three of them matter.

It needs integer $b$. Supplies and demands in tonnes to one decimal place are not integers, and the optimum may be fractional. Rescaling the units restores the property when the data is commensurable.

It says nothing about the costs. They may be any real numbers; unimodularity is a property of the constraint matrix alone.

It is not preserved by arbitrary additions. Capacities on individual routes, $x_{ij}\le u_{ij}$, do preserve it. The extra rows keep the structure. A constraint linking several routes, such as a limit on the total leaving two depots together, adds a column entry that breaks the two-nonzeros-per-column pattern, and integrality is no longer guaranteed. That is why a modified transportation problem may need integer programming after all.

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

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.