Question

Can there be multiple optimal solutions to an assignment problem? How to identify such situations

Answer 1

An Assignment downside will have quite one best answer, that is named multiple best solutions. The that means of multiple best solutions is – the full price or total profit can stay same for various sets or combos of allocations. It suggests that we've got the pliability of distribution completely different allocations whereas still maintaining Minimum (Optimal) price or most (Optimal) profit.

We can discover multiple best solutions once there area unit multiple zeroes in any columns or rows within the final (Optimal) table within the Assignment downside.

Example:-

We contemplate associate degree example wherever four jobs (J1, J2, J3, and J4) must be dead by four staff (W1, W2, W3, and W4), one job per employee. The matrix below shows the price of assignment a specific employee to a specific job. the target is to reduce the full valueof the assignment.
J1 J2 J3 J4
W1 82 83 69 92
W2 77 37 49 92
W3 11 69 5 86
W4 8 9 98 23
Below we are going to make a case for the Hungarian formula exploitation this instance. Note that a general description of the formula may be found here.
Step 1: cipher row minima
We begin with subtracting the row minimum from every row. the littlest part within the initialrow is, as an example, 69. Therefore, we have a tendency to substract sixty nine from every part within the initial row. The ensuing matrix is:
J1 J2 J3 J4
W1 13 14 0 23 (-69)
W2 40 0 12 55 (-37)
W3 6 64 0 81 (-5)
W4 0 1 90 15 (-8)
Step 2: cipher column minima
Similarly, we have a tendency to cipher the column minimum from every column, giving the subsequent matrix:
J1 J2 J3 J4
W1 13 14 0 8
W2 40 0 12 40
W3 6 64 0 66
W4 0 1. 90 0
(-15)
Step 3: cowl all zeros with a minimum range of lines
We will currently confirm the minimum range of lines (horizontal or vertical) that ar needed to hide all zeros within the matrix. All zeros may belined exploitation three lines:
J1 J2 J3 J4
W1 13 14 0. 8
W2 40 0 12 40 x
W3 6 64 0 66
W4 0 1 90 0 x
x
Because the quantity of lines needed (3) is less than the scale of the matrix (n=4), we have a tendency to continue with Step four.
Step 4: produce extra zeros
First, we discover that the littlest uncovered range is half dozen. we have a tendency to cipher this range from all uncovered components and add it to any or all components that are lined double. This leads to the subsequent matrix:
J1 J2 J3 J4
W1 7. 8 0 2
W2 40 0 18 40
W3 0. 58 0 60
W4 0 1 96 0
Now we have a tendency to come to Step three.
Step 3: cowl all zeros with a minimum range of lines
Again, we have a tendency to confirm the minimum range of lines needed to hide all zeros within the matrix. currently there ar four lines required:
J1 J2 J3 J4
W1 7 8 0 2 x
W2 40 0 18 40 x
W3 0 58 0 60 x
W4 0 1 96 0 x
Because the quantity of lines needed (4) equals the scale of the matrix (n=4), associate degree best assignment exists among the zeros within the matrix. Therefore, the formula stops.
The best assignment
The following zeros cowl associate degree best assignment:
J1 J2 J3 J4
W1 7 8 0 2
W2 40 0 18 40
W3 0 58 0 60
W4 0 1 96 0
This corresponds to the subsequent best assignment within the original value matrix:
J1 J2 J3 J4
W1 82 83 69 92
W2 77 37 49 92
W3 11 69 5 86
W4 8 9 98. 23
Thus, employee one ought to perform job three, employee a pair of job a pair of, employee threejob one, and employee four ought to perform job four. the full value of this best assignment is to 69 + 37 + 11 + 23= 140.