Unbalanced Problems

Establish whether the assignment problems are balanced one or not. This means to check the number of rows to be equal to number of columns. If this happens, then we will proceed as discussed earlier. If this is not achieved, then we have to add dummy row/ column as per the case to balance the problem by allotting zeros (0).

Example 6.1:

A department with four subordinates had to perform four tasks. Each subordinate differs in its performance and efficiency. The tasks also differ in its intrinsic difficulty. The estimated time taken by each subordinate to perform each task has been given in the following matrix.

Tasks                                       Men

                        E                      F                      G                      H

A                      18                    26                    17                    11

B                      13                    18                    14                    26

C                      38                    19                    18                    15

D                      19                    26                    24                    10

How to allot the task to each subordinate to get the minimized total man hours?

Solution:

Step 1:

Subtract the smallest value from each row to the corresponding row to reduce the matrix as follow (subtract 11 from row one, 13 from row two, 15 from third row and 10 from fourth row).

7          15        6          0

0          15        1          3

23        4          3          0

9          16        14        0

Step 2:

Subtract the smallest value from each column to the corresponding column to reduce the matrix as follow (subtract 0 from column one, 4 from column two, 1 from third column and 0 from fourth column).

7          11        5          0

0          11        0          13

23        0          2          0

9          12        13        0

Step 3:

Start from the first row, we put asquare to first zero in each row and cross our all other zeroes in the same row. By doing so, we;

7          11        5          0

0          11        0          13

23        0          2          0

9          12        13        0

Note:

Since row two has two zeros, we will arbitrarily choose this to made assignment to zero in the column one and put a square around it. Moreover, column three and four do not have any assignments.

Step 4:

1. Tick the row four as it does not have any assignment. In the 4^th column and 4^th row, there is a zero. So, we will tick this 4^th
2. In the row first of ticked column i.e. 4^th column, there is an assignment made. Thus, first row will be ticked.
3. Draw straight lines through all the marked columns and unmarked rows.

Following matrix highlights the above steps:

7          11        5          0          √

0          11        0          13

23        0          2          0

9          12        13        0          √

Step 5:

Whether this solution is optimal or not? Of course not! This is because there are only 3 lines drawn and it is less than order of the matrix (4). Hence, we have to generate new zeros to increase the minimum number of lines to make it an optimal solution.

Step 6:

Find out the smallest element that is not covered by any of these lines. It is the value ‘5’. Subtract this value from all uncovered elements and add to all elements that are lying at the intersection of two lines. Thus, we get the following matrix;

2          6          0          0

0          11        0          18

23        0          2          5

4          7          8          0

Step 7:

Repeat Step 3 to reduce the matrix row-wise to make an assignment to a single zero, we get;

E          F         G          H

A          2          6          0          0

B          0          11        0          18

C          23        0          2          5

D          4          7          8          0

Result:

Now, we can see that an optimal solution is obtained. Each column and each row have only one assignment. Thus, optimum assignment will be;

A→G, B→E, C→F, D→H

Therefore,

Minimum total time taken for this assignment problem would be obtained by-

17 + 13 + 19 + 10 = 59 man-hours

Example 6.2:

A marketing manager has to cover 5 districts with his 5salesmen. Considering the capability of each salesman and nature of each district, its manager has estimated that sales per month (in hundred rupees) 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 out the assignment of 5 salesmen to 5 districts to get maximum sales.

Solution:

This is a maximization problem needs to convert into a minimization problem. It can be done by subtracting all elements with the largest element i.e. 41. Thus, the following matrix can be obtainedby reducing it with 41;

11        3          1          13        1

1          17        13        20        5

0          14        8          11        4

19        3          0          5          5

12        8          1          6          2

Step 1:

Subtracting the smallest value of each row with every other element of the same row, we get;

10        2          0          12        0

0          16        12        19        4

0          14        8          11        4

19        3          0          5          5

11        7          0          5          1

Step 2:

Subtracting the smallest value of each column with every other element of the same column, we get;

11        3          1          13        1

1          17        13        20        5

0          14        8          11        4

19        3          0          5          5

12        8          1          6          2

Step 3:

Start from the row one to make the assignment a single zero. Cross out all the other zeros, then we get;

10        0          0          7          0

0          14        12        14        4

0          12        8          6          4

19        1          0          0          5

11        5          0          0          1

Step 4:

Here 3^rd row and 4^th column do not have any assignment. Now, draw the minimum numbers of straight lines horizontally and vertically to cover all the zeroes, we get;

10        0          0          7          0

0          14        12        14        4

0          12        8          6          4

19        1          0          0          5

11        5          0          0          1

We find that number of lines (i.e. 4) is less than order of matrix (i.e. 5). This means the solution is not optimal.

Step 5:

The value 4 is the least uncovered element which is subtracted from all uncovered elements and added to the intersection of each element. Thus, the matrix reduces to;

A          B          C          D          E

1          10        0          0          7          0

2          0          14        12        14        4

3          0          8          4          2          0

4          23        1          0          0          5

5          15        5          0          0          1

Result:

The optimum solution will be;

1 →B, 2 →A, 3 →E, 4 →C, 5 →D

i.e., 38 + 40 + 37 + 41 + 35 = 191

Thus, the maximum sale would be Rs. 19,100.