Question

Solve the following minimal assignment problem

	Jobs
Machines	I	II	III
M1	1	4	5
M2	4	2	7
M3	7	8	3

Answer 1

Hint: We start solving the problem by recalling the definition and steps of solving the assignment problem using the Hungarian algorithm. We then perform row and column reduction by checking the minimum element present in that row and column. We then draw lines connecting all zeroes and check whether the total no. of lines is equal to the order of the matrix. We then allow the machines to the jobs and add the costs that were actually given in the problem.

Complete step-by-step solution:
According to the problem, we need to find the minimum cost for the given assignment problem.

	Jobs
Machines	I	II	III
M1	1	4	5
M2	4	2	7
M3	7	8	3

We know that in this assignment problem, each machine has to be allotted to only one job.
We need to solve this using the Hungarian algorithm, which follows steps as follows:
(i) We first reduce the row by subtracting every element of the row with the smallest element of that row.
(ii) Next, we do the column subtraction by subtracting every element of the column with the smallest element of that column. (Note that the elements should be greater than zero in the cells).
(iii) Now, we draw the minimum number of lines that cover all the zeros in the cells.
(iv) If the number of lines is less than the order of matrix given, then we need to add the highest element which is not present on any line to the elements that were present at the intersection of these lines and repeat step (iii) and (iv).
(v) If the number of lines is equal to the order of the matrix given, then examine each row and column of the given matrix to allocate the machine to the jobs wherever the cells we just got 0.
Now, let us do the row reduction. We can see that the minimum element in row 1 is 1, the minimum element in row 2 is 2, the minimum element in row 3 is 3. We subtract this from the remaining elements in that row which is as follows.
Row reduction:

	Jobs
Machines	I	II	III
M1	1-1	4-1	5-1
M2	4-2	2-2	7-2
M3	7-3	8-3	3-3

After the row reduction, the given matrix looks as follows:

	Jobs
Machines	I	II	III
M1	0	3	4
M2	2	0	5
M3	4	5	0

Now, we do the column reduction to the obtained matrix. We can see that the minimum element in column 1 is 0, the minimum element in column 2 is 0, the minimum element in column 3 is 0. We subtract this from the remaining elements in that column, which will not change the matrix we just obtained. So, the matrix we get after making column reduction is as follows:

	Jobs
Machines	I	II	III
M1	0	3	4
M2	2	0	5
M3	4	5	0

Now, we draw the lines which cover all the zeroes in the given matrix. So, we get it as follows:

	Jobs
Machines	I	II	III
M1	0	3	4
M2	2	0	5
M3	4	5	0

We can see that the total number of lines obtained is 3 which is equal to the order of the matrix.
Now, we examine the elements where we just got 0, which as follows:

	Jobs
Machines	I	II	III
M1	0
M2		0
M3			0

From the above matrix, we can see that the machine M1 is to be assigned to Job I, the machine M2 is to be assigned to Job II and the machine M3 is to be assigned to Job III.
Let us add the costs that were present in the cells at the present of the problem.
The minimum cost incurred = 1+2+3.
The minimum cost incurred = 6.
$\therefore$ The minimal cost we get by solving the given assignment problem is 6.

Note: We should confuse assignment problems with the transportation problem, in which we need to assign one machine to only one task. The numbers which were present in the cells of the matrix are costs incurred due to assigning machine to that job. We can also solve this problem by converting the given matric into a linear programming problem. We can also get multiple solutions for this type of problem.