Hungarian solution method. Hungarian method for solving assignment problems

Solution algorithm:

1. We solve the problem to the minimum. Target this step- obtaining 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.

Hungarian method 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 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.

The assignment problem

Algorithm for solving the bottleneck assignment problem

Bottleneck assignment problem

LECTURE 13. Assignment problems. Hungarian algorithm

This problem is solved by the algorithm described above. Here is her production.

Available n jobs on some assembly line and n the workers who need to be assigned to these jobs; known performance c ij worker i at work j. The fact that, with some distribution to jobs, a worker i k falls on workplace jk can be described by the following table:

Having a way s assignment to workplaces, you can find the minimum productivity specific to this method and note that it is this minimum productivity that determines the speed and productivity of the conveyor. The workplace where minimum productivity is realized is called bottleneck in assignment.

The goal is to maximize

Step 0. We fix the productivity matrix and any assignment to jobs. Let s- minimum performance for this purpose. Let's build worksheet the same dimensions as the matrix C; in a cell with a number ( ij) in this table we will put the symbol “´” if ; otherwise we will leave this cell empty.

Step 1. Considering the worksheet constructed in the previous step as a worksheet in the algorithm for selecting the largest matching in a bipartite graph, we will find the corresponding largest matching. If it turns out n ribs, then a new assignment to jobs is restored along them and with a new, higher, minimum performance. Let us denote it again by s and back to Step 0. If the number of edges is less n, then the existing assignment to jobs is already optimal.

Problem statements:

Example 13.1. Required to distribute m works (or performers) on n machines. Job i (i=1,...,m), performed on a machine j(j=1,..., n), is associated with costs. The task consists of distributing work across machines (one job is performed on one machine) that corresponds to minimizing total costs c ij.

Example 13.2. C=(c ij) – cost of production of the part i on the machine j you need to find the distribution of machines so that the total cost of production is minimal.

Example 13.3. Transport problem. Points of production of goods and points of consumption of goods are specified. It is required to determine the optimal one-to-one correspondence between points of production and points of consumption, based on the transportation cost matrix C between relevant points (i.e., minimize the total cost of transportation).

Here the works represent the “origin points” and the machines represent the “destination points”. Supply at each source point is equal to 1. Likewise, demand at each destination point is equal to 1. The cost of “transporting” (attaching) the work i to the machine j equal to c ij. If some work cannot be done on a certain machine, then the corresponding cost is taken to be very a large number.

Before solving such a problem, it is necessary to eliminate the imbalance by adding fictitious work or machines depending on the initial conditions. Therefore, without loss of generality we can put m = n.

Let = 0 if j-my work is not being done on i-th machine, = 1, if j-I work is performed on i-th machine. Thus, the solution to the problem can be written in the form two-dimensional array. A feasible solution is called appointment. A feasible solution is constructed by choosing exactly one element in each row of a matrix and exactly one element in each column of that matrix.

Note 1 . For a given value n exists n! feasible solutions.

Mathematical model tasks:

Minimize function , with restrictions:

, (12.1)

, (12.2)

Constraints (12.1) are necessary to ensure that each job is performed exactly once. Constraints (12.2) guarantee that each machine will be assigned exactly one job.

Example 13.4. To illustrate the assignment problem, consider a table with three jobs and three machines. Part production cost i on the machine j :

We need to find the distribution of machines so that the total cost of production is minimal.

The specific structure of the assignment problem makes it possible to use effective method to solve it.

Note 2. The optimal solution to the problem will not change if an arbitrary constant value is subtracted from any row or column of the cost matrix.

Remark 2 shows that if it is possible to construct a new matrix with zero elements and these zero elements or a subset of them correspond to an admissible solution, then such a solution will be optimal.

.

Optimal destination: , , , others , .

Unfortunately, it is not always possible to determine the solution so simply. For such cases, consider the following algorithm.

Step 1.(Reduction of rows and columns). The goal of this step is to obtain 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. Subtracting the corresponding minimum value from the elements of each row, we obtain 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.

Meaningful formulation of the problem. There are n cars in the association, each capable of transporting Q i tons of cargo per month (i = 1,2,…, n). With their help, it is necessary to ensure the transportation of goods (lumber, screws, etc.) from suppliers to consumers by n routes in the amount of R j tons per month (j = 1,2,…, n).
The task is to transport all the goods with minimal costs; to do this, each car must be sent along one and only its route. If the car’s ability to transport cargo is lower than the consumer’s need for this cargo, then this route the vehicle cannot be assigned. Therefore, a matrix C is compiled, characterizing the costs i-th car, if it is assigned to j-th route.

Hungarian method for solving assignment problems

Algorithm of the Hungarian method.

The assignment problem is a special case of the transport problem, so any algorithm can be used to solve it linear programming, however, it is more effective Hungarian method.

The specific features of assignment problems gave rise to the emergence of an effective Hungarian method for solving them. The main idea of ​​the Hungarian method is to move from the original square matrix value C to its equivalent matrix Ce with non-negative elements and a system of n independent zeros, of which no two belong to the same row or the same column. For a given n, there are n! feasible solutions. If in the assignment matrix X we arrange n units so that in each row and column there is only one unit, arranged in accordance with the located n independent zeros of the equivalent cost matrix Se, then we obtain feasible solutions to the assignment problem.

It should be borne in mind that for any invalid assignment, the corresponding cost is conditionally assumed to be equal to a sufficiently large number M in minimum problems. If the original matrix is ​​not square, then an additional required number of rows or columns should be introduced, and their elements should be assigned values ​​determined by the conditions of the problem, possibly after reduction, and the dominant alternatives, expensive or cheap, should be excluded.

HUNGARIAN METHOD

