Content deleted Content added
m Disambiguate Optimization to Optimization (mathematics) using popups |
→Modeling: restoring section mysteriously removed by Macrakis |
||
Line 8:
The algorithm models an assignment problem as a ''n''×''m'' cost matrix, where each element represents the cost of assigning the ''n''th worker to the ''m''th job. By default, the algorithm performs minimization on the elements of the matrix; hence in the case of a price-minimization problem, it is sufficient to begin [[Gaussian elimination]] to make zeros appear (at least one zero per line and per column). However, in the case of a profit-maximization problem, the cost matrix needs to be modified so that minimization of its elements results in maximizing the original cost values. In an infinite-cost problem, the initial cost matrix can be re-modelled by subtracting every element of each line from the maximum value of the element that line (or column respectively). In a finite-cost problem, all the elements are subtracted from the maximum value of the whole matrix.
==Algorithm==
The algorithm works by increasing the number of zeros in the matrix and searching for a set of starred zeros, one in every row and column. Zeros are primed, starred, or neither during the algorithm. If there are insufficent zeros a quick [[Gaussian elimination]] adds more. If there are not enough starred zeros, the primed zeros are starred and the starred zeros primed. Primed zeros are zeros in a column without any more zeros, which, because they are in the same row as another zero were not starred.
==A minimization problem==
| |||