ETF2480 Chap.5 Transportation and Assignment Networks
Transportation and Assignment Networks
Transportation models allocate flow from supply nodes to demand nodes. Each arc carries a shipment decision and unit cost, while source and destination rows enforce the published totals. Balanced models have equal aggregate supply and demand. Dummy nodes can represent unused supply or penalised unmet demand, but their costs must match that business meaning.
Assignment is a special unit-supply and unit-demand case in which every agent receives one task and every task receives one agent. Standard network structure can produce integral extreme solutions from an LP, although added side constraints may remove that property and require explicit integer decisions.
What this chapter covers
- 01
Source and destination indices
- 02
Supply and demand balance
- 03
Balanced and unbalanced transport
- 04
Dummy nodes and penalties
- 05
One-to-one assignment
- 06
Network integrality and side constraints
Worked example · free
Allocate shipments across a balanced network
- +2Let xij be units shipped from plant i to customer j and impose both plant and customer balances.
- +1Use East's cheaper A route for 20 units, leaving 5 East units for B.
- +1Send all 35 West units to B, meeting B demand of 40 with the 5 East units.
- +2Cost is 20(3) + 5(7) + 35(4) = $235; verify all four node totals.
Key terms
- Transportation model
- A network model allocating flow from supply nodes to demand nodes at minimum cost or another objective.
- Balanced network
- A transportation problem whose total supply equals total demand.
- Dummy node
- An added source or destination representing unused supply, shortage or another explicit balancing consequence.
- Assignment model
- A transportation special case with unit supply, unit demand and one-to-one matches.
- Node-arc incidence
- A matrix recording how directed arcs leave and enter network nodes.
Transportation and Assignment Networks FAQ
How do I balance excess supply?
Add a dummy destination whose demand equals the excess. Its arc cost should represent genuine non-use, disposal or storage consequences. A zero cost is defensible only when sending flow to the dummy has no relevant effect.
Why can assignment be solved as an LP?
The standard assignment matrix has network structure that gives integral extreme points with integral unit data. This special property supports a continuous formulation, but extra cross-assignment rules can break it, so inspect extensions rather than assuming integrality.
What does a zero shipment mean?
It means the optimisation chose not to use that available arc under the objective and constraints. Present zeros clearly in a table or network so the reader can distinguish an unused route from an omitted variable or unavailable connection.
What checks complete a transport solution?
Recalculate every source total, every destination total and the full arc-cost objective. Explain dummy flow and zero routes explicitly, and revisit integrality whenever a side constraint changes the pure network structure.
Exam move
Draw the bipartite network before writing algebra. Put supplies beside source nodes, demands beside destination nodes and unit costs on arcs. Define the index order once and keep it consistent in the cost table, variables and summations. Write source balances, then destination balances, and check aggregate totals. For unbalanced data, decide what excess supply or unmet demand means before adding a dummy node.
Practise assignment as a separate case: each agent row and task column sums to one. Then add one side constraint and ask whether the standard integrality argument still applies. After solving, present the allocation as a table and recompute every row total, column total and cost. Interpret any dummy flow and unused routes in operational language.
Start each exercise with a supply-demand checksum; an imbalance must be represented explicitly rather than repaired silently. When introducing a dummy destination, assign a cost that reflects disposal or non-use and state what positive dummy flow means. For a dummy source, distinguish genuine emergency procurement from unmet demand and attach the corresponding penalty.
Practise rebuilding the objective from a shipment table by multiplying every occupied cell by its unit cost, including any artificial route. For assignment cases, test each agent row and task column for a total of one and list forbidden matches before solving. Add one coupling rule, such as limiting junior assignments, and inspect whether fractional relaxation values appear.
Use node potentials or reduced costs only after verifying the base allocation. Finish by reporting zero-flow routes deliberately so a reader can tell the difference between an omitted datum and an unused option.
Working through Transportation and Assignment Networks in ETF2480? Sia is AskSia’s AI Management tutor — ask any ETF2480 Transportation and Assignment Networks question and get a clear, step-by-step explanation grounded in how ETF2480 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
