ETF5248 Chap.4 Network Flow Models
Network Flow Models
Network models describe movement through nodes and directed arcs. A variable records flow on an arc, capacity limits that flow, and conservation reconciles inflow, outflow, supply and demand at each node.
Once the network is drawn correctly, specialised objectives distinguish shortest-path, maximum-flow, minimum-cost-flow, transportation and assignment problems.
This chapter develops the node-arc formulation, shows how source and sink equations differ from transshipment rows, and uses cut capacity as an independent check on a maximum-flow claim.
It also maps the transportation table and assignment matrix back to a network so supplies, demands, forbidden links and integrality are visible rather than buried in solver syntax.
Direction is part of the data. An arc from A to B does not automatically permit travel from B to A, and a missing arc should not receive a variable.
With the convention outflow minus inflow equals supply, origins have positive right-hand sides, destinations have negative ones and transshipment nodes have zero. Summing all node equations provides a quick global check because total supply must equal total demand in a balanced network. In maximum flow, the value leaving the source must match the value entering the sink, while any cut separating them provides an upper bound.
Reaching a cut capacity proves optimality only if every intermediate node conserves flow and no arc exceeds capacity. Transportation and assignment are structured network cases: row sums protect supplies or one-to-one origins, column sums meet demands or destination assignments, and forbidden links are omitted. Drawing this structure first prevents spreadsheet cells from disguising impossible routes.
What this chapter covers
- 01
Nodes, directed arcs and capacities
- 02
Flow conservation at transshipment nodes
- 03
Shortest path and minimum cost
- 04
Maximum flow and source-sink value
- 05
Cuts as optimality checks
- 06
Transportation and assignment structures
Worked example · free
Compute flow value and verify a bottleneck cut
- 1Total flow leaving the source is 4 + 3 = 7 units.
- 1Total flow entering the sink is also 4 + 3 = 7 units, so the source-sink totals agree.
- 1The stated cut capacity is 4 + 3 = 7 units, and the flow saturates both crossing arcs.
- 1Any source-sink flow is bounded by every cut, so a feasible flow equal to a seven-unit cut is maximum.
Key terms
- Node
- A location, state or event at which network flow can enter, leave, originate or terminate.
- Arc
- A directed connection that can carry flow and may have capacity or cost.
- Transshipment node
- A node with neither net supply nor net demand, so inflow equals outflow.
- Cut
- A partition separating the source from the sink, with capacity measured on crossing forward arcs.
- Assignment model
- A network model matching entities one-to-one through binary allocation variables.
Network Flow Models FAQ
How do I write node conservation?
Choose one sign convention and keep it throughout. A useful form is outflow minus inflow equals supply, where supply is positive at an origin, zero at a transshipment node and negative at a demand node. Sum every incident directed arc exactly once with the correct sign.
How are shortest path and maximum flow different?
Shortest path selects a route with minimum total distance or cost, often using binary arc choices. Maximum flow sends as much quantity as possible from source to sink subject to arc capacities and conservation. The same network picture can support different models, so the objective matters.
Why is a cut useful?
The capacity of any source-sink cut is an upper bound on feasible flow because all source-to-sink movement must cross it. If a feasible flow reaches the capacity of a particular cut, the bound and achieved value match, proving that the flow is maximum.
When is a transportation model balanced?
It is balanced when total supply equals total demand. If they differ, a dummy destination or origin can represent unused supply or unmet demand, but its cost and meaning must be stated. A dummy node is a modelling device, not a reason to hide the imbalance.
Exam move
Draw the directed network before writing equations. Label every node balance, arc capacity and cost, then create a variable only for an allowed arc. After solving, make a node-audit table containing total inflow, total outflow and net supply or demand. For maximum flow, find at least one cut and compare its capacity with the returned value.
For transportation and assignment, check both row and column totals and explain any dummy node. These independent checks catch reversed arcs, omitted links and sign errors quickly.
Working through Network Flow Models in ETF5248? Sia is AskSia’s AI Mathematics tutor — ask any ETF5248 Network Flow Models question and get a clear, step-by-step explanation grounded in how ETF5248 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
