written 5.2 years ago by | modified 4 weeks ago by |

I | II | III | IV | V | |
---|---|---|---|---|---|

1 | 6 | 2 | 5 | 2 | 6 |

2 | 2 | 5 | 8 | 7 | 7 |

3 | 7 | 8 | 6 | 9 | 8 |

4 | 6 | 2 | 3 | 4 | 5 |

5 | 9 | 3 | 8 | 9 | 10 |

6 | 4 | 7 | 5 | 6 | 8 |

**1 Answer**

0

7.1kviews

Solve the following assignment problem.

written 5.2 years ago by | modified 4 weeks ago by |

I | II | III | IV | V | |
---|---|---|---|---|---|

1 | 6 | 2 | 5 | 2 | 6 |

2 | 2 | 5 | 8 | 7 | 7 |

3 | 7 | 8 | 6 | 9 | 8 |

4 | 6 | 2 | 3 | 4 | 5 |

5 | 9 | 3 | 8 | 9 | 10 |

6 | 4 | 7 | 5 | 6 | 8 |

ADD COMMENT
EDIT

1

98views

written 5.2 years ago by | • modified 5.2 years ago |

*(NOTE: The question does not specify whether to maximize or minimize the allocations. So we assume itâ€™s a minimization problem while solving)*

Consider the matrix:

- Subtracting the smallest element in each row, from all the other row elements:

Number of lines = 3 < order of matrix = 5

- Subtracting the smallest element in each column, from all the other column elements:

Allocation can be made as shown. However, each row and column do not have one allocation. Drawing minimum number of lines through the zeroes:

- Subtracting the minimum uncovered element from all the other uncovered elements, and adding it to the elements where 2 lines intersect:

Allocation can be made as shown above. Each row and column still do not have one allocation. Drawing minimum number of lines through the zeroes:

- Subtracting the minimum uncovered element from all the other uncovered elements, and adding it to the elements where 2 lines intersect:

The remaining zeroes can be allocated in 2 possible ways (alternate solution):

Making the same allocations in the original matrix:

**Minimum = 11 + 7 + 17 + 12 + 13 = 60**

AND

**Minimum = 11 + 10 + 17 + 6 + 16 = 60**

ADD COMMENT
EDIT

Please log in to add an answer.