Assignment problem: Hungarian method 2

Assignment Problem: Hungarian method from Tobias Huber, Philipp Motsch & Marc Sarvas

Theory:

---

The hungarian method is a special form of the linear optimazation. We assume that the initial matrix is a n x n matrix. The main goal is to reduce the matrix column by column and line by line until you get a unique allocation.

Example:

---

There are 6 jobs for 6 candidates. The goal is to allocate the jobs to the candidates in a way where the costs are minimal.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Steps 1 and 2

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Steps 3 and 4

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Steps 5,6 and 7

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Step 7 has to be repeated because the maximal number of independent "0"`s is not equal to the number of row and column

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

This is the optimal solution. Taken together every candidate gets one job. The first candidate gets job 6, the second one gets job 3. candidate 3 gets job 2 ; the 4th candidate gets job 1. Job 5 belongs to candidate 5 and candidate 6 gets job 4.

References:

---

[1] Operations Research Skript TU Kaiserslautern, Prof. Dr. Oliver Wendt