Zurückblättern Weiterblättern Übergeordnetes Thema Sachgebiet Hauptinhaltsverzeichnis Stichwortverzeichnis Hilfeseiten        


Zuordnungsproblem

Die Darlegung erfolgt an Hand eines Beispiels.
Beispiel

Es sollen Transportaufträge an Transportunternehmen so vergeben werden, daß jedes Unternehmen genau einen Auftrag erhält. Gesucht ist die kostengünstigste Zuordnung, wenn das -te Unternehmen für die Ausführung des -ten Auftrages die Kosten berechnet.

Ein Zuordnungsproblem ist ein spezielles Transportproblem mit und für alle .

(18.28a)

(18.28b)

Jede zulässige Verteilungsmatrix enthält in jeder Zeile und jeder Spalte genau eine 1 und sonst Nullen. Ausgehend von einer zulässigen Verteilungsmatrix kann das Zuordnungsproblem ohne Beachtung der Ganzzahligkeitsforderungen mit dem Transportalgorithmus gelöst werden. Dabei ist jede zulässige Basislösung (Ecke) entartet, da Basisvariable gleich Null sind. Es sind daher Maßnahmen zur Vermeidung von Zyklen zu treffen.