The optimal solution of the following assignment problem using Hungarian…

Concept: An assignment problem asks for a one-to-one pairing of n workers with n jobs that makes the total cost as small as possible. Every complete assignment uses exactly one cell from each row and exactly one from each column, so subtracting a constant from a whole row or a whole column lowers every complete assignment's total by the same amount and cannot change which pairing is cheapest. The Hungarian method uses this invariance: reduce rows and columns until zeros appear, then look for a set of independent zeros, one in every row and every column. Such a set is an optimal assignment, and its cost read back from the original table is the answer.

Application: Applying the method to the given cost table:

1. Row reduction: subtract each row's smallest entry (A: 8, B: 4, C: 15, D: 10). The rows become A: 0, 18, 9, 3; B: 9, 24, 0, 22; C: 23, 4, 3, 0; D: 9, 16, 14, 0.

2. Column reduction: columns I, III and IV already contain a zero, while column II has smallest entry 4, so subtract 4 from column II. The table becomes A: 0, 14, 9, 3; B: 9, 20, 0, 22; C: 23, 0, 3, 0; D: 9, 12, 14, 0.

3. Row A now has its single zero in column I and row B has its single zero in column III, so the pairings A with I and B with III are forced.

4. Row D has its single zero in column IV, so D pairs with IV. Column II then holds the zero left for row C, giving C with II.

5. These four zeros lie in four different rows and four different columns, so they form a complete independent-zero set and therefore an optimal assignment: A with I, B with III, C with II, D with IV.

6. Total cost in the original table = 8 + 4 + 19 + 10 = 41.

Cross-check: The row reductions removed 8 + 4 + 15 + 10 = 37 and the column reduction removed a further 4, so every complete assignment must cost at least 37 + 4 = 41. The assignment found costs exactly 41, so it attains that lower bound and no cheaper assignment can exist.

Total cost of each offered ordering, read from the original table:

The smallest total, 41, belongs to the ordering I, III, II, IV, that is A with I, B with III, C with II and D with IV.