Topper Copies

Solve the assignment problem represented by the following matrix $$\begin{array}{c|cccccc} & I & II & III & IV & V & VI \\ \hline A & 9 & 22 & 58 & 11 & 19 & 27 \\ B & 43 & 78 & 72 & 50 & 63 & 48 \\ C & 41 & 28 & 91 & 37 & 45 & 33 \\ D & 74 & 42 & 27 & 49 & 39 & 32 \\ E & 36 & 11 & 57 & 22 & 25 & 18 \\ F & 3 & 56 & 53 & 31 & 17 & 28 \end{array}$$

Divyank Gupta, AIR 21, 2024

Sol^n) Given as assignment problem.

Then by using Hungarian Method

subtracting Smallest element of of each Row from each element and subtracting small column element from from every column element we get

Then drawing line through marked Row and Marked column for least no' of lines .

$\to$ Now subtracting smallest element from non-cancelled element and not changing cancelled element . Adding smaller element on intersection of 2 lines. we get

[a matrix with some zeros boxed and some entries struck out]

Assignment I

A $\to$ IV, B $\to$ I, C $\to$ VI, D $\to$ III, E $\to$ II, F $\to$ V

Total cost = 142

But there is another assignment

[a second matrix with different zeros boxed and some entries struck out]

Assignment II

A $\to$ IV, B $\to$ VI, C $\to$ II, D $\to$ III, E $\to$ V, F $\to$ I

Total cost = 142