Equal total supply and demand do not guarantee that a transportation plan exists when some routes are forbidden. A factory may have enough goods overall, yet the customers reachable from a group of factories may be unable to absorb all of that group's supply. Before minimizing transport cost or constructing a transportation basis, we need to know whether the permitted routes can carry any balanced plan at all.
The subset criterion
Definition 14.1.1
(Allowed-route plan and neighborhood)
Let and be finite sets of origins and destinations. Supplies and demands are nonnegative real numbers, and is the set of allowed routes. A feasible plan consists of nonnegative for satisfying
For , the neighborhood of is , the set of destinations reachable from . The empty set has no neighbors.
There is no variable on a forbidden route. Assume . A necessary condition is
Indeed, all supply from must enter destinations in , whose total demand limits how much they can receive. Surprisingly, checking these inequalities is also sufficient.
Theorem 14.1.2
(Allowed-route feasibility criterion)
For finite , nonnegative supplies and demands with common total , a feasible plan using only exists if and only if for every subset .
Proof
(A flow network, its cuts, and a residual cut)
Necessity follows by summing the row equations over and comparing the resulting shipment into with the column sums there. For sufficiency build a directed network: source has an arc to each origin of capacity ; every allowed route has capacity ; and each destination has an arc to sink of capacity . A flow of value saturates all source and sink arcs, so its route flows are a feasible plan. Conversely every feasible plan gives such a flow. The choice is sufficient because no route can need more than the total supply.
We show that every – cut has capacity at least ; its capacity counts only original arcs directed from the source side to the sink side. Let its source side contain origins and destinations . Its capacity is
If any allowed route crosses the cut, the last term alone is at least . Otherwise , and the assumed inequality gives , so the first two terms already total at least .
For completeness, why does this cut bound produce a flow of value ? A maximum flow exists: the finite vector of arc flows lies in a closed bounded set, and flow value is continuous. If its residual network had an – path, increasing flow along forward residual arcs and decreasing it along backward residual arcs by the smallest residual capacity on that path would increase the value, a contradiction. Let be the vertices reachable from in the residual network. Then ; every original arc leaving is saturated and every original arc entering has zero flow. Summing conservation over shows that the flow value equals this cut's capacity. The cut bound gives value at least , while the source arcs give value at most . Hence the value is and a feasible plan exists.
The proof has two halves: a lower bound on every cut, and a cut whose capacity equals the flow value. The first half is where the subset inequalities enter.
Proof X-ray
What the subset condition controls
The key move is the capacity on every route arc. It is large enough never to restrict a feasible plan, yet any cut that lets an allowed route cross from the source side to the sink side already costs at least . Such cuts are therefore harmless, and the only cuts that need checking are those with . For these the capacity is , and the cheapest choice is ; that is exactly why the inequality is tested on a group of origins together with all of its neighbors, not on single origins.
The hypotheses enter at separate points. The common total is what lets a flow of value saturate the sink arcs as well as the source arcs, so that both the row and the column equations hold. Finiteness makes the arc-flow vectors a closed bounded set, so a maximum flow exists. The closing step uses backward residual arcs: the reachable set is a cut whose capacity equals the flow value only because every arc into carries zero flow, and an arc carrying positive flow into would give a backward residual arc out of , making its tail reachable after all. If the total is zero, all supplies and demands are zero and the zero plan works, including when there are no allowed routes.
Worked example 14.1.3
(A group bottleneck and a repair)
Take supplies , demands , and let origins ship only to destinations , while origin can ship to . Totals are both , every origin and destination has at least one route, and each individual origin has enough neighboring demand. Nevertheless has supply while has demand . Its inequality fails, so no plan exists. In the flow network the source side gives a cut of capacity : from to origin , and from the two destinations to .
If route becomes allowed, the following plan satisfies every balance:
Its row sums are and its column sums are . The newly opened route removes this particular obstruction; the displayed plan, rather than the opening alone, certifies feasibility.
Residual paths repair an early choice
Worked example 14.1.4
(A residual path undoes a greedy shipment)
Suppose supplies and demands are both , and the routes are . After sending two units on first, origin has only a route to destination , which is already full, so no forward augmentation is available. The residual path has bottleneck : the middle backward arc removes the earlier shipment on . Augmentation produces , and . Row sums are and column sums are , and only allowed routes are used, so this is a feasible plan.
Integral plans
The augmenting-path argument also controls the arithmetic of the plan it produces.
Corollary 14.1.5
(Integral data give an integral plan)
If all supplies and demands are integers and the subset criterion holds, then there is a feasible plan using only whose shipments are all integers.
Proof
(Augment by whole units)
For integral supplies and demands, all capacities are integers. Starting from zero flow, every residual capacity and every positive bottleneck is an integer, so each augmentation preserves integrality and raises the value by at least one. The value is at most , hence after at most augmentations no further augmenting path exists. The residual-cut argument above then gives value whenever the criterion holds, and the resulting feasible plan is integral.
This is an existence statement; it does not say every feasible plan is integral. Costs play no part in the feasibility criterion. Once a plan is found, cost minimization requires further optimality arguments.
Worked example 14.1.6
(Checking every subset, including an origin with no routes)
Take supplies , demands and routes , , while origin has no allowed route at all. Totals are . The nonempty subsets give
All seven inequalities hold, so a plan exists, and since the data are integers an integral one exists. Origin must send its unit on . Destination then needs one more unit, which must come from origin , and origin sends its remaining unit to destination :
Row sums are and column sums are . The edge case is origin : an origin with no routes is harmless exactly when its supply is zero, and the singleton inequality is what records this.
Common mistakes
The most tempting shortcut is to test only one origin at a time.
Counterexample mode
Single-origin checks are not enough
Claim: if totals balance, every vertex has an allowed route, and for each single origin , then a feasible plan exists. Take supplies , demands and routes , , . Every origin and destination has a route, and the single-origin inequalities read , and . Yet origins and each have only one route, so and are forced, and destination would receive at least units against a demand of . No plan exists. The subset detects this: . The repaired statement is the criterion itself, which tests every subset of origins.
Common mistake
(Modeling a forbidden route by a high cost)
A forbidden route has no variable. Assigning it a very high but finite cost still lets it carry goods, so a cost model with such a route may report a plan that is not allowed. Feasibility with respect to is decided before any cost enters.
Common mistake
(Treating a greedy dead end as infeasibility)
When forward augmentation stalls, the plan built so far may simply be a poor early choice, as in the residual-path example. A greedy dead end does not prove infeasibility. Only a valid cut of capacity below , or a violated subset inequality, supplies that certificate.
Practice
Quick check
(Supplies are and demands . Routes are , and . Find a violated subset inequality or a feasible plan.)
Solution · Answer
The subset has supply and neighboring demand , so the plan is impossible. The single-origin inequalities all hold, which makes the group test useful.
Quick check
(Supplies and demands are both . Only diagonal routes are allowed. Is a feasible plan? Give an allowed plan or a certificate of infeasibility.)
Solution · Answer
No: those two shipments use forbidden routes. The diagonal plan is feasible.
Quick check
(Supplies are , demands , and routes are and . Identify a cut with capacity below total supply and state how much additional demand at destination would be needed to remove that specific inequality violation.)
Solution · Answer
For , . Put , origin and destination on the source side. Its cut capacity is . Raising that neighbor's demand by at least removes this inequality violation, but changing demand also changes the total balance and must be accompanied by an appropriate model adjustment before concluding feasibility.