Practice: The Transportation Model

(a) As a flow. Five arcs carry flow: $A\to 3$ with $30$, $B\to 1$ with $35$, $B\to 3$ with $5$, $C\to 2$ with $25$, $C\to 3$ with $5$. The left nodes emit $30$, $40$ and $30$; the right nodes absorb $35$, $25$ and $40$. Checking node by node: $A$ emits $30$ on its single arc; $B$ emits $35+5=40$; $C$ emits $25+5=30$. Shop 1 absorbs $35$; Shop 2 absorbs $25$; Shop 3 absorbs $30+5+5=40$. (b) Why five. A basis is a spanning tree of the bipartite graph. The graph has $m+n=3+3=6$ nodes, and a spanning tree on $6$ nodes has $5$ edges. So a basic plan uses $m+n-1=5$ arcs. The count comes from the tree structure, not from the grid: it is one fewer than the number of nodes, which is also why one of the six equality constraints is redundant. The five arcs here do form a tree: $A\to 3$, $B\to 3$, $C\to 3$, $B\to 1$, $C\to 2$ connect all six nodes with no cycle. (c) Adding a sixth arc. In a graph, adding an edge to a spanning tree creates exactly one cycle. So the sixth route completes a unique closed loop through arcs already carrying flow. Flow can then be pushed around that loop, increased on some arcs, decreased on others, while every node's balance is preserved, so the plan stays feasible but is no longer basic. In the table this is the closed loop the transportation simplex traces: entering a cell and alternately adding and subtracting a quantity around a rectangle-like path of filled cells. The network reading explains why such a loop exists and why it is unique, which the table presents as a rule to follow. (d) What each answers directly. The table answers feasibility and cost more directly: balance is a comparison of two margin totals, checking a plan is $m+n$ additions along rows and columns, and the whole cost structure is visible at once for comparing routes. The network answers structural questions more directly: why a basis has $m+n-1$ arcs, why adding an arc creates exactly one cycle, and how the model extends to transshipment through intermediate nodes or capacities on individual arcs. The table has no natural place to record an intermediate point.

(a) The model. Let $x_{ij}$ be the number of kegs delivered from brewery $i\in \{P,Q\}$ to bar $j\in \{1,2,3\}$ this week.

subject to the supply family

the demand family

and $x_{ij}\ge 0$. (b) Balance. Total supply is $80+50=130$; total demand is $60+45+40=145$. They differ, so no $x$ satisfies both families at once and the model as written is infeasible. This is structural: summing the supply equations and summing the demand equations both give the total shipped, so the two totals must agree for any feasible plan to exist. (c) Restoring balance. Demand exceeds supply by $145-130=15$ kegs, so the shortage is on the supply side and a dummy supply point of $15$ kegs is added. Shipping from the dummy to bar $j$ represents $j$ going short by that many kegs and buying from the wholesaler. Its cost entries are the premiums: $3$ to Bar 1, $6$ to Bar 2, $2$ to Bar 3. These are the right numbers because the brewery price is paid either way; what differs between serving a keg and not serving it is the premium. Setting all three to zero would assert that going short costs nothing. The model would then be indifferent about which bar is left unserved, and would choose to short whichever bar is most expensive to deliver to, here Bar 3 from Q at 9, or Bar 1 from Q at 8, regardless of what the shortfall actually costs the business. Since the premiums differ substantially ($6$ for Bar 2 against $2$ for Bar 3), zeros would produce a materially wrong plan. (d) Integrality. The supplies $(80,50,15)$ and demands $(60,45,40)$ are integers, and the constraint matrix of a transportation problem is totally unimodular. Each variable appears in exactly one supply constraint and one demand constraint, with coefficient $1$ in both. Every basic feasible solution is therefore integral, so the optimal plan delivers whole kegs with no integrality constraint imposed and nothing to round. A change that would remove the guarantee: a constraint linking several routes, such as a limit on the total number of kegs leaving P and Q together on Monday deliveries. That adds a row whose column entries fall outside the supply/demand split, breaking the structure that gives total unimodularity, and whole-keg answers would then need an integer program. (Per-route capacities such as $x_{P1}\le 50$ would not break it; simple bounds preserve total unimodularity.) A second acceptable answer: quoting delivery by the lorry-load rather than per keg makes the objective nonlinear in $x$, so the model is not a transportation problem at all.