Hungarian algorithm: Difference between revisions

Revision as of 16:36, 2 February 2006

Revision as of 02:09, 12 February 2006

Line 11:

==A minimization problem==

Given <math>n</math> workers and tasks, and an ''n''×''n'' matrix containing the cost of assigning each worker to a task, find the cost minimizing assigmentassignment.

First the problem is written in the form of a matrix as given below

Line 23:

where a, b, c and d are the workers who have to perform tasks 1, 2, 3 and 4. a1, a2, a3, a4 denote the penalties incurred when a does task 1, 2, 3, 4 respectively. Same hold true for the other symbols as well. The matrix is square: each agent can perform only one task.

Then we perform row operations on the matrix. To do this, the lowest of all ai''a''_''i'' [i belonging to 1-4] is taken and is subtracted from the other elements in that row. This will lead to at least one zero in that row [We get multiple zeros when there are two equal elements which also happen to be the lowest in that row]. This procedure is repeated for all rows. We now have a matrix with at least one zero per row. Now we try to assign tasks to agents such that each agent is doing only one task and the penalty incurred in each case is zero. This is illustrated below.

'''Note-Matrix notation hasnthas not been used since formatting is not possible with that'''