From supplies and demands to a plan
A cheapest individual route need not give a cheapest overall shipping plan: using it consumes supply and demand that might be more valuable elsewhere. We need to choose all shipments together. This section studies a finite balanced transportation model.
Definition 2.3.1
(Balanced transportation problem)
There are suppliers and destinations, with supplies , demands , and finite per-unit costs on every supplier–destination pair. The model is balanced if . A plan is a matrix with , row sums and column sums . Its total cost is .
These are exact requirements, not upper bounds: unused supply and unmet demand need explicit modeling. Zero supplies and demands are allowed. Costs may be negative; with fixed finite total shipment, they do not make this model unbounded below.
Proposition 2.3.2
(Balanced complete models are feasible)
If the model is balanced and every supplier–destination pair is allowed, a plan exists.
Proof
(Ship the smaller remainder until nothing remains)
Keep remaining supplies and demands , initially and . While some , the remaining totals are equal, so some . Ship from to and subtract it from both remainders; at least one of them becomes zero. Each step reduces the number of positive remainders, so the process stops after at most steps. Then every , and balance forces every . The shipments are nonnegative and have the required row and column sums.
The proof used the route from to whichever pair it picked, and this is where completeness enters.
Counterexample mode
Balance alone does not give feasibility
With forbidden routes, balance does not guarantee a plan. Take supplies and demands , and allow only the routes and . The model is balanced, but the column sum for destination is because neither variable exists. With forbidden routes or capacities, feasibility must be checked separately.
Prices give a lower bound
Assign real numbers to suppliers and to destinations, subject to on every route. Such a pair is called a feasible price vector.
Theorem 2.3.3
(Price lower bound and tight-route optimality)
Let be a plan and let satisfy for all . Then
If moreover only on tight routes, where , then equality holds and is a minimum-cost plan.
Proof
(Sum the price inequalities with plan weights)
Multiplying each inequality by the nonnegative and summing gives . The row sums turn the first term into , and the column sums turn the second into . The gap is
a sum of nonnegative terms. If every used route is tight, every term is zero, so the cost of equals the bound. Every other plan costs at least the same bound, so is optimal.
The prices are unrestricted in sign because supply and demand are equality constraints. The certificate is sufficient; the argument does not assume that an algorithm finds prices for every possible input.
Proof X-ray
Separate feasibility from the certificate
Assumptions and where they enter: nonnegativity of lets each price inequality be multiplied without reversing it; the row and column equalities convert the weighted price sums into the bound. These are the only two places where the plan matters, and they are why the prices may have any sign: no inequality on or is ever multiplied by a negative number.
Key move: the gap is a sum of shipment times slack. A positive shipment on a strictly slack route makes the gap positive, while tightness on all used routes makes it zero.
What would break: tightness cannot rescue a plan with incorrect row or column sums. With the prices of the example below, the matrix with entries , and zeros elsewhere uses only tight routes and costs , below the bound ; it fails the first row and third column sums, so the equality step of the proof does not apply.
How it closes: the theorem certifies optimality of one plan; it does not claim that tight prices exist for every optimal plan. That converse is a duality statement, not proved here.
Common mistake
(Checking only the routes in use)
If every used route is tight, the identity in the proof makes cost and bound equal automatically, whatever happens on unused routes. Equality therefore proves nothing until every unused inequality is checked. In the example below, and are tight on the three used routes and give the value , but and , so they are not feasible prices and certify nothing.
A complete example
Worked example 2.3.4
(A plan and prices of equal value)
Supplies are , demands , and the cost matrix and plan are
The row sums are and column sums are . The plan costs . Choose and . The matrix of is , entrywise at most . The price bound is . It equals the plan cost; therefore this plan is optimal. The negative supplier price is permitted and does not mean that a shipment has negative quantity.
Common mistake
(Rejecting a certificate because a price is negative)
Supply and demand constraints are equalities, so their prices are free in sign. The price above is legitimate. Requiring would be the rule for inequality constraints of the form , which is a different model.
Concept lensStructural
Prices are not unique
For any real , replace every by and every by . Every route sum stays the same. Balance cancels the change in the bound, since . Thus the same certificate has infinitely many representations; an individual price is not meaningful without a normalization.
The prices in the first example were given. They can be computed from the plan, and a degenerate plan needs one extra step.
Worked example 2.3.5
(Computing prices from a degenerate plan)
Take the same data. Tight routes give one equation each, and the five unknowns are fixed up to the shift of the lens above, so after setting we need tight routes. The plan uses only three: , , . They give and , but links row to nothing else.
Declare one unused route tight at zero shipment, say : then and , the prices of the first example. The two remaining routes have slacks and , both nonnegative, so the prices are feasible.
Choosing instead gives and . The slacks are now on and on , again feasible, with bound . A degenerate plan can have genuinely different certificates, not only shifted ones; each choice must be checked on all six routes.
Beyond the balanced complete model
If supply exceeds demand, one may introduce a dummy destination whose demand is the surplus and whose costs represent the specified cost of unused supply. This is a modeling choice, not an automatic assertion that waste is free. A shortage can analogously be represented by a dummy supplier only after a shortage cost and interpretation are specified. If some routes are forbidden, omit their variables and inequalities; check feasibility separately. Route capacities introduce extra constraints and require a corresponding modified dual certificate.
Worked example 2.3.6
(A dummy destination for surplus supply)
Change the supplies to with the same demands , and suppose unused supply may be left at zero cost. Add a fourth destination with demand and costs . Extend the plan by , so the plan is with an extra column ; the row sums are and the cost is still .
Tight equations on the used routes give , , , and . The unused inequalities and require . Take , so . All eight inequalities hold: the sums are in row and in row , against costs and . The bound is , so the plan is optimal. The free disposal route forces : one more unit at supplier cannot have negative value when it can be discarded at no cost.
Exercises
Quick check
(Verify each row and column sum in the displayed plan and compute its cost independently.)
Solution · Answer
Rows sum to and columns to . The cost is .
Quick check
(Check all six price inequalities and calculate the price lower bound.)
Solution · Answer
The six sums are , each no larger than its cost . The bound is .
Quick check
(Change only the cost from to . Is the displayed price vector still feasible? Does that alone show whether the old plan is optimal?)
Solution · Answer
No: . This invalidates that lower-bound certificate, but alone proves neither optimality nor nonoptimality of the plan for the changed costs. Indeed the old plan remains optimal: the feasible prices , certify its new cost .
Quick check
(Shift the displayed prices by . Compute the new prices and bound. Why is the bound unchanged?)
Solution · Answer
The shifted prices are and . Their bound is . Balance makes the shift cancel.