Assignment No 2

1) What is Assignment Problem

A-

Assignment Problem is a special type of linear programming problem

where the objective is to minimise the cost or time of completing a
number of jobs by a number of persons.

The assignment problem in the general form can be stated as follows:

“Given n facilities, n jobs and the effectiveness of each facility for

each job, the problem is to assign each facility to one and only one job
in such a way that the measure of effectiveness is optimised
(Maximised or Minimised).”

Several problems of management has a structure identical with the

assignment problem.

2) State and discuss Hungarian method to solve Assignment problem.

A-Check to see if the number of rows and columns are equal; if they are, the assignment problem is
considered to be balanced. Then go to step 1. If it is not balanced, it should be balanced before the algorithm is
applied.

Step 1 – In the given cost matrix, subtract the least cost element of each row from all the entries in that row.
Make sure that each row has at least one zero.

Step 2 – In the resultant cost matrix produced in step 1, subtract the least cost element in each column from all
the components in that column, ensuring that each column contains at least one zero.

Step 3 – Assign zeros

 Analyse the rows one by one until you find a row with precisely one unmarked zero. Encircle this lonely unmarked zero
and assign it a task. All other zeros in the column of this circular zero should be crossed out because they will not be used
in any future assignments. Continue in this manner until you’ve gone through all of the rows.
 Examine the columns one by one until you find one with precisely one unmarked zero. Encircle this single unmarked zero
and cross any other zero in its row to make an assignment to it. Continue until you’ve gone through all of the columns.

Step 4 – Perform the Optimal Test

 The present assignment is optimal if each row and column has exactly one encircled zero.
  The present assignment is not optimal if at least one row or column is missing an assignment (i.e., if at least one row or
column is missing one encircled zero). Continue to step 5. Subtract the least cost element from all the entries in each
column of the final cost matrix created in step 1 and ensure that each column has at least one zero.

Step 5 – Draw the least number of straight lines to cover all of the zeros as follows:

(a) Highlight the rows that aren’t assigned.

(b) Label the columns with zeros in marked rows (if they haven’t already been marked).

(c) Highlight the rows that have assignments in indicated columns (if they haven’t previously been marked).

(d) Continue with (b) and (c) until no further marking is needed.

(f) Simply draw the lines through all rows and columns that are not marked. If the number of these lines equals
the order of the matrix, then the solution is optimal; otherwise, it is not.

Step 6 – Find the lowest cost factor that is not covered by the straight lines. Subtract this least-cost component
from all the uncovered elements and add it to all the elements that are at the intersection of these straight lines,
but leave the rest of the elements alone.

Step 7 – Continue with steps 1 – 6 until you’ve found the highest suitable assignment.

3) Five men are available to do the five different jobs. From past records, the time
(Hrs.) that each man takes to do each job is known and given in the following
table:

Jobs
I II III IV V
A 2 9 2 7 1
B 6 8 7 6 1
Mens C 4 6 5 3 1
D 4 2 7 3 1
E 5 3 9 5 1

Find Assignment of men to jobs that will minimize the total time taken.

A-

Column reduction (directly as a shortcut, instead of row reduction first, since all value in the fifth column are ‘1’):
subtracting the minimum number in each column, from all the other numbers in that column:
Allocations can be made as shown above. However, each row and column does not have an allocation. So
drawing minimum number of lines through the zeros:

Number of lines = 4, while order of the matrix = 5. So solution is not optimal.

From all uncovered elements, we take the minimum of these elements (here 2) and subtract it from all the
uncovered elements, while we add it to the elements where two lines intersect:

Allocations can be made as shown above.

Making the same allocations is the main matrix:

So minimum total time taken: 4 + 2 + 2 + 3 + 1 = 12

4) A marketing manager having five salesmen and five sales districts.

Considering the capabilities of the salesman and nature of districts, the
marketing manager estimate that sales per month (in Hundred rupees) for each
salesmen in each district would be as follows:

District
I II III IV V
 A 32 38 40 28 40
B 40 24 28 21 36

Salesmen C 41 27 33 30 37
D 22 38 41 36 36
E 29 33 40 35 39

Find the Assignment Problem of salesmen to districts that will result in

