Assignment Problem

Some Special Cases

Multiple Optimal Solutions

Sometimes, it is possible to cross out all the zeros in the reduced matrix in two or more ways. If you can choose a zero cell arbitrarily, then there will be multiple optimum solutions with the same total pay-off for assignments made. In such a case, the management may select that set of optimal assignments, which is more suited to their requirement.

Example

The Spicy Spoon restaurant has four payment counters. There are four persons available for service. The cost of assigning each person to each counter is given in the following table.

Assign one person to one counter to minimize the total cost.

Solution.

After applying steps 1 to 3 of the Hungarian Method, we obtain the following matrix.

Table

Job
Person	1	2	3	4
A		3	6	9
B		1	2	3
C		1	2	3
D

Now by applying the usual procedure, we get the following matrix.

Table

Job
Person	1	2	3	4
A		2	5	8
B			1	2
C			1	2
D	1

The resulting matrix suggest the alternative optimal solutions as shown in the following tables.

Table

Job Person 1 2 3 4 A 2 4 7 B 1 C 1 D 2 1

Job Person 1 2 3 4 A 2 4 7 B 1 C 1 D 2 1

The persons B & C may be assigned either to job 2 or 3.
The two alternative assignments are: