MECH SHALA's video: Hungarian method for assignment -2

hungarian method to solve assignment problem in operartion research in hindi. The Hungarian method is a combinatorial optimization algorithm which was developed and published by Harold Kuhn in 1955. This method was originally invented for the best assignment of a set of persons to a set of jobs. It is a special case of the transportation problem. The algorithm finds an optimal assignment for a given “n x n” cost matrix. “Assignment problems deal with the question how to assign n items (e.g. jobs) to n machines (or workers) in the best possible way. […] Mathematically an assignment is nothing else than a bijective mapping of a finite set into itself To solve the problem we have to perform the following steps: Step 1 – Subtract the row minimum from each row. Step 2 – Subtract the column minimum from each column from the reduced matrix. tep 3 – Assign one “0” to each row & column. The rule to assign the “0”: - If there is an assignable “0”, only 1 assignable “0” in any row or any column, assign it. - If there are more than 1, leave it and proceed. This rule would try to give us as many assignments as possible. Now there are also cases where you won’t get an optimal solution for a reduced matrix after one iteration. hungarian method Step 1 – Assign one “0” to each row & column. Step 2 – Tick all unassigned row. Step 3 – If a row is ticked and has a “0”, then tick the corresponding column (if the column is not yet ticked). Step 4 – If a column is ticked and has an assignment, then tick the corresponding row (if the row is not yet ticked). Step 5 - Repeat step 5 and 6 till no more ticking is possible. Step 6 – Draw lines through unticked rows and ticked columns. The number of lines represents the maximum number of assignments possible. Step 7 – Find out the smallest number which does not have any line passing through it. We call it Theta. Subtract theta from all the numbers that do not have any lines passing through them and add theta to all those numbers that have two lines passing through them. Keep the rest of them the same. hungarian method https://www.youtube.com/watch?v=KmnMXV6qYQg