Assignment problem: Hungarian method 3: Unterschied zwischen den Versionen

Version vom 1. Juli 2013, 01:27 Uhr

The Hungarian method is a combinatorial optimization algorithm which was developed and published by Harold Kuhn in 1955. This method was originally invented for the best assignment of a set of persons to a set of jobs. It is a special case of the transportation problem. The algorithm finds an optimal assignment for a given “n x n” cost matrix. “Assignment problems deal with the question how to assign n items (e.g. jobs) to n machines (or workers) in the best possible way. […] Mathematically an assignment is nothing else than a bijective mapping of a finite set into itself […]” [1]

The assignment constraints are mathematically defined as:

To make clear how to solve an assignment problem with the Hungarian algorithm we will show you the different cases which can occur with several examples.

Example 1 – Minimization problem

In this example we have to assign 4 workers to 4 machines. Each worker causes different costs for the machines. Your goal is to minimize the total cost to the condition that each machine goes to exactly 1 person and each person works at exactly 1 machine. For comprehension: Worker 1 causes a cost of 6 for machine 1 and so on …

To solve the problem we have to perform the following steps:

Step 1 – Subtract the row minimum from each row.

Step 2 – Subtract the column minimum from each column from the reduced matrix.

The idea behind these 2 steps is to simplify the matrix since the solution of the reduced matrix will be exactly the same as of the original matrix.

Step 3 – Assign one “0” to each row & column.

Now that we have simplified the matrix we can assign each worker with the minimal cost to each machine which is represented by a “0”. - In the first row we have one assignable “0” therefore we assign it to worker 3. - In the second row we also only have one assignable “0” therefore we assign it to worker 4. - In the third row we have two assignable “0”. We leave it as it is for now. - In the fourth row we have one assignable “0” therefore we assign it. Consider that we can only assign each worker to each machine hence we can’t allocate any other “0” in the first column. - Now we go back to the third row which now only has one assignable “0” for worker 2.