Advertisements
Advertisements
Question
Find the assignments of salesman to various district which will yield maximum profit
| Salesman | District | |||
| 1 | 2 | 3 | 4 | |
| A | 16 | 10 | 12 | 11 |
| B | 12 | 13 | 15 | 15 |
| C | 15 | 15 | 11 | 14 |
| D | 13 | 14 | 14 | 15 |
Solution
Step 1:
Since it is a maximization problem, subtract each of the elements in the table from the largest element, i.e., 16
| Salesman | District | |||
| 1 | 2 | 3 | 4 | |
| A | 0 | 6 | 4 | 5 |
| B | 4 | 3 | 1 | 1 |
| C | 1 | 1 | 5 | 2 |
| D | 3 | 2 | 2 | 1 |
Step 2: Row minimum
Subtract the smallest element in each row from every element in its row.
The matrix obtained is given below:
| Salesman | District | |||
| 1 | 2 | 3 | 4 | |
| A | 0 | 6 | 4 | 5 |
| B | 3 | 2 | 0 | 0 |
| C | 0 | 0 | 4 | 1 |
| D | 2 | 1 | 1 | 0 |
Step 3: Column minimum
Here, each column contains element zero.
∴ Matrix obtained by column minimum is same as above matrix.
Step 4:
Draw minimum number of vertical and horizontal lines to cover all zeros.
First cover all rows and columns which have maximum number of zeros.
| Salesman | District | |||
| 1 | 2 | 3 | 4 | |
| A | 0 | 6 | 4 | 5 |
| B | 3 | 2 | 0 | 0 |
| C | 0 | 0 | 4 | 1 |
| D | 2 | 1 | 1 | 0 |
Step 5:
From step 4, minimum number of lines covering all the zeros are 4, which is equal to order of the matrix, i.e., 4.
∴ Select a row with exactly one zero, enclose that zero in () and cross out all zeros in its respective column.
Similarly, examine each row and column and mark the assignment ().
∴ The matrix obtained is as follows:
| Salesman | District | |||
| 1 | 2 | 3 | 4 | |
| A | 0 | 6 | 4 | 5 |
| B | 3 | 2 | 0 | 0 |
| C | 0 | 0 | 4 | 1 |
| D | 2 | 1 | 1 | 0 |
Step 6:
The matrix obtained in step 5 contains exactly one assignment for each row and column.
∴ Optimal assignment schedule is as follows:
| Salesman | District | Profit (in ₹) |
| A | 1 | 16 |
| B | 3 | 15 |
| C | 2 | 15 |
| D | 4 | 15 |
∴ The maximum profit
= 16 + 15 + 15 + 15
= ₹ 61
RELATED QUESTIONS
Four new machines M1, M2, M3 and M4 are to be installed in a machine shop. There are five vacant places A, B, C, D and E available. Because of limited space, machine M2 cannot be placed at C and M3 cannot be placed at A. The cost matrix is given below.
| Machines | Places | ||||
| A | B | C | D | E | |
| M1 | 4 | 6 | 10 | 5 | 6 |
| M2 | 7 | 4 | – | 5 | 4 |
| M3 | – | 6 | 9 | 6 | 2 |
| M4 | 9 | 3 | 7 | 2 | 3 |
Find the optimal assignment schedule
A company has a team of four salesmen and there are four districts where the company wants to start its business. After taking into account the capabilities of salesmen and the nature of districts, the company estimates that the profit per day in rupees for each salesman in each district is as below:
| Salesman | District | |||
| 1 | 2 | 3 | 4 | |
| A | 16 | 10 | 12 | 11 |
| B | 12 | 13 | 15 | 15 |
| C | 15 | 15 | 11 | 14 |
| D | 13 | 14 | 14 | 15 |
Find the assignment of salesman to various districts which will yield maximum profit.
In the modification of a plant layout of a factory four new machines M1, M2, M3 and M4 are to be installed in a machine shop. There are five vacant places A, B, C, D and E available. Because of limited space, machine M2 cannot be placed at C and M3 cannot be placed at A. The cost of locating a machine at a place (in hundred rupees) is as follows.
| Machines | Location | ||||
| A | B | C | D | E | |
| M1 | 9 | 11 | 15 | 10 | 11 |
| M2 | 12 | 9 | – | 10 | 9 |
| M3 | – | 11 | 14 | 11 | 7 |
| M4 | 14 | 8 | 12 | 7 | 8 |
Find the optimal assignment schedule.
Fill in the blank :
When the number of rows is equal to the number of columns then the problem is said to be _______ assignment problem.
Fill in the blank :
If the given matrix is not a _______ matrix, the assignment problem is called an unbalanced problem.
Fill in the blank :
A dummy row(s) or column(s) with the cost elements as _______ is added to the matrix of an unbalanced assignment problem to convert into a square matrix.
Maximization assignment problem is transformed to minimization problem by subtracting each entry in the table from the _______ value in the table.
Fill in the blank :
In maximization type, all the elements in the matrix are subtracted from the _______ element in the matrix.
To convert the assignment problem into a maximization problem, the smallest element in the matrix is deducted from all other elements.
State whether the following is True or False :
The purpose of dummy row or column in an assignment problem is to obtain balance between total number of activities and total number of resources.
State whether the following is True or False
In number of lines (horizontal on vertical) > order of matrix then we get optimal solution.
Solve the following problem :
The estimated sales (tons) per month in four different cities by five different managers are given below:
| Manager | Cities | |||
| P | Q | R | S | |
| I | 34 | 36 | 33 | 35 |
| II | 33 | 35 | 31 | 33 |
| III | 37 | 39 | 35 | 35 |
| IV | 36 | 36 | 34 | 34 |
| V | 35 | 36 | 35 | 33 |
Find out the assignment of managers to cities in order to maximize sales.
Choose the correct alternative:
The cost matrix of an unbalanced assignment problem is not a ______
A ______ assignment problem does not allow some worker(s) to be assign to some job(s)
State whether the following statement is True or False:
To convert the assignment problem into maximization problem, the smallest element in the matrix is to deducted from all other elements
State whether the following statement is true or false:
To convert a maximization-type assignment problem into a minimization problem, the smallest element in the matrix is deducted from all elements of the matrix.
To solve the problem of maximization objective, all the elements in the matrix are subtracted from the largest element in the matrix.
Three new machines M1, M2, M3 are to be installed in a machine shop. There are four vacant places A, B, C, D. Due to limited space, machine M2 can not be placed at B. The cost matrix (in hundred rupees) is as follows:
| Machines | Places | |||
| A | B | C | D | |
| M1 | 13 | 10 | 12 | 11 |
| M2 | 15 | - | 13 | 20 |
| M3 | 5 | 7 | 10 | 6 |
Determine the optimum assignment schedule and find the minimum cost.
