Advertisements
Advertisements
Question
A car hire company has one car at each of five depots a, b, c, d and e. A customer in each of the fine towers A, B, C, D and E requires a car. The distance (in miles) between the depots (origins) and the towers(destinations) where the customers are given in the following distance matrix.
| a | b | c | d | e | |
| A | 160 | 130 | 175 | 190 | 200 |
| B | 135 | 120 | 130 | 160 | 175 |
| C | 140 | 110 | 155 | 170 | 185 |
| D | 50 | 50 | 80 | 80 | 110 |
| E | 55 | 35 | 70 | 80 | 105 |
How should the cars be assigned to the customers so as to minimize the distance travelled?
Solution
Here the number of rows and columns are equal.
∴ The given assignment problem is balanced.
Step 1: Select the smallest element in each row and subtract this from all the elements in its row.
| Depots | ||||||
| a | b | c | d | e | ||
| A | 30 | 0 | 45 | 60 | 70 | |
| B | 15 | 0 | 10 | 40 | 55 | |
| Customers | C | 30 | 0 | 45 | 60 | 75 |
| D | 0 | 0 | 30 | 30 | 60 | |
| E | 20 | 0 | 35 | 45 | 70 | |
Step 2: Select the smallest element in each column and subtract this from all the elements in its column.
| Depots | ||||||
| a | b | c | d | e | ||
| A | 30 | 0 | 35 | 30 | 15 | |
| B | 15 | 0 | 0 | 10 | 0 | |
| Customers | C | 30 | 0 | 35 | 30 | 20 |
| D | 0 | 0 | 20 | 0 | 5 | |
| E | 20 | 0 | 25 | 15 | 15 | |
Step 3: (Assignment)
Examine the rows with exactly one zero, mark the zero by □ mark other zeros, in its column by X
| Depots | ||||||
| a | b | c | d | e | ||
| A | 30 | 0 | 35 | 30 | 15 | |
| B | 15 | 0 | 0 | 10 | 0 | |
| Customers | C | 30 | 0 | 35 | 30 | 20 |
| D | 0 | 0 | 20 | 0 | 5 | |
| E | 20 | 0 | 25 | 15 | 15 | |
Step 4: Now Examine the rows with exactly one zero, mark the zero by □ mark other zeros, in its column by X
| Depots | ||||||
| a | b | c | d | e | ||
| A | 30 | 0 | 35 | 30 | 15 | |
| B | 15 | 0 | 0 | 10 | 0 | |
| Customers | C | 30 | 0 | 35 | 30 | 20 |
| D | 0 | 0 | 20 | 0 | 5 | |
| E | 20 | 0 | 25 | 15 | 15 | |
Step 5: Cover all the zeros of table 4 with three lives.
Since three assignments were made please note that check [✓] Row C and E which have no assignment.
| Depots | ||||||
| a | b | c | d | e | ||
| A | 30 | 0 | 35 | 30 | 15 | |
| B | 15 | 0 | 0 | 10 | 0 | |
| Customers | C✓ | 30 | 0 | 35 | 30 | 20 |
| D | 0 | 0 | 20 | 0 | 5 | |
| E✓ | 20 | 0 | 25 | 15 | 15 | |
Step 6: Develop the new revised tableau. Examine those elements that are not covered by a line in Table 5.
Take the smallest element in each row and subtract from the uncovered cells, depots
| Depots | ||||||
| a | b | c | d | e | ||
| A | 30 | 0 | 35 | 30 | 15 | |
| B | 15 | 0 | 0 | 10 | 0 | |
| Customers | C | 30 | 0 | 35 | 30 | 0 |
| D | 0 | 0 | 20 | 0 | 5 | |
| E | 20 | 0 | 25 | 0 | 0 | |
Step 7: Go to step 3 and repeat the procedure until you arrive at an optimal assignments depots
Step 8: Determine an assignment
| Depots | ||||||
| a | b | c | d | e | ||
| A | 30 | 0 | 35 | 30 | 15 | |
| B | 15 | 0 | 0 | 10 | 0 | |
| Customers | C | 30 | 0 | 35 | 30 | 0 |
| D | 0 | 0 | 20 | 0 | 5 | |
| E | 20 | 0 | 25 | 0 | 0 | |
Here all the five assignments have been made.
The optimal assignment schedule and total distance is
| Customers | Depots | Total Distances |
| A | b | 130 |
| B | c | 130 |
| C | e | 185 |
| D | a | 50 |
| E | d | 80 |
| Total | 575 | |
∴ The optimum Distance (minimum) is 575 kms.
APPEARS IN
RELATED QUESTIONS
Determine `l_92 and l_93, "given that" l_91 = 97, d_91 = 38 and q_92 = 27/59`
A departmental head has three jobs and four subordinates. The subordinates differ in their capabilities and the jobs differ in their work
contents. With the help of the performance matrix given below, find out which of the four subordinates should be assigned which jobs ?
| Subordinates | Jobs | ||
| I | II | III | |
| A | 7 | 3 | 5 |
| B | 2 | 7 | 4 |
| C | 6 | 5 | 3 |
| D | 3 | 4 | 7 |
A job production unit has four jobs A, B, C, D which can be manufactured on each of the four machines P, Q, R and S. The processing cost of each job for each machine is given in the following table:
| Jobs | Machines (Processing Cost in ₹) |
|||
| P | Q | R | S | |
| A | 31 | 25 | 33 | 29 |
| B | 25 | 24 | 23 | 21 |
| C | 19 | 21 | 23 | 24 |
| D | 38 | 36 | 34 | 40 |
Find the optimal assignment to minimize the total processing cost.
The assignment problem is said to be unbalance if ______
Choose the correct alternative :
In an assignment problem if number of rows is greater than number of columns then
In an assignment problem, if number of column is greater than number of rows, then a dummy column is added.
State whether the following is True or False :
In assignment problem, each facility is capable of performing each task.
A computer centre has got three expert programmers. The centre needs three application programmes to be developed. The head of the computer centre, after studying carefully the programmes to be developed, estimates the computer time in minitues required by the experts to the application programme as follows.
| Programmers | ||||
| P | Q | R | ||
| Programmers | 1 | 120 | 100 | 80 |
| 2 | 80 | 90 | 110 | |
| 3 | 110 | 140 | 120 | |
Assign the programmers to the programme in such a way that the total computer time is least.
Assign four trucks 1, 2, 3 and 4 to vacant spaces A, B, C, D, E and F so that distance travelled is minimized. The matrix below shows the distance.
| 1 | 2 | 3 | 4 | |
| A | 4 | 7 | 3 | 7 |
| B | 8 | 2 | 5 | 5 |
| C | 4 | 9 | 6 | 9 |
| D | 7 | 5 | 4 | 8 |
| E | 6 | 3 | 5 | 4 |
| F | 6 | 8 | 7 | 3 |
A dairy plant has five milk tankers, I, II, III, IV and V. Three milk tankers are to be used on five delivery routes A, B, C, D and E. The distances (in kms) between the dairy plant and the delivery routes are given in the following distance matrix.
| I | II | III | IV | V | |
| A | 150 | 120 | 175 | 180 | 200 |
| B | 125 | 110 | 120 | 150 | 165 |
| C | 130 | 100 | 145 | 160 | 170 |
| D | 40 | 40 | 70 | 70 | 100 |
| E | 45 | 25 | 60 | 70 | 95 |
How should the milk tankers be assigned to the chilling center so as to minimize the distance travelled?
