Transportation and assignment¶
Part 3 · Flows · Chapter 7 · Lecture notes, volume 3 (PDF) · Exercises: Transportation and assignment
-
7.1 The transportation problem
Unbalanced instances · Transshipment as transportation
-
7.2 Basic solutions
-
7.3 Initial basic feasible solutions
The minimum cost rule
-
7.4 The potential method
The potential method on the transportation instance · Degeneracy
-
7.5 The assignment problem
Degeneracy of the potential method · Reductions and potentials · Independent zeros and lines · The Hungarian algorithm · The Hungarian algorithm on the example
Prerequisites
-
From this module, Chapter 1 «Graphs»: trees, leaves, fundamental cycles and the rank of the node–arc incidence matrix.
-
From this module, Chapter 3 «Shortest paths»: distances, and Chapter 4 «Network flow models»: the minimum cost flow model, the dummy node, integer vertices, potentials and reduced costs.
-
From the module Linear Programming, Chapter 9 «Duality theory»: the dual of an LP model and the weak and strong duality theorems.
Objectives
At the end of this chapter you will be able to:
-
write the transportation model and its tableau, balance an instance with a dummy origin or destination, and reduce an uncapacitated transshipment instance to a transportation instance;
-
recognize the bases of the transportation model as the spanning trees of a bipartite network, compute a basic solution and recognize a degenerate one;
-
build an initial basic feasible solution with the north-west corner rule and the minimum cost rule;
-
run the potential method, with potentials, reduced costs, cycles and pivots, and certify the optimality of a solution with the dual model;
-
write the assignment model, prove the theorem of König and Egerváry, and run the Hungarian algorithm, reading its potentials as an optimal dual solution.
Next: 7.1 The transportation problem
Exercises on this chapter: Transportation and assignment