Answer to Question #237108 in Operations Research for opr

Question

) Five applicants are competing for four jobs . The scores from aptitude tests related to the four vacancies are given below. It is believed the tests measure an applicant possible performance in the job.

JOBS

APPLICANTS 1 2 3 4

A 18 15 12 25

B 9 11 10 15

C 12 10 14 16

D 9 10 10 21

E 14 18 26 26

Determine who should be assigned which job in order to maximize overall output

Answer 1

Solution of Assignment problem using Hungarian method-2 (MAX case):

Here the problem is of Maximazition type and convert it into minimization by substracting it from maximum value 26:

Here given problem is unbalanced and add 1 new column to convert it into a balance.

Step-1: Find out the each row minimum element and subtract it from that row

Step-2: Find out the each column minimum element and subtract it from that column.

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

Determine the minimum number of lines, required to cover all zeros in the matrix.

There are 3 lines required to cover all zeros, which is less than size of matrix (5), so goto step-4

Step-4: Create additional zeros, Develop the new revised table by selecting the smallest element, among the cells not covered by any line (say k = 1)

Subtract k = 1 from every element in the cell not covered by a line.

Add k = 1 to every elment in the intersection cell of two lines.

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

Determine the minimum number of lines, required to cover all zeros in the matrix.

There are 3 lines required to cover all zeros, which is less than size of matrix (5), so goto step-4

Step-4: Create additional zeros, Develop the new revised table by selecting the smallest element, among the cells not covered by any line (say k = 4)

Subtract k = 4 from every element in the cell not covered by a line.

Add k = 4 to every elment in the intersection cell of two lines.

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

Determine the minimum number of lines, required to cover all zeros in the matrix.

There are 4 lines required to cover all zeros, which is less than size of matrix (5), so goto step-4

Step-4: Create additional zeros, Develop the new revised table by selecting the smallest element, among the cells not covered by any line (say k = 2)

Subtract k = 2 from every element in the cell not covered by a line.

 Add k = 2 to every elment in the intersection cell of two lines.

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

Determine the minimum number of lines, required to cover all zeros in the matrix.

There are 5 lines required to cover all zeros, which is equal to size of matrix (5), so an optimal assignment exists and the algorithm stops

The Optimal assignments are

Optimal solution is