maximum sale
A-
. Here the 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:
(

9 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. Subtract the smallest element of each row from every element of the
corresponding row, we get
(

8 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. Subtract the smallest element of each column from every element of the
corresponding column, we
get the following reduced matrix
(
 8 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 3. Starting with row one, we make assignment in a single zero and cross
out all other zeros in the column
marked, we get
(

8 [0] ⨂ 7 0
[0] 14 12 14 4
⨂ 12 8 6 4
19 1 [0] ⨂ 5
11 5 ⨂ [0] 1)

Here row three and column 5 do not have any assignment.

Step 4. Draw the minimum number of horizontal and vertical lines wchich cover
all the zeroes as follows
Since the number of lines (4) is less than the order of matrix (5), the solution is
not optimal.
Step 5. The least uncovered element 4 is subtracted from all the uncovered
elements and added to the
intersection of the elements, we get the following reduced matrix.
Optimum assignment is
1 → 𝐵, 2 → 𝐴, 3 → 𝐸, 4 → 𝐶, 5 → 𝐷
i.e.,
38 + 40 + 37 + 41 + 35 = 191 (in hundred rupees).
Maximum sales would be Rs 19,100.
5) Find the following assignment problem for minimization

A B C
I 10 7 8
II 8 9 7
III 7 12 6
IV 10 10 8
A-
A B C
I 10 7 8
II 8 9 7
III 7 12 6
IV 10 10 8

We can start by subtracting the smallest value in each row

A B C
I 3 0 1
II 1 2 0
III 1 6 0
IV 2 2 0

Now, we can subtract the smallest value in each column

A B C
I 2 0 1
II 0 2 0
III 0 6 0
IV 1 2 0

Now, we need to draw the minimum number of horizontal and vertical lines to cover all zeros in the
matrix.

A B C
I 2 0 1
II 0 2 0
III 0 6 0
IV 1 2 0
In this case, the smallest uncovered value is 2, and there is only one value covered by two lines, which
is 6. Therefore, the new matrix becomes:

css
Copy code
A B C
I 0 0 1
II 0 2 0
III 0 4 0
IV 1 0 0
 I -> B
II -> A
III -> C
IV -> A
Therefore, the minimum total cost is 0 + 0 + 0 + 1 = 1.
6) Considering a problem of assigning four clerks to four tasks. The time(Hours)
required to complete the task is given bellow

Tasks
A B C D
I 4 7 5 6
II - 8 7 4
Clerks III 3 - 5 3
IV 6 6 4 2

A-

Here's the given assignment matrix:

A B C D

I 4 7 5 6

II - 8 7 4

III 3 - 5 3

IV 6 6 4 2

Let's replace the blanks with a large number, say 100:

A B C D

I 4 7 5 6

II 100 8 7 4

III 3 100 5 3

IV 6 6 4 2
 To solve this assignment problem, we can use the Hungarian Algorithm or any
other method for solving assignment problems. Let's proceed with the Hungarian
Algorithm to find the optimal assignment of clerks to tasks.

Here's the given assignment matrix:

css

Copy code

A B C D

I 4 7 5 6

II - 8 7 4

III 3 - 5 3

IV 6 6 4 2

Since there are blank entries in the matrix, we need to replace them with large
enough numbers. In the Hungarian Algorithm, typically we replace blank entries with
the maximum value in the matrix. However, in this case, we need to ensure that these
values are large enough to not be chosen in the final assignment.

Let's replace the blanks with a large number, say 100:

css

Copy code

A B C D

I 4 7 5 6

II 100 8 7 4

III 3 100 5 3
 IV 6 6 4 2

Now, let's subtract the smallest value in each row from all the values in that row:

A B C D

I 0 3 1 2

II 96 0 1 0

III 0 97 2 0

IV 4 4 2 0

Next, let's subtract the smallest value in each column from all the values in that
column:

A B C D

I 0 0 0 2

II 96 0 0 0

III 0 97 1 0

IV 4 4 1 0

Now, let's draw the minimum number of horizontal and vertical lines to cover all zeros
in the matrix. In this case, we need four lines to cover all the zeros.

A B C D

I 0 0 0 2

II 96 0 0 0

III 0 97 1 0

IV 4 4 1 0
 In this case, the smallest uncovered value is 1, and there are two values covered by
two lines, which are 1 and 0. Therefore, the new matrix becomes:

A B C D

I 1 1 1 2

II 97 1 1 1

III 1 98 2 1

IV 5 5 2 1

Now, we can see that each row and each column has exactly one zero, indicating
an optimal assignment. So, the optimal assignment with the minimum time required
is as follows:

I -> A

II -> B

III -> D

IV -> C

Therefore, the minimum total time required is 1 + 8 + 3 + 4 = 16 hours.