Assignment Problems Questions and Answers

Answer: A

The optimal assignment is I → A, II → C, III → B, IV → D.

Its total cost is the lowest possible:

\[ 10 + 5 + 20 + 20 = 55 \]

The Hungarian method (or checking all 24 assignments) confirms that no other assignment costs less; the next best cost 62. The other options cost more: I → A, II → B, III → C, IV → D costs 10 + 30 + 12 + 20 = 72; I → B, II → A, III → C, IV → D costs 25 + 15 + 12 + 20 = 72; and I → B, II → C, III → A, IV → D costs 25 + 5 + 35 + 20 = 85.

Answer: C

The optimal cost is 20.

Hungarian method. Subtract each row's minimum (7, 5, 4, 2), then each column's minimum (0, 0, 0, 1). That removes 19 in total, so no assignment can cost less than 19.

In the reduced matrix, M2 and M4 both have their only zero in column J1, so a complete assignment of zeros is impossible. Covering the zeros and adjusting by the smallest uncovered value adds one more unit, giving 20, and then a full set of independent zeros exists:

\[ \begin{aligned} & M_{1} \to J_{3} = 7,\ M_{2} \to J_{1} = 5 \\ & M_{3} \to J_{4} = 5,\ M_{4} \to J_{2} = 3 \\ & \text{Total} = 7 + 5 + 5 + 3 = 20 \end{aligned} \]

Checking every one of the 24 assignments confirms that none costs less than 20, so 18 is impossible, and 24 and 26 are feasible but not optimal.

Answer: B

The optimal assignment is U \(\to\) II, V \(\to\) IV, W \(\to\) III, X \(\to\) I, at a total cost of 16.

Hungarian method. Subtract each row minimum (5, 3, 2, 5):

U: 5, 0, 8, 10; V: 0, 6, 15, 0; W: 8, 5, 1, 0; X: 0, 6, 4, 2.

Column minima are 0, 0, 1, 0; subtracting 1 from column III gives U: 5, 0, 7, 10; V: 0, 6, 14, 0; W: 8, 5, 0, 0; X: 0, 6, 3, 2. A full set of independent zeros is U-II, V-IV, W-III, X-I, so this assignment is optimal, with cost \(5 + 3 + 3 + 5 = 16\) (the total reduction \(15 + 1\)).

The other options cost far more: U-II, V-III, W-I, X-IV costs \(5 + 18 + 10 + 7 = 40\); U-III, V-IV, W-II, X-I costs \(13 + 3 + 7 + 5 = 28\); U-IV, V-II, W-III, X-I costs \(15 + 9 + 3 + 5 = 32\).

Answer: C

The Hungarian method rests on the fact that the optimal assignment is not affected by adding or subtracting a constant from any row or column.

Adding or subtracting a constant from every entry of a row (or column) changes the cost of every complete assignment by exactly that constant, because every assignment uses exactly one cell in each row and column. The ranking of assignments, and so the optimum, stays the same. The method uses this to reduce rows and columns until enough zeros appear.

Option A states only the subtraction half of the theorem. Option B is wrong because the objective value does change, by the constant. Option D misdescribes the procedure: entries are reduced row by row and column by column, not one at a time.

Answer: A

The optimal assignment is I → W, II → V, III → U, with total time 280.

With three programmers there are only six assignments, so they can be compared directly:

The Hungarian method gives the same result. Option B costs 300 and option C 370, and an optimal assignment always exists for a square cost table, so D is wrong.

Answer: C

The optimal assignment is \(M_1 \rightarrow J_4, M_2 \rightarrow J_1, M_3 - J_3, M_4 - J_2\).

Total cost of each option:

• A: 8 + 4 + 2 + 6 = 20
• B: 7 + 3 + 1 + 5 = 16
• C: 7 + 3 + 1 + 3 = 14
• D: 8 + 6 + 1 + 4 = 19

Option C is also provably optimal. Every machine must take at least its row minimum, and the row minima are 7 (M1), 3 (M2), 1 (M3) and 3 (M4):

\[ 7 + 3 + 1 + 3 = 14 \]

No assignment can cost less than 14, and C achieves it with each machine on a different job, so it is optimal. The Hungarian method reaches the same assignment.

Answer: D

The binary solution is due to the (totally) unimodular property.

The assignment constraints \(\sum_{j} x_{ij} = 1\), \(\sum_{i} x_{ij} = 1\) have a coefficient matrix that is totally unimodular: every square submatrix has determinant 0 or \(\pm 1\). With integer right-hand sides, every basic feasible solution of such a system is integral (by Cramer's rule), and with the bounds \(0 \le x_{ij} \le 1\) the vertices are 0-1 vectors. So solving the linear programming relaxation already gives a binary assignment.

A linear formulation alone does not give integrality, a non-empty feasible region only guarantees some solution, and the Hungarian method is an exact algorithm, not an approximate one.

Answer: A

The minimum time is 200 hours.

One optimal assignment takes the diagonal: 20 + 50 + 90 + 40 = 200. The Hungarian method confirms the minimum. Subtracting row minima (20, 40, 70, 30) and then column minima leaves

\[ \begin{pmatrix} 0 & 0 & 0 & 20 \\ 0 & 0 & 0 & 20 \\ 0 & 0 & 0 & 0 \\ 0 & 10 & 30 & 0 \end{pmatrix} \]

and a full assignment through zeros exists (for example the diagonal), so the minimum total is the sum of the subtracted amounts, \(20 + 40 + 70 + 30 + 0 + 10 + 20 + 10 = 200\). Several assignments reach 200. So 210 is not the minimum, and the statements about a basic feasible solution do not describe this result.

Answer: B

The best assignment is the one with the least total cost. In option (B), A goes to I at cost 8, B to III at 4, C to II at 19 and D to IV at 10, a total of 41. The other assignments cost more, for example A-I, B-III, C-IV, D-II costs 8 + 4 + 15 + 26 = 53, and A-II, B-III, C-IV, D-I costs 26 + 4 + 15 + 19 = 64, and option (A) with the diagonal costs 8 + 28 + 18 + 10 = 64. So the Hungarian method gives the assignment of option (B), with the cost 41.