The Hungarian method is used to solve. Hungarian method for solving assignment problems
Step 1.(Reduction of rows and columns). Target this step consists in obtaining the maximum possible number of zero elements in the cost matrix. To do this, the minimum element of the corresponding row is subtracted from all elements of each row, and then the minimum element of the corresponding column is subtracted from all elements of each column of the resulting matrix. As a result, a reduced cost matrix is obtained and proceeds to searching for assignments.
Step 2.(Definition of assignments). At this step, you can use the algorithm for finding the “largest matching with a matrix of a bipartite graph (there are other possibilities), if all =0 of the matrix are replaced with “1”, and >0 with “0”.
If the full purpose cannot be found, then further modification of the cost matrix is necessary, i.e. go to step 3.
Step 3. (Modification of the reduced matrix). For the reduced cost matrix:
a) Calculate the number of zeros in each uncrossed row and each uncrossed column.
b) Cross out the row or column with the maximum number of zeros.
c) Carry out steps a) and b) until all zeros are crossed out.
d) From all uncrossed elements, subtract the minimum uncrossed element and add it to each element located at the intersection of two lines.
Go to step 2.
Note 3.If original problem is a maximization problem, then all elements of the cost matrix should be multiplied by (-1) and added with sufficient a large number so that the matrix does not contain negative elements. The problem should then be solved as a minimization problem.
Example 13.5. Let us demonstrate the operation of the Hungarian algorithm using the example of an assignment problem with the following cost matrix:
Iteration 1
Step 1. Reduction of rows and columns.
The values of the minimum elements of rows 1, 2, 3 and 4 are 2, 4, 11 and 4 respectively. By subtracting from the elements of each row the corresponding minimum value, we get the following matrix:
The values of the minimum elements of columns 1, 2, 3 and 4 are 0, 0, 5 and 0 respectively. Subtracting the corresponding minimum value from the elements of each column, we obtain the following matrix.
Step 2. Search feasible solution, for which all assignments have zero cost. We use an algorithm for finding the largest matching. Let's transform the matrix into a matrix of a bipartite graph, then into worksheet:
Finding a matching:
This matching is not perfect, i.e. there is no full purpose. On to Step 3.
Step 3. Modification of the reduced matrix.
a) The number of zeros in lines 1, 2, 3 and 4 is 1, 1, 2 and 1, respectively. For columns, the corresponding values are 2, 1, 1, and 1.
b) The maximum number of zeros, two each, are contained in line 3 and column 1. Select line 3 and cross out all its elements horizontal line.
c) The number of uncrossed zeros in lines 1, 2 and 4 is 1, 1 and 1, respectively. For columns, the corresponding values are 2, 1, 0, and 0. Therefore, we must select column 1 and cross it out with a vertical line. After this, there will only be one uncrossed zero left - element (2,2). Therefore, you can cross out either row 2 or column 2. Crossing out row 2 with a horizontal line, we get the following matrix:
d) The value of the minimum uncrossed element is 2. Subtracting it from all uncrossed elements and adding it with all elements located at the intersection of two lines, we get new matrix costs.
Task: Solve the maximum assignment problem.
We will not give any verbal conditions, they can be different, for example, “6 candidates are being hired for 6 vacancies and they received appropriate assessments during the interview for each vacancy, recruit candidates for six vacancies so that the total assessment of the candidates is maximum” or “six machines perform six jobs in the time specified in the table, compose production plan..." We will assume that we have a matrix (payment, time, etc.) and we need to solve the problem of assignments using the Hungarian method to the maximum, i.e. select one cell in a row and column so that the sum is maximum.
Solution:
Step 1:
Comment: The first step is required only to solve the problem to the maximum; if you need to solve it to the minimum, then skip it.
Let's transform the matrix by replacing each element of the matrix with the difference between the maximum element of this row and the element itself.
Subtract 
Step 2.
You want to get zeros in every row and every column. There are no zeros in the third, fifth and sixth columns; subtract the minimum element of the corresponding column from the elements of these columns.
Subtract 
Step 3.
We have obtained a matrix in which there is a zero in each row and each column. Our goal is to mark one cell in each row and each column so that they are zero. In this matrix, only the first four rows and columns satisfy this requirement. Let's mark the corresponding cells with a frame.
Let us mark as “dissatisfied row” the 5th, in which we could not mark such a zero, and the second column, it contains a zero in the fifth line. But the second column also contains a zero in the first row, so let’s mark that as “dissatisfied.” The first line no longer contains zeros, i.e. The process of marking the dissatisfied rows is completed, and we have a situation called “bottleneck”.
In the table we will mark dissatisfied rows and columns with asterisks, and the number next to the asterisk will indicate the order of marking (for a better understanding of the process).
Let's select the minimum element in the marked rows outside the marked rows. It's the 3 that's in the fifth column and the fifth column.
Subtract this element from the marked rows and add it to the resulting columns.
Let's follow these steps and notice that we can now mark a zero in the fifth row and fifth column.
Step 4.
Another zero is missing in the 6th line. Let's mark it as dissatisfied, it has a zero in the first column, mark it as dissatisfied, it, in turn, contains a zero in the second row, mark it, but it does not contain more zeros, the marking process is legal.
- Tutorial
Hello friends! In this article I would like to talk about an interesting algorithm from the discipline “Operations Research”, namely Hungarian method and how to use it to solve assignment problems. I’ll touch a little on the theories about in what cases and for what tasks it’s applicable. this algorithm, I’ll analyze it step by step using a fictitious example, and share my modest sketch of the code for its implementation in the R language. Let’s get started!
A few words about the method
In order not to describe a lot of theory with mathematical terms and definitions, I propose to consider a couple of options for constructing the assignment problem, and I think you will immediately understand in what cases the Hungarian method is applicable:- The problem of assigning workers to positions. It is necessary to distribute workers to positions so that maximum efficiency, or were minimum costs to work.
- Assignment of machines to production sections. The distribution of machines so that when they operate, production is as profitable as possible, or the cost of maintaining them is minimal.
- Selecting candidates for different vacancies based on assessments. We will look at this example below.
As a result, the problem must be solved so that one performer (person, machine, tool, ...) can perform only one job, and each job is performed by only one performer.
Necessary and sufficient condition solving a problem is its closed type. Those. when the number of performers = the number of works (N=M). If this condition is not met, then you can add fictitious performers, or fictitious works, for which the values in the matrix will be zero. This will not affect the solution of the problem in any way, it will only give it the necessary closed type.
Step-by-step algorithm as an example
Formulation of the problem: Let there be an important Scientific Conference. To conduct it, you need to set up sound, light, images, register guests and prepare for breaks between performances. There are 5 organizers for this task. Each of them has certain ratings for the performance of a particular job (let’s assume that these ratings are set as the arithmetic average of the reviews of their employees). It is necessary to distribute the organizers so that their total score is maximum. The task looks like this:
If the problem is solved to the maximum (as in our case), then in each row of the matrix it is necessary to find the maximum element, subtract it from each element of the corresponding row and multiply the entire matrix by -1. If the problem is solved at a minimum, then this step must be skipped.
There must be only one selected zero in each row and each column. (i.e. when zero is selected, then the remaining zeros in this row or in this column are no longer taken into account). In this case it is impossible to do this:
(If the problem is solved to a minimum, then you need to start from this step). We continue the solution further. Reduction of the matrix by rows (we look for the minimum element in each row and subtract it from each element accordingly):
Because all minimal elements are zero, then the matrix has not changed. We carry out the reduction by columns:
Again, make sure that there is only one selected zero in each column and each row. As can be seen below, in in this case it is impossible to do this. I presented two options for how to select zeros, but neither of them gave the desired result:
We continue the solution further. Cross out rows and columns that contain zero elements ( IMPORTANT! The number of strikeouts should be minimal). Among the remaining elements, we look for the minimum, subtract it from the remaining elements (which are not crossed out) and add it to the elements that are located at the intersection of crossed out rows and columns (what is marked in green is subtracted there; what is marked in gold is summed there; then, We don’t touch what is not painted over):
As you can now see, there is only one selected zero in each column and row. We complete the task!
We substitute the locations of the selected zeros into the initial table. Thus we obtain the optimum, or optimal plan, in which the organizers are distributed among the works and the sum of marks is the maximum:
If you are solving a problem and it is still impossible to choose zeros so that there is only one in each column and row, then we repeat the algorithm from the place where the reduction was carried out along the lines (the minimum element in each line).
Implementation in the R programming language
The Hungarian algorithm was implemented using recursions. I hope that my code will not cause any difficulties. First, you need to compile three functions, and then begin the calculations.The data for solving the problem is taken from the example.csv file, which looks like:
#We connect the library for the convenience of calculations library(dplyr) #Read the csv file (the first column is the names of the rows; the first line is the names of the columns) table<- read.csv("example.csv",header=TRUE,row.names=1,sep=";")
#Проводим расчеты
unique_index <- hungarian_algorithm(table,T)
#Выводим
cat(paste(row.names(table)," - ",names(table)),sep = "\n")
#Считаем оптимальный план
cat("Оптимальное значение -",sum(mapply(function(i, j) table, unique_index$row, unique_index$col, SIMPLIFY = TRUE)))
#____________________Алгоритм венгерского метода__________________________________
hungarian_algorithm <- function(data,optim=F){
#Если optim = T, то будет искаться максимальное оптимальное значение
if(optim==T)
{
data <- data %>% apply(1,function(x) (x-max(x))*(-1)) %>% t() %>% as.data.frame() optim<- F
}
#Редукция матрицы по строкам
data <- data %>% apply(1,function(x) x-min(x)) %>% t() %>% as.data.frame() #Finding the indices of all zeros zero_index<- which(data==0, arr.ind = T)
#Нахождение всех "неповторяющихся" нулей слева-направо
unique_index <- from_the_beginning(zero_index)
#Если количество "неповторяющихся" нулей не равняется количеству строк в исходной таблице, то..
if(nrow(unique_index)!=nrow(data))
#..Ищем "неповторяющиеся" нули справа-налево
unique_index <- from_the_end(zero_index)
#Если все еще не равняется, то продолжаем алгоритм дальше
if(nrow(unique_index)!=nrow(data))
{
#Редукция матрицы по столбцам
data <- data %>% apply(2,function(x) x-min(x)) %>% as.data.frame() zero_index<- which(data==0, arr.ind = T)
unique_index <- from_the_beginning(zero_index)
if(nrow(unique_index)!=nrow(data))
unique_index <- from_the_end(zero_index)
if(nrow(unique_index)!=nrow(data))
{
#"Вычеркиваем" строки и столбцы которые содержат нулевые элементы (ВАЖНО! количество вычеркиваний должно быть минимальным)
index <- which(apply(data,1,function(x) length(x)>1)) index2<- which(apply(data[-index,],2,function(x) length(x)>0)) #Among the remaining elements we look for the minimum min_from_table<- min(data[-index,-index2])
#Вычитаем минимальный из оставшихся элементов
data[-index,-index2] <- data[-index,-index2]-min_from_table
#Прибавляем к элементам, расположенным на пересечении вычеркнутых строк и столбцов
data <- data+min_from_table
zero_index <- which(data==0, arr.ind = T)
unique_index <- from_the_beginning(zero_index)
if(nrow(unique_index)!=nrow(data))
unique_index <- from_the_end(zero_index)
#Если все еще количество "неповторяющихся" нулей не равняется количеству строк в исходной таблице, то..
if(nrow(unique_index)!=nrow(data))
#..Повторяем весь алгоритм заново
hungarian_algorithm(data,optim)
else
#Выводим индексы "неповторяющихся" нулей
unique_index
}
else
#Выводим индексы "неповторяющихся" нулей
unique_index
}
else
#Выводим индексы "неповторяющихся" нулей
unique_index
}
#_________________________________________________________________________________
#__________Функция для нахождения "неповторяющихся" нулей слева-направо___________
from_the_beginning <- function(x,i=0,j=0,index = data.frame(row=numeric(),col=numeric())){
#Выбор индексов нулей, которые не лежат на строках i, и столбцах j
find_zero <- x[(!x[,1] %in% i) & (!x[,2] %in% j),]
if(length(find_zero)>2)( #Write the row index into vector i<- c(i,as.vector(find_zero))
#Записываем индекс столбца в вектор
j <- c(j,as.vector(find_zero))
#Записываем индексы в data frame (это и есть индексы уникальных нулей)
index <- rbind(index,setNames(as.list(find_zero), names(index)))
#Повторяем пока не пройдем по всем строкам и столбцам
from_the_beginning(find_zero,i,j,index)}
else
rbind(index,find_zero)
}
#_________________________________________________________________________________
#__________Функция для нахождения "неповторяющихся" нулей справа-налево___________
from_the_end <- function(x,i=0,j=0,index = data.frame(row=numeric(),col=numeric())){
find_zero <- x[(!x[,1] %in% i) & (!x[,2] %in% j),]
if(length(find_zero)>2)(i<- c(i,as.vector(find_zero))
j <- c(j,as.vector(find_zero))
index <- rbind(index,setNames(as.list(find_zero), names(index)))
from_the_end(find_zero,i,j,index)}
else
rbind(index,find_zero)
}
#_________________________________________________________________________________
Result of program execution:
Solution algorithm:
1. We solve the problem to the minimum. The goal of this step is to obtain the maximum possible number of zeros in matrix C. To do this, we find the minimum element in matrix C in each row and subtract it from each element of the corresponding row. Similarly, in each column we subtract the corresponding minimum element.
If a non-square matrix is given, then we make it square by setting the costs equal to the maximum number in the given matrix.
2. If after completing the first step it is possible to make assignments, that is, select a zero element in each row and column, then the resulting solution will be optimal. If the appointments could not be made, then proceed to the third step.
3. Using the minimum number of lines, we cross out all the zeros in the matrix and, among the not crossed out elements, select the minimum one, add it to the elements standing at the intersection of the lines and subtract it from all the not crossed out elements. Next, move on to step 2.
The Hungarian method is most effective when solving transport problems with integer volumes of production and consumption.
Example
The assignment problem is a special case of the transport problem, in which ai = bj = 1. Therefore, it can be solved by transport problem algorithms. Let's consider another method, which is more effective and takes into account the specifics of the mathematical model. This method is called the Hungarian algorithm.
It consists of the following steps:
1) transformation of matrix rows and columns;
2) determination of purpose;
3) modification of the transformed matrix.
1st step. The goal of this step is to obtain the maximum possible number of zero elements in matrix C. To do this, subtract the minimum element of the corresponding row from all elements of each row, and subtract the minimum element of the corresponding column from all elements of each column.
2nd step. If, after performing the 1st step, one zero element can be selected in each row and each column of matrix C, then the resulting solution will be an optimal assignment.
3rd step. If an admissible solution consisting of zeros has not been found, then we draw the minimum number of lines through some columns and rows so that all zeros are crossed out. Select the smallest uncrossed element. We subtract this element from each uncrossed out element and add it to each element standing at the intersection of the drawn lines.
If after the 3rd step the optimal solution is not achieved, then the procedure for drawing straight lines should be repeated until an acceptable solution is obtained.
Example.
Distribute resources among objects.
Solution. 1st step. The values of the minimum elements of rows 1, 2, 3 and 4 are 2, 4, 11 and 4 respectively. Subtracting the corresponding minimum value from the elements of each row, we obtain
The values of the minimum elements of columns 1, 2, 3 and 4 are 0, 0, 5, 0 respectively. Subtracting the corresponding minimum value from the elements of each column, we obtain
2nd step. No full assignment has been received and the cost matrix needs to be modified.
3rd step. Cross out column 1, row 3, row 2 (or column 2). The value of the minimum uncrossed element is 2:
We subtract it from all uncrossed out elements and, adding it with all elements located at the intersection of two lines, we get
Answer. We direct the first resource to the 3rd object, the second - to the 2nd object, the fourth - to the 1st object, the third resource - to the 4th object. Destination cost: 9 + 4 + 11 + 4 = 28.
Notes 1. If the original matrix is not square, then you need to introduce fictitious resources or fictitious objects to make the matrix square.
HUNGARIAN METHOD
The Hungarian method is one of the most interesting and most common methods for solving transport problems.
Let us first consider the main ideas of the Hungarian method using the example of solving a choice problem (assignment problem), which is a special case of the T-problem, and then generalize this method for an arbitrary T-problem.
Hungarian method for the assignment problem
Formulation of the problem. Let us assume that there are various jobs and mechanisms, each of which can perform any job, but with unequal efficiency. We denote the performance of the mechanism when performing work, and = 1,...,n; j = 1,...,n. It is required to distribute the mechanisms among the jobs in such a way that the total effect of their use is maximized. This task is called choice problem or assignment problem.
Formally, it is written like this. You must select the following sequence of elements 
from the matrix
so that the sum is maximum and at the same time from each row and column WITH only one element was selected.
Let us introduce the following concepts.
Zero matrix elements WITH are called independent zeros if for any row and column at the intersection of which the element is located does not contain other such elements.
Two rectangular matrices WITH And D are called equivalent ( C ~ D), if for everyone i,j. Assignment problems defined by equivalent matrices are equivalent (that is, the optimal solutions for one of them will be optimal for the second, and vice versa).
Description of the Hungarian method algorithm
The algorithm consists of a preliminary stage and no more than ( n-2) sequential iterations. Each iteration is associated with equivalent transformations of the matrix obtained as a result of the previous iteration, and with the selection of the maximum number of independent zeros. The final result of the iteration is an increase in the number of independent zeros by one. As soon as the number of independent zeros becomes equal n, the selection problem is solved, and the optimal assignment option is determined by the positions of independent zeros in the last matrix.
Preliminary stage. Find the maximum element in j- m column and all elements of this column are sequentially subtracted from the maximum. This operation is performed on all columns of the matrix WITH. The result is a matrix with non-negative elements, each column of which has at least one zero.
Next consider i- th row of the resulting matrix, search for its minimum element a i and subtract the minimum from each element of this row. This procedure is repeated with all lines. As a result, we get the matrix WITH 0 (WITH 0 ~ C), each row and column of which has at least one zero. Described conversion process WITH V WITH 0 is called a matrix reduction.
Find an arbitrary zero in the first column and mark it with an asterisk. Then we look at the second column, and if there is a zero in it located in a row where there is no zero with an asterisk, then we mark it with an asterisk. Similarly, we look through all the columns of the matrix one by one WITH 0 and mark the following zeros with a “*” if possible. Obviously, the zeros of the matrix WITH 0 marked with an asterisk are independent. This concludes the preliminary stage.
(k+1)th iteration. Let's assume that k-th iteration has already been carried out and as a result the matrix is obtained WITHk. If it contains exactly n zeros followed by an asterisk, then the solution process ends. Otherwise we go to ( k+1) -th iteration.
Each iteration starts with the first and ends with the second stage. Between them, a couple of stages can be carried out several times: the third - the first. Before the iteration starts, the “+” sign marks the columns of the matrix WITHk, which contain zeros with asterisks.
First stage. View unselected columns WITHk. If there are no zero elements among them, then proceed to the third stage. If the unselected zero of the matrix WITHk is detected, then one of two cases is possible: 1) a line containing an unselected zero also contains a zero with an asterisk; 2) this line does not contain a zero with an asterisk.
In the second case, we go straight to the second stage, marking this zero with a stroke.
In the first case, this unselected zero is marked with a stroke and the line in which it is contained is highlighted (with a “+” sign to the right of the line). They look through this line, find a zero with an asterisk and destroy the “+” sign from the selection of the column that contains this zero.
Next, they look through this column (which has already become unselected) and look for the unselected zero (or zeros) in which it is located. This zero is marked with a stroke and the line containing such a zero (or zeros) is highlighted. Then they look through this line, looking for a zero with an asterisk in it.
This process, in a finite number of steps, ends with one of the following outcomes:
1) all zeros of the matrix WITHk highlighted, i.e. are in the highlighted rows or columns. In this case, they move on to the third stage;
2) there is an unselected zero in a line where there is no zero with an asterisk. Then they move on to the second stage, marking this zero with a stroke.
Second phase. At this stage, the following chain of matrix zeros is constructed WITHk: a leading zero with a prime, a zero with an asterisk located in the same column as a leading zero with a prime in the same row as a leading zero with an asterisk, etc. So, the chain is formed by moving from 0 " to 0 * along the column, from 0 * to 0 " along the row, etc.
It can be proven that the described algorithm for constructing a chain is unambiguous and finite, and the chain always begins and ends with a zero with a prime.
Next, we place asterisks over the elements of the chain that are in odd places (0 "), destroying them above the even elements (0 *). Then we destroy all the strokes above the elements WITHk and "+" symbols. The number of independent zeros will be increased by one. On this ( k+ 1) -th iteration is completed.
Third stage. They move to this stage after the first if all matrix zeros WITHk highlighted. In this case, among the unselected elements WITHk choose the minimum and designate it h (h>0). Next they subtract h from all matrix elements WITHk located in unselected rows and added to all elements located in selected columns. As a result, a new matrix is obtained WITH "k, equivalent WITHk. Note that with this
transformation, all zeros with an asterisk matrix WITHk remain zeros in WITH " k , in addition, new unselected zeros appear in it. Therefore, we move back to the first stage. Having completed the first stage, depending on its result, they either move on to the second stage or return to the third stage.
After a finite number of repetitions, the next first stage will necessarily end with a transition to the second stage. After its execution, the number of independent zeros will increase by one and ( k+ 1) - the first iteration will be completed.
Example 3.4. Solve assignment problem with matrix
When solving the problem we use the following notation:
The selection sign “+” to be destroyed is circled; The chain, as before, is indicated by arrows.
Preliminary stage. We find the maximum element of the first column - 4. Subtract from it all the elements of this column. Similarly, to obtain the second, third, fourth and fifth columns of the new matrix, we subtract all the elements of these columns from five, three, two and three, respectively. We obtain the matrix WITH "(C"~C). Since in each line WITH " is zero, then WITH " = WITH 0 and the matrix reduction process ends. Next, we look for and mark with “*” independent zeros in WITH 0 starting from the first line.
First iteration. First stage. We highlight the first, second, and fourth columns of the matrix with a “+” sign WITH 0 that contain 0 * .
We look through the unselected third column, find an unselected zero in it WITH 23 = 0, mark it with a stroke and highlight the second line with a “+” sign. We look through this line and find the element in it WITH 22 = 0 * and destroy the selection mark of the second column containing 0 * . Then we look at the second column - there are no unselected elements in it. We move on to the last unselected column (the fifth), looking for unselected zeros in it. Since there are no unselected zeros, we move on to the third stage.
Third stage. Finding the minimum element in the unselected part of the matrix WITH 0 (i.e. elements that lie in columns and rows not marked with a "+" sign). It is equal h = 1.
Subtract h= 1 from all elements of unselected rows (i.e., all except the second) and add to all elements of the selected columns (first and fourth). Let's get the matrix WITH " 1 and move on to the first stage.
First stage. Before starting it, we again highlight the first, second and fourth columns with a “+” sign. We look through the unselected third column, find an unselected zero in it WITH 23 = 0, mark it with a dash sign. Since the second line has 0 * (element WITH 22), then select the second row with a “+” sign, then destroy the selection sign of the second column, where 0 * lies. Then we look at the second column and find an unselected zero in it WITH 12 = 0, mark it with a dash sign. Because the first line has a zero with an asterisk WITH 14 = 0 * , then we highlight it with the “+” sign and destroy the selection sign of the fourth column, where this 0 * sign was located. Then we review the fourth column and find an unselected zero in it WITH 54 = 0. Since there is no zero with an asterisk in the line where it is located, marking this 0 with a stroke, we move on to the second stage.