The Hungarian algorithm Quiz

1. A row of a cost matrix is $(12, 9, 15)$. What is it after row reduction?

• A. $(0,-3,3)$
• B. $(3,0,6)$
• C. $(12,9,15)$
• D. $(9,6,12)$

2. There are five workers and three jobs. What is done before using the algorithm?

• A. Two dummy workers are added
• B. Five dummy jobs are added
• C. One dummy job is added
• D. Two dummy jobs are added, with all entries equal (e.g. $0$)

3. The largest profit in a matrix is $20$. What does a profit of $7$ become when converted?

• A. $13$
• B. $7$
• C. $27$
• D. $20$

4. After reducing a $4\times4$ matrix, three lines cover all the zeros. What is the next step?

• A. Read off the allocation from the zeros
• B. Start again with the columns
• C. Subtract the smallest uncovered entry from uncovered entries and add it to entries covered twice
• D. Add the smallest uncovered entry to every uncovered entry

5. A mechanic cannot do job 3. How is this entered in the cost matrix?

• A. As $0$
• B. As a very large number $M$
• C. The row is deleted
• D. As the smallest cost in the matrix