The Hungarian method is one of the most interesting and most common methods of solving transport tasks.

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's assume that there is various works 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, 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 problem of choice is solved, and best option assignments is determined by the positions of the 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. As a result, a matrix with non-negative elements is formed, in each column of which there is at least, one zero.

Next we 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 above 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 finite number repetitions, the next first stage will definitely 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 get the second, third, fourth and fifth columns new matrix subtract all the elements of these columns from n" 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.

Consider the following example. Let there be five people to perform five different jobs. From the reporting data we know how much time it takes each of them to complete each job. These data are shown in the table.

performers
needs

IN in this case the values ​​represent the time spent by each worker on each job, and the values ​​are either 1 or 0, with 1 if worker i is assigned to job j and 0 in all other cases. Thus, the problem is reduced to minimizing the function. cost route linear programming

subject to the following restrictions.

It is clear that if we discard the last condition and replace it with the condition

This results in a transport problem in which all needs and all resources are equal to one. In the optimal solution, all are either an integer or zero, with one being the only possible integer. Thus, solving the transport problem under these conditions always leads to equality.

However, due to degeneracy, methods for solving transport problems in the case of the assignment problem turn out to be ineffective. For any assignment, supplies by row always automatically coincide with demand by column and therefore, instead of 2n-1, we get n non-zero values. In this regard, it is necessary to fill the matrix with n-1 values ​​of e, and it may turn out that non-zero values ​​determine the optimal solution, but the check does not detect it, since the values ​​of e are placed incorrectly.

The method for solving the assignment problem is based on two fairly obvious theorems. The first of them states that the solution will not change if some constant is added to or subtracted from any column or row of the matrix. This theorem is precisely formulated as follows:

Theorem 1.

If minimizes

for everyone, such as

then also minimizes the functionality

where in front of everyone

Theorem 2.

If everything is possible, it is possible to find a set such that

then this solution is optimal.

The second theorem is obvious. To prove the first theorem, we note that

Due to the fact that the quantities subtracted from Z to obtain do not depend on, it reaches a minimum whenever Z is minimized, and vice versa.

The solution method developed is to add constants to the rows and columns and subtract them from the rows and columns until a sufficient number of values ​​vanish to give a solution equal to zero.

Finding a solution begins by subtracting the smallest element from each row and then from each column. The table shows the results for the example above.

Table A)

performers		deducted

Table B)

performers
deducted

A total of 10 units were subtracted from the columns and rows. Therefore, to correctly evaluate any solution obtained using table (B), it is necessary to add 10 units to the result

First of all, they strive to find a solution that includes only those cells of table (B) that contain zero elements, since such a solution, if it can be found, will be the best of all possible. However, there are cases where several solutions have the same quality. An acceptable solution is marked in table (B) with brackets. However, in order to determine whether the solution can be improved, the following algorithm is applied.

Let us first note that any further subtraction from a row or column, although it may lead to the appearance of new zeros, inevitably leads to the appearance of negative elements, so that the zero solution is now not necessarily optimal. However, negative elements can be eliminated by adding the corresponding numbers to the rows or columns. For example, if you subtract 2 from column 1 in table (B), then the element 2 will appear in row 1. If you now add 2 to row 1, you will again get a matrix with non-negative elements. The challenge is to get new zeros in the specified way, but at the same time ultimately obtain a matrix containing a solution consisting of only zeros. It can be proven that the algorithm described below provides a solution to this problem.

1. Draw the minimum number of horizontal and vertical lines that intersect all zeros at least once. Performing this step on table (B) gives the result in table 1.

Table 1

Note that in this case only four lines are used, and therefore the zero cells do not contain the optimal solution.

• 2. Select the smallest element through which no line is drawn. In the example it is 1 in cell (5,2).
• 3. Subtract this number from all elements through which no lines are drawn, and add it to all elements through which two lines are drawn. This example produces the result shown in Table 2.

table 2

This step should result in a zero appearing in a cell where there was none previously. In the example under consideration, this is cell (5,2).

4. Determine whether there is a solution among the new set of zeros. If a solution is not found (in this example there is none), then return to step 1 and perform all subsequent steps until a solution is found. Continuing to consider this example, we obtain the result shown in Table 3.

Table 3

This table already contains a solution, marked with brackets and having a value of 13, which is 1 better than the original feasible solution. , .

Example 2.

Four students and four types of work were presented. The following table corresponds to the cost matrix for this problem.

Let's perform the first step of the algorithm.

Now let's subtract minimum costs from the elements of the corresponding rows.

At the second step of the algorithm we find minimum values by columns and subtract them from the elements of the corresponding columns. As a result, we obtain the matrix presented in the following table.

In the last matrix, the arrangement of zero elements does not allow assigning one job to each child. For example, if we assign Dasha to clean the garage, the first column is excluded from further consideration and then there will be no zero elements in Alla’s row.

• 1) In the last matrix, we draw the minimum number of horizontal and vertical lines along the rows and columns in order to cross out all zero elements.
• 2) Find the smallest uncrossed out element and subtract it from the remaining uncrossed out elements and add it to the elements located at the intersection of the drawn lines.

In the problem this example three straight lines are required, this leads to the following table:

The smallest uncrossed out element is equal to 1. We subtract this element from the remaining uncrossed out elements and add it to the elements located at the intersection of lines. As a result, we obtain the matrix presented in the following table.

The optimal solution shown in the table suggests Dasha to clean the garage, Katya to mow the lawns, Alla to wash the cars, and Sasha to walk the dogs. Corresponding value objective function equals 1+10+5+5=21. The same value can be obtained by summing the values ​​of and and the value of the element that is the smallest among all those not crossed out.