Back to the on-screen lesson ·
One variable per arc, one balance row per node, and the structure that makes the answers come out whole.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to draw the arcs of a transportation model from a description, write the capacity matrix of a small network, apply conservation at a node, count the rows and columns of a transportation model, and recognise which problems have the network structure that makes their relaxations integral.
You can write a model as rows and columns, and you know that a totally unimodular matrix makes an integer program easy. Networks are where that happens, and this lesson is about recognising one.
A node is a place and an arc is a one-way connection between two of them. A balance row says what enters a node equals what leaves it. The node-arc incidence matrix has one row per node and one column per arc, with a $+1$ where the arc leaves and a $-1$ where it arrives.
A network model has one variable per arc and one row per node. The row says the flow is balanced there — what arrives leaves — except at a source and a sink, where it is created and absorbed. Written out, each arc's column holds exactly one $+1$, one $-1$ and zeros.
That single structural fact makes the matrix totally unimodular, so with whole supplies, demands and capacities every vertex of the relaxation is already integral. Transportation, assignment, shortest path and maximum flow are all this shape, and all of them are therefore linear programs whose answers come out whole without any branching.
Recognising the shape is the skill. A problem qualifies when its variables are arcs and each appears in exactly two balance rows. A single row cutting across the arcs — a shared budget, a setup cost, a side capacity on a group of arcs — destroys the structure and can turn an easy problem into an NP-hard one. That is frequently a choice the modeller made rather than a fact about the situation.
Another way: steps
Another way: picture
Two warehouses on the left, three shops on the right, and a line for each route between them. Each line carries one number, the quantity shipped; each warehouse's lines must total no more than it holds, and each shop's must total at least what it needs.
The number of possible answers is taken for the difficulty: an assignment problem has factorially many assignments and is easy, while a knapsack with far fewer has no such guarantee. The other error is adding one convenient side constraint across the arcs without noticing that it has left the family.
Assigning three workers to three jobs: nine binary variables, three worker rows and three job rows.
A bipartite network.
Every variable appears in exactly one worker row and one job row, so the matrix is totally unimodular and the relaxation returns a real assignment.
Solved as a linear program.
Add 'and the total training cost is at most $C$' and that row touches every variable at once. The structure is gone, and so is the guarantee.
One row out of the family.
One row per node and one column per arc.
Nodes are rows.
So $6$ rows and $11$ columns, and each column holds one $+1$, one $-1$ and four zeros.
Warehouse 1 can deliver to shops A and B. Warehouse 2 can deliver to shops B and C. Draw one arc for each available route, from the warehouse to the shop.
This task has no paper form; do it on a device.
A network on nodes $1$, $2$, $3$ has arcs $1 \to 2$ of capacity $8$, $1 \to 3$ of capacity $9$ and $2 \to 3$ of capacity $6$. Write the capacity matrix, rows the node an arc leaves and columns the node it enters.
This task has no paper form; do it on a device.
Three intermediate nodes each receive flow along two arcs: node P receives $7$ and $6$, node Q receives $7$ and $4$, node R receives $9$ and $7$. Fill in what must leave each.
| Arrives on the first arc | Arrives on the second | Must leave in total | |
|---|---|---|---|
| Node P | 7 | 6 | |
| Node Q | 7 | 4 | |
| Node R | 9 | 7 |
A transportation model ships from $3$ warehouses to $6$ shops. How many constraints does it have, besides non-negativity?
Answer:
Assigning $3$ workers to $3$ jobs, one each, has $3$ factorial possible assignments. Why can it nonetheless be solved as a linear program?
Select every problem that is a network flow problem, so that its relaxation returns whole numbers with no branching.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A transportation model ships from $7$ warehouses to $4$ shops. How many constraints does it have, besides non-negativity?
Answer:
You can build a network model, count its rows and columns, and recognise the structure that makes it easy. Say in your own words why one side constraint across the arcs can destroy that structure.
7. Your turn: a flow model has $6$ nodes and $11$ arcs. What is the shape of its incidence matrix?, step 2