The Omega pharmaceutical firm has five salespersons, whom the firm wants to assign to five sales regions. Given their various previous contacts, the salespersons are able to cover the regions in different amounts of time. The amount of time (days) required by each salesperson to cover each city is shown in the following table:
Salesperson Region (days)
A B C D E
1 17 10 15 16 20
2 12 9 16 9 14
3 11 16 14 15 12
4 14 10 10 18 17
5 13 12 9 15 11
Which salesperson should be assigned to each region to minimize total time? Identify the optimal assignments and compute total minimum time.
Please type your subject in the School Subject box. Any other words, including obscure abbreviations, are likely to delay responses from a teacher who knows that subject well.
student
Eco
To solve this assignment problem and find the optimal assignments and total minimum time, we can use the Hungarian Algorithm, also known as the Munkres algorithm. Here's how you can apply it step-by-step:
Step 1: Create a cost matrix
- Create a 5x5 matrix representing the cost of assigning each salesperson to each region.
- Subtract each entry from the maximum value in the matrix to convert it into a minimization problem.
- For the given table, the cost matrix would look like this:
| A B C D E
-------------------
1 | 3 10 5 4 0
2 | 8 11 4 11 6
3 | 9 4 6 5 8
4 | 6 10 10 2 3
5 | 7 8 11 5 9
Step 2: Subtract the minimum value from each row
- For each row, subtract the minimum value in that row from all the elements in that row.
- This step helps in finding the minimum time for each salesperson.
- The modified matrix would be:
| A B C D E
-------------------
1 | 3 10 5 4 0
2 | 8 11 4 11 6
3 | 9 4 6 5 8
4 | 6 10 10 2 3
5 | 7 8 11 5 9
Step 3: Subtract the minimum value from each column
- For each column, subtract the minimum value in that column from all the elements in that column.
- This step helps in finding the minimum time for each region.
- The modified matrix would be:
| A B C D E
-------------------
1 | 0 10 0 2 0
2 | 5 11 0 9 3
3 | 6 4 1 4 7
4 | 3 10 5 0 0
5 | 4 8 9 3 8
Step 4: Mark the zeros with lines to cover all zeros
- Begin with a matrix full of zeros, and draw lines through rows or columns to cover all the zeros in the matrix.
- Try to cover as many zeros as possible with the minimum number of lines.
- Ensure that no line covers more than one zero in a row or column.
- The goal is to cover all the zeros with the minimum number of lines.
- The marked zeros would be:
| A B C D E
-------------------
1 | 0 X 0 2 X
2 | X 11 0 9 3
3 | X 4 1 4 7
4 | 3 X X 0 0
5 | 4 8 X X 8
Step 5: Cover all columns without a marked zero with the minimum number of lines
- In this step, we cover all the columns that do not have any marked zeros.
- We repeat this step until all the columns have either a marked zero or a line covering them.
- The marking and covering in this step would look like:
| A B C D E
-------------------
1 | 0 X 0 2 X
2 | X X 0 9 X
3 | X X 1 4 X
4 | 3 X X 0 0
5 | 4 X X X 8
Step 6: Find the minimum number of lines needed to cover all the zeros
- Since we have covered all the zeros in the matrix, the number of lines needed to cover them is the minimum number of lines.
- In this case, the minimum number of lines needed is 5 (one for each row).
Step 7: Find an uncovered zero and subtract the minimum value from all uncovered values
- Find an uncovered zero in the matrix and subtract the minimum value (uncovered values only) from all the uncovered values.
- The modified matrix would be:
| A B C D E
--------------
1 | 0 X 0 2 X
2 | X X 0 8 X
3 | X X 0 3 X
4 | 0 X X 0 0
5 | 0 X X X 8
Step 8: Add the minimum value to all double-covered values
- Find any zeros that are covered twice by the lines and add the minimum value (uncovered values only) to those zeros.
- The modified matrix would be:
| A B C D E
--------------
1 | 0 X 0 2 X
2 | X X 0 8 X
3 | X X 0 3 X
4 | 0 X X 0 0
5 | 0 X X X 8
Step 9: Repeat steps 4 to 8 until all the zeros are covered
- Repeat steps 4 to 8 until all the zeros in the matrix are covered or marked.
- In this case, all the zeros are covered after Step 8.
Step 10: Determine the optimal assignments and compute total minimum time
- The optimal assignments can be obtained by selecting the lines that cover the zeros and looking at the value of the non-covered zeros.
- The optimal assignments for this problem are:
| Assigned to
----------------
1 | C
2 | E
3 | A
4 | D
5 | B
- The total minimum time can be computed by summing up the values of the assigned cells in the original table.
- The total minimum time for this problem is: 15 + 14 + 11 + 18 + 9 = 67 days.
Therefore, the optimal assignments for each region are: A to region C, B to region E, C to region A, D to region D, and E to region B. The total minimum time required to cover all the regions is 67 days.