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?
Advertisements
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
Solve the following minimal assignment problem :
| Machines | A | B | C | D | E |
| M1 | 27 | 18 | ∞ | 20 | 21 |
| M2 | 31 | 24 | 21 | 12 | 17 |
| M3 | 20 | 17 | 20 | ∞ | 16 |
| M4 | 21 | 28 | 20 | 16 | 27 |
Solve the following minimal assignment problem and hence find minimum time where '- ' indicates that job cannot be assigned to the machine :
| Machines | Processing time in hours | ||||
| 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 |
In a factory there are six jobs to be performed each of which should go through two machines A and B in the order A - B. The processing timing (in hours) for the jobs arc given here. You are required to determine the sequence for performing the jobs that would minimize the total elapsed time T. What is the value of T? Also find the idle time for machines · A and B.
| Jobs | J1 | J2 | J3 | J4 | J5 | J6 |
| Machine A | 1 | 3 | 8 | 5 | 6 | 3 |
| MAchine B | 5 | 6 | 3 | 2 | 2 | 10 |
Five different machines can do any of the five required jobs, with different profits resulting from each assignment as shown below:
| Job | Machines (Profit in ₹) | ||||
| A | B | C | D | E | |
| 1 | 30 | 37 | 40 | 28 | 40 |
| 2 | 40 | 24 | 27 | 21 | 36 |
| 3 | 40 | 32 | 33 | 30 | 35 |
| 4 | 25 | 38 | 40 | 36 | 36 |
| 5 | 29 | 62 | 41 | 34 | 39 |
Find the optimal assignment schedule.
The objective of an assignment problem is to assign ______.
Solve the following problem :
A dairy plant has five milk tankers, I, II, III, IV and V. These 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 | 175 |
| 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?
Choose the correct alternative:
Assignment Problem is special case of ______
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?
A job production unit has four jobs P, Q, R, and S which can be manufactured on each of the four machines I, II, III, and IV. The processing cost of each job for each machine is given in the following table:
| Job | Machines (Processing cost in ₹) |
|||
| I | II | III | IV | |
| P | 31 | 25 | 33 | 29 |
| Q | 25 | 24 | 23 | 21 |
| R | 19 | 21 | 23 | 24 |
| S | 38 | 36 | 34 | 40 |
Find the optimal assignment to minimize the total processing cost.
A plant manager has four subordinates and four tasks to perform. The subordinates differ in efficiency and task differ in their intrinsic difficulty. Estimates of the time subordinate would take to perform tasks are given in the following table:
| I | II | III | IV | |
| A | 3 | 11 | 10 | 8 |
| B | 13 | 2 | 12 | 2 |
| C | 3 | 4 | 6 | 1 |
| D | 4 | 15 | 4 | 9 |
Complete the following activity to allocate tasks to subordinates to minimize total time.
Solution:
Step I: Subtract the smallest element of each row from every element of that row:
| I | II | III | IV | |
| A | 0 | 8 | 7 | 5 |
| B | 11 | 0 | 10 | 0 |
| C | 2 | 3 | 5 | 0 |
| D | 0 | 11 | 0 | 5 |
Step II: Since all column minimums are zero, no need to subtract anything from columns.
Step III: Draw the minimum number of lines to cover all zeros.
| I | II | III | IV | |
| A | 0 | 8 | 7 | 5 |
| B | 11 | 0 | 10 | 0 |
| C | 2 | 3 | 5 | 0 |
| D | 0 | 11 | 0 | 5 |
Since minimum number of lines = order of matrix, optimal solution has been reached
Optimal assignment is A →`square` B →`square`
C →IV D →`square`
Total minimum time = `square` hours.
