Assignment problem Example - Part 2

Duration: 25 min

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 lecture on solving an assignment problem using the Hungarian method, a technique for minimizing total cost in a matrix of assignments. The instructor, standing at a whiteboard, walks through the step-by-step algorithm, starting with the initial cost matrix. The process begins with row reduction, where the smallest element in each row is subtracted from all elements in that row, as seen in the first transformation of the matrix. This is followed by column reduction, where the smallest element in each column is subtracted from all elements in that column. The goal of these reductions is to create at least one zero in each row and column, which are potential assignment points. The instructor then explains the process of drawing the minimum number of lines (horizontal and vertical) to cover all zeros in the matrix. If the number of lines equals the number of rows (or columns), an optimal assignment is possible. If not, the algorithm proceeds to find the minimum uncovered value, subtract it from all uncovered elements, and add it to elements covered by two lines. This step is repeated until the number of lines required to cover all zeros equals the matrix dimension. The final step involves making the optimal assignments by selecting one zero from each row and column, ensuring no two assignments share a row or column. The video concludes with the calculation of the total minimum cost by summing the original values from the initial matrix, which is shown to be 59.

Chapters

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

    The video opens with a view of a whiteboard displaying the title 'Assignment Problem' and the method 'Hungarian Method'. The instructor, seen from behind, begins the lecture by presenting the initial cost matrix, which is a 5x4 matrix with values like 18, 26, 19, 11, 13, 28, 19, 21, 38, 19, 18, 15, 19, 26, 24, 10. The instructor explains that the goal is to find the minimum cost assignment. The first step shown is 'Row Reduction', where the instructor subtracts the smallest value in each row from all elements in that row, resulting in a new matrix with zeros in the first column of each row. The instructor then points to the next step, 'Column Reduction', which is written on the board.

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

    The instructor continues the explanation, focusing on the 'Column Reduction' step. He points to the matrix and explains that the smallest value in each column is subtracted from all elements in that column. The board shows the result of this operation, with a new matrix where the first column is all zeros, and other values are reduced accordingly. The instructor then begins to explain the next phase of the algorithm, which involves drawing lines to cover all zeros. He writes the instruction '4. Marking Pairs' and '5. Draw the lines' on the board, indicating the next steps in the process.

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

    The instructor demonstrates the process of drawing the minimum number of lines to cover all zeros in the matrix. He draws a vertical line through column A and a horizontal line through row I, covering all zeros. He then explains that since the number of lines (2) is less than the number of rows (5), an optimal solution is not yet found. He proceeds to find the minimum uncovered value, which is 1, and explains the next step: subtract this value from all uncovered elements and add it to elements covered by two lines. The board shows the updated matrix after this operation, with new zeros appearing in the uncovered areas.

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

    The instructor continues the iteration of the Hungarian method. He explains that the number of lines required to cover all zeros is still not equal to the matrix dimension. He identifies the minimum uncovered value as 1 again and performs the same operation: subtract it from uncovered elements and add it to elements covered by two lines. The board shows the updated matrix, which now has more zeros. The instructor then draws a vertical line through column A and a horizontal line through row I, and then a vertical line through column B and a horizontal line through row II, covering all zeros. He notes that the number of lines is now 4, which is still less than 5, so the process continues.

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

    The instructor performs another iteration. He identifies the minimum uncovered value as 1 and applies the standard procedure: subtract it from all uncovered elements and add it to elements covered by two lines. The board shows the resulting matrix, which now has a different pattern of zeros. He then draws lines to cover all zeros, and the number of lines is now 5, which equals the number of rows. This indicates that an optimal assignment is possible. The instructor then begins to make the assignments by selecting one zero from each row and column, ensuring no two assignments share a row or column.

  6. 20:00 – 24:54 20:00-24:54

    The instructor completes the assignment process. He identifies the optimal assignments: I-A, II-B, III-C, IV-D, and V-A. He then calculates the total minimum cost by summing the original values from the initial matrix: 17 (I-A) + 13 (II-B) + 19 (III-C) + 10 (IV-D) + 10 (V-A) = 59. He writes the final answer on the board, 'Cost = 59'. The video concludes with a summary of the entire algorithm, including the steps of row reduction, column reduction, drawing lines, and making assignments, emphasizing that the total cost is the sum of the original values of the assigned cells.

The video provides a comprehensive, step-by-step walkthrough of the Hungarian method for solving the assignment problem. It begins with the initial cost matrix and systematically applies row and column reductions to create a matrix with zeros, which represent potential assignments. The core of the method is the iterative process of covering all zeros with the minimum number of lines. If the number of lines is less than the matrix size, the algorithm adjusts the matrix by finding the minimum uncovered value and modifying the elements accordingly. This process repeats until the number of lines equals the matrix dimension, at which point an optimal assignment can be made. The final cost is calculated by summing the original values from the initial matrix for the selected assignments. The video effectively demonstrates the entire algorithm, from start to finish, with clear visual aids on the whiteboard, making it a valuable resource for understanding this optimization technique.