HAMEEDA MATHTUBER · YouTube · 6:47
This 407-second lesson solves a balanced 4x4 assignment problem with the Hungarian method. From the original cost matrix, the instructor subtracts row minima 10, 5, 11 and 8, then column minima 0, 2, 2 and 0. Selecting one independent zero per row and column gives A to Job 2, B to Job 3, C to Job 4 and D to Job 1. The original costs add to rupees. The video demonstrates this example but does not prove the method in general.
Use the learning inspector for key ideas and moments, or open the reading tabs for the complete notes.
Generated from the video's visuals and explanation; not verbatim speech.
The video opens with a handwritten title 'BALANCED ASSIGNMENT PROBLEM' and a 4x4 cost matrix representing persons A, B, C, D and jobs 1, 2, 3, 4. The instructor explains that an assignment problem is balanced if the number of rows equals the number of columns; otherwise, it is unbalanced. Since this matrix has 4 rows and 4 columns, it is confirmed as a balanced problem.
To solve this balanced problem, the instructor states they will use the Hungarian method. The first step of this method is 'Row Reduction'. This involves identifying the smallest number (minimum entry) in each row of the original cost matrix.
For Row A, the minimum is 10. The instructor subtracts 10 from each element in Row and writes the results [0, 2, 9, 1] in the corresponding row of a new, empty matrix drawn below.
For Row B, the minimum is 5. Subtracting 5 from each element yields [0, 5, 2, 3], which are written in the second row of the new matrix.
For Row C, the minimum is 11. Subtracting 11 gives [1, 3, 2, 0], filling the third row.
Finally, Row D has minimum 8. Subtracting 8 gives [0,4,3,1]; the completed row-reduced matrix is then used for column reduction.
The clip opens on a handwritten solution sheet for a balanced assignment problem. At the top is the original 4x4 cost table, and below it the completed Step 1 matrix from row reduction: , , , . The speaker finishes writing the last entry of row D, setting up the transition to the next algorithmic stage.
The presenter announces the next step, column reduction, and states that it must be applied to the matrix obtained in Step 1. This establishes the dependency between steps: the new matrix is not built from the original costs directly, but from the row-reduced matrix already on the page.
Column 1 is examined first. Its entries are 0, 0, 1, 0, so the least element is 0. Since subtracting 0 changes nothing, the first column of the Step 2 matrix is copied as 0, 0, 1, 0. The visual writing reinforces the rule that each column is reduced independently using its own minimum.
Column 2 is then processed. The entries are 2, 5, 3, 4, and the minimum is 2. Subtracting 2 from every entry gives 0, 3, 1, 2. This is written into the second column of the new matrix, producing at least one zero in that column while preserving relative differences within the column.
Column 3 follows. Its entries are 9, 2, 2, 3, with minimum 2. Subtracting 2 yields 7, 0, 0, 1. The presenter writes these values into the third column of the Step 2 matrix, again creating zeros where the original column minimum occurred.
Column 4 is handled last. The entries are 1, 3, 0, 1, and the minimum is 0, so the column remains 1, 3, 0, 1. With all four columns completed, the Step 2 matrix is now [[0,0,7,1],[0,3,0,3],[1,1,0,0],[0,2,1,1]].
The speaker moves to step three and explains that the next task is to inspect the reduced matrix row by row and count how many zeros each row contains. This shifts the method from arithmetic reduction to structural examination of the zero pattern.
The rationale is stated explicitly: each job must be assigned to exactly one person, so the matrix must eventually allow a selection in which each row and each column contributes one zero. This connects the zero-counting procedure to the one-to-one nature of the balanced assignment problem.
Row A is (0,0,7,1), so it contains two zeros. Because there is more than one candidate in that row, the presenter says not to select either zero yet. The same reasoning is applied to row B, (0,3,0,3), which also has two zeros.
Row C, (1,1,0,0), is checked next and likewise contains two zeros, so the speaker moves on toward the last row. Within this clip, the process stops during that final inspection, leaving the broader assignment selection for a later step.
We begin with the reduced matrix after row and column operations. The goal is to find a set of independent zeros—one in each row and column—to define the optimal assignment.
Looking at row D, there is only one zero available at column 1. We select this zero by circling it. Consequently, we must eliminate other zeros in column 1 by striking them out, specifically at positions (A,1) and (B,1).
Moving to row A, the zero at (A,1) is now struck out. The only remaining valid zero is at (A,2). We circle this zero to assign Person A to Job 2.
Next, we examine row B. It contains a single zero at (B,3). We circle this zero, assigning Person B to Job 3.
Finally, for row C, we look at the available zeros. The zero at (C,3) must be struck out because column 3 is already assigned to Person B. This leaves the zero at (C,4) as the only option. We circle it, assigning Person C to Job 4.
With all rows processed, we have successfully identified four independent zeros. The optimal assignment plan is: A Job 2, B Job 3, C Job 4, and D Job 1.
To find the total minimum cost, we cannot use the reduced matrix values (which are zeros). Instead, we must refer back to the original cost matrix provided at the start of the problem.
The instructor returns to the original cost matrix. The chosen cells contribute 12, 7, 11 and 8; the final part of the video adds them to obtain 38 rupees.
As the instructor prepares the total, the completed row-reduced matrix remains visible. Its correct row minima were 10 for A, 5 for B, 11 for C and 8 for D. The 7 mentioned at this point is the original cost for the selected B assignment, not its row minimum.
The finished column-reduced matrix and circled independent zeros remain visible while the instructor confirms A to Job 2, B to Job 3, C to Job 4 and D to Job 1.
Finally, the total optimum cost is calculated. This is done by taking the original costs from the initial matrix that correspond to the selected optimal assignments. The costs are Person A to Job , Person B to Job , Person C to Job , and Person D to Job . Summing these values () gives the total optimum cost of Rs 38.
An assignment problem is classified as balanced when the number of available persons (rows) is exactly equal to the number of jobs (columns). If these numbers differ, the problem is unbalanced and requires different handling.
The first step in solving a balanced assignment problem using the Hungarian method is row reduction. To perform this, find the minimum value in each row of the cost matrix. Then, subtract this minimum value from every element within that same row to create a new reduced matrix.
The worksheet identifies the problem as a balanced assignment problem and uses a 4x4 matrix with rows A, B, C, D and columns 1, 2, 3, 4. In this context, balance means the numbers of rows and columns match, supporting a one-to-one assignment of jobs to persons.
Column reduction is performed on the matrix obtained after row reduction. For each column, find the smallest entry and subtract that minimum from every entry in the same column. This creates at least one zero in each column without changing the relative ordering inside that column.
Starting from Step , the column minima are 0, 2, 2, and 0. Applying them column by column gives Step .
After column reduction, the next step is to inspect the reduced matrix row by row and count zeros. The speaker links this to the requirement that each job be assigned to one person and that each row and column should ultimately provide a single selected zero.
If a row contains two zeros, the presenter does not immediately choose either one for assignment. In the displayed matrix, rows A, B, and C each have two zeros, so the clip delays selection from those rows until the zero pattern is further analyzed.
After reducing rows and columns, the next step is to find 'independent zeros'. You scan rows with only one available zero, circle it, and strike out other zeros in that same column. Repeat until every row has exactly one circled zero.
The positions of the circled zeros in the reduced matrix directly give the optimal assignment. For example, a circled zero at Row A, Column 2 means Person A is assigned to Job 2.
Crucially, the total cost is NOT the sum of the reduced matrix values. You must take the assignment pairs (e.g., A->2) and look up their corresponding values in the ORIGINAL cost matrix, then sum those up.
Once the optimal assignments (person-to-job pairs) are determined from the reduced matrix, the total minimum cost is found by looking up the original costs for these specific pairs in the initial cost matrix and summing them up. It is crucial to use the original costs, not the reduced ones.
Explore conditions, steps and evidence. Supplementary explanations are labeled separately from content shown in the video.
The speaker mentions 'number of rows' and 'four rows'.
The matrix has four rows labeled A, B, C, D.
rows
Horizontal lines in the cost matrix representing persons or agents.
Set of horizontal lines in the matrix
The speaker mentions 'number of columns' and 'four columns'.
The matrix has four columns labeled 1, 2, 3, 4.
columns
Vertical lines in the cost matrix representing jobs or tasks.
Set of vertical lines in the matrix
The speaker says 'subtract the minimum entry of each row'.
Calculations like , are performed.
minimum entry
The smallest numerical value found within a specific row of the cost matrix.
Real numbers present in the matrix
The handwritten matrices use row labels A, B, C, and D.
A, B, C, D
Row labels of the cost matrix, representing persons or jobs in the assignment problem.
Set of four row indices.
The handwritten matrices use column labels 1, 2, 3, and 4.
1, 2, 3, 4
Column labels of the cost matrix, representing jobs or persons in the assignment problem.
Set of four column indices.
The Step 1 matrix is written as a 4x4 array with rows , , , .
Step 1 matrix
The matrix obtained after row reduction, used as input for column reduction.
4x4 nonnegative integer matrix.
The Step 2 matrix is filled progressively and ends as rows , , , .
Step 2 matrix
The matrix obtained after column reduction from the Step 1 matrix.
4x4 nonnegative integer matrix.
Rows of both matrices are labeled A, B, C, D.
The speaker refers to them as persons A, B, C, and D.
A, B, C, D
Persons (rows) in the assignment problem.
Set of 4 persons.
Columns of both matrices are labeled 1, 2, 3, 4.
The speaker refers to them as jobs 1, 2, 3, and 4.
1, 2, 3, 4
Jobs (columns) in the assignment problem.
Set of 4 jobs.
A 4x4 matrix with entries like 10, 12, 19, 11 is shown at the top of the page.
Cost Matrix
Original matrix containing the cost of assigning each person to each job.
4x4 matrix of non-negative integers.
A 4x4 matrix under 'Step 2: Column Reduction' containing zeros and positive integers.
Reduced Matrix
Matrix after row and column reductions in the Hungarian method.
4x4 matrix of non-negative integers.
The top matrix is labeled with rows A, B, C, D under the heading Persons.
A, B, C, D
Person labels (rows) in the assignment cost matrix.
Row indices of the cost matrix.
Speaker defines balanced and unbalanced assignment problems based on the equality of rows and columns.
The title 'BALANCED ASSIGNMENT PROBLEM' is written at the top.
An assignment problem is considered balanced if the number of rows (persons) is equal to the number of columns (jobs). If they are not equal, it is an unbalanced assignment problem.
Number of rows equals number of columns for a balanced problem.
Speaker states 'we have to follow the Hungarian method in order to solve this problem'.
The Hungarian method is an algorithm used to solve assignment problems optimally.
Applicable to balanced assignment problems.
Speaker explains 'First we have to do the row reduction. That is, we have to subtract the minimum entry of each row from all the entries of the respective row'.
A new empty matrix is drawn below the original one to record the reduced values.
The first step of the Hungarian method involves finding the minimum element in each row of the cost matrix and subtracting that minimum value from every element in the same row.
Requires the original cost matrix.
The page heading reads 'Solution: This is a balanced assignment problem.'
The speaker discusses assigning each job to one person, consistent with an assignment problem setup.
The video treats the given 4x4 cost table as a balanced assignment problem, meaning the number of rows equals the number of columns so that a one-to-one assignment can be sought.
The cost matrix is square (same number of rows and columns).
Each job is to be assigned to exactly one person.
'Next we have to move on to the next step, which is column reduction.'
'Now we shall consider the first column. The least element of this column has to be subtracted from the other elements.'
The presenter writes a new 4x4 matrix under 'Step 2 : Column Reduction' by subtracting column minima from the Step 1 matrix.
After row reduction, the next step is column reduction: for each column of the current matrix, identify the smallest entry and subtract that minimum from every entry in the same column. This produces a new matrix while preserving the relative differences within each column.
Apply to the matrix obtained after row reduction.
Subtract the minimum separately for each column.
'Now we have to go to step three.'
'We have to start with first row of the matrix received in this step and we have to start examine how many zeros it has.'
'So now we have to check that each row and column has one zero.'
The pen points across rows of the Step 2 matrix while the speaker counts zeros row by row.
The next step after column reduction is to inspect the reduced matrix row by row and count how many zeros each row contains. The speaker states that the goal is to ensure each row and column has one zero before making assignments.
Use the matrix obtained after column reduction.
Examine rows sequentially and count zeros in each row.
Text 'Step 2: Column Reduction' is visible above the matrix.
Speaker explains selecting zeros and striking out corresponding zeros in the same column.
In the column reduction step of the Hungarian method, zeros are selected such that each row and column has exactly one selected zero. When a zero is selected for a row, other zeros in its column are struck out to prevent multiple assignments to the same job.
The matrix must be square or balanced.
Each row and column must have exactly one selected zero for an optimal assignment.
Speaker states 'job has been assigned to all the persons' and lists the assignments.
Circled zeros appear at positions (A,2), (B,3), (C,4), and (D,1).
Once a set of independent zeros covering all rows and columns is found, the corresponding positions give the optimal assignment. Each circled zero represents assigning that row's person to that column's job.
There must be exactly n independent zeros in an n x n matrix.
The text 'This is a balanced assignment Problem' is written on the paper.
An assignment problem is considered balanced when the number of persons (or sources) equals the number of jobs (or destinations). In this video, there are 4 persons and 4 jobs, making it a balanced problem.
Number of persons = Number of jobs
The text 'Step 1 : Row Reduction' is written above the second matrix.
The completed row-reduced matrix is visible; comparison with the original table gives row minima 10, 5, 11 and 8.
The first step in the Hungarian method for solving an assignment problem. It involves finding the minimum element in each row of the cost matrix and subtracting this minimum value from all elements in that same row.
Applied to the initial cost matrix.
The text 'Step 2 : Column Reduction' is written above the third matrix.
The second step in the Hungarian method. It involves taking the matrix resulting from the row reduction, finding the minimum element in each column, and subtracting this minimum value from all elements in that same column.
Applied to the row-reduced matrix.
Zeros in the column-reduced matrix are circled or crossed out to select one zero per row and column. The selected assignments are listed in a table: Person A to Job 2, B to Job 3, C to Job 4, D to Job 1.
After row and column reductions, zeros in the matrix represent potential optimal assignments. The goal is to select a set of zeros such that there is exactly one selected zero in each row and each column. This is done by circling a zero and crossing out other zeros in the same row and column, repeating until all rows/columns are covered.
The matrix must have been reduced using row and column reduction steps.
'Now the idea of the problem is each job has to be assigned to a one person.'
In the assignment problem being solved, each job must be assigned to exactly one person.
The problem is a balanced assignment problem.
For every job, there is exactly one assigned person.
'So now we have to check that each row and column has one zero.'
The speaker states this as the checking condition, but does not fully justify why this condition is sufficient at this moment in the clip.
Before proceeding to select assignments, the reduced matrix should be checked so that each row and column has one zero.
The matrix has already undergone row reduction and column reduction.
For each row and each column of the reduced matrix.
Speaker calculates , , , .
Values 0, 2, 9, 1 are written in the first row of the new matrix.
Subtract the minimum element (10) from the first element of row A.
Row reduction rule.
Subtract the minimum element (10) from the second element of row A.
Row reduction rule.
Subtract the minimum element (10) from the third element of row A.
Row reduction rule.
Subtract the minimum element (10) from the fourth element of row A.
Row reduction rule.
The reduced first row is [0, 2, 9, 1].
Speaker calculates , , , .
Values 0, 5, 2, 3 are written in the second row of the new matrix.
Subtract the minimum element (5) from the first element of row B.
Row reduction rule.
Subtract the minimum element (5) from the second element of row B.
Row reduction rule.
Subtract the minimum element (5) from the third element of row B.
Row reduction rule.
Subtract the minimum element (5) from the fourth element of row B.
Row reduction rule.
The reduced second row is [0, 5, 2, 3].
Speaker calculates , , , .
Values 1, 3, 2, 0 are written in the third row of the new matrix.
Subtract the minimum element (11) from the first element of row C.
Row reduction rule.
Subtract the minimum element (11) from the second element of row C.
Row reduction rule.
Subtract the minimum element (11) from the third element of row C.
Row reduction rule.
Subtract the minimum element (11) from the fourth element of row C.
Row reduction rule.
The reduced third row is [1, 3, 2, 0].
Speaker starts calculating , .
Values 0, 4 are written in the fourth row of the new matrix before the video ends.
The calculation for the last two elements of row D is cut off by the end of the video.
Subtract the minimum element (8) from the first element of row D.
Row reduction rule.
Subtract the minimum element (8) from the second element of row D.
Row reduction rule.
The reduced fourth row starts with [0, 4, ...].
The speaker explains subtracting the least element of each column from all elements of that column.
The Step 2 matrix is filled column by column from the Step 1 matrix.
Start from the Step 1 matrix shown on the page.
Observed directly from the handwritten matrix.
For column 1, the least element is 0, so subtracting 0 leaves the column unchanged.
Column minimum rule stated by the speaker.
For column 2, the least element is 2.
Column minimum rule stated by the speaker.
Subtract 2 from every entry in column 2 to obtain the new column 2 entries.
Arithmetic subtraction from the identified column minimum.
For column 3, the least element is 2.
Column minimum rule stated by the speaker.
Subtract 2 from every entry in column 3 to obtain the new column 3 entries.
Arithmetic subtraction from the identified column minimum.
For column 4, the least element is 0, so the column remains unchanged.
Column minimum rule stated by the speaker.
Combine the transformed columns to form the Step 2 matrix.
Assembly of the column-wise results.
The column-reduced matrix is [[0,0,7,1],[0,3,0,3],[1,1,0,0],[0,2,1,1]].
The speaker examines the first, second, third, and last rows and notes that each has two zeros.
The pen points to the rows of the Step 2 matrix while counting zeros.
Inspect row A of the Step 2 matrix.
Direct reading from the displayed matrix.
Row A contains two zeros, so the speaker says not to select either zero yet.
Counting zero entries in the row.
Inspect row B of the Step 2 matrix.
Direct reading from the displayed matrix.
Row B also contains two zeros.
Counting zero entries in the row.
Inspect row C of the Step 2 matrix.
Direct reading from the displayed matrix.
Row C also contains two zeros.
Counting zero entries in the row.
Inspect row D of the Step 2 matrix.
Direct reading from the displayed matrix.
The spoken explanation says the last row is checked next; visually the displayed row D has one zero.
Counting zero entries in the row.
The first three rows each contain two zeros, so the speaker postpones selecting assignments from those rows within this clip.
Speaker narrates the process of selecting zeros and striking out others row by row.
Visual progression of circles and crosses on the matrix cells.
Identify the only zero in row D at column 1. Circle it and strike out other zeros in column 1 (at A,1 and B,1).
Row D has only one available zero, forcing the assignment D->1.
Identify the remaining available zero in row A at column 2. Circle it.
The zero at A,1 was struck out, leaving A,2 as the only option for row A.
Identify the only zero in row B at column 3. Circle it.
Row B has only one zero remaining after previous strikes.
Identify the remaining available zero in row C at column 4. Circle it and strike out the zero at C,3.
Column 3 already has an assignment (B->3), so C must take column 4.
The optimal assignments are A->2, B->3, C->4, and D->1.
The speaker says, 'the total minimum cost, you have to add all this and you have to find. So when we add all this, we get rupees 38 as the total optimum cost.'
A table lists the original costs for the selected assignments: A->2 is 12, B->3 is 7, C->4 is 11, D->1 is 8. The sum is written as 'Total Optimum Cost = Rs 38'.
Sum the original costs corresponding to the optimal assignments identified from the reduced matrix.
The total cost of an assignment plan is the sum of the individual costs of each person-job pair.
The result of the addition is 38.
Arithmetic calculation.
The total optimum cost for the given assignment problem is Rs 38.
A 4x4 cost matrix is provided with persons A, B, C, D and jobs 1, 2, 3, 4.
Speaker walks through the row reduction process for this specific matrix.
Solve the given 4x4 assignment problem using the Hungarian method.
Cost matrix: Row A [10, 12, 19, 11], Row B [5, 10, 7, 8], Row C [12, 14, 13, 11], Row D [8, 12, 11, 9]
Perform row reduction on the cost matrix.
Find the smallest number in each row.
Definition of minimum element.
Apply the row reduction rule to create a new matrix.
Row reduction step of the Hungarian method.
The partially reduced matrix has rows A [0, 2, 9, 1], B [0, 5, 2, 3], C [1, 3, 2, 0], and D starting with [0, 4, ...].
Visual check of the written numbers in the new matrix against the calculated subtractions.
The full worked example is written on paper from the Step 1 matrix to the Step 2 matrix.
The speaker narrates each column minimum and subtraction.
Given the row-reduced matrix [[0,2,9,1],[0,5,2,3],[1,3,2,0],[0,4,3,1]], perform column reduction.
Step 1 matrix: , , , .
Rows labeled A, B, C, D and columns labeled 1, 2, 3, 4.
Obtain the Step 2 matrix by subtracting the minimum element of each column from all entries in that column.
The least element in column 1 is 0, so column 1 is unchanged.
Column reduction rule.
The least element in column 2 is 2.
Column reduction rule.
Subtract 2 from each entry of column 2.
Arithmetic subtraction.
The least element in column 3 is 2.
Column reduction rule.
Subtract 2 from each entry of column 3.
Arithmetic subtraction.
The least element in column 4 is 0, so column 4 is unchanged.
Column reduction rule.
Assemble the transformed columns into the final Step 2 matrix.
Combining column-wise results.
[[0,0,7,1],[0,3,0,3],[1,1,0,0],[0,2,1,1]]
Each column of the result contains at least one zero, matching the stated purpose of column reduction.
The speaker checks rows one by one and comments on the number of zeros.
The pen points to rows A, B, and C of the Step 2 matrix.
After column reduction, inspect the matrix to see how many zeros each row contains before making assignments.
Step 2 matrix: , , , .
Determine whether any row can be assigned immediately based on the zero count.
Row A is (0,0,7,1), so it contains zeros in columns 1 and 2.
Direct counting from the matrix.
Because there are two zeros, the speaker postpones selection.
Stated in the audio.
Row B is (0,3,0,3), so it contains zeros in columns 1 and 3.
Direct counting from the matrix.
Row C is (1,1,0,0), so it contains zeros in columns 3 and 4.
Direct counting from the matrix.
Since the first three rows each have two zeros, the speaker proceeds to inspect row D.
Stated in the audio.
Rows A, B, and C each contain two zeros, so no assignment is selected from those rows within this clip.
The conclusion follows directly from the displayed Step 2 matrix.
Full problem setup and solution steps are written on the paper.
Speaker explains the steps and reads out the final assignments and a cost value.
The final total minimum cost calculation is not completed within the clip.
Find the optimal assignment and minimum cost for 4 persons (A, B, C, D) and 4 jobs (1, 2, 3, 4) given the cost matrix.
Cost Matrix: , , , .
Reduced Matrix after Row and Column Reductions is provided.
Determine the optimal person-job assignments and calculate the total minimum cost.
Apply column reduction logic: select independent zeros in the reduced matrix.
Hungarian method requires finding n independent zeros.
Assignments found: A->Job 2, B->Job 3, C->Job 4, D->Job 1.
Derived from the circled zeros in the reduced matrix.
Look up original costs for these assignments: Cost(A,2)=12, Cost(B,3)=7, Cost(C,4)=11, Cost(D,1)=8.
Total cost must be calculated from the original cost matrix, not the reduced one.
Optimal assignments: A to Job 2, B to Job 3, C to Job 4, D to Job 1. The original costs sum to rupees, as written on the board near the end.
Check that each person and job is used exactly once and costs match the original matrix.
The entire video demonstrates the solution to a specific 4x4 assignment problem.
Find the optimal assignment of 4 persons (A, B, C, D) to 4 jobs (1, 2, 3, 4) that minimizes the total cost, given the following cost matrix: A: [10, 12, 19, 11] B: [5, 10, 7, 8] C: [12, 14, 13, 11] D: [8, 12, 11, 9]
A 4x4 cost matrix representing the cost of assigning each person to each job.
Determine the optimal person-to-job assignments and the corresponding total minimum cost.
Identify the minimum value in each row of the initial cost matrix.
Definition of the row reduction step.
Subtract the row minimum from each element in its respective row.
Application of the row reduction formula.
Identify the minimum value in each column of the row-reduced matrix.
Definition of the column reduction step.
Subtract the column minimum from each element in its respective column.
Application of the column reduction formula.
Select zeros from the column-reduced matrix such that there is one per row and column. The video shows circling A2, crossing out other zeros in row A and col 2; circling B3, crossing out others; circling C4; circling D1.
Method for finding the optimal assignment from the reduced matrix.
Sum the original costs for the selected assignments (A->2 is 12, B->3 is 7, C->4 is 11, D->1 is 8).
Calculation of the final objective function value.
The optimal assignments are Person A to Job 2, Person B to Job 3, Person C to Job 4, and Person D to Job 1. The total optimum cost is Rs 38.
The sum of the selected original costs () correctly equals the stated total optimum cost of 38.
A hand draws a new 4x4 grid below the original matrix and fills it with calculated values row by row.
Original cost matrix
New empty grid
Pen
Calculated numbers
New grid is drawn
Numbers are written into the grid sequentially from top-left to bottom-right
The original cost matrix remains unchanged at the top
The visual event demonstrates the practical application of the row reduction step, showing how the new matrix is constructed from the original data.
The camera shows a handwritten solution sheet with an original 4x4 table at top, then 'Step 1 : Row Reduction', then 'Step 2 : Column Reduction'.
Original 4x4 cost table
Heading 'Solution: This is a balanced assignment problem'
Step 1 matrix
Step 2 matrix
Pen and hand
The view shifts downward as the presenter writes the Step 2 matrix.
The Step 2 matrix is filled column by column.
Later the pen points across rows of the completed Step 2 matrix.
The row labels remain A, B, C, D.
The column labels remain 1, 2, 3, 4.
The Step 1 matrix stays visible above the Step 2 matrix.
The visual structure shows the sequential Hungarian-method workflow from the original problem to row reduction, then column reduction, then zero inspection.
The hand writes entries into the Step 2 matrix one column at a time.
Empty Step 2 grid
Step 1 matrix
Pen
Column 1 is copied as 0,0,1,0.
Column 2 is written as 0,3,1,2.
Column 3 is written as 7,0,0,1.
Column 4 is written as 1,3,0,1.
The matrix size remains 4x4.
The row and column labels do not change.
The animation makes explicit that column reduction is performed independently on each column of the Step 1 matrix.
The pen points to successive rows of the completed Step 2 matrix while the speaker counts zeros.
Completed Step 2 matrix
Pen tip
Attention moves from row A to row B to row C and then toward the last row.
The matrix entries themselves do not change during this inspection.
This visual sequence corresponds to the next algorithmic step: checking how many zeros appear in each row before assignment selection.
Hand uses a pen to draw circles around specific zeros and crosses over others in the lower matrix.
Reduced Matrix
Pen
Circles
Crosses
Zeros are sequentially circled to indicate selection.
Other zeros in the same columns are crossed out to indicate exclusion.
The numerical values in the matrix remain unchanged.
The grid structure remains constant.
The visual marking demonstrates the algorithmic step of isolating a unique assignment for each row and column.
The camera or paper moves upwards, revealing the top section of the page.
Paper
Original Cost Matrix
The view shifts from the solution area to the problem statement area.
The content on the paper is static.
This action is necessary to reference the original costs for the final calculation step.
A hand uses a pen to point to and underline the minimum value in each row of the top cost matrix.
Top cost matrix
Pen
Hand
The pen moves from row to row, pointing to the smallest number in each row, which is then underlined.
The numbers in the matrix do not change during this action.
This visual action demonstrates the process of finding the minimum element in each row, which is the first part of the row reduction step.
The video shows pre-written matrices for 'Step 1: Row Reduction' and 'Step 2: Column Reduction'.
The actual subtraction calculations are not shown being performed; the results are already written.
Row Reduced Matrix
Column Reduced Matrix
The view shifts down the page to show the subsequent matrices in the solution process.
The structure of a 4x4 grid is maintained.
These visuals present the intermediate states of the cost matrix after applying the row and column reduction rules of the Hungarian method.
Circles are drawn around specific zeros in the 'Column Reduction' matrix, and other zeros in the same row/column are crossed out.
Column Reduced Matrix
Circles
Crosses
Specific zero elements are marked with circles to indicate selection, while conflicting zeros are marked with crosses.
The numerical values in the matrix remain unchanged.
This visual process illustrates how to choose a set of independent zeros from the reduced matrix, which corresponds to the optimal assignment of persons to jobs.
'And so if we see in this row, there are two zeros. So let us not select any of the zero.'
One might think any zero in the reduced matrix can be chosen right away for assignment.
The speaker explicitly postpones selection when a row contains two zeros, indicating that immediate assignment should wait until the zero pattern is more constrained.
Speaker explicitly says 'we have to see the cost value from the original given matrix'.
Students might mistakenly sum the values from the reduced matrix (which are mostly zeros) to find the total cost.
The total minimum cost must always be calculated by summing the corresponding entries from the ORIGINAL cost matrix.
Speaker states that after confirming it is a balanced problem, they will follow the Hungarian method.
Confirming the problem is balanced is a necessary preliminary step before applying the standard Hungarian method.
Speaker introduces row reduction as the first thing to do when following the Hungarian method.
Row reduction is a specific step contained within the broader procedure of the Hungarian method.
The page labels the problem as balanced and then proceeds through Step 1 and Step 2.
The speaker moves from the balanced-problem setup to column reduction.
The column-reduction method is applied because the problem has been identified as a balanced assignment problem and already passed through row reduction.
'Now we have to go to step three' immediately after finishing the Step 2 matrix.
The zero inspection is performed on the Step 2 matrix.
The zero-counting step uses the matrix produced by column reduction as its input.
The speaker links the zero check to the requirement that each job be assigned to one person and that each row and column have one zero.
The row-and-column zero check is presented as a way to enforce the one-to-one assignment requirement.
The entire clip shows steps labeled 'Step 1' and 'Step 2' typical of this method.
Column reduction and finding independent zeros is a prerequisite step before extracting the optimal assignment.
The solution is presented sequentially as 'Step 1: Row Reduction' followed by 'Step 2: Column Reduction'.
The column reduction step is applied to the matrix that has already undergone row reduction.
The optimal assignments are selected from the zeros present in the 'Column Reduction' matrix.
The selection of the optimal assignment is based on the pattern of zeros created by the preceding reduction steps.
Speaker defines balanced and unbalanced problems.
Speaker explains and demonstrates row reduction.
The speaker defines and demonstrates column reduction.
The Step 2 matrix is constructed from the Step 1 matrix.
The page shows 'Step 1 : Row Reduction' followed by 'Step 2 : Column Reduction'.
'we have to consider the matrix that we have obtained in step one'
'there are two zeros. So let us not select any of the zero.'
Heading: 'This is a balanced assignment problem.'
'each job has to be assigned to a one person.'
'Now we have to go to step three... examine how many zeros it has.'
Speaker explains how to select zeros row by row.
Speaker mentions looking at the original matrix for costs.
The video shows the full procedure for solving an assignment problem.
The section labeled 'Step 1: Row Reduction' explains this concept.
The speaker explains how to calculate the total minimum cost by adding the original costs of the selected assignments.
Covered · Introduction and definition of balanced assignment problem.
Covered · Explanation and execution of the row reduction step.
Covered · The page shows the balanced assignment problem heading and the completed Step 1 matrix while the speaker finishes writing the last entry of row D.
Covered · The speaker introduces column reduction and works through all four columns to build the Step 2 matrix.
Covered · The speaker moves to step three, explains the one-job-one-person idea, and inspects rows A, B, C, and the last row for zeros.
Covered · Explanation and visual demonstration of selecting independent zeros in the reduced matrix.
Covered · Listing the final assignments derived from the marked zeros.
Covered · Referencing the original cost matrix to begin calculating the total minimum cost.
Covered · Identification of the problem type and explanation of the row reduction step.
Covered · Explanation of the column reduction step and selection of optimal assignments from the reduced matrix.
Covered · Calculation and statement of the total optimum cost.
Reviewed English material v20, 0:00-0:44: the board presents a 4x4 person-job cost table and calls it balanced because the numbers of persons and jobs match.
Reviewed English material v20, 0:44-6:47: row minima 10,5,11,8 and column minima 0,2,2,0 lead to independent zeros A-2, B-3, C-4, D-1; original costs sum to 38 rupees.
To select independent zeros, scan the reduced matrix for rows or columns with only one available zero. Circle that zero and strike out other zeros in the same row and column.
Conditions: The matrix has been reduced using row and column operations.; The goal is to find n independent zeros for an n x n matrix.
The presenter avoids selecting a zero when a row has two zeros because the goal is to find a set of independent zeros where each row and column has exactly one selected zero. Choosing arbitrarily from a row with multiple zeros might lead to conflicts later, so the process is postponed until the zero pattern is more constrained.
Conditions: The matrix has undergone row and column reduction.; The goal is to find an optimal assignment.
A balanced assignment problem means that the number of rows (persons) is equal to the number of columns (jobs). This allows for a one-to-one assignment where each person is assigned to exactly one job.
Conditions: The cost matrix is square (same number of rows and columns).; Each job is to be assigned to exactly one person.
Column reduction is the second step of the Hungarian method. It involves taking the matrix obtained after row reduction, finding the minimum element in each column, and subtracting this minimum value from all elements in that same column.
Conditions: The matrix must have already undergone row reduction.; The problem is a balanced assignment problem.
To calculate the total cost, you must look at the original cost matrix, not the reduced matrix. Identify the positions of the circled zeros in the reduced matrix, find the corresponding entries in the original matrix, and sum those values.
Conditions: The optimal assignment has been determined from the reduced matrix.; The original cost matrix is available.
The purpose of step three is to inspect the reduced matrix row by row and count how many zeros each row contains. This helps determine if a unique assignment can be made or if further steps are needed to isolate independent zeros.
Conditions: The matrix has undergone row and column reduction.; The goal is to find an optimal assignment.
The total optimum cost is calculated by summing the original costs corresponding to the selected optimal assignments. You take the person-job pairs identified from the reduced matrix and add up their values from the initial cost matrix.
Conditions: The optimal assignments have been identified.; The original cost matrix is known.
To perform row reduction, identify the minimum entry in each row of the cost matrix and subtract that minimum value from every element in the same row. This creates a new matrix where each row contains at least one zero.
Conditions: The problem is a balanced assignment problem.; The Hungarian method is being applied.
Continue with related videos in the same subject.
YouTube9:59
YouTube3:03
YouTube7:39