Das Projekt "Ungarische Methode" ist Teil eines Visual C++ basierten Programmpaketes zur Visualisierung von Algorithmen auf Graphen. Damit kann das Zuordnungsproblem auf bipartiten Graphen gelöst werden.

Die Ungarische Methode ist ein primal duales Optimierungsverfahren. Die Berechnung der Optimallösung erfolgt auf der Kostenmatrix. In jedem Iterationsschritt vergrößert sich der Zielfunktionswert. Dazu werden in der Kostenmatrix Nullen erzeugt. Diese Nullen werden durch möglichst wenig Zeilen und Spalten der Matrix überdeckt. Das Minimum der nichtüberdeckten Zahlen in der Matrix wird anschließend zur Berechnung einer neuen Lösung verwendet. Wie bei primal dualen Verfahren üblich ist die aktuelle Lösung zunächst nicht zulässig. Wenn erstmals in einer Iteration eine zulässige Lösung auftritt, ist diese optimal.

Das Programm ist so geschrieben, dass der Algorithmus anschaulich nachvollzogen werden kann. Dadurch eignet es sich besonders für die Lehre.

Zuordnungsprobleme liefern eine untere Schranke für Traveling-Salesman-Probleme. Sie sind deshalb auch in diesem Kontext interessant.

• Prof. Dr. Ekkehard Schneider (Projektleitung)