Assignment Problem (Hungarian Method)

This video lesson is available to enrolled students.

Enroll to watch — Coal India Management Trainee (CS) Recruitment 2026

AI Summary

An AI-generated summary of this video lecture.

This video is a detailed, step-by-step tutorial on solving a minimization assignment problem using the Hungarian Method. The instructor begins by presenting a 5x5 cost matrix, which represents the cost of assigning five jobs (I, II, III, IV, V) to five workers (A, B, C, D, E). The core of the lesson is the application of the Hungarian Method, which involves a series of systematic reductions. The first step shown is Row Reduction, where the smallest value in each row is subtracted from all elements in that row. The instructor demonstrates this process for each of the five rows, resulting in a new matrix. The next step is Column Reduction, where the smallest value in each column of the row-reduced matrix is subtracted from all elements in that column. The instructor performs this calculation, leading to a matrix with at least one zero in each row and column. The video then transitions to the assignment phase, where the instructor explains the process of covering all zeros with the minimum number of lines. The method involves marking rows and columns with zeros to determine if an optimal assignment is possible. The instructor identifies that the number of lines required (four) is less than the number of rows (five), indicating that the solution is not yet optimal. The final part of the video shows the instructor calculating the smallest uncovered value (which is 2) and using it to adjust the matrix by subtracting it from all uncovered elements and adding it to elements covered by two lines. This process is repeated until an optimal assignment is found, and the final cost is calculated by summing the original costs of the assigned jobs.

Chapters

1. 0:00 – 2:00 00:00-02:00

   The video opens with a whiteboard displaying the title 'Linear Programming Problem' and the sub-topic 'Minimize Assignment Problem'. The instructor, a man in a pink shirt, begins by writing a 5x5 cost matrix on the board. The matrix has rows labeled I, II, III, IV, V and columns labeled A, B, C, D, E. The instructor then writes the title 'Assignment Problem (Hungarian Method)' on the board, indicating the method to be used. On the right side of the board, a list of steps for the Hungarian Method is visible, starting with '1. Row Reduction' and '2. Column Reduction'. The instructor is seen writing the first row of the cost matrix, which is 6, 12, 3, 11, 15.

2. 2:00 – 5:00 02:00-05:00

   The instructor proceeds to perform the first step of the Hungarian Method: Row Reduction. He explains that the smallest value in each row must be subtracted from all elements in that row. He starts with the first row, which has values 6, 12, 3, 11, 15. He identifies the minimum value as 3 and subtracts it from each element, resulting in a new row: 3, 9, 0, 8, 12. He then moves to the second row (4, 2, 7, 1, 10), identifies the minimum as 1, and subtracts it to get 3, 1, 6, 0, 9. He continues this process for the third row (4, 2, 7, 1, 10), subtracting 1 to get 3, 1, 6, 0, 9. For the fourth row (8, 11, 10, 7, 11), the minimum is 7, resulting in 1, 4, 3, 0, 4. For the fifth row (16, 19, 12, 23, 21), the minimum is 12, resulting in 4, 7, 0, 11, 9. The instructor then writes the resulting matrix on the board.

3. 5:00 – 10:00 05:00-10:00

   After completing the row reduction, the instructor moves to the second step: Column Reduction. He explains that the smallest value in each column of the row-reduced matrix must be subtracted from all elements in that column. He begins with the first column of the row-reduced matrix: 3, 3, 3, 1, 4. The minimum value is 1, so he subtracts 1 from each element, resulting in 2, 2, 2, 0, 3. He continues this for the second column (9, 1, 1, 4, 7), where the minimum is 1, resulting in 8, 0, 0, 3, 6. For the third column (0, 6, 6, 3, 0), the minimum is 0, so the values remain unchanged. For the fourth column (8, 0, 0, 0, 11), the minimum is 0, so the values remain unchanged. For the fifth column (12, 9, 9, 4, 9), the minimum is 4, resulting in 8, 5, 5, 0, 5. The instructor writes the final column-reduced matrix on the board.

