a
b
c
d
x
y
z
AC
i
Randomize
About Hungarian method calculator
Solve assignment / transportation problems using the Hungarian method online with detailed step-by-step solution. with complete, detailed, step-by-step description of solutions, that solves linear-programming problems up to 20×20 in size with coefficients of this type: decimal numbers and fractions.
To start the calculation, you need to first enter the problem dimensions in the input fields at the very top of the screen, and also choose the desired operation from the side menu.
A little below you will find an input window where you need to enter the coefficients, constraints, and right-hand-side values using the keyboard. The input control panel is also located here, which simplifies work with LP problems and contains the following control elements:
- The first element allows you to expand the input window. This can be especially useful when the tableau does not fit completely on the screen. If the table is still not fully visible after expanding the window, you can change the scale using the + / - buttons;
- The second element copies the current problem input to the memory buffer. This can be useful when you frequently solve the same LP problem or need to transfer data between operations;
- And the last element pastes the previously copied input, which allows you to restore problem data in just a few clicks instead of re-entering it manually;
And further down you will find a toolbar that allows you to customize the calculator and make it easier to work with. It is visually divided into three parts, each of which is responsible for the following functionality:
- The first part lets you select the number format used when displaying the solution result. You can also turn off step-by-step comments if you already understand the method and only need to check your own calculations, or hide the step-by-step solution entirely if you only need the final answer;
- The second part contains buttons that let you modify the input table dimensions, clear individual coefficients or the entire input, and the main button with an equal sign that takes you to the solution screen. All these buttons are duplicated by keyboard shortcuts. Hover over a button to see the corresponding key in a tooltip. You can also use the arrow keys to move the cursor between input fields;
- And the last part allows you to choose the number of digits after the decimal point for rounding non-integer results. A live preview shows how the rounded values will appear;
What is the Hungarian method?
The Hungarian method (Kuhn-Munkres algorithm) solves the assignment problem: given an n x n cost matrix, find a perfect matching between n workers and n jobs that minimizes total cost. The assignment problem is a special case of the transportation problem where each supply and each demand equals 1. The algorithm runs in polynomial time and is guaranteed to find the globally optimal assignment.
How to solve an assignment problem with the Hungarian method?
Start by subtracting the column minimum from every element of each column (column reduction), then subtract the row minimum from every element of each row (row reduction). Find the minimum number of horizontal and vertical lines needed to cover all zeros in the reduced matrix. If n lines are needed, the covered zeros contain an optimal assignment — extract it. Otherwise, find the smallest uncovered element, subtract it from all uncovered elements, and add it to all elements covered by two lines, then repeat the zero-cover step. Continue until n independent zeros can be selected, giving the optimal assignment.
Example of solving an assignment problem with the Hungarian method
The solution of the problem begins with a preliminary stage. The result of which will be the matrix C0 which is called the adapted commodity cost matrix and the matrixX0, matrix of volumes of commodity traffic.
The preliminary stage begins with the receipt of the matrix C', for which we find the smallest values in the columns of the matrix C and subtract these elementwise from the corresponding columns.
Get the matrix C0 by repeating a similar operation already for rows of the matrix C'.
In matrices X0 in place of nonzero elements of the matrix C0 necessarily located 0. On the positions of the empty elements of the matrix, write the smallest of two values: the balance of stocks, in the row where the empty cell is located and the balance of needs, in the column where it is located.
The value of the sum of balances of needs and stocks is an absolute measure of the optimal distribution of resources, presented in the current matrix X. For optimal distribution, this sum is 0.
After the preliminary stage, we begin to perform an iterative process of finding the optimal matrix X. Each iteration ends with the receipt of a new matrix X, as a result of the successful implementation of the second stage. And the iteration begins with the first stage. If it is impossible to successfully implement the second stage, the third stage is performed, and then we return to the first.
First stage
We supplement the rows and columns of the current matrix C with residuals from the current matrix X. We denote by a horizontal line above the zeros in the current matrix C located at the place of non-zero elements of the current matrix X. We denote by the pluses of the current matrix C, the residual for which is 0;
Second stage
The second stage involves the construction of a chain, if it succeeds, then we get a new matrix X and complete the current iteration. If not, then proceed to the third stage.
Building a chain:
We are looking for a zero in a column not marked above +, and we denote it by a horizontal dash, and to the right of the line where it is located we append +. If the residual of the row where the given zero is located is not zero, then the construction of the chain can be considered complete, if not, then continue to build the chain. The next element that allows you to extend the chain should be 0, which meets the following requirements:
- located in the line where 0' - in the column marked above +;
- marked on top by a horizontal line;
If you can find a zero that meets these requirements, then we denote it * and tidy + from the column where it is located by taking it in brackets. After finding 0* it is necessary to find 0 in the column where it is located. If there is one, we denote it by a horizontal bar. If found 0' located in a row with a zero residual, then we continue building the chain by trying to find 0* in this line. If the row residual is where 0' non-zero, the chain building process is complete. If all the options for building a chain were worked out and it was not possible to build it, then proceed to the third stage. A chain is a set of an odd number of zeros, in which at even places always 0* , and on odd 0'. The minimum chain length is one 0.
After receiving the chain, we define Θ. Θ is the minimum of such numbers:
- discrepancy of the column where it is located 0' from which the chain begins;
- discrepancy of the line where it is located 0' in which the chain ends;
- values from the current matrix X, located at the positions 0* chains;
After determining Θ, we proceed to the calculation of the new matrix X, adding Θ to the elements of the current matrix X located in the positions 0' chains, and taking away Θ from the elements of the current matrix X on the positions 0* chains;
Third stage
We include in the rectangular contours of the row and columns labeled +. Among the elements not in the contours, choose the smallest value. We get the intermediate matrix C~, taking away the smallest value from line elements that are not in the contours, leaving the lines in the contours unchanged. We get a new matrix C by adding the smallest value to the elements of the columns of the matrix C~which are in contours, leaving columns, not in contours unchanged. Obtaining a new matrix C, the third stage is completed. After that, we apply the operations of the first and second stage to the obtained matrix.
We implement the first and second stage.
Since it is impossible to build a chain, we proceed to the third stage.
We obtain an intermediate matrix.
We get a new matrix C.
We implement the first and second stage.
Find Θ.
Calculate the new matrix X.
We implement the first and second stage.
Since it is impossible to build a chain, we proceed to the third stage.
We obtain an intermediate matrix.
We get a new matrix C.
We implement the first and second stage.
Find Θ.
Calculate the new matrix X.
Since the value of the sum of residual needs and stocks is zero, the matrix X is optimal and you can get the result by finding the sum of the products of nonzero elements of the current matrix X and the corresponding elements of the original matrix C.
(3 * 0) + (1 * 1) + (1 * 2) + (5 * 0) + (5 * 0) = 3
Frequently asked questions
What does the Hungarian method solve?
It solves the assignment problem — pairing n workers with n jobs so that the total cost is minimized and each worker is assigned exactly one job.
Why does the cost matrix have to be square?
Each worker must be matched to exactly one job, so the number of workers and jobs must be equal. When they are not, dummy rows or columns with zero cost are added to square the matrix.
How does the row and column reduction work?
Subtracting the smallest entry of each row, then each column, creates zeros without changing which assignment is optimal. The method then finds a complete set of independent zeros, adjusting the matrix until one exists.
How do I read the result?
The result marks the optimal worker-to-job assignment and reports the minimum total cost — the sum of the original costs of the chosen pairs.