In the previous section, we used Hungarian Method to solve an assignment problem.

In this section, we provide another example to enhance your knowledge. Let's concentrate on the following example:

The Winner Publishing Company employs typists on hourly basis. There are five typists for service and their charges and speeds are different.

According to an earlier understanding only one job is given to one typist and the typist is paid for full hour even if he works for a fraction of an hour. Find the least cost allocation for the following data:

Typist | Rate per hour (Rs.) _{} |
No. of pages Typed / hour _{} |
---|---|---|

A | 5 | 12 |

B | 6 | 14 |

C | 3 | 8 |

D | 4 | 10 |

E | 4 | 11 |

Job | No. of pages |
---|---|

P | 199 |

Q | 175 |

R | 145 |

S | 198 |

T | 178 |

Solution.

The following matrix gives the cost incurred if the ith typist (i = A, B, C, D & E) executes the jth job (j = P, Q, R, S & T):

Job | |||||
---|---|---|---|---|---|

Typist | P | Q | R | S | T |

A | 85 | 75 | 65 | 125 | 75 |

B | 90 | 78 | 66 | 132 | 78 |

C | 75 | 66 | 57 | 114 | 69 |

D | 80 | 72 | 60 | 120 | 72 |

E | 76 | 64 | 56 | 112 | 68 |

Identify the minimum element in each row and subtract it from every element of that row.

Table

Job | |||||
---|---|---|---|---|---|

Typist | P | Q | R | S | T |

A | 20 | 10 | 0 | 60 | 10 |

B | 24 | 12 | 0 | 66 | 12 |

C | 18 | 9 | 0 | 57 | 12 |

D | 20 | 12 | 0 | 60 | 12 |

E | 20 | 8 | 0 | 56 | 12 |

Identify the minimum element in each column and subtract it from every element of that column.

Table

Job | |||||
---|---|---|---|---|---|

Typist | P | Q | R | S | T |

A | 2 | 2 | 0 | 4 | 0 |

B | 6 | 4 | 0 | 10 | 2 |

C | 0 | 1 | 0 | 1 | 2 |

D | 2 | 4 | 0 | 4 | 2 |

E | 2 | 0 | 0 | 0 | 2 |

Make the assignments for the reduced matrix

Table

Job | |||||
---|---|---|---|---|---|

Typist | P | Q | R | S | T |

A | 2 | 2 | 4 | ||

B | 6 | 4 | 10 | 2 | |

C | 1 | 1 | 2 | ||

D | 2 | 4 | 4 | 2 | |

E | 2 | 2 |

The number of assigned cells is not equal to the number of rows (and columns). Therefore, we draw the minimum number of vertical and horizontal lines necessary to cover all the zeros in the reduced matrix

Table

Repeating the usual process as explained in the previous example, we get the following matrix:

Table

Job | |||||
---|---|---|---|---|---|

Typist | P | Q | R | S | T |

A | 2 | 2 | 2 | 4 | |

B | 4 | 2 | 8 | ||

C | 1 | 2 | 1 | 2 | |

D | 2 | 2 | |||

E | 2 | 2 | 2 |

The number of assigned cells is not equal to the number of rows (and columns). Therefore, we draw the minimum number of vertical and horizontal lines necessary to cover all the zeros in the reduced matrix

Table

Job | |||||
---|---|---|---|---|---|

Typist | P | Q | R | S | T |

A | 2 | 1 | 2 | 3 | |

B | 4 | 1 | 7 | ||

C | 2 | 2 | |||

D | 1 | 1 | |||

E | 3 | 3 | 3 |

Since the number of assignments is equal to the number of rows (&
columns), this is the **optimal solution**.

Substituting the values from original table:

75 + 66 + 114 + 80 + 64 = Rs. 399.