4. 10:00 – 15:00 10:00-15:00

   The instructor now begins the assignment phase. He explains that the goal is to find the minimum number of lines (horizontal and vertical) required to cover all the zeros in the matrix. He starts by marking the rows that have exactly one zero. He identifies row I (2, 8, 0, 8, 8) has a single zero in column C, so he marks row I. Row II (2, 0, 0, 5, 5) has two zeros, so he does not mark it. Row III (2, 0, 0, 0, 5) has three zeros, so he does not mark it. Row IV (0, 3, 3, 0, 0) has two zeros, so he does not mark it. Row V (3, 6, 0, 5, 5) has a single zero in column C, so he marks row V. He then marks the columns that have exactly one zero. Column C has zeros in rows I, II, III, and V, so it is not marked. Column D has a zero in row IV, so he marks column D. He then marks the rows that have a zero in a marked column. Row IV has a zero in column D, so he marks row IV. He then marks the columns that have a zero in a marked row. Column C has a zero in row IV, so he marks column C. He repeats this process until no more rows or columns can be marked. He then draws lines through the unmarked rows and marked columns. He counts the number of lines drawn, which is four, and notes that this is less than the number of rows (five), indicating that the solution is not optimal.

5. 15:00 – 20:00 15:00-20:00

   The instructor explains the next step when the number of lines is less than the number of rows. He states that the smallest value among the uncovered elements must be found. He identifies the uncovered elements in the matrix: 2, 8, 8, 2, 0, 0, 0, 3, 3, 0, 0, 5, 5, 3, 6, 0, 5, 5. The smallest value among these is 2. He then explains the adjustment process: subtract this value (2) from all uncovered elements and add it to all elements covered by two lines. He demonstrates this by subtracting 2 from the uncovered elements (e.g., 2 becomes 0, 8 becomes 6, 8 becomes 6, etc.) and adding 2 to the elements covered by two lines (e.g., 0 becomes 2, 0 becomes 2, 0 becomes 2, etc.). He then draws the new matrix on the board.

6. 20:00 – 25:00 20:00-25:00

   The instructor continues the process of finding the optimal assignment. He performs the line covering again on the newly adjusted matrix. He marks rows with a single zero: row I (0, 6, 0, 6, 6) has a single zero in column A, so he marks row I. Row II (0, 0, 0, 3, 3) has three zeros, so he does not mark it. Row III (0, 0, 0, 0, 3) has four zeros, so he does not mark it. Row IV (0, 1, 1, 0, 0) has two zeros, so he does not mark it. Row V (1, 4, 0, 3, 3) has a single zero in column C, so he marks row V. He then marks columns with a single zero: column A has a zero in row I, so he marks column A. Column C has a zero in row V, so he marks column C. He then marks rows with a zero in a marked column: row I has a zero in column A, so he marks row I (already marked). Row V has a zero in column C, so he marks row V (already marked). He then marks columns with a zero in a marked row: column A has a zero in row I, so he marks column A (already marked). Column C has a zero in row V, so he marks column C (already marked). He draws lines through the unmarked rows and marked columns. He counts the number of lines, which is now five, equal to the number of rows, indicating an optimal assignment has been found.

7. 25:00 – 27:21 25:00-27:21

   The instructor now identifies the optimal assignment. He looks for a single zero in each row and column. He finds that row I has a single zero in column A, so he assigns job I to worker A. Row II has a single zero in column B, so he assigns job II to worker B. Row III has a single zero in column D, so he assigns job III to worker D. Row IV has a single zero in column E, so he assigns job IV to worker E. Row V has a single zero in column C, so he assigns job V to worker C. He then calculates the total cost by summing the original costs from the initial matrix: I-A (6), II-B (2), III-D (7), IV-E (11), V-C (12). The total cost is 6 + 2 + 7 + 11 + 12 = 38. He writes the final answer on the board.

The video provides a comprehensive, step-by-step walkthrough of the Hungarian Method for solving a minimization assignment problem. It begins with the initial cost matrix and systematically applies the two main reduction steps—Row Reduction and Column Reduction—to transform the matrix into a form where an optimal assignment can be found. The core of the method is the iterative process of covering all zeros with the minimum number of lines. When the number of lines is less than the number of rows, the algorithm adjusts the matrix by finding the smallest uncovered value and using it to modify the matrix elements. This process is repeated until the number of lines equals the number of rows, at which point an optimal assignment is possible. The final step is to identify the unique assignments from the zeros in the matrix and calculate the total cost. The video effectively demonstrates the entire algorithm, from start to finish, making it a valuable resource for understanding this optimization technique.