The node equations and the capacity bounds are a linear programme, and its matrix has one column per arc with a single plus one and a single minus one in it. That programme is the whole of this course: four problems usually taught as four separate algorithms are the same programme with a different right-hand side, and the lab solves all of them with the same exact simplex.
Core ideas
The programme itself takes two lines to write. What takes a lesson is seeing that the four famous problems are not analogies for it.
Number the nodes down the side and the arcs across the top. Column j of N holds +1 in the row of arc j's tail, −1 in the row of its head, and zero in every other row. The row for node i then reads exactly “what leaves i minus what arrives at i”, so Nx = b is conservation at every node at once. Nothing about the drawing survives into the programme except this matrix.
Every column of N holds one +1 and one −1, so the rows sum to the zero vector and N never has full row rank. That is the same statement as Σ bᵢ = 0, seen from the other side: one node equation is implied by the others, which is why a transportation tableau with m rows and n columns has a basis of m + n − 1 cells rather than m + n.
The capacity bounds are rows of the programme too, one per bounded arc. Write a network in which nothing is capacitated and the programme has node rows only: on the transportation data the lab solves a five-row programme in six variables, where the same six arcs with capacities would have given eleven rows. Which rows exist is a modelling decision, and it is visible in the size of the tableau.
The material
The matrix first, then the objective, then four instances solved by the same code with nothing changed but the numbers.
Given a directed network with costs c, capacities u and supplies b, the minimum-cost flow problem is min cᵀx subject to Nx = b and 0 ≤ x ≤ u, where N is the node-arc incidence matrix: one row per node, one column per arc, +1 at the tail, −1 at the head.
It is a linear programme with equality rows, so it is solved by the two-phase simplex method exactly as written. No new algorithm is introduced here and none is needed.
Every one of those five numbers is a whole number. Nothing in the programme asked for that: there is no integrality constraint anywhere, the simplex method was free to stop at a corner with halves in it, and on a general linear programme it very often does. It came out whole because of what N is, and that is proved later on this course rather than left as a happy observation.
What follows is not a family of related problems. It is one programme, one matrix and one objective, and the only thing that changes between the four is what was typed into the boxes. The lab's mode for this lesson has a single control for the data set and prints the same tableau each time.
Two sources and three sinks, arcs from every source to every sink, no capacity on any of them, supplies 20, 30 and demands 10, 25, 15. The programme has five rows — one per node and nothing else, because no arc is bounded — and six columns.
The optimum ships 10 and 10 from the first source and 25 and 5 from the second, for a total of 245. The tableau method usually taught for this is in the next two lessons; the point here is that it does not need one.
Three workers, three jobs, an arc from every worker to every job at capacity 1, every supply +1 and every demand −1. Fifteen rows and nine columns.
The optimum is 9, at the assignment that gives the second job to the first worker, the first to the second and the third to the third. Every variable came out 0 or 1: the programme is a transportation problem whose margins happen to be ones, and no binary variable was declared anywhere.
One unit at the source, one unit demanded at the sink, every capacity 1, and the arc costs read as lengths. Moving a single unit as cheaply as possible is moving it along the cheapest route.
On the lab's data the optimum is 6, carried on s>b, b>a and a>t. Bellman-Ford's labels on the same network are 0, 3, 2, 6, and the label at the sink is the same 6 — the relaxation and the simplex method reaching one number by different routes.
Price every arc at zero, add one arc from the sink back to the source with no upper bound and a cost of −1, and supply nothing anywhere. The only way to earn anything is to run flow round the loop, so minimising the cost maximises the flow.
The optimum is −5, and 5 is the maximum flow — and also the capacity of the smallest cut in the same network, which is the theorem two lessons from the end of this course. The return arc is deliberately unbounded: bounding it would cap the answer at whatever bound you chose.
What it buys is that everything already proved about linear programmes now applies to all four. A dual exists and its variables have units; complementary slackness holds; a shadow price on a node row is worth something per unit of supply. The rest of this course is mostly reading those duals, and each one turns out to be an object with a name of its own.
What it costs is speed, and honesty about that matters. A specialised method that knows the basis is a spanning tree will beat a general tableau on a large network, which is why such methods exist. On the size of instance this course works with, the general programme is both fast enough and the right reference: when a hand method and the programme disagree, the programme is not the one that is wrong.
Interactive
Transportation, assignment, shortest path and maximum flow are this programme with different data
Method
Columns before rows, and the redundancy noticed on purpose rather than discovered by a solver.
The j-th arc is the j-th column and the j-th component of x. Fix this order once and write it down; almost every confusion later comes from a flow vector whose order stopped matching the arc list.
For each arc write +1 in its tail's row and −1 in its head's row. Every column has exactly two non-zero entries, whatever the network looks like, and if one of yours does not then you have written a loop or missed an endpoint.
Positive where goods enter, negative where they leave, zero at every node that merely passes things on. The rows of N sum to zero, so the programme is infeasible unless b does too.
xⱼ ≤ uⱼ for each capacitated arc; nothing at all for the rest. Non-negativity is already part of the standard form and does not need a row.
A vector of numbers is not a shipping plan until each component is written on its arc. Do this even when the answer looks obvious — it is how you notice that the optimum sends nothing at all down two of the routes.
Each block below is what changed. The matrix is built the same way every time, the objective is cᵀx every time, and the solver is the same exact simplex every time.
The sizes are the part to notice. The transportation instance has five rows because not one of its arcs is capacitated; the assignment instance has fifteen because all nine are. Same programme, same builder, and the shape of the tableau is a consequence of the data rather than of the problem's name.
For a rehearsal, take the shortest-path data and raise the capacity on every arc from 1 to 2 while leaving b at one unit. The answer does not move. Then ask yourself why the capacities were there at all — and notice that with b at one unit they never bind, so the honest model has no capacity rows in it.
The harder rehearsal: change the maximum-flow instance's return arc from *:-1 to 10:-1 and re-solve, then to 3:-1. The first changes nothing; the second caps the answer at 3. A bound you invented has become the answer, which is the cost of modelling “no limit” with a number.
You should be able to build N column by column, say why its rows are dependent, decide which arcs earn a capacity row, recognise the four special cases by what their b, u and c look like, and read a solved flow vector back onto the drawing.
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.