• Home   /  
  • Archive by category "1"

Assignment Problem Hungarian Method Sample Pdf Files

The Hungarian algorithm: An example

We consider an example where four jobs (J1, J2, J3, and J4) need to be executed by four workers (W1, W2, W3, and W4), one job per worker. The matrix below shows the cost of assigning a certain worker to a certain job. The objective is to minimize the total cost of the assignment.

J1J2J3J4
W182836992
W277374992
W31169586
W4899823

Below we will explain the Hungarian algorithm using this example. Note that a general description of the algorithm can be found here.

Step 1: Subtract row minima

We start with subtracting the row minimum from each row. The smallest element in the first row is, for example, 69. Therefore, we substract 69 from each element in the first row. The resulting matrix is:

J1J2J3J4
W11314023(-69)
W24001255(-37)
W3664081(-5)
W4019015(-8)

Step 2: Subtract column minima

Similarly, we subtract the column minimum from each column, giving the following matrix:

J1J2J3J4
W1131408
W24001240
W3664066
W401900
(-15)

Step 3: Cover all zeros with a minimum number of lines

We will now determine the minimum number of lines (horizontal or vertical) that are required to cover all zeros in the matrix. All zeros can be covered using 3 lines:

J1J2J3J4
W1131408
W24001240  x
W3664066
W401900  x
x

Because the number of lines required (3) is lower than the size of the matrix (n=4), we continue with Step 4.

Step 4: Create additional zeros

First, we find that the smallest uncovered number is 6. We subtract this number from all uncovered elements and add it to all elements that are covered twice. This results in the following matrix:

J1J2J3J4
W17802
W24001840
W3058060
W401960

Now we return to Step 3.

Step 3: Cover all zeros with a minimum number of lines

Again, We determine the minimum number of lines required to cover all zeros in the matrix. Now there are 4 lines required:

J1J2J3J4
W17802  x
W24001840  x
W3058060  x
W401960  x

Because the number of lines required (4) equals the size of the matrix (n=4), an optimal assignment exists among the zeros in the matrix. Therefore, the algorithm stops.

The optimal assignment

The following zeros cover an optimal assignment:

J1J2J3J4
W17802
W24001840
W3058060
W401960

This corresponds to the following optimal assignment in the original cost matrix:

J1J2J3J4
W182836992
W277374992
W31169586
W4899823

Thus, worker 1 should perform job 3, worker 2 job 2, worker 3 job 1, and worker 4 should perform job 4. The total cost of this optimal assignment is to 69 + 37 + 11 + 23 = 140.

Solve your own problem online

Please, wait while we are validating your browser

One thought on “Assignment Problem Hungarian Method Sample Pdf Files

Leave a comment

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *