Definition: Zuordnungsprobleme

Zuordnungsprobleme gehören zu den speziellen Transportproblemen. Der Unterschied zum klassischen Transportproblem liegt darin, dass hier nicht Mengen möglichst kostenminimal von einem zum anderen Ort transportiert werden sollen, sondern es geht um die kostenminimale Zurodnung von Sachen, Personen oder Betriebsmitteln auf bestimmte Orte, Stellen oder Aufgaben. Dabei sind alle Angebots- und Bedarfsmenge gleich 1 ($a_i = b_j = 1$). Die mathematische Formulierung eines linearen Zuordnungsproblems ist gegeben zu:

$z = \sum_{i = 1}^n \sum_{j = 1}^n c_{ij} x_{ij}$   $\rightarrow $ min!

u.d.N.

$\sum_{j = 1}^n x_{ij} = 1$

$\sum_{i = 1}^n x-{ij} = 1$

$x_{ij} \in \{0,1 \}$

Es besteht die Möglichkeit solche Zurodnungsprobleme mit den Optimierungsverfahren für Transportprobleme zu lösen. Hier kommt es aber häufig zu einer Degeneration (siehe Abschnitt Sonderfälle bei Optimierungsmodellen). Deswegen sind spezielle Verfahren für die Lösung solcher Zurodnungsprobleme entwickelt worden. Die Ungarische Methode ist ein solches Verfahren und soll im folgenden Abschnitt ausführlich behandelt werden.