Snl Christopher Lowell Skin

, Hungarian method

minimum cost solution for this graph, simple and weighted undirected.

STEP BY STEP ...

Notes:

To solve a problem of allocation in which the goal is to maximize the objective function , multiply the payoff matrix by negative one (-1) and solve the problem as one of minimization, which is not the case.

In a big problem, it may be difficult to obtain the minimum number of rows needed to cover all the zeros in the matrix current cost. It can be shown that if j lines are needed to cover all zeroes, then j can be assigned only work at zero cost in the current matrix, which accounts for over when they need more lines.

If the number of rows and columns in the matrix of costs are different, the problem of allocation is unbalanced. The Hungarian method can provide an incorrect solution if the problem is not balanced, because of the above, it should balance any issues first assignment (adding rows or columns ficiticias) before resolving by the Hungarian method. ADD
I8 and I9 to equlibrar space as recommended.
* I = start, F = final. STEP 1 .-

first

Find smallest element in each row of cost matrix m * m;

a new array is constructed on by subtracting from each cost the minimum cost of each row, find for this new matrix, the minimum cost in each column.

Below is built a new matrix (called the reduced cost matrix) by subtracting the cost of each cost minimum in its column.

STEP 2 .- Draw the minimum number of lines (horizontal or vertical or both), which are required to cover all the zeros in the reduced cost matrix; if m lines are needed to cover all zeros, you have an optimal solution between the zeros of the matrix covered . If you require less than m lines to cover all zeroes, continue with step 3 .
Each horizontal line must go through the whole line (row) and each vertical line across the column.

The number of lines that needed was 6, and 6 is less

am, proceed to the next step.

STEP 3 .-

Find the smallest number that is not covered by a line on the cost matrix. Subtract the value of this number to each item covered by a line and add it to each item covered by two lines.

is deve

Finally back to step 2.

AND OUR PARENT AS FOLLOWS:

again when changing vertical and horizontal lines, we realize that the amount is the same as above, 6

and as 6 is less than m, continue with step 3.

AND IS WELL ...

As the number of lines increased by assigning numbers as indicated, now has to m = 7, therefore has an optimal solution between the zeros of the matrix covered.

GRAPH ..

So the matrix is \u200b\u200brepresented above.
Taking into account the costs that occurred at the beginning of example, in the data table.