Advertisements
Advertisements
प्रश्न
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
उत्तर
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
संबंधित प्रश्न
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 |
Choose the correct alternative :
The assignment problem is said to be balanced if it is a ______.
Fill in the blank :
When an assignment problem has more than one solution, then it is _______ optimal solution.
State whether the following is True or False :
It is not necessary to express an assignment problem into n x n matrix.
If the given matrix is ______ matrix, the assignment problem is called balanced problem
State whether the following statement is True or False:
The objective of an assignment problem is to assign number of jobs to equal number of persons at maximum cost
A departmental head has four subordinates and four tasks to be performed. The subordinates differ in efficiency and the tasks differ in their intrinsic difficulty. His estimates of the time each man would take to perform each task is given below:
| Tasks | |||||
| 1 | 2 | 3 | 4 | ||
| Subordinates | P | 8 | 26 | 17 | 11 |
| Q | 13 | 28 | 4 | 26 | |
| R | 38 | 19 | 18 | 15 | |
| S | 9 | 26 | 24 | 10 | |
How should the tasks be allocated to subordinates so as to minimize the total manhours?
Choose the correct alternative:
The purpose of a dummy row or column in an assignment problem is to
Choose the correct alternative:
In an assignment problem involving four workers and three jobs, total number of assignments possible are
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?
