The Assignment Problem (Hungarian Method)

Pleased solve this asap

The Assignment Problem (Hungarian Method) Person 3 4 14 11 Job 1 2 3 4 5 1 9 6 12 11 7 2 11 15 13 9 12 13 6 10 14 13 8 12 10 5 7 10 8 9 14 1 2 3 4 5 1 9 6 12 11 7 2 11 15 13 9 Job Person 3 14 13 6 10 4 11 13 8 12 10 5 7 10 8 9 14 Step 1 7 6 6 9 7 12 14 Step 1: Row Reduction ... pull the lowest value from the row and deduct that lowest value from all elements in the corresponding row. 1 2 3 4 5 Job 1 9-7 6-6 12-6 11-9 7-7 Person 3 14-7 13-6 6-6 10-9 14-7 2 11-7 15-6 13-6 9-9 12-7 4 11-7 13-6 8-6 12-9 10-7 5 7-7 10-6 8-6 9-9 14-7 1 2 3 4 5 Job 1 2 0 6 2 0 Person 3 7 7 0 1 7 2 4 9 7 0 5 4 4 7 2 3 3 5 0 4 2 0 7 Step 2: Column Reduction ... pull the lowest value from each column and deduct that lowest value from all elements in the corresponding column. Job 1 2 3 4 5 Step 2 1 2 0 6 2 0 0 2 4 9 7 0 5 0 Person 3 7 7 0 1 7 0 4 4 7 2 3 3 2 5 0 4 2 0 7 0 1 2 3 4 5 Job 1 2-0 0-0 6-0 2-0 0-0 Person 3 7-0 7-0 0-0 1-0 7-0 2 4-0 9-0 7-0 0-0 5-0 4 4-2 7-2 2-2 3-2 3-2 5 0-0 4-0 2-0 0-0 7-0 1 2 3 4 5 Job 1 2 0 6 2 0 Person 3 7 7 0 1 7 2 4 9 7 0 5 4 2 5 0 1 1 5 0 4 2 0 7 Are we optimal, or no? To answer this question, we need to do the following procedure. Step 3: Draw the minimum number of lines to cover all the zeros in the matrix. Step 3.1 Start from the first row and ask the following question. Is there exactly one zero in that row? If yes, mark that zero entry and draw a vertical line passing through that zero, otherwise, skip to the next row. 2 9 Person 3 7 7 0 1 7 1 2 3 4 5 Job 4 2 5 0 1 1 Step 3.2 Start from the first (uncrossed) column and ask the following question. Is there exactly one zero in that column? If yes, mark that zero entry and draw a horizontal line passing through that zero, otherwise, skip to the next column. Ask the question, do I have the same number of zeros and jobs. If yes, you are done. If no you need to do the following procedure [in this case it is no because we have (4 zeros marked and 5 jobs). Step 4. Find the smallest value that is not crossed out. In this case it is going to be equal 1. 2 0 Person 3 7 7 0 1 7 1 2 3 4 5 Job 4 2 5 0 1 1 2 Step 5. Add that smallest value (which is 1) to all the cross lines' values intersections). Step 6. Subtract the smallest value (which 1) to all the uncrossed (undeleted) values. Step 7. Leave all other values the same without changing. 1 2 3 4 5 Job 1 2 0 6+1 2 0 Person 3 7-1 7-1 0 1-1 7-1 2 4 9 7+1 0 5 4 2-1 5-1 0 1-1 1-1 5 0 4 2+1 0 7 4 Our new matrix is Person 2 3 1 4 6 2 9 6 3 8 0 4 o 0 5 5 6 What do you do now? REPHAT ALL OVER Start from step 3.1 qor Job 1 Person 5 7 units of time Job 2 Person 1 > 6 units of time Job 3 Person 3 6 units of time Job 4 Person 2 9 units of time Job 5 Person 4 10 units of time