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
संबंधित प्रश्न
Solve the following minimal assignment problem and hence find the minimum value :
| I | II | III | IV | |
| A | 2 | 10 | 9 | 7 |
| B | 13 | 2 | 12 | 2 |
| C | 3 | 4 | 6 | 1 |
| D | 4 | 15 | 4 | 9 |
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 ______.
Choose the correct alternative:
The assignment problem is said to be balanced if ______
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
State whether the following statement is True or False:
In assignment problem each worker or machine is assigned only one job
Choose the correct alternative:
North – West Corner refers to ______
Choose the correct alternative:
In an assignment problem involving four workers and three jobs, total number of assignments possible are
A natural truck-rental service has a surplus of one truck in each of the cities 1, 2, 3, 4, 5 and 6 and a deficit of one truck in each of the cities 7, 8, 9, 10, 11 and 12. The distance(in kilometers) between the cities with a surplus and the cities with a deficit are displayed below:
| To | |||||||
| 7 | 8 | 9 | 10 | 11 | 12 | ||
| From | 1 | 31 | 62 | 29 | 42 | 15 | 41 |
| 2 | 12 | 19 | 39 | 55 | 71 | 40 | |
| 3 | 17 | 29 | 50 | 41 | 22 | 22 | |
| 4 | 35 | 40 | 38 | 42 | 27 | 33 | |
| 5 | 19 | 30 | 29 | 16 | 20 | 33 | |
| 6 | 72 | 30 | 30 | 50 | 41 | 20 | |
How should the truck be dispersed so as to minimize the total distance travelled?
