A transportation table records shipments from several origins to several destinations. Its row sums are supplies and its column sums are demands. This section studies the complete balanced model: every route is allowed, supplies and demands are nonnegative, and their totals agree. The unit costs may be any finite real numbers. A tree is a convenient bookkeeping device for exchanges; a zero shipment on a tree edge is allowed and is essential when a solution is degenerate.
Why a tree?
Write for the shipment from origin to destination . The constraints are
The sum of all row equations equals the sum of all column equations; because total supply equals total demand, any one equation follows from the others. Think of the origins and destinations as the two vertex classes of the complete bipartite graph, with one edge for each cell . For origins and destinations, a spanning tree of this graph has edges.
Definition 23.1.1
(Transportation tree and its basic solution)
A transportation tree is a set of cells whose edges form a spanning tree of the complete bipartite graph on the origins and destinations: it is connected, contains no cycle, reaches every origin and destination, and has cells. Its cells are the basic cells. The associated basic solution sets every nonbasic cell to zero and solves the balance equations on the tree cells. It is a basic feasible solution when all its entries are nonnegative.
The tree theorem below shows that the columns of the tree cells are independent, so the balance equations have rank exactly . Some basic shipments can be zero; counting positive shipments alone therefore does not identify a basis.
Theorem 23.1.2
(A tree determines a unique basic shipment)
Given balanced supplies and demands and a spanning tree on all origins and destinations, there is exactly one real shipment array supported on its edges satisfying the balances. It is a feasible transportation solution precisely when its entries are nonnegative.
Proof
(Peel off leaves one at a time)
Give each vertex a remaining balance, initially its supply or demand. A finite tree with more than one vertex has a leaf. Its sole incident shipment must equal its current remaining balance. Remove the leaf and edge, subtracting that shipment from the remaining balance at the neighboring vertex. The remaining supply and demand balances have equal totals. Repeating determines every edge value uniquely, and the final vertex has zero remaining balance. Each removed vertex satisfies its original equation by construction, and the final vertex does too because its remaining balance is zero. Thus the real solution exists and is unique; it is feasible exactly when all its entries are nonnegative.
Each step of the peeling is forced, which gives uniqueness; existence needs one more observation about the last vertex.
Proof X-ray
Where balance and the tree shape are used
The leaf step uses only that a leaf's equation contains a single unknown, so that unknown is forced. Acyclicity guarantees that a leaf always exists, and that deleting it leaves a smaller tree, so the procedure continues until one vertex remains. Spanning matters because a vertex outside the tree would have no edge at all, and its equation could not hold unless its supply or demand were zero.
The balance hypothesis is used only once, at the end. The invariant is that remaining supply total equals remaining demand total. Removing a leaf with remaining balance lowers one side by (the leaf disappears) and the other side by (its neighbor is reduced), so the invariant persists. When one vertex is left, one side of the invariant is an empty sum, so that vertex's remaining balance is zero and its equation holds with no edge left to adjust. Without balance the same peeling still forces every edge value, but the last equation fails, and no solution exists.
The proof also shows that independence and the tree shape are two descriptions of the same thing.
Concept lensCombinatorial
Bases are exactly spanning trees
Write for the column of in the balance system: it has a one in row equation and a one in column equation . A set of cells has linearly independent columns exactly when it contains no cycle. If the cells contain a cycle, alternately adding and subtracting its columns around the cycle gives zero, because each row and column on the cycle is met once with each sign. If they contain no cycle, they form a forest; the leaf-peeling argument applied to the right-hand side zero forces every coefficient to vanish, so the columns are independent. Since the rank is , a basis has independent cells, and an acyclic set of edges on vertices is a spanning tree. Linear algebra asks for independent columns; the graph asks for a spanning tree. They select the same sets of cells.
The count alone is not enough, as the next check shows.
Counterexample mode
The right number of cells need not form a basis
Claim: any cells determine a unique basic shipment. Take , , supplies and demands , which are balanced. The four cells have the count . For every with ,
has row sums and column sums , so the balances have infinitely many solutions on these cells. The claim fails because the cells contain the cycle and miss destination . With supplies and demands the same cells admit no solution at all, since nothing can reach destination . The correct hypothesis is that the cells form a spanning tree, not merely that there are of them.
Prices and one exchange
Choose row prices and column prices so that on every tree edge. Start with one arbitrary price, say , and propagate along the tree; absence of cycles makes the prices well defined, and connectedness makes every price determined.
Definition 23.1.3
(Tree prices and reduced costs)
For a transportation tree, prices and are tree prices if on every tree cell. The reduced cost of a cell is ; it is zero on tree cells.
Theorem 23.1.4
(Nonnegative reduced costs certify optimality)
Let the basic solution of a transportation tree be feasible, and let be tree prices with for every nonbasic cell. Then every feasible array obeys
and attains this bound. Hence is optimal.
Proof
(Substitute the reduced costs)
Substitute into the cost of . Using the balance equations,
Every is nonnegative (zero on tree cells, nonnegative by hypothesis elsewhere) and every , so the last sum is nonnegative. The array is supported on tree cells, where , so for the last sum vanishes and attains the bound. Prices may be negative; only the reduced-cost inequalities matter.
If a nonbasic reduced cost is negative, adding its edge to the tree creates one cycle. Increase its shipment by and alternate decrease and increase around that cycle. Each row and column on the cycle has one increase and one decrease, so balances remain unchanged. Choose as the smallest shipment on a decreased edge. Nonnegativity is preserved and at least one edge becomes zero. Remove one such edge to obtain a new tree. The total cost changes by , because the tree-edge prices cancel around the cycle. When , this is a degenerate pivot: the basis changes but the shipment and cost do not. A negative reduced cost in that particular basis is then not by itself proof that the current shipment is nonoptimal. Repeated degenerate pivots may cycle; an appropriate anti-cycling rule is needed for a termination guarantee.
Worked examples
Worked example 23.1.5
(A tree pivot and an optimality certificate)
Take supplies , demands and costs
Start with , using its four positive cells as the tree. Its cost is . Set ; the tree equations give , , , . The nonbasic cell has reduced cost . Its cycle changes cells with signs . The bottleneck is . After the pivot,
Both decreasing cells reach zero. Retain as a zero basic cell and remove . The new tree prices are and . The nonbasic reduced costs are and . The lower bound is , matching the shipment cost. Hence is optimal. Retaining a zero edge was necessary to keep a spanning tree; it does not mean shipping a positive amount on that route.
Worked example 23.1.6
(Leaf peeling that produces a zero basic cell)
Take supplies , demands and the tree with cells . It has cells and is connected: origin joins destinations , and origin joins destinations .
Destination is a leaf, so and origin has remaining balance . Destination is a leaf, so and origin has remaining balance . Now origin is a leaf with only cell left, so , and destination keeps remaining balance . The last edge gives , which leaves both origin and destination with zero.
Row sums and column sums check. The solution is feasible and degenerate: the basic cell carries zero. Only three cells are positive, yet the basis has four cells; dropping would disconnect origin from the rest of the tree, and the prices could no longer be propagated.
Worked example 23.1.7
(A tree whose basic solution is infeasible)
Take supplies , demands and the tree with cells . Origin is a leaf, so , and destination has remaining balance . Destinations and are leaves, so and , which leaves origin with . The last edge gives , and both remaining balances are then zero.
Row sums are and column sums are , so the balances hold, as the theorem promises. The entry makes the array infeasible. A tree always gives a basic solution, but the simplex method may only use trees whose basic solution is nonnegative, and tree prices computed here would certify nothing.
Common mistakes
Common mistake
(Counting positive shipments to find the basis)
A degenerate feasible solution has fewer than positive shipments. Taking only the positive cells as the basis leaves a forest rather than a tree, and the price equations then have more than one free price. Add zero-valued cells that reconnect the forest without creating a cycle, as in the second worked example.
Common mistake
(Reading a negative reduced cost as proof of nonoptimality)
A negative shows that this basis fails to certify optimality. It does not show that the shipment can be improved: if a decreased cell on the cycle already carries zero, the step is and the cost is unchanged. Another tree for the same shipment may have all reduced costs nonnegative.
Practice
Quick check
(For the first worked example's optimal table, use the stated prices to check both nonbasic inequalities and verify the objective directly.)
Solution · Answer
The price sums in cells and are and . The cost is , equal to the price lower bound.
Quick check
(A proposed tree exchange has entering reduced cost , but one decreasing basic cell contains zero. What is the permitted step and what conclusion follows?)
Solution · Answer
The bottleneck is zero. Enter the cell and remove a zero-valued decreasing tree cell; the array and objective do not change. This pivot proves neither strict improvement nor optimality, so pricing must continue.
Quick check
(For two origins and two destinations, supplies , demands and costs , find two distinct optimal arrays and explain why their costs agree.)
Solution · Answer
The diagonal and off-diagonal arrays both cost . Indeed , so every feasible exchange around the four-cell cycle has zero cost change. Every feasible array has the form with , and its cost does not depend on , so every feasible array is optimal.