QBUS2310 Chap.9 Network Flow and Assignment Models
Network Flow and Assignment Models
Network structure turns many large linear models into node and arc balances. A flow entering a transshipment node must leave it, while source and sink balances encode supply and demand. Shortest path, assignment, transportation, and maximum flow are special cases. Integrality results depend on network structure and integer data, not on a blanket claim that all LP solutions are integral.
These terms let a reader confirm that a proposed flow satisfies conservation at every node. Flow Conservation is the requirement that inflow and outflow balance at a transshipment node. Arc Capacity is an upper bound on flow along a directed connection. Minimum Cost Flow is a network model that satisfies balances and capacities at the least total arc cost.
Shortest Path is a route between nodes with minimum total length or cost. Assignment Problem is a one-to-one matching model between two sets of entities. Minimum Cut is a source-sink partition whose forward arc capacities bound maximum flow. The flow above is verified against conservation and the cut bound: A valid network model consists of directed arc variables, one balance per node, and capacity bounds.
A feasible five-unit flow must satisfy all balances, and any cut with capacity below five proves that demand is impossible.
What this chapter covers
- 01
Nodes, arcs and direction
- 02
Flow conservation
- 03
Arc costs and capacities
- 04
Minimum-cost flow
- 05
Shortest-path models
- 06
Assignment structure
- 07
Maximum flow and minimum cut
- 08
Network integrality conditions
Network Flow and Assignment Models worked example
- +1Define one nonnegative flow variable for each directed arc and retain the direction in the index.
- +1At every intermediate node, set total inflow equal to total outflow. At the source and sink, use net balances of plus and minus five.
- +1Bound each arc flow by its capacity and sum costs if the goal is minimum cost.
- +1For any source-sink cut, every feasible flow must cross from the source side to the sink side. The cut's total forward capacity is therefore an upper bound.
Key terms
- Flow Conservation
- The requirement that inflow and outflow balance at a transshipment node.
- Arc Capacity
- An upper bound on flow along a directed connection.
- Minimum Cost Flow
- A network model that satisfies balances and capacities at the least total arc cost.
- Shortest Path
- A route between nodes with minimum total length or cost.
- Assignment Problem
- A one-to-one matching model between two sets of entities.
- Minimum Cut
- A source-sink partition whose forward arc capacities bound maximum flow.
Network Flow and Assignment Models FAQ
Why does nodes, arcs and direction matter?
Flow Conservation: The requirement that inflow and outflow balance at a transshipment node. Arc Capacity: An upper bound on flow along a directed connection. Keep these two roles separate when checking the model, because confusing them changes the feasible set, bound, or operational interpretation.
How can I check minimum-cost flow?
Arc Capacity: An upper bound on flow along a directed connection. Minimum Cost Flow: A network model that satisfies balances and capacities at the least total arc cost. Keep these two roles separate when checking the model, because confusing them changes the feasible set, bound, or operational interpretation.
What separates flow conservation from arc capacity?
Minimum Cost Flow: A network model that satisfies balances and capacities at the least total arc cost. Shortest Path: A route between nodes with minimum total length or cost. Keep these two roles separate when checking the model, because confusing them changes the feasible set, bound, or operational interpretation.
Which error is most likely around assignment structure?
Shortest Path: A route between nodes with minimum total length or cost. Assignment Problem: A one-to-one matching model between two sets of entities. Keep these two roles separate when checking the model, because confusing them changes the feasible set, bound, or operational interpretation.
How should I practise network integrality conditions?
Assignment Problem: A one-to-one matching model between two sets of entities. Minimum Cut: A source-sink partition whose forward arc capacities bound maximum flow. Keep these two roles separate when checking the model, because confusing them changes the feasible set, bound, or operational interpretation.
Exam move
Draw arrows before equations. For each node, write inflow minus outflow equals its net demand or supply, then check that summing all node balances gives zero. Rehearse the chapter method in this order: Define one nonnegative flow variable for each directed arc and retain the direction in the index. At every intermediate node, set total inflow equal to total outflow.
At the source and sink, use net balances of plus and minus five. Bound each arc flow by its capacity and sum costs if the goal is minimum cost. For any source-sink cut, every feasible flow must cross from the source side to the sink side. The cut's total forward capacity is therefore an upper bound.
Working through Network Flow and Assignment Models in QBUS2310? Sia is AskSia’s AI Mathematics tutor — ask any QBUS2310 Network Flow and Assignment Models question and get a clear, step-by-step explanation grounded in how QBUS2310 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
