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
संबंधित प्रश्न
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 is given in the following table:
|
Jobs
|
Machines |
|||
|
P |
Q |
R |
S |
|
|
Processing Cost (Rs.)
|
||||
|
A |
31 |
25 |
33 |
29 |
|
B |
25 |
24 |
23 |
21 |
|
C |
19 |
21 |
23 |
24 |
|
D |
38 |
36 |
34 |
40 |
How should the jobs be assigned to the four machines so that the total processing cost is minimum?
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 |
The assignment problem is said to be balanced if ______.
Choose the correct alternative:
The assignment problem is said to be balanced if ______
If the given matrix is ______ matrix, the assignment problem is called balanced problem
State whether the following statement is True or False:
In assignment problem each worker or machine is assigned only one job
What is the Assignment problem?
Choose the correct alternative:
North – West Corner refers to ______
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 department store has four workers to pack goods. The times (in minutes) required for each worker to complete the packings per item sold is given below. How should the manager of the store assign the jobs to the workers, so as to minimize the total time of packing?
| Workers | Packing of | |||
| Books | Toys | Crockery | Cutlery | |
| A | 3 | 11 | 10 | 8 |
| B | 13 | 2 | 12 | 12 |
| C | 3 | 4 | 6 | 1 |
| D | 4 | 15 | 4 | 9 |
