UNBALANCED PROBLEMS
Establish whether the problem is a balanced one i.e., the number of rows = number of columns If proceed as discussed earlier. If not, then add a dummy row or column to make the problem a balanced 0 by allotting zero v11ues to each cell of the dummy row or column, as the case may be.
Example 6.1. A department head has four subordinates and four tasks to be performed. Subordinate differ in efficiency and the tasks differ in their intrinsic difficulty. His estimate of time each man would take to perform each task is given in the matrix below
Tasks 
Men 

E 
F 
G 
H 

A B C D 
18 13 38 19 
26 18 19 26 
17 14 18 24

11 26 15 10 
How should the tasks be allotted, one to a man, so as to minimise the total man hours?
Sol. Step I. Subtract the smallest element of each row from every element of the corresponding row, the reduced matrix is as follows (subtract II from row one, 13 from row 2, 15 from row 3 and 10 from row 4)
Step II. Subtract the smallest element of each column of the above reduced matrix from every element of the corresponding column, we get the following reduced matrix (subtract 0 from column I, 4 from column 2, 1 from column 3 and 0 from column 4),
Step III. Start with row I we make assignment to a single zero and put a square (⎕) around it and cross out all other zeros in the column so marked. By doing so, we get
Note that row 2 had two zeroes, we have arbitrarily made assignment to zero in column 1 and put a square around it. Also, note that column 3 and row 4 do not have any assignment.
Step IV. (i) Tick row 4 as it does not have any assignment. In fourth column of the ticked row (row 4) there is a zero, so we tick fourth column.
(ii) In the first row of ticked column (column 4) there is an assiglU11ent made, so first row is ticked.
(iii) Draw straight lines through all unmarked rows and marked columns,
The following matrix shows the above operations.
Step V. Is the present solution an optimal solution? To find that we know, there are 3 lines drawn which is less than the order of the cost matrix (4). Hence it is not an optimal solution we have to generate new zeros in the matrix to increase the minimum number of lines.
Step VI Let us find out the smallest element not covered by the lines. It is 5. Subtract 5 from all the uncovered elements and add 5 to all the elements lying at the intersection of lines, we get the following reduced matrix.
Step VII. Repeat step III on the reduced matrix i.e., scrutinise all the elements row wise, say with row one, make assignment to a single zero and crossout all other zeros in the column so marked, we get
It can be seen now each row and each column has only one assignment, an optimal solution has been obtained. The optimum assignment is A → G, B → E, C → F, D → H.
The minimum total time for this assignment would be obtained by addingthe relevant times i.e., 17 + 13 + 19 + 10 = 59 manhours.
Example 6.2. A marketing manager has 5 salesmen and 5 districts. Considering the capabilities of the salesman and the nature of districts the marketing manager estimates that sales sides per month (in hundred rupees) for each salesman in each district would be as follows.
Salesman 
Districts 

A 
B 
C 
D 
E 

1 
30 
38 
40 
28 
40 
2 
40 
24 
28 
21 
36 
3 
41 
27 
33 
30 
37 
4 
22 
38 
41 
36 
36 
5 
29 
33 
40 
35 
39 
Find the assignment of salesman to districts that will result in maximum sales.
Sol. This is a maximisation problem and has to be converted into a minimisation problem by subtracting all the elements from the largest element of the sales table. Here largest element is 41. Hence, the equivalent sales table for this problem would be obtained by reducing all the elements from 41 and rewriting it as follows.
Step I. Subtract the smallest element of each row from every element of the corresponding row, we get
Step II. Subtract the smallest element of each column from every element of the corresponding column, we get the following reduced matrix.
Step III. Starting with row one, we make assignment to a single zero and cross out all other zeros in so marked, we get
Here roll three and column 4 do not have any assignment.
Draw the minimum number of horizontal and vertical lines which cover all the zeros as follows
Since the number of lines (4) is less than the order of the matrix (5) the solution is not optimal.
Step V. The least uncovered element 4 is subtracted from all the uncovered elements and added to the intersection of elements, we get the following reduced matrix.
Optimum assignment is
1 → B,
2 →A
3 →E,
4 → C,
5 → D
i.e.. 38 + 40 + 37 + 41 + 35 = 191
Maximum sales would be Rs 19,100.
Recent Comments