The Hindu Business Line : Some properties of assignment model

The objective of the model is to determine the optimum (least-cost) assignment of workers to jobs. The assignment problem is a special type of linear programming problem where assignees are being assigned to perform tasks.

However, the assignees need not be people. They also could be machines, or vehicles, or plants, or even time slots to be assigned tasks.

Property 1: Since an assignment model is always a square matrix it can be noticed that the final solution can always be synchronised in the diagonal, that is, all the diagonal elements can be reduced to zero. This can be achieved by shifting the elements in a row or a column fully.

The solution is 8 + 6 + 13 + 10 = 37. Now the elements in the matrix (see Tables 1, 2 and 3) can be shifted in such a way that diagonal elements become zero (see Tables 4, 5, 6).

Property 2: The solution to any assignment problem equals the elements reduced from each row, each column and elements reduced in case the lines drawn does not equal the order of the matrix. In almost all the balanced situations, this property holds good. In the above example it can be seen that the elements from each of the rows are 8+6+12+10, and the element reduced in column 1 adds up to the solution.

Property 3: Where the elements of the matrix yield a constant difference it can be noticed that the minimum as well as the maximum are equal and one of the possible answers will lie at the diagonals. In the example shown in Table 7, both the maximum and minimum equal 132.

Property 4: If the assignment is on a proportion and if it is noticed that the elements are on a descending order the maximum occurs in the diagonal from north-west corner and the minimum occurs from the north-east corner.

Maximum is 42+25+16+9 = 92 and Minimum is 21+20+20+18 = 79 (see Table 8).

Property 5: If all the elements are different and if an element happens to be the minimum of the row as well as the column, it will enter the solution invariably.

This property can be used in a restricted sense to reduce the order of the matrix. Where the order of the matrix is reduced to two, the final answer is the diagonal elements of the 2 x 2 matrix plus the elements already noticed.

In the above example (property 1) 8 and 6 happen to be the minimum in row 1 and column 3, and in row 2 and column 4. After their elimination, the net 2 x 2 matrix will be 13, 16 and 14, 10.

Hence, the least of the diagonal elements, that is, 13+10 or 16+14 will have to be chosen. Obviously 13+10 is the answer. Final solution will be 13+10+6+8 = 37.