A network on this course is not a picture. It is a list of ordered arcs, each with a capacity and a cost, and a supply at every node; and a flow on it is a number per arc that has to survive two separate tests. Conservation is local, so a flow can balance in total and still fail. Capacity is a different test entirely, so a flow can conserve everywhere and still ask an arc to carry more than it can.
Core ideas
Drawing the arrows is the easy part. The three ideas here are the ones that decide whether what you have written down can be solved at all.
A matrix indexed by a pair of nodes has one cell for that pair. A directed network needs two: a to b may hold 4 units at a price of 2 while b to a holds 3 at a price of 5, and those are different variables in the programme that follows. The lab stores an array of arcs for exactly this reason, and it will hold two copies of the same arc if you type it twice.
Each node carries one equation: what leaves minus what arrives equals what that node supplies. Add all those equations together and every arc appears once positively and once negatively, so the total is always zero — which means a single overall verdict can never detect a violation. The imbalances have to be reported node by node or they are invisible.
A flow that conserves at every node has said nothing about whether the arcs can carry it. Those are two independent checks and the lab runs both. An arc written with no upper bound contributes no capacity row at all — which is what “unbounded” means, and is different from an arc bounded by some very large constant, because the constant can bind and infinity cannot.
The material
The data, then the two tests, then the three ways the data itself can already be wrong.
A directed network is a set of nodes together with a list of arcs. Each arc has a tail, a head, a capacity u (possibly no upper bound) and a cost c per unit. Each node i carries a supply bᵢ, positive where goods enter the network and negative where they leave.
A flow is one number xⱼ ≥ 0 for each arc. It is feasible when it conserves at every node and respects every capacity.
The lab takes a network as text, one clause per arc: s>a 5:2 is an arc from s to a with capacity 5 and cost 2. A * in the capacity field means no upper bound; 7/2 is seven halves, exactly, because the field separator is a colon and a slash is therefore free to mean division. A clause running from a node back to itself is refused rather than drawn, and so is a negative capacity.
Two arcs in that list join the same pair of nodes. a>b carries up to 4 at a price of 2; b>a carries up to 3 at a price of 5. They are two variables. Sending one unit forward and two back costs 12; sending two forward and one back costs 9 — same total movement, different bill, because the directions are priced separately. The lab draws the pair in its own colour so that the two arrows cannot be read as one edge.
Change one number in the flow above — a>b from 2 to 1 — and the net outflows become 4, −1, 1, −4 against supplies 4, 0, 0, −4. Node a now takes in one more unit than it sends on, and node b sends on one more than it takes in.
Those two errors are equal and opposite, so the imbalances still sum to zero, and any check that adds them up passes. The lab names a and b instead, and shades the two of them, because a verdict of “this flow is invalid” is not something a reader can act on.
Set the supplies to s: 5, t: −5 and the flow to s>a 5, a>b 5, b>a 0, a>t 0, b>t 5. Every node balances exactly.
Two arcs are over capacity: a>b is asked for 5 where it holds 4, and b>t for 5 where it holds 4. Conservation cannot see this, because the node equations contain no capacities at all. The two tests are separate and the lab runs them separately.
Add the node equations together. Every arc leaves exactly one node and enters exactly one, so its variable appears once with a plus and once with a minus and cancels. What is left is Σᵢ bᵢ = 0. So if the supplies do not sum to zero, the equations contradict each other and no flow of any kind exists — a test that costs one addition and needs no algorithm.
Leave the network alone and set the supplies to s: 6, t: −4. The lab reports a total of 2 and stops: adding the four node equations gives 2 = 0.
This is worth meeting before the programme is written rather than after a solver reports infeasibility, because the diagnosis is completely different. Nothing is wrong with the network; the demand does not match the supply, and the fix is to say what happens to the surplus.
The second is quieter. A flow may only name arcs that exist: write s>c 1 on a network with no such arc and the lab refuses it rather than creating one. This sounds pedantic until you have spent twenty minutes on a transportation problem in which a route you assumed was available was never in the data.
Everything from here on is this object with an objective attached. The arcs become the columns of a matrix, the nodes become its rows, the supplies become the right-hand side, and the whole of the rest of the course is what that matrix turns out to be like.
Interactive
Two arcs between the same pair are two variables — and conservation is checked node by node
Method
The data first, then conservation, then capacity, and the cost last. Doing them in that order means an infeasible instance never reaches the arithmetic.
If Σ bᵢ is not zero, stop. There is no feasible flow and no flow you write down will be one. This is one addition and it is the cheapest test on the course.
And that every arc in the network has been given a value, even if that value is zero. A missing arc is usually a typing error; an invented arc is usually a wish.
Out minus in, one node at a time, against bᵢ. Do not add the results up: the sum is always zero and it will tell you nothing. Write the imbalance beside each node and look for the non-zero ones.
0 ≤ xⱼ ≤ uⱼ on each arc. Conservation has said nothing about this. An arc with no upper bound needs only xⱼ ≥ 0.
Σⱼ cⱼ xⱼ. Pricing an infeasible flow produces a number, and the number is meaningless; the lab still prints it, because a reader who watches a cost appear beside a red banner learns something a hidden field cannot teach.
The same five arcs throughout. Only the supplies and the flow change, and each line of arithmetic below is a test rather than a step towards an answer.
Case B is the one to sit with. It is cheaper than case A, it passes every capacity, and the imbalances add to zero. Nothing about it is wrong except that it is not a flow, and the only way to find that out is to look at the nodes one at a time.
For a rehearsal, take case A and try to move one unit off a>t without breaking anything. You will find that the unit has to go somewhere, that the only other way out of a is a>b, and that b then has to pass it on — so the repair is forced, and the repaired flow costs 22 rather than 20. That forced chain is a cycle in disguise, and it comes back as the stepping-stone cycle in the transportation lessons.
The harder rehearsal: type an arc with * in the capacity field and satisfy yourself that the lab stops printing a capacity ratio for it. An unbounded arc contributes no row to the programme that follows, which is not the same thing as contributing a row with a very large number in it.
You should be able to write a directed network as arcs with capacities and costs, check the supplies sum to zero before anything else, compute net outflow node by node without adding the results up, check capacities separately, and explain why an arc and its reverse are two variables.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.