Flows¶
Part 3 of the course, volume 3 of the lecture notes: chapters 4–7.
Network flow models and total unimodularity; maximum flow and minimum cut; minimum cost flow with negative cycles, potentials and reduced costs; transportation, transshipment and assignment problems.
Lecture notes (PDF) Exercises (PDF)
-
4. Network flow models
Networks and flows · The minimum cost flow model · Feasibility conditions · Removing the lower bounds
-
5. Maximum flow
The maximum flow problem · Cuts · The residual network · The max-flow min-cut theorem
-
6. Minimum cost flow
The residual network with costs · Circulations and their decomposition · Negative cycle optimality conditions · Optimality conditions with potentials
-
7. Transportation and assignment
The transportation problem · Basic solutions · Initial basic feasible solutions · The